文章参考传智扫地扫讲义

1.单向循环链表的内存结构示意图

对于单向循环链表，的一个关键是循环，就是原来的链表的最后一个结点的next域指向null,现在变为指向第零个结点（默认描述从下标零开始，符合c语言的下标描述），如下图：（我们下面讲解的也是按照这个图进行）

2.单向循环链表的插入

单向循环链表的插入，分为两种情况，

一种是在中间和尾部插入

一种是在头部插入第一个元素，因为单向循环链表是有环的，环的形成就在插入第一个元素的时候，同时在已经有第一个元素的情况下，进行头插法的时候，因为第一个元素改变 了，所以要改变最后一个元素的next域，形成正确的闭环。如下图所示：

3.单向循环链表的删除

3.1 删除中间结点和尾部结点

示意图如下，和非循环链表相同

3.2 删除头部结点

算法示意图如下：

如果弄清楚了单向链表的特点，那兑现代码就不难了，下面是代码 circle_list.h

#ifndef _CIRCLELIST_H_ #define _CIRCLELIST_H_ typedef void CircleList; /* typedef struct _tag_CircleListNode CircleListNode; struct _tag_CircleListNode { CircleListNode* next; }; */ typedef struct _tag_CircleListNode { struct _tag_CircleListNode * next; }CircleListNode; CircleList* CircleList_Create(); void List_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); //游标指向2号位置 //把2号位置返回出来,同时让游标下移到3号位置 CircleListNode* CircleList_Next(CircleList* list); #endif

circle_list.cpp如下：

//能够实现单循环链表，并且解决约瑟夫问题 #include"circle_list.h" #include<iostream> typedef struct tagMycirclelist { CircleListNode head; int length; CircleListNode *cursor;//光标 }Mycirclelist; //创建一个循环链表 CircleList* CircleList_Create() { Mycirclelist *tmp = (Mycirclelist *)malloc(sizeof(Mycirclelist)); if (tmp == NULL) { printf("malloc failed err:\n"); return NULL; } tmp->length = 0; tmp->cursor = NULL; tmp->head.next = NULL;//而上层使用的头指针应该是head.next的地址，上层不知道，而我知道 //所以当上层应用程序把句柄给我进行插入的时候，及得我要用head.next的地址，而不是句柄的地址 return tmp; } void List_Destroy(CircleList* list) { if (list != NULL) free(list); } void CircleList_Clear(CircleList* list) { if (list == NULL) { //打回去 return; } Mycirclelist *tmp = (Mycirclelist *)list; tmp->length = 0; tmp->cursor = 0; tmp->head.next = NULL; //删除链表中的每一个元素 } int CircleList_Length(CircleList* list) { if (list == NULL) { //打回去 return -1; } Mycirclelist *tmp = (Mycirclelist *)list; return tmp->length; } //实现循环链表的插入 int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) { if (list == NULL) { //打回去 return -1; } Mycirclelist *tmp = (Mycirclelist *)list; //定义一个辅助指针变量 CircleListNode *current = &(tmp->head); for (int i = 0; (i < pos)&&(current->next!=NULL); i++) { current = current->next; } node->next = current->next; current->next = node; /* //关于游标的使用问题，游标是为了有需求的人使用，如果正常情况下游标始终指向第0个元素 一个真正使用的是约瑟夫问题 */ //然后给游标赋值 if (tmp->length == 0) { tmp->cursor = node; } //长度加1 tmp->length++; //关键地方到了，主要是插入第一个元素，或者是头插一个元素的时候，非常重要， //这个是循环链表实现的精髓所在,说明current没有移动 //这个情况是插入第一个元素或者是头插法 if (current == &(tmp->head)) { //要获取到最后一个结点，刚才搞错了 CircleListNode*last = CircleList_Get(list, CircleList_Length(list)-1); if (last!= NULL) { last->next = current->next; } } return 0; } //通过位置来获取元素 CircleListNode* CircleList_Get(CircleList* list, int pos) { if (list == NULL) { //打回去 return NULL; } Mycirclelist *tmp = (Mycirclelist *)list; //定义一个辅助指针变量 CircleListNode *current = &(tmp->head); for (int i = 0; i < pos&& current->next != NULL; i++) { current = current->next; } return current->next; } //删除算法 CircleListNode* CircleList_Delete(CircleList* list, int pos) { if (list == NULL) { //打回去 return NULL; } CircleListNode*ret = NULL;//返回给上层使用 Mycirclelist *tmp = (Mycirclelist *)list; //定义一个辅助指针变量 CircleListNode *current = &(tmp->head); for (int i = 0; i < pos&&current->next != NULL; i++) { current = current->next; } //缓存要删除的结点，返回给上层 ret = current->next; current->next = current->next->next; tmp->length--; //判断如果是删除的第一个元素，要进行修正 if (current == &(tmp->head)) { //要获取到最后一个结点，刚才搞错了 CircleListNode*last = CircleList_Get(list, CircleList_Length(list)-1); last->next = current->next; } //如果删除的是游标的位置，要将游标位置下移 if (ret=tmp->cursor) { tmp->cursor = ret->next; } //若删除元素后，链表长度为0 if (tmp->length == 0) { tmp->head.next = NULL; tmp->cursor = NULL; } return ret; } //根据结点的值 进行数据的删除,转化为位置进行删除 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) { if (list == NULL) { //打回去 return NULL; } CircleListNode*ret = NULL;//返回给上层使用 Mycirclelist *tmp = (Mycirclelist *)list; int i = 0;//辅助计数器 //定义一个辅助指针变量 CircleListNode *current = &(tmp->head); for ( i = 0; i < CircleList_Length(list), current != NULL; i++) { if (node == current) { break; } } ret=CircleList_Delete(list, i); return ret; } //复位游标的问题 CircleListNode* CircleList_Reset(CircleList* list) { if (list == NULL) { //打回去 return NULL; } Mycirclelist *tmp = (Mycirclelist *)list; if (tmp != NULL) { tmp->cursor = tmp->head.next; return tmp->cursor; } } //获取到当前游标 CircleListNode* CircleList_Current(CircleList* list) { if (list == NULL) { //打回去 return NULL ; } CircleListNode*ret = NULL;//返回给上层使用 Mycirclelist *tmp = (Mycirclelist *)list; return tmp->cursor; } //游标下移 //游标指向2号位置 //把2号位置返回出来,同时让游标下移到3号位置 CircleListNode* CircleList_Next(CircleList* list) { if (list == NULL) { //打回去 return NULL; } CircleListNode*ret = NULL;//返回给上层使用 Mycirclelist *tmp = (Mycirclelist *)list; if (tmp != NULL&&tmp->cursor != NULL) { ret = tmp->cursor;//报存原来游标位置 tmp->cursor = ret->next; } //通过游标的值 }

