Question

数据结构试验设计上老师提出了一个问题，关于线性结构的应用，约瑟夫环问题.

设有n个人坐在圆桌周围，从第s个人开始报数，数到m的人出列，然后再从下一个人开始报数，数到m的人出列，如此重复，直到所有人都出列为止。要求输出列的顺序。

Answer 1

运用顺序表：(在vs2008上编写的）
#include<stdio.h>
typedef struct
{ int data[50];
}seqlist;
main()
{
int n=0,m=0,s=0,i=0,j=0,k=0,s1=0,w=0;
seqlist L;
printf("please input n: ");
scanf("%d",&n);
printf("please input m: ");
scanf("%d",&m);
printf("please input s: ");
scanf("%d",&s);L.data[0]=0;
for(i=1;i<=n;i++)
{
L.data[i]=i;
}
s1=s;
for(i=n;i>=2;i--)
{
s1=(s1+m-1)%i;
if(s1==0)
s1=i;
w=L.data[s1];
for(j=s1;j<=i-1;j++)
L.data[j]=L.data[j+1];
L.data[i]=w;
}
for(k=1;k<=n/2;k++)
{
w=L.data[k];
L.data[k]=L.data[n-k+1];
L.data[n-k+1]=w;
}
for(i=1;i<=n;i++)
printf(" %d ",L.data[i]);
getch();
}

Answer 2

用循环单链表, 设一个头指针,一个计数器,一个游标指针,计算数到几,数一个人,计数器加1，游标指针往下走一个， 数到m,游标指针指向的节点断开并输出,同时计数器变成1，游标在往下走1个,(注意循环的时候如果转过一圈,游标指针不是简单加1了,如果遇到头节点要变成1), 还有种情况就是头节点要断开,那就把头节点指针往下挪一个就可以了

Answer 3

我手上有倒是有一个。但是是有什么初始密码，每人手里还拿了一个密码的。跟你这个题目要求有的出入。我的也是用线性表的。是《数据结构》的一道课后习题。

追问

(⊙o⊙)…额，看看。

追答

你给个邮箱地址吧。贴上来麻烦