单向链表只能通过前驱结点找后继结点，一旦丢失一个结点，那后面的结点都无法找到，循环链表将链表尾部的next域指向链表头部的元素，形成一个闭环，通过中间的任意一个元素都可以找到链表中的某个元素，循环链表的api函数有两个难点，难点一在于头插法的链表插入，我们看图说话： 约瑟夫问题：关于约瑟夫问题的基本解释，可以问度娘，大概意思是，有一个封闭的环，从一开始数，数到第三个，那个数字就被删除，一直循环到所有的数字都出去就算完成；
#ifndef _CIRCELIST_H_ #define _CIRCELIST_H_ typedef void CircleList; typedef struct _tag_CircleListNode { struct _tag_CircleListNode* next; }CircleListNode; CircleList* CircleList_Create(); void CircleList_Destroy(CircleList* list); void CircleList_Clear(CircleList* list); int CircleList_Length(CircleList* list); int CircleList_Insert(CircleList* list, CircleListNode* node, int pos); CircleListNode* CircleList_Get(CircleList* list, int pos); CircleListNode* CircleList_Delete(CircleList* list, int pos); //add CircleListNode* CircleList_DeleteNode(CircleList* List, CircleListNode* node); CircleListNode* CircleList_Reset(CircleList* list); CircleListNode* CircleList_Current(CircleList* list); CircleListNode* CircleList_Next(CircleList* list);//游标指向 下一个位置，把二号位置返回出来，同时让游标下移到下一个位置 #endif``` #include<Windows.h> #include<iostream> #include<malloc.h> #include"CircleLIst.h" using namespace std; typedef struct _tag_CircleList { CircleListNode header; CircleListNode* slider; int length; }TCircleList; CircleList* CircleList_Create() { TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList)); if (ret == NULL) { return NULL; } ret->length = 0; ret->header.next = NULL; ret->slider = NULL; return ret; } void CircleList_Destroy(CircleList* list) { if (list == NULL) { return ; } free(list); } void CircleList_Clear(CircleList* list) { TCircleList* slist = (TCircleList*)list; if (slist == NULL) { return; } slist->header.next = NULL; slist->slider = NULL; slist->length = 0; } int CircleList_Length(CircleList* list) { TCircleList* slist =(TCircleList*) list; if (slist == NULL) { return -1; } return slist->length; } int CircleList_Insert(CircleList* list,CircleListNode* node,int pos) { TCircleList* slist = (TCircleList*)list; if (slist == NULL || pos < 0 || node == NULL) { return -1; } CircleListNode* current = (CircleListNode*)slist; for (int i = 0; (i < pos)&&(current->next!=NULL); i++) { current = current->next; } node->next = current->next; current->next = node; //如果是第一次插入节点 if (slist->length == 0) { slist->slider = node; } slist->length++; if (current == (CircleListNode*)slist)//如果是头插法，current仍然指向链表头部,如果pos是0，就是从头部删除一个元素 { CircleListNode* last = CircleList_Get(slist, slist->length - 1);//求出最后一个元素的位置 last->next = current->next;//让尾部节点指向新节点； } return 0; } CircleListNode* CircleList_Get(CircleList* list, int pos) { TCircleList* slist = (TCircleList*)list; if (slist == NULL||pos<0) { return NULL; } CircleListNode* current = (CircleListNode *) slist;//指向头结点 for (int i = 0; i < pos; i++) { current = current->next; } return current->next; } CircleListNode* CircleList_Delete(CircleList* list,int pos) { TCircleList* slist = (TCircleList*)list; CircleListNode* ret = NULL; if (slist == NULL || pos < 0) { return NULL; } CircleListNode* current = (CircleListNode*)slist; CircleListNode* last = NULL; for (int i = 0; i < pos; i++) { current = current->next; } if (current == (CircleListNode*)slist)//如果删除的是第一个元素 { last = (CircleListNode*)CircleList_Get(slist,(slist->length)-1);//last的生命周期到这里就结束了 } ret = current->next; current->next = ret->next;//跳一个结点，指向下一个结点；//结点指向头部结点的下一个结点 slist->length--; if (last != NULL) { slist->header.next = ret->next; last->next = ret->next; }//跳一个结点，指向下一个结点； if (slist->slider == ret) { slist->slider = ret->next; }//如果删除的元素是游标所指的元素，游标下移； if (slist->length == 0) { slist->header.next = NULL; slist->slider = NULL; }//如果删除之后长度为0；将所有的全都置为零； return ret; } CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) { TCircleList* slist = (TCircleList*)list; CircleListNode* ret = NULL; int i = 0; if (slist != NULL) { CircleListNode* current = (CircleListNode*)slist; for (i = 0; i < slist->length; i++) { if (current->next == node) { ret = current->next; break; } current = current->next; } if (ret != NULL) { CircleList_Delete(slist, i); } } return ret; } CircleListNode* CircleList_Reset(CircleList* list)//游标重新指向链表的头部 { TCircleList* slist = (TCircleList*)list; CircleListNode* ret = NULL; if (slist != NULL) { slist->slider=slist->header.next; ret = slist->slider; } return ret; } CircleListNode* CircleList_Current(CircleList* list)//返回游标当前所指位置的值 { TCircleList* slist = (TCircleList*)list; CircleListNode* ret = NULL; if (slist != NULL) { ret = slist->slider; } return ret; } CircleListNode* CircleList_Next(CircleList* list) { TCircleList* slist = (TCircleList*)list; CircleListNode* current = NULL; if (slist != NULL) { current = slist->slider; } slist->slider = current->next; return current; } #include<Windows.h> #include<iostream> #include"循环链表.h" using namespace std; struct value { CircleListNode header; int v; }; //约瑟夫问题求解 int main() { CircleList* list=CircleList_Create(); struct value v1, v2, v3, v4, v5, v6, v7, v8; v1.v = 1; v2.v = 2; v3.v = 3; v4.v = 4; v5.v = 5; v6.v = 6; v7.v = 7; v8.v = 8; CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list)); CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list)); for (int i = 0; i < CircleList_Length(list); i++) { struct value* pv = (struct value*)CircleList_Next(list); cout << pv->v<<" "; } cout << endl; CircleList_Reset(list); while (CircleList_Length(list) > 0) { struct value* pv = NULL; for (int i = 1; i < 3; i++) { CircleList_Next(list); } pv = (struct value*)CircleList_Current(list); cout << pv->v; CircleList_DeleteNode(list, (CircleListNode*)pv); } CircleList_Destroy(list); return 0; };