数据结构试验设计上老师提出了一个问题,关于线性结构的应用,约瑟夫环问题小弟才疏学浅,约瑟夫问题的一种描述是：编号为1,2,...,n的n个人按顺时针方向围坐一圈,每个人持有一个密码（正

Question

数据结构试验设计上老师提出了一个问题,关于线性结构的应用,约瑟夫环问题 小弟才疏学浅,
约瑟夫问题的一种描述是：编号为1,2,...,n的n个人按顺时针方向围坐一圈,每个人持有一个密码（正整数）.一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报道m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.设计程序求出出列顺序.
基本要求：
利用单项循环链表储存结构模拟其过程,按照出列的顺序打印个人编号.

Answer 1

#include
struct list//建立一个结构体,包括每个人的编号,密码和下一级的指针
{
int id;
struct list *next;
};
list* input(int n)//链表的初始化
{
list *p,*q,*l;
int i,m;
p=new list;
l=new list;
l->next=NULL;
p=l;
p->id=1;//第一个人的初始化
for(i=2;iid=i;
q->next=NULL;
p->next=q;
p=q;
}
p->next=l;//使表尾指向表头,成循环链表
return p;
}
int main()
{
int num,m1,i;
list *q,*p;
printf("输入人数：");
while(scanf("%d",&num)!=EOF)
{
printf("密码为:");
scanf("%d",&m1);
p=input(num);
printf("最后一人序号为:");
while(p->next!=p)
{
for(i=1;inext;
}
q->next=p->next;
delete p;
p=q;
}
printf("%4d",p->id);
delete p;
printf("\n");
}
}