约瑟夫环问题仿真
设编号为1，2，…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。设计一个程序模拟此过程，给出出列人的编号序列。
二、问题分析
这是一个线性结构，可以用线性表表示。进行的主要操作时报数，出列，这相当于对线性表进行删除操作，因此宜选用链表存储结构，每个节点代表一个人，n个人围坐成一圈循环报数，则利用单循环链表解决本问题更容易，因此需要先创建一个含有n个结点的单循环链表，每个结点的数据域可以用来存储结点的编号和密码，密码可由随机函数产生。结点的指针域指向下一个结点的位置。第一次报数前首先应该找到第k个结点，然后从它开始报数，删除该结点，并且需要把该结点的密码作为新的m值，从该结点开始重新报数。
三、解决思路及算法
我们首先定义结点，包含结点编号，结点密码以及next指针，每个人的密码则通过随机生成数的方式产生。然后我们定义Outlist函数：
S1：设p，q两个指针，p指向表头结点。
S2：找到第k个结点并将q指向该结点，将该结点的密码赋值给m。
S3：从该点向后数m个结点，q=p，p=p->next。
S4：将该结点密码赋值给m，输出该结点的编号，q->next=p->next。
S5：释放p点
S6；循环S3-S5直到p为空。
四、测试样例
五、反思启发
模拟此过程，找到一个人并将其密码赋值给下一个人，这是最开始接触觉得比较棘手的问题。在编程的过程中，我运用指针和链表的能力得到了提高，如何改变指针的指向并删除已报数的结点是比较困难的事情。我们也进一步思考了如何用循环链表解决此问题的方法，两种方法的基本思路是一样的。
六、代码附录
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
typedef struct LNode
{
int num,pwd;
struct LNode *next;
}LNode,*Linklist;
Linklist Createlist(Linklist head,int n)
{
int i;
Linklist p,q;
head=(Linklist)malloc(sizeof(LNode));
q=head;
q->num=1;
q->pwd=rand()%10+1;
for(i=2;i<=n;i++)
{
p=(Linklist)malloc(sizeof(LNode));
p->num=i;
p->pwd=rand()%10+1;
q->next=p;
q=p;
}
p->next=head;
return head;
}
void print(Linklist head)
{
Linklist p,q;
p=head;
printf("输出每个人的密码\n");
while(p->next!=head)
{
printf("第%d个人的密码是：%d\n",p->num,p->pwd);
p=p->next;
}
printf("第%d个人的密码是:%d\n",p->num,p->pwd);
}
void Outlist(Linklist head,int k)
{
Linklist p,q;
int m,i;
p=head;
for(i=1;i<k;i++)
{
p=p->next;
}
q=p;
m=p->pwd;
while(p!=p->next)
{
for(i=1;i<m;i++)
{
q=p;
p=p->next;
}
m=p->pwd;
printf("%3d",p->num);
q->next=p->next;
free(p);
p=q->next;
}
printf("%3d",p->num);
free(p);
printf("\n");
}
int main()
{
int k,n;
printf("请输入总人数和从第几个人开始报数:\n");
scanf("%d%d",&n,&k);
Linklist L,head;
head=Createlist(L,n);
print(head);
printf("\n出队的次序:\n");
Outlist(head,k);
return 0;
}
平均时间复杂度O(n²)