Question

关于循环队列实现约瑟夫环（C语言）的问题

/*约瑟夫环(已知n个人（编号0,1,2,3...n-1）围坐在一张圆桌周围，从编号为k的人开始报数，
数到m的那个人出列，他的下一个又从0开始报数，数到m的人出列，以此进行下去，直到全部出
列。要使用无头结点的循环单链表)*/

#include<stdlib.h>
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;

}node;

//n为人数；k为第一个开始报数的人；m为出列喊到的数
void Josephus(int n, int k, int m)
{

node *p = (node*)malloc(sizeof(node));
p->data = 0;
p->next = p;
node *r = p;
for(int i=1; i<n; i++) //创建编号为1...n的人
{
node *q = (node*)malloc(sizeof(node));
q->data = i;

/* q->next = r->next; (/*...*/里的语句不懂，是如何创建循环链表的，怎么用尾结点连接第一个结点？)
r->next = q;
r = q; */

}
//把当前指针移动到第一个报数的人
while(k--) //编号为k的人开始报数
{
r = p;
p = p->next;
}
while(n--) //报到m就输出该结点并删除该结点
{
for(int s = m;s>0;s--)
{
r = p;
p = p->next;
}
r->next = p->next;
printf("%d->",p->data); //报数为m的人输出
free(p); //删除报数为m的人
p = r->next; //从报数为m的下一个人开始继续报数
}
}
int main(void)
{
Josephus(15,6,2);
printf("\n");
return 0;
}

请懂得大神解释下，还有不懂的不要把网上的答案贴上来，谢谢！

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励20（财富值+成长值）

Answer 1

首先，p是指向头结点的，或者说第一个结点，然后：
p->next = p; //p->next也指向头结点，也就是头结点的next指向自己，那么一开始只有一个结点时这就已经是一个循环链表了，后面再插入结点时只要尾结点的next指向头结点，就能保持它仍然是循环链表。
node *r = p;//用r来指向尾结点，r=p，因为p->next=p，所以也就是r->next==p，尾结点的next指向头结点。
for循环中：
q->next = r->next;//把新增结点的next指向头结点，其实等价于q->next=p，因为r->next==p，尾结点的next是指向头结点的。
r->next = q;//把原先的尾结点的next指向新增结点。
r = q;//把尾结点改为新增结点，因为上面已经将新增结点的next指向头结点，所以这个操作过后，尾结点的next仍然指向头结点，也就保持了链表仍然是循环链表。