约瑟夫环C语言数据结构实验报告.docx

约瑟夫环问题 实验目的 约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 实验内容 利用带头结点的单循环链表设计一个程序，以人机交互方式执行，用户制定约瑟夫环游戏的总人数n和初始报数上线m，然后输入每个人所持有的密码password。模拟约瑟夫环，从头开始报数，直到所有人都出列，系统按照出列顺序给出编号。 实验平台 Microsoft Visual C++ 设计流程 利用单循环链表求解本问题，先创建一个有n+1个结点（包括一个头结点）组成的单循环链表，依次录入n个密码值password。然后从第一个结点出发，连续略过m-1个结点，将第m个结点从链表中删除，并将第m个结点的密码值作为新的m值，接着再次从下一个结点出发，重复以上过程，直至链表为空。 源代码清单 #includestdio.h #includemalloc.h typedef struct list { int num; int passward; struct list *next; }node; node *creatlist(int n) { node *p,*q,*head; int i=1; head=(node *)malloc(sizeof(node)); head-num=i; printf(请输入第1个人的密码：); scanf(%d,head-passward); p=head; for(i=2;i=n;i++) { q=(node *)malloc(sizeof(node)); if(q==0)return 0; printf(请输入第%d个人的密码：,i); scanf(%d,q-passward); q-num=i; p-next=q; p=q; } p-next=head; return head; } void josephus(node *l,int k) { int i; node *p=l,*q,*s; printf(\n-----------按照出列顺序输出每个人的编号-----------\n); while(p-next!=p) { for(i=1;ik;i++) { q=p; p=p-next; } printf(第%d个人出列，所持密码是%d\n,p-num,p-passward); k=p-passward; s=p; q-next=p-next; p=p-next; free(s); } printf(第%d个人出列，所持密码是%d\n,p-num,p-passward); printf(\n); } void main() { node *l; int n,k; printf(请输入实验人数n：); scanf(%d,n); printf(请输入初始报数上限m：); scanf(%d,k); printf(\n); l=creatlist(n); josephus(l,k); } 调试与测试结果