数据类型及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. }
