数据结构实验报告 实验名称：约瑟夫环 实验类型：综合性实验 实验日期：2013/5/22 1.问题描述 设有编号为 1,2,…,n 的 n（n＞0）个人围成一个圈，每个人持有一个密码 m。从 第一个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起 重新报数，报到 m 时停止报数，报 m 的出圈，……，如此下去，直到所有人全 部出圈为止。当任意给定 n 和 m 后，设计算法求 n 个人出圈的次序。 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意 结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针 first 指示。 . 3.算法设计 #include #include #include typedef struct Node { int data1; int data2; struct Node *next; }; struct Node *p,*q,*first; void main() { int n,k,m,i,a; printf("请输入总人数 n="); scanf("%d",&n); printf("请输入起点 k="); scanf("%d",&k); first=(struct Node*)malloc(sizeof(struct Node)); //确定首元 

p=first; for(i=1;idata1=i; p=p->next; } p->next=(struct Node*)malloc(sizeof(struct Node)); //为下一个申请内存 //最后一个单独处理 //指向首元，形成循环链表 //p 指针重新指向首元 p->data1=n; p->next=first; p=first; printf("请问是否同意所有人持有相同 m 值?\n(1.同意 2.不同意)\n"); //开始录入 m 值 scanf("%d",&a); getchar(); switch(a) {case 1: printf("请输入 m 值:\n"); scanf("%d",&m); for(i=1;i<=n;i++) { p->data2=m; p=p->next; break; case 2: for(i=1;i<=n;i++) } { } break; printf("请输入第%d 个人所持有的 m 值\n",i); scanf("%d",&(p->data2)); p=p->next; default:printf("输入错误\n"); } while(p->data1 !=k) p=p->next; m=p->data2; while(n>1) { while(p->data1 !=k) p=p->next; for(i=1;inext; { } q=p->next; printf("%d ",q->data1); //录入结束 //将 p 指向第 k 个节点 //将 p 指向第 k 个节点 /开始报数,找到报 m-1 的结点，此时 p 指向 m-1 //q 为报 m 的结点 //输出报 m 的结点的值 

m=q->data2; k=q->next->data1; p->next=q->next; free(q); n--; //k 为下一轮报数的起点 //删除报 m 的结点 printf("%d\n",p->data1); //输出最后一个结点的值 } } . 4.界面设计 汉语提示，可选择不同的约瑟夫环问题 5. 运行、测试与分析 (1)运行程序，输入 n=9,k=1,所有人持有相同的 m 值，且 m=5，运行结果为 5 1 7 4 3 6 9 2 8，见图 1 图 1 （2）运行程序，输入 n=9,k=1,所有人持有的 m 值不相同，且第 1~9 个人的 m 值 分别是 1，2，3，4，5，6，7，8，9，运行结果为 2 4 8 1 5 6 3 7 9，见图 2 

图 2 . 6.实验收获及思考 通过该实验，我更深一层地理解了单链表，尤其是循环链表。通过解决约瑟夫环 问题，锻炼了我的独立思考能力，将问题模型化的能力，同时也暴露了我考虑问 题不全面，只看局部不重全局的问题。