# 第十课 — 循环链表，约瑟夫环问题的解决

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
CircleListNode* CircleList_Reset(CircleList* list);
CircleListNode* CircleList_Current(CircleList* list);
CircleListNode* CircleList_Next(CircleList* list);

```typedef struct _tag_CircleList
{
CircleListNode* slider;//游标
int length;
} TCircleList;```

```typedef void CircleList;
typedef struct _tag_CircleListNode
{
struct _tag_CircleListNode* next;
}CircleListNode;```

```CircleList* CircleList_Create()
{
TCircleList * clist=(TCircleList *)malloc(sizeof(TCircleList));
if(clist != NULL)
{
clist->slider=NULL;
clist->length=0;
}
return clist;
}```

```void CircleList_Destroy(CircleList* list)
{
free(list);
}

void CircleList_Clear(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;

if( sList != NULL )
{
sList->length = 0;
sList->slider = NULL;
}
}

int CircleList_Length(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
int ret = -1;

if( sList != NULL )
{
ret = sList->length;
}

return ret;
}```

```int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
TCircleList *clist=(TCircleList *)list;
int ret=(list != NULL && node != NULL && pos>=0);// !=优先级大于&&
int i=0;
if(ret)
{
CircleListNode* current=(CircleListNode*)clist;
for (i = 0; i < pos && current->next != NULL; ++i)//思考为什么要加current->next != NULL？
{
current=current->next;//满足条件进入了说明不是第一次插入，即pos等于0处已经插入过了。
}
node->next=current->next;
current->next=node;
if(clist->length==0)//第一次插入
{
node->next=node;//循环链表，需要把尾部指向头部
clist->slider=node;//游标要指向第一个节点
}
clist->length++;
}
return ret;
}```

current->next != NULL是保证current指针的移位是正确的，如果current->next  == NULL，那么第一次插入就不会进入这个for循环，而当链表只有头结点的时候，是不应该执行current指针的移位的。

```CircleListNode* CircleList_Get(CircleList* list, int pos)
{
TCircleList *clist=(TCircleList *)list;
int i ;
if( (clist != NULL) && (pos >= 0) )
{
CircleListNode* current = (CircleListNode*)clist;

for(i=0; i<=pos; i++)//移动pos+1次，刚好取得pos位置
{
current = current->next;
}
return current;
}
return NULL;
}```

删除指定位置：

```CircleListNode* CircleList_Delete(CircleList* list, int pos)
{
TCircleList * clist=(TCircleList *)list;
CircleListNode* ret = NULL;
int i = 0;
if(clist !=NULL && pos>=0)
{
CircleListNode* current = (CircleListNode*)clist;
CircleListNode* last = (CircleListNode*)CircleList_Get(clist, clist->length - 1);
for (i = 0; i < pos; ++i)//正常删除，不是特殊点
{
current=current->next;
}
ret=current->next;
current->next=ret->next;
clist->length--;

//特殊点,如果删除的是第一个节点
if (current==(CircleListNode*)clist)
{
last->next = ret->next;
}
//如果删除的是游标指向的位置，需要把游标后移
if( clist->slider == ret )
{
clist->slider = ret->next;
}
//如果上面的删除导致没有节点了，需要把头结点还原
if( clist->length == 0 )
{
clist->slider = NULL;
}

}
return ret;
}```

```CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
TCircleList * clist=(TCircleList *)list;
CircleListNode* ret = NULL;
int i = 0;

if( clist != NULL )
{
CircleListNode* current = (CircleListNode*)clist;

for(i=0; i<clist->length; i++)
{
if( current->next == node )//如果找到要删除的节点，就把这个节点返回
{
ret = node;
//ret = current->next;和上面的等价
break;
}

current = current->next;
}

if( ret != NULL )//不等于NULL证明上面的for循环找到了对应需要删除的节点
{
CircleList_Delete(clist, i);
}
}

return ret;
}```

```CircleListNode* CircleList_Reset(CircleList* list)
{
TCircleList* slist = (TCircleList*)list;
CircleListNode* ret = NULL;
if (slist != NULL)
{
ret=slist->slider;
}
return ret;
}```

```CircleListNode* CircleList_Current(CircleList* list)
{
TCircleList *clist=(TCircleList *)list;
CircleListNode* ret=NULL;
if (clist !=NULL)
{
ret=clist->slider;
}
return ret;
}```

```CircleListNode* CircleList_Next(CircleList* list)
{
TCircleList *clist=(TCircleList *)list;
CircleListNode* ret=NULL;
if (clist != NULL && clist->slider !=NULL)
{
ret = clist->slider;
clist->slider = ret->next;
}
return ret;
}```

main.c

```#include <stdio.h>
#include <stdlib.h>
#include "CircleList.h"

struct Value
{
int v;
};

int main(int argc, char *argv[])
{
int i = 0;
CircleList* list = CircleList_Create();

struct Value v1;
struct Value v2;
struct Value v3;
struct Value v4;
struct Value v5;
struct Value v6;
struct Value v7;
struct Value 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(i=0; i<CircleList_Length(list); i++)
{
struct Value* pv = (struct Value*)CircleList_Next(list);

printf("%d\n", pv->v);
}

printf("\n");

CircleList_Reset(list);

while( CircleList_Length(list) > 0 )
{
struct Value* pv = NULL;

for(i=1; i<3; i++)//我们游标只用移动两次
{
CircleList_Next(list);
}

pv = (struct Value*)CircleList_Current(list);

printf("%d\n", pv->v);

CircleList_DeleteNode(list, (CircleListNode*)pv);
}

CircleList_Destroy(list);

return 0;
}```

先打印1到8，然后约瑟夫环问题输出，结果和上面的图片一致。

原文作者：Liu_Jing
原文地址: https://www.cnblogs.com/Liu-Jing/p/7301348.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。