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

单向循环链表

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);

头文件部分

typedef int Element;typedef struct _loop_node {Element val;struct _loop_node* next;
}LoopNode;//定义单向循环链表的头结构
typedef struct {LoopNode header;LoopNode* rear;      int num;
}LinkLoopList;//1.初始化接口
void initLinkLoopList(LinkLoopList* link_loop);//2.头插
int insertLinkLoopHeader(LinkLoopList* link_loop, Element value);
//3.尾插
int insertLinkLoopRear(LinkLoopList* link_loop, Element value);//4.遍历显示
void showLinkLoopList(const LinkLoopList* link_loop);//5.删除节点
int deleteLinkLoopList(LinkLoopList* link_loop, Element value);//6.释放整个数据域 不释放头(头置空)
void destroyLinkLoopList(LinkLoopList* link_loop);

实现

1.初始化接口

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

2.头插

int insertLinkLoopHeader(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;return 0;
}

3.尾插

int insertLinkLoopRear(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;return 0;
}

4.遍历显示

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

5.删除节点

int deleteLinkLoopList(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);}return 0;
}

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

void destroyLinkLoopList(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函数

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

输出结果

520 100 101 102 103 104 105 106 107 108 109
=======================
520 101 102 103 104 105 106 107 108 109
Table 0 element!

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

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

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

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

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