单向循环链表超详细精讲 | 带头节点带头指针 + 完整可运行c语言代码

单向循环链表

1.带头节点的单向循环链表

前置知识

所谓单向循环链表就是在普通单向链表基础上，把最后一个节点的 next 指针不再置为 NULL，而是指向链表第一个节点（头节点/首元节点）

​ 先展示下链表的样子(这里我加了了个count 给写成了结构体) (count用来统计链表中的节点数量)

1.插入相关

1.1头插

1.创建新节点 2.更新新节点 3.更新头节点 4.更新尾指针(只有在第一次插入时候)

1. 创建新节点 ------>link_loop *new_node = malloc(sizeof(link_loop));

2. 更新新节点 ------>new_node->next = link_loop->header.next;

3. 更新头节点 ------>link_loop->header.next = new_node;

4. 更新尾指针(只有在第一次插入时候) ------>link_loop->rear = new_node;

1.创建新节点 2.更新新节点 3.更新头节点 4.更新尾指针(只有在第一次插入时候)

link_loop*new_node=malloc(sizeof(link_loop));//其实这里也展现了我们在 单链表 中所说的 备份思想new_node->next=link_loop->header.next;link_loop->header.next=new_node;if(link_loop->rear==&link_loop->header){link_loop->rear=new_node;}

1.2 尾插

1.创建新节点 2.更新新节点 3.更新尾指针的next 3.更新尾指针

1. 创建新节点 ------>LoopNode *new_node = malloc(sizeof(LoopNode));

2. 更新新节点 ------>new_node->next = link_loop->rear->next;

​

3. 更新尾指针的next ------>link_loop->rear->next = new_node;

4. 更新尾指针 ------>link_loop->rear = new_node;

1.创建新节点 2.更新新节点 3.更新尾指针的next 3.更新尾指针

LoopNode*new_node=malloc(sizeof(LoopNode));//其实这里也展现了我们在 单链表 中所说的 备份思想new_node->next=link_loop->rear->next;link_loop->rear->next=new_node;link_loop->rear=new_node;

2.删除相关

其实这里的删除和单链表那里的删除完全一样!!! 1.引入辅助指针p，p找到待删除位置的前一个节点 2.引入辅助指针备份待删除位置 tmp 3.修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表 4.删除tmp

1. 引入辅助指针p，p找到待删除位置的前一个节点 ------>LoopNode *p = 前驱节点

2. 引入辅助指针备份待删除位置 tmp ------>LoopNode *tmp = p->next;

3. 修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表 ------>p->next = tmp->next;

4. 删除tmp ------>free(tmp);

1.引入辅助指针p，p找到待删除位置的前一个节点 2.引入辅助指针备份待删除位置 tmp 3.修改前驱节点的 next 指针，跳过待删除节点，重新衔接链表 4.删除tmp

LoopNode*p=前驱节点 LoopNode*tmp=p->next;p->next=tmp->next;free(tmp);

头文件部分

typedefintElement;typedefstruct_loop_node{Element val;struct_loop_node*next;}LoopNode;//定义单向循环链表的头结构typedefstruct{LoopNode header;LoopNode*rear;intnum;}LinkLoopList;//1.初始化接口voidinitLinkLoopList(LinkLoopList*link_loop);//2.头插intinsertLinkLoopHeader(LinkLoopList*link_loop,Element value);//3.尾插intinsertLinkLoopRear(LinkLoopList*link_loop,Element value);//4.遍历显示voidshowLinkLoopList(constLinkLoopList*link_loop);//5.删除节点intdeleteLinkLoopList(LinkLoopList*link_loop,Element value);//6.释放整个数据域 不释放头(头置空)voiddestroyLinkLoopList(LinkLoopList*link_loop);

实现

1.初始化接口

voidinitLinkLoopList(LinkLoopList*link_loop){//刚开始就是自己指自己link_loop->header.next=link_loop->rear=&link_loop->header;//表中的节点数量为0link_loop->num=0;}

2.头插

intinsertLinkLoopHeader(LinkLoopList*link_loop,Element value){//1 先有新节点LoopNode*node=malloc(sizeof(LoopNode));if(node==NULL){return-1;}//插入代码node->val=value;node->next=link_loop->header.next;link_loop->header.next=node;//判断尾指针是否需要更新if(link_loop->rear==&link_loop->header){link_loop->rear=node;}//增加链表中节点的数量++link_loop->num;return0;}

3.尾插

intinsertLinkLoopRear(LinkLoopList*link_loop,Element value){//1 先有新节点LoopNode*node=malloc(sizeof(LoopNode));if(node==NULL){return-1;}//插入代码node->val=value;node->next=link_loop->rear->next;link_loop->rear->next=node;link_loop->rear=node;//增加链表中节点的数量++link_loop->num;return0;}

4.遍历显示

voidshowLinkLoopList(constLinkLoopList*link_loop)//这里加const 因为是只读{//引入辅助指针nodeLoopNode*node=link_loop->header.next;//单向循环链表 首尾相连while(node!=&link_loop->header){printf("%d ",node->val);//不断向后遍历node=node->next;}printf("\n");}

5.删除节点

intdeleteLinkLoopList(LinkLoopList*link_loop,Element value){//引入辅助指针nodeLoopNode*node=&link_loop->header;//找到待删除位置的前一个节点while(node->next!=&link_loop->header&&node->next->val!=value){node=node->next;}//删除代码if(node->next->val==value){LoopNode*temp=node->next;node->next=temp->next;free(temp);//减少链表中节点的数量--link_loop->num;}//没找到要删除的节点else{printf("NO %d element!\n",value);}return0;}

6.释放整个数据域 不释放头(头置空)

voiddestroyLinkLoopList(LinkLoopList*link_loop){//引入辅助节点nodeLoopNode*node=link_loop->header.next;while(node!=&link_loop->header){//删除代码LoopNode*tmp=node;node=node->next;free(tmp);--link_loop->num;}//最后删除完毕 打印链表中的节点数量printf("Table %d element!\n",link_loop->num);//头置空link_loop->rear=NULL;link_loop->header.next=NULL;}

测试案例

main函数

voidtest03(){LinkLoopList table;//初始化表initLinkLoopList(&table);//循环尾插for(inti=0;i<10;i++){insertLinkLoopRear(&table,i+100);}//头插insertLinkLoopHeader(&table,520);//遍历展示showLinkLoopList(&table);printf("=======================\n");//删除节点deleteLinkLoopList(&table,100);//遍历展示showLinkLoopList(&table);//销毁该表的元素区域 头置空destroyLinkLoopList(&table);}intmain(){test03();return0;}

输出结果

520100101102103104105106107108109=======================520101102103104105106107108109Table0element!

2.带头指针的单向循环链表

​ 经过上面的带头节点的单向循环链表的理解 这个可以说非常简单了
​ 我们可以延用在单链表中所讲的(具体参考主页数据结构专栏)最万金油的思路

​引入辅助节点，充当头节点

​ 嘻嘻嘻嘻 单向循环链表部分到此结束😆😆

​ (有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