【数据结构】循环链表API及实现（一）

2023-02-08 116

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】循环链表API及实现

数据类型及API声明

循环链表是指首尾相连的链表，尾部元素指向头部元素，本文使用的模型是尾部元素指向0位置元素，而不是指向链表头。

1. //链表句柄
2. typedef void CircleList;
3. 
4. //循环链表的结点
5. typedef struct CircleListNode CircleListNode;
6. 
7. //循环链表的头结点
8. typedef struct CircleListHead CircleListHead;
9. 
10. //创建一个循环链表
11. CircleList* CircleList_Create();
12. 
13. //销毁一个循环链表
14. void List_Destroy(CircleList* list);
15. 
16. //清空一个循环链表
17. void CircleList_Clear(CircleList* list);
18. 
19. //返回循环链表的长度
20. int CircleList_Length(CircleList* list);
21. 
22. //插入一个元素
23. int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);
24. 
25. //返回一个元素
26. CircleListNode* CircleList_Get(CircleList* list, int pos);
27. 
28. //按位置删除一个元素
29. CircleListNode* CircleList_Delete(CircleList* list, int pos);
30. 
31. //按结点值删除一个元素
32. CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
33. 
34. //重置游标指向第一个结点元素
35. CircleListNode* CircleList_Reset(CircleList* list);
36. 
37. //返回当前游标
38. CircleListNode* CircleList_Current(CircleList* list);
39. 
40. //游标下移
41. CircleListNode* CircleList_Next(CircleList* list);

循环链表的API实现

循环链表结点结构体

链表结点包含了指向下一个结点的指针。

1. struct CircleListNode
2. {
3.  CircleListNode* next;
4. };

表头结构体

表头包含一个链表结构体head，用于指向链表的0号结点，包含一个游标slider，用于指示当前结点，包含一个长度length，用于指示链表元素个数

1. struct CircleListHead
2. {
3.  CircleListNode  head;
4.  CircleListNode* slider;
5.  int       length;
6. };

创建循环链表并返回循环链表句柄

函数功能：创建一个循环链表并返回循环链表句柄，其实就是创建一个表头
函数参数：无，链式结构不需要提前分配内存，而线性表的顺序结构需要提前分配内存
函数返回：表头

1. CircleList* CircleList_Create()
2. {
3.  CircleListHead* pHead = NULL;
4.  pHead = (CircleListHead*)malloc(sizeof(CircleListHead));
5.  if (pHead == NULL)
6.  {
7.    printf("head = (CircleListHead*)malloc(sizeof(CircleListHead)) err\n");
8.    return NULL;
9.  }
10.   memset(pHead, 0, sizeof(CircleListHead));
11.   return pHead;
12. }

销毁循环链表

函数功能：销毁循环链表就是释放表头资源，销毁循环链表前需要逐个删除链表结点
函数参数：循环链表的句柄
函数返回：无

1. void CircleList_Destroy(CircleList* list)
2. {
3.  CircleListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("list == NULL\n");
7.    return;
8.  }
9.  pHead = (CircleListHead*)list;
10.   free(pHead);
11. }

清空循环链表

函数功能：返回到循环链表刚创建的状态，即表头指针域指向NULL，长度置为0
函数参数：循环链表的句柄
函数返回：无

1. void CircleList_Clear(CircleList* list)
2. {
3.  CircleListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("list == NULL\n");
7.    return;
8.  }
9.  pHead = (CircleListHead*)list;
10.   pHead->head.next = NULL;
11.   pHead->slider = NULL;
12.   pHead->length = 0;
13. }

返回循环链表元素个数

函数功能：获取循环链表长度，即结点个数
函数参数：循环链表句柄
函数返回：节点个数

1. int CircleList_Length(CircleList* list)
2. {
3.  CircleListHead* pHead = NULL;
4.  if (list == NULL)
5.  {
6.    printf("list == NULL\n");
7.    return -1;
8.  }
9.  pHead = (CircleListHead*)list;
10.   return pHead->length;
11. }

插入元素

函数功能：在循环链表中插入一个元素，被插入的元素已经在主调函数分配好内存，只需把链表结点CircleListNode串接起来即可
函数参数：list 循环链表句柄 node 待插入元素 pos 插入位置
函数返回：成功返回0

1. int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
2. {
3.  int i = 0;
4.  CircleListHead* pHead = NULL;
5.  CircleListNode* pCurrent = NULL;
6.  if ((list == NULL) || (node == NULL) || (pos < 0))
7.  {
8.    printf("err: (list == NULL) || (node == NULL) || (pos < 0)\n");
9.    return -1;
10.   }
11.   pHead = (CircleListHead*)list;
12.   pCurrent = &(pHead->head);
13.   for (i = 0; i < pos; i++)
14.   {
15.     pCurrent = pCurrent->next;
16.   }
17.   node->next = pCurrent->next;
18.   pCurrent->next = node;
19.   //第一次插入要设置游标位置
20.   if (CircleList_Length(list) == 0)
21.   {
22.     pHead->slider = node;
23.   }
24.   pHead->length++; //必须要先加1在判断是不是头插法，
25.            //因为插入后长度就变了，如果函数在最后加1，那么 pHead->length-1就不是尾部元素了
26.            //那样的话CircleList_Get(list, pHead->length - 1)获取的是尾部元素的上一个元素
27.   //如果是在0号位置插入（即头插法），pos为0，pCurrent不会移动
28.   if (pCurrent == (&(pHead->head)))
29.   {
30.     //获取尾部元素
31.     CircleListNode* pLast = CircleList_Get(list, pHead->length - 1);
32.     //node->next = pCurrent->next;
33.     //pCurrent->next = node;
34.     //形成环
35.     pLast->next = node;
36.   }
37.   return 0;
38. }

插入元素示意图

（1）普通位置插入

（2）尾部插入

（3）首次插入

（4）头部插入

根据上面的四种图片分析，前三种情况下，插入和普通链表的插入一样，借助一个辅助指针变量pCurrent，pCurrent为当前指针位置，初始状态他应该指向表头，当我们需要在pos号位置插入元素时，就将pCurrent后移pos位，比如要在2号位置插入，将pCurrent后移2次，那么pCurrent将指在1号结点处，而1号结点的next域指向2号结点，这时只需要把待插入结点插在pCurrent后面即可完成插入。但是第四种情况，也就是在0号位置插入时（头插法），因为循环链表要形成一个环，所以此时应该获取尾部结点，把尾部结点的指针域指向头部元素，也就是新插入的node元素，来形成一个循环。

返回指定位置元素

函数功能：获取一个指定位置的元素
函数参数：list 循环链表句柄 pos 要获取的元素标号
函数返回：获取的结点元素

1. CircleListNode* CircleList_Get(CircleList* list, int pos)
2. {
3.  int i = 0;
4.  CircleListHead* pHead = NULL;
5.  CircleListNode* pCurrent = NULL;
6.  if ((list == NULL) || (pos < 0))
7.  {
8.    printf("err: (list == NULL) || (pos < 0)\n");
9.    return NULL;
10.   }
11.   pHead = (CircleListHead*)list;
12.   pCurrent = &(pHead->head);
13.   for (i = 0; i < pos; i++)
14.   {
15.     pCurrent = pCurrent->next;
16.   }
17.   return pCurrent->next;
18. }