线性表之“循环单链表”

结构：

在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。

循环单链表的优点在于通过任意一个节点可以遍历整个表的所有节点，而单链表只能遍历该节点之后的节点，在他之前的节点是不能遍历的。

举例：

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

约瑟夫环问题我们就可以通过循环单链表的方式求出答案。代码如下：

下载地址：https://github.com/gongjiehong/ListNode/archive/master.zip

[code lang=”C”]// MARK: 循环单链表

LinkList create_circle_list(int length);

/**
* @author 龚杰洪, 16-08-05 14:08:21
*
* 约瑟夫环： 已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
*
* @param head 链表的头指针
* @param k 开始报数的编号
* @param m 每次报数的数字 m > 1
*
* @return 最后那个没有被out的
*
* @since 1.0
*/
DataType josephus(LinkList head, int k, int m);
[/code]

[code lang=”C”]// MARK: 循环单链表
LinkList create_circle_list(int length)
{
ListNode *p = NULL, *head = NULL, *q = NULL;
for (int index = 1; index <= length; index ++)
{
if (index == 1)
{
// 初始化头指针并赋值
head = (LinkList)malloc(sizeof(ListNode));
head->data = index;
head->next = NULL;
// 赋值为头指针
p = head;
}
else
{
// 出事化后续的节点并赋值
q = (LinkList)malloc(sizeof(ListNode));
q->data = index;
q->next = NULL;
// next指向后续的节点
p->next = q;
// 指针更换为下一节点的指针
p = q;
}
}
// 尾节点的指针指向头指针
if (p->next == NULL)
{
p->next = head;
}
return head;
}

DataType josephus(LinkList head, int k, int m)
{
ListNode *p = head, *q = NULL;
int i;

// 找到开始报数的那个人
while (p->data != k) {
p = p->next;
}

// 如果不是空表的时候执行循环，剩下的那个为幸存者
while (p->next != p)
{
for (i = 0; i < m – 1; i++)
{
// q为临时缓存
q = p;
// 往下一个报数
p = p->next;
}
// p = p->next的替换
q->next = p->next;

printf("%3d out.\n", p->data);
free(p);
// 释放以后将后一个指针前移
p = q->next;
}
return p->data;
}
[/code]

[code lang=”C”]
int n, k, m;
printf("请输入链表的长度：\n");
scanf("%d",&n);

ListNode *p = create_circle_list(n);

printf("请输入开始报数的标号：\n");
scanf("%d",&k);

printf("请输入出列的数：\n");
scanf("%d",&m);

printf("最后没被out的那个： %d \n", josephus(p, k, m));

[/code]