文章目录循环单链表结点定义初始化插入遍历删除循环双链表结点定义初始化插入遍历删除时间复杂度循环条件在循环链表中“终点”就是“起点”。表尾结点的next指针不再指向NULL而是指向头结点带头结点或指向第一个数据结点不带头结点。下面将以“带头结点”为标准介绍循环链表。循环单链表结点定义与普通单链表完全一样typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;初始化关键头结点指向自己。boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));// 分配一个头结点if(LNULL)// 内存不足分配失败returnfalse;L-nextL;// 不再是 NULL而是指向头结点自己returntrue;}// 判断空表if (L-next L) return true;// 判断结点p是否为循环单链表的表尾结点if(p-next L) return true;插入在 p 之后插入 s。在普通单链表中尾插需要判空if(p-next ! NULL);在循环单链表中完全不需要判断p是否是尾结点无论p是尾结点还是中间结点p-next永远指向一个有效地址至少是头结点boolInsertNextNode(LNode*p,inte){if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;// 无论 p 是尾结点还是中间结点p-next 永远指向一个有效地址至少是头结点s-nextp-next;p-nexts;returntrue;}遍历voidPrintList(LinkList L){if(LNULL||L-nextL)return;// 空表检查LNode*pL-next;// 从首元结点开始while(p!L){// 只要没回到头结点就继续printf(%d ,p-data);pp-next;}}删除删除 p 的后继 q。不需要担心q是尾结点而让p-next变成NULL因为q-next永远有效(要么是常规结点要么是头结点不会是NULL)。boolDeleteNextNode(LNode*p,inte){// p 后面不能是头结点即 p 是尾结点或空表if(pNULL||p-nextL)returnfalse;LNode*qp-next;eq-data;p-nextq-next;// 即使 q 是尾结点q-next 也指向 L安全free(q);returntrue;}循环双链表结点定义与普通双链表一样typedefstructDNode{intdata;structDNode*prior,*next;}DNode,*DLinkList;初始化关键将头结点的前驱和后继指向头结点自己。boolInitDLinkList(DLinkListL){L(DNode*)malloc(sizeof(DNode));// 分配一个头结点if(LNULL)// 内存不足分配失败returnfalse;L-priorL;// 头结点的前驱指向头结点自己L-nextL;// 头结点的后继指向头结点自己returntrue;}// 判断空表if (L-next L) return true;// 判断结点p是否为循环双链表的表尾结点if(p-next L) return true;插入在 p 之后插入 s。boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)returnfalse;// 顺序至关重要s-nextp-next;// 1. s 抓住后面的节点s-priorp;// 2. s 回头抓住 p// 在普通双链表中插入时必须加 if(p-next ! NULL) 判断在循环双链表中这一步消失了// 因为循环p-next 绝对不可能是 NULL所以这条语句永远合法p-next-priors;// 3. 让后面的节点回头看见 s无需 if 判空p-nexts;// 4. p 断开旧链指向 sreturntrue;}遍历// 正向遍历与循环单链表一样条件 p ! LvoidPrintForward(DLinkList L){if(L-nextL)return;DNode*pL-next;while(p!L){// 若p!L则一直循环printf(%d ,p-data);pp-next;}}// 反向遍历利用 prior 往前倒条件同样是 p ! LvoidPrintBackward(DLinkList L){if(L-priorL)return;// 或 L-next LDNode*pL-prior;// 从尾结点开始while(p!L){printf(%d ,p-data);pp-prior;}}删除删除 p 的后继 q。boolDeleteNextDNode(DNode*p,inte){if(pNULL||p-nextp)returnfalse;// 空表或只有头结点DNode*qp-next;eq-data;p-nextq-next;// p 跨过 q// 无需判空q-next 绝对不可能是 NULL至少是头结点或某个节点q-next-priorp;free(q);returntrue;}时间复杂度表头表尾都可直接访问O(1)循环条件普通链表while(p ! NULL)所有循环链表while(p ! L)
循环链表（循环单链表与循环双链表）
文章目录循环单链表结点定义初始化插入遍历删除循环双链表结点定义初始化插入遍历删除时间复杂度循环条件在循环链表中“终点”就是“起点”。表尾结点的next指针不再指向NULL而是指向头结点带头结点或指向第一个数据结点不带头结点。下面将以“带头结点”为标准介绍循环链表。循环单链表结点定义与普通单链表完全一样typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;初始化关键头结点指向自己。boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));// 分配一个头结点if(LNULL)// 内存不足分配失败returnfalse;L-nextL;// 不再是 NULL而是指向头结点自己returntrue;}// 判断空表if (L-next L) return true;// 判断结点p是否为循环单链表的表尾结点if(p-next L) return true;插入在 p 之后插入 s。在普通单链表中尾插需要判空if(p-next ! NULL);在循环单链表中完全不需要判断p是否是尾结点无论p是尾结点还是中间结点p-next永远指向一个有效地址至少是头结点boolInsertNextNode(LNode*p,inte){if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;// 无论 p 是尾结点还是中间结点p-next 永远指向一个有效地址至少是头结点s-nextp-next;p-nexts;returntrue;}遍历voidPrintList(LinkList L){if(LNULL||L-nextL)return;// 空表检查LNode*pL-next;// 从首元结点开始while(p!L){// 只要没回到头结点就继续printf(%d ,p-data);pp-next;}}删除删除 p 的后继 q。不需要担心q是尾结点而让p-next变成NULL因为q-next永远有效(要么是常规结点要么是头结点不会是NULL)。boolDeleteNextNode(LNode*p,inte){// p 后面不能是头结点即 p 是尾结点或空表if(pNULL||p-nextL)returnfalse;LNode*qp-next;eq-data;p-nextq-next;// 即使 q 是尾结点q-next 也指向 L安全free(q);returntrue;}循环双链表结点定义与普通双链表一样typedefstructDNode{intdata;structDNode*prior,*next;}DNode,*DLinkList;初始化关键将头结点的前驱和后继指向头结点自己。boolInitDLinkList(DLinkListL){L(DNode*)malloc(sizeof(DNode));// 分配一个头结点if(LNULL)// 内存不足分配失败returnfalse;L-priorL;// 头结点的前驱指向头结点自己L-nextL;// 头结点的后继指向头结点自己returntrue;}// 判断空表if (L-next L) return true;// 判断结点p是否为循环双链表的表尾结点if(p-next L) return true;插入在 p 之后插入 s。boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)returnfalse;// 顺序至关重要s-nextp-next;// 1. s 抓住后面的节点s-priorp;// 2. s 回头抓住 p// 在普通双链表中插入时必须加 if(p-next ! NULL) 判断在循环双链表中这一步消失了// 因为循环p-next 绝对不可能是 NULL所以这条语句永远合法p-next-priors;// 3. 让后面的节点回头看见 s无需 if 判空p-nexts;// 4. p 断开旧链指向 sreturntrue;}遍历// 正向遍历与循环单链表一样条件 p ! LvoidPrintForward(DLinkList L){if(L-nextL)return;DNode*pL-next;while(p!L){// 若p!L则一直循环printf(%d ,p-data);pp-next;}}// 反向遍历利用 prior 往前倒条件同样是 p ! LvoidPrintBackward(DLinkList L){if(L-priorL)return;// 或 L-next LDNode*pL-prior;// 从尾结点开始while(p!L){printf(%d ,p-data);pp-prior;}}删除删除 p 的后继 q。boolDeleteNextDNode(DNode*p,inte){if(pNULL||p-nextp)returnfalse;// 空表或只有头结点DNode*qp-next;eq-data;p-nextq-next;// p 跨过 q// 无需判空q-next 绝对不可能是 NULL至少是头结点或某个节点q-next-priorp;free(q);returntrue;}时间复杂度表头表尾都可直接访问O(1)循环条件普通链表while(p ! NULL)所有循环链表while(p ! L)
