• 数据结构系列学习（四） - 单向循环链表(Circular Linked List)

    目录

    引言：

    学习：

    代码实现：

    头文件（Circular_Linked_List）：

    结构体设计：

    功能函数声明： 

    代码：

    源文件（Circular_Linked_List）：

    初始化函数（Init_clist）：

    判空函数（IsEmpty）：

    查找函数（Search）：

    获取有效长度函数（Get_length）：

    清空函数（Clear）：

    销毁函数（Destroy）： 

    打印函数（Show）： 

    头插函数（Insert_head）：

    尾插函数（Insert_tail） ：

    按位置插函数（Insert_pos）： 

    头删函数（Delete_head）： 

    尾删函数（Delete_tail）： 

    按位置删函数（Delete_pos） ：

    按值删函数（Delete_val） ：

    测试： 

    测试初始化函数、按位置插函数、打印函数：

    测试头插函数：

     测试尾插函数：

    测试按位置插函数： 

    测试头删删数： 

    测试尾删函数：

    测试按位置删函数： 

    测试按值删函数：

    测试销毁函数：

    测试查找函数：

    总结：

    思考：

    引言：

    数据结构学习目录：

    数据结构系列学习(一) - An Introduction to Data Structure

    数据结构系列学习（二） - 顺序表（Contiguous_List） 

    数据结构系列学习（三） - 单链表(Linked_List)

    在上一篇文章中我们学习并使用C语言对不带头节点的单链表进行了实现，在这篇文章中我们将对另一种的链式存储结构——循环链表中的单向循环链表进行学习并使用代码实现。

    学习：

    作为链式存储的另一种存储结构——循环链表，我们首先应该明确的是，单向循环链表和普通的单链表有什么区别？

    我们用两张图来对这两种存储结构进行区分：

    不带头节点的单链表的结构如下图所示，链表头节点的数据域中不存放数据，指针域保存下一个节点的地址，依次类推，每一个节点的保存下一个节点的地址并保存数据，直到最后一个节点指针域为空。

    单向循环链表的结构如下图所示，头节点中的数据域不存放数据，每一个节点存放下一个节点的地址，与不带头节点的单链表不同的是，循环链表中的最后一个节点保存的是头节点的地址，整个链表形成了一个环状的结构。

     

    单向循环链表和单链表的结构区分我们已经大致清楚，那么循环链表存在的意义是什么呢？

    既然形成了一个环状的结构，那么我们就可以从链表中的任何一个节点出发，遍历至整个链表中的所有节点。

    当然，如果链表的结构发生了改变，那么相应的功能也要随机发生改变。因为单向循环链表中末尾节点的指针域不再为空，而是去存储头节点的地址，所以当我们在进行对链表的初始化、尾部插入数据、按位置插入数据、头部删除数据、尾部删除数据、按位置删除数据、按值删除数据、打印数据等操作时，对这些功能的实现方式也要做相应的修改。

    代码实现：

    头文件（Circular_Linked_List）：

    结构体设计：

    单向循环链表的结构体设计和单链表一样，我们对int进行类型重命名，重命名为Elem_type，定义名为CNode的结构体变量，成员分别为Elem_type类型的data域，结构体指针类型的next域。

    1. typedef int Elem_type;//范型定义
    2. typedef struct CNode
    3. {
    4.     Elem_type data;
    5.     struct CNode *next;
    6. }CNode, *PCnode;//结构体别名

    功能函数声明： 

    我们需要在单向循环链表中实现功能：

    初始化函数(Init_clist)；

    判空函数(IsEmpty)；

    查找函数(Search)；

    获取有效长度(Get_length)；

    清空函数(Clear)；

    销毁函数(Destroy)；

    销毁函数(Destroy1)；

    打印函数(Show)；

    头插函数(Insert_head)；

    尾插函数(Insert_tail)；

    按位置插函数(Insert_pos)；

    头删函数(Delete_head)；

    尾删函数(Delete_tail)；

    按位置删函数(Delete_pos)；

    按值删函数(Delete_val)；

    代码：

    1. void Init_clist(PCnode cplist);
    2. bool IsEmpty(PCnode cplist);
    3. PCnode Search(PCnode cplist,Elem_type val);
    4. int Get_length(PCnode cplist);
    5. bool Clear(PCnode cplist);
    6. bool Destroy(PCnode cplist);//无限头删
    7. bool Destroy2(PCnode cplist);//不借助头节点，有两个辅助指针
    8. void Show(PCnode cplist);
    9. bool Insert_head(PCnode cplist,Elem_type val);
    10. bool Insert_tail(PCnode cplist,Elem_type val);
    11. bool Insert_pos(PCnode cplist,int pos,Elem_type val);
    12. bool Delete_head(PCnode cplist);
    13. bool Delete_tail(PCnode cplist);
    14. bool Delete_pos(PCnode cplist,int pos);
    15. bool Delete_val(PCnode cplist,Elem_type val);

    源文件（Circular_Linked_List）：

    初始化函数（Init_clist）：

    我们在介绍单向循环链表的时候就说过，单向循环链表的末尾节点保存的是头节点的地址，那么我们初始化的时候，初始节点的next域保存的其实就是初始节点自身的地址。

    1. void Init_clist(PCnode cplist)
    2. {
    3.     //问题：如果没有一个有效节点，那么头节点的next域应该指向谁？ 答：指向自己
    4.     assert(cplist != nullptr);
    5.     cplist->next = cplist;
    6. }

    判空函数（IsEmpty）：

    单向循环链表为空的意思就是说链表中没有保存任何有效的数据，那也就是说只有头节点的存在，且头节点中没有任何数据，我们直接将返回值设定为头节点的地址保存在头节点的next域中即可。

    1. bool IsEmpty(PCnode cplist)
    2. {
    3.     return cplist->next == cplist;
    4. }

    查找函数（Search）：

    查找函数的返回值我们设定为要查找值的地址，首先我们要做的就是对链表进行判空操作，如果链表为空，那么我们直接将返回值置为空地址。新定义一个结构体类型的指针变量p指向头节点之后的第一个有效节点，循环的终止条件为p指向头节点（因为头节点不存放数据），如果要查找的值等于p指向节点的data域里存放的值，则返回该节点的地址。如果没找到，则返回空地址。

    1. PCnode Search(PCnode cplist,Elem_type val)
    2. {
    3.     assert(cplist != nullptr);
    4.     if(IsEmpty(cplist)){
    5.         return nullptr;
    6.     }
    7.     PCnode p = cplist->next;
    8.     for(;p != cplist;p = p->next){
    9.         if(val == p->data){
    10.             return p;
    11.         }
    12.     }
    13.     return nullptr;
    14. }

    获取有效长度函数（Get_length）：

    定义一个结构体类型的指针变量p指向头节点之后的第一个有效节点，再定义一个整形值count用来统计有效节点的个数，定义循环，循环的终止条件为不指向头节点，循环每执行一次count的值加1，设最终的返回值为count即可。

    1. int Get_length(PCnode cplist)
    2. {
    3.     assert(cplist != nullptr);
    4.     PCnode p = cplist->next;
    5.     int count = 0;
    6.     for(;p != cplist;p = p->next){
    7.         count++;
    8.     }
    9.     return count;
    10. }

    清空函数（Clear）：

    在链表中清空和销毁类似，所以我们直接在清空函数中调用销毁函数即可。

    1. bool Clear(PCnode cplist)
    2. {
    3.     Destroy(cplist);
    4.     return true;
    5. }

    销毁函数（Destroy）： 

    当cp不为空时，循环执行头删函数，直到链表彻底变空为止。

    1. bool Destroy(PCnode cplist)//无限头删
    2. {
    3.     while(!IsEmpty(cplist)){
    4.         Delete_head(cplist);
    5.     }
    6.     return true;
    7. }

    打印函数（Show）： 

    定义结构体类型的指针变量p指向头节点之后的第一个有效节点，定义关于指针p的循环，循环终止条件为不指向头节点，每执行一次循环则打印一次p所指向节点的数据域，直到循环完成。

    1. void Show(PCnode cplist)
    2. {
    3.     //判定：使用不需要前驱的for循环
    4.     assert(cplist != nullptr);
    5.     PCnode p = cplist->next;
    6.     for(;p != cplist;p = p->next){
    7.         printf("%5d",p->data);
    8.     }
    9.     printf("\n");
    10. }

    头插函数（Insert_head）：

    通过malloc函数在堆区申请新节点为新节点分配内存空间，将要插入的值赋值给新节点的数据域，然后进行next域的替换，将原先头节点之后的第一个有效节点的地址赋值给pnewnode的next域，再将原先头节点中存放的第一个有效节点的地址替换为pnewnode的地址，如图：

     

    1. bool Insert_head(PCnode cplist,Elem_type val)
    2. {
    3.     assert(cplist != nullptr);
    4.     PCnode pnewnode = (PCnode) malloc(1 * sizeof(CNode));
    5.     assert(pnewnode != nullptr);
    6.     pnewnode->data = val;
    7.     pnewnode->next = cplist->next;
    8.     cplist->next = pnewnode;
    9.     return true;
    10. }

    尾插函数（Insert_tail） ：

    通过malloc函数在堆区申请新节点为新节点分配内存空间，将要插入的值赋值给新节点的数据域，定义结构体类型的指针p指向头节点，定义循环，循环的终止条件为p指针的next域不等于头节点（也就是遍历到末尾节点），然后进行next域的替换，我们将原先保存在末尾节点next域中的头节点的地址赋值给pnewnode的next域，然后再将pnewnode的地址赋值给原先末尾节点的next域即可，如图：

    1. bool Insert_tail(PCnode cplist,Elem_type val)
    2. {
    3.     assert(cplist != nullptr);
    4.     PCnode pnewnode = (PCnode) malloc(1 * sizeof(CNode));
    5.     assert(pnewnode != nullptr);
    6.     pnewnode->data = val;
    7.     PCnode p = cplist;
    8.     for(;p->next != cplist;p = p->next);
    9.     pnewnode->next = p->next;
    10.     p->next = pnewnode;
    11.     return true;
    12. }

    按位置插函数（Insert_pos）： 

    通过malloc函数在堆区申请新节点为新节点分配内存空间，将要插入的值赋值给新节点的数据域，定义结构体类型的指针p指向头节点，定义循环，终止条件为i < pos，此时p指向待插入位置的前一个节点，那么p的next域存放的也就是待插入的节点的地址，然后进行next域的替换，将待插入位置后面节点的地址赋值给pnewnode的next域，再将pnewnode本身的地址赋值给指向待插入位置前一个节点的指针p的next域即可。

      

    1. bool Insert_pos(PCnode cplist,int pos,Elem_type val)
    2. {
    3.     assert(cplist != nullptr);
    4.     PCnode pnewnode = (PCnode) malloc(1 * sizeof(CNode));
    5.     assert(pnewnode != nullptr);
    6.     pnewnode->data = val;
    7.     PCnode p = cplist;
    8.     for(int i = 0;i < pos;i++){
    9.         p = p->next;
    10.     }
    11.     pnewnode->next = p->next;
    12.     p->next = pnewnode;
    13.     return true;
    14. }

    头删函数（Delete_head）： 

    首先对链表进行判空，如果链表为空则直接返回为假，定义一个结构体类型的指针变量p指向头节点之后的第一个有效节点（也就是我们的待删除节点），将原先头节点中保存的第一个有效节点地址替换为第二个有效节点的地址，然后再释放p指针即可，如图：

     

    1. bool Delete_head(PCnode cplist)
    2. {
    3.     assert(cplist != nullptr);//安全性处理
    4.     if(IsEmpty(cplist)){
    5.         return false;
    6.     }
    7.     PCnode p = cplist->next;//找到待删除节点
    8.     cplist->next = p->next;//跨越指向
    9.     free(p);//释放删除节点
    10.     return true;
    11. }

    尾删函数（Delete_tail）： 

    首先对链表进行判空，如果链表为空则直接返回为假，定义一个结构体类型的指针变量p指向头节点，定义关于p的循环，循环终止条件为p的next域不为头节点（也就是遍历到最后一个节点），再定义一个结构体类型的指针变量q指向头节点，定义关于q的循环，循环终止条件为q的next域不为p（也就是遍历到p指向的节点的前一个节点），将原先存放在p指向的节点的next域中的头节点地址复制给q所指向的节点的next域，这样我们就完成了尾删操作，如图：

    1. bool Delete_tail(PCnode cplist)
    2. {
    3.     assert(cplist != nullptr);
    4.     if(IsEmpty(cplist)){
    5.         return false;
    6.     }
    7.     PCnode p = cplist;
    8.     for(;p->next != cplist;p = p->next);
    9.     PCnode q = cplist;
    10.     for(;q->next!=p;q = q->next);
    11.     q->next = p->next;
    12.     free(p);
    13.     return true;
    14. }

    按位置删函数（Delete_pos） ：

    首先对链表进行判空，如果链表为空则直接返回为假，定义一个结构体类型的指针变量q指向头节点，定义循环，循环的终止条件为i < pos，这时q所指向的就是待删除节点的前一个节点，q的next域也就是待删除节点了，再定义一个结构体类型的指针变量p指向q的next域，那么p的next域也就是待删除节点的后一个节点，然后我们进行跨越指向操作，将p的next域复制给原本存储待删除节点地址的q的next域即可，然后再释放p指针。

    1. bool Delete_pos(PCnode cplist,int pos)
    2. {
    3.     assert(cplist != nullptr);
    4.     if(IsEmpty(cplist)){
    5.         return false;
    6.     }
    7.     PCnode q = cplist;
    8.     for(int i = 0;i < pos;i++){
    9.         q = q->next;
    10.     }
    11.     PCnode p = q->next;
    12.     q->next = p->next;
    13.     free(p);
    14.     return true;
    15. }

    按值删函数（Delete_val） ：

    首先对链表进行判空，如果链表为空则直接返回为假，定义一个结构体类型的指针变量p用来保存查找函数的返回值，如果p指针为空则返回假，再定义一个结构体类型的指针变量q指向头节点，定义循环，循环终止条件为q的next域不为p（也就是遍历到要删除值节点的前一个节点），然后进行跨越指向操作，将q的next域中原本存放待删除节点地址替换为p的next域，然后再将指针p进行释放。

    1. bool Delete_val(PCnode cplist,Elem_type val)
    2. {
    3.     assert(cplist != nullptr);
    4.     if(IsEmpty(cplist)){
    5.         return false;
    6.     }
    7.     PCnode p = Search(cplist,val);
    8.     if(p == nullptr){
    9.         return false;
    10.     }
    11.     PCnode q = cplist;
    12.     for(;q->next != p;q = q->next);
    13.     q->next = p->next;
    14.     free(p);
    15.     return true;
    16. }

    测试： 

    测试初始化函数、按位置插函数、打印函数：

    1. #include
    2. #include
    3. #include
    4. #include "Circular_Linked_List.h"
    5. int main()
    6. {
    7.     CNode circle;
    8.     Init_clist(&circle);
    9.     for(int i = 0;i < 10;i++){
    10.         Insert_pos(&circle,i,i + 1);
    11.     }
    12.     printf("原始数据为：\n");
    13.     Show(&circle);
    14. /*
    15.     其他测试函数添加位置
    16. */
    17.     return 0;
    18. }

    运行结果：

     

    测试头插函数：

    这里我们要将100插入到链表的头部：

    1.     Insert_head(&circle,100);
    2.     printf("\n头插后的数据为：\n");
    3.     Show(&circle);

    运行结果： 

     测试尾插函数：

    这里我们要将100插入到链表的尾部：

    1.     Insert_tail(&circle,100);
    2.     printf("\n头删后的数据为：\n");
    3.     Show(&circle);

    运行结果：

     

    测试按位置插函数： 

    这里我们要将100插入到头节点之后的第二个有效节点之后：

    1.     Insert_pos(&circle,2,100);
    2.     printf("\n头删后的数据为：\n");
    3.     Show(&circle);

    运行结果：

     

    测试头删删数： 

    这里我们要将链表头节点之后的第一个有效节点删除：

    1.     Delete_head(&circle);
    2.     printf("\n头删后的数据为：\n");
    3.     Show(&circle);
    4.     return 0;

    运行结果：

     

    测试尾删函数：

    这里我们要将链表的末尾节点进行删除：

    1.     Delete_tail(&circle);
    2.     printf("\n尾删后的数据为：\n");
    3.     Show(&circle);
    4.     return 0;

    运行结果：

     

    测试按位置删函数： 

    这里我们要删除链表中头节点之后的第四个有效节点之后的节点：

    1.     Delete_pos(&circle,4);
    2.     printf("\n按位置删后的数据为：\n");
    3.     Show(&circle);
    4.     return 0;

    运行结果：

     

    测试按值删函数：

    这里我们要删除链表中为3的值：

    1.     Delete_val(&circle,3);
    2.     printf("\n按位置删后的数据为：\n");
    3.     Show(&circle);
    4.     return 0;

    运行结果：

     

    测试销毁函数：

    1.     Destroy(&circle);
    2.     printf("\n头删后的数据为：\n");
    3.     Show(&circle);

     运行结果：

    测试查找函数：

    1.     PCnode p = Search(&circle,5);
    2.     printf("%p",p);
    3.     return 0;

    运行结果：

      

    我们如果把要查找的值换成链表中并不存在的值，这返回空地址，也就是nullptr：

    总结：

    单向循环链表总体来说和不带头节点的单链表十分的类似，在我们写代码之前就应该将单向循环链表的构造梳理清楚，并将这两者之间的区别搞清楚，这样在我们写代码的时候效率才会高。

    思考：

    1. /*面试笔试喜欢问的问题：
    2.  * 第一题：单链表怎么进行逆置？
    3.  * 第二题：单链表如何获取倒着打印的数据？
    4.  * 第三题：如何判断两个单链表是否存在交点？如果存在相交点则找到第一个相交点？
    5.  * 第四题：如果判断一个单链表是否存在环？如果存在环，则找到入环点。
    6.  * 第五题：给一个随机节点的地址，如何在O(1)时间内删除这个节点？（这个随机节点不能是尾节点）
    7.  * 第六题：如何判断一个单链表是否是回文链表
    8.  */

    2022年11月7日 23:00 

  • 相关阅读:
    vim 从嫌弃到依赖(19)——替换
    LRU 该用什么数据结构
    BLE学习(3)：ATT和GATT详解
    容器化应用系统上生产的最佳实践
    一次磁盘占用率 100% 的排查记录
    OpenAI GPT-4.5 Turbo 泄露，六月或将发布
    VUE3.0对比VUE2.0
    LeetCode 算法：反转链表 c++
    汇编-ARMv8架构指令集
    BWMT的思考
  • 原文地址：https://blog.csdn.net/weixin_45571585/article/details/127724891