测试代码框架：

#include"circle_list.h" #include<iostream> using namespace std; struct Tercher { CircleListNode circlenode; int value; }; int main() { //定义老师对象 struct Tercher t1; struct Tercher t2; struct Tercher t3; struct Tercher t4; t1.value = 1; t2.value = 2; t3.value = 3; t4.value = 4; //初始化一个链表，得到句柄 CircleList*handle = CircleList_Create(); CircleList_Insert(handle, (CircleListNode*)&t1,0); CircleList_Insert(handle, (CircleListNode*)&t2, 0); CircleList_Insert(handle, (CircleListNode*)&t3, 0); CircleList_Insert(handle, (CircleListNode*)&t4, 0); //如何证明链表是有环的，进行两次打印 for (int i = 0; i < 2 * CircleList_Length(handle); i++) { Tercher*p = (Tercher*)CircleList_Get(handle, i); if (p != NULL) { printf("value:[%d]\n", p->value); } } //进行元素的删除，然后再打印 CircleList_Delete(handle,0);//头删除 CircleList_Delete(handle, CircleList_Length(handle) - 1);//尾删除 //如何证明链表是有环的，进行两次打印 for (int i = 0; i < 2 * CircleList_Length(handle); i++) { Tercher*p = (Tercher*)CircleList_Get(handle, i); if (p != NULL) { printf("value:[%d]\n", p->value); } } printf("test finish!!!\n"); List_Destroy(handle); }

打印长度是  2 * CircleList_Length(handle)为了 证明链表是有环的

输出结果如下：