实验报告
实验课名称：数据结构实验一 实验名称：约瑟夫环问题 班级 000 学号 000 姓名 神刀公子 时间 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。
1
设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++)
2
{ q=(struct node*)malloc(sizeof(struct node)); if(q==0) return 0; p->next=q; p=q; p->value=i; } p->next=head; return head; } （2）约瑟夫环报数的算法在运行为循环方式，报数者除非本身已经出去，否则继续顺序报数，其报数循环的代码为 void Joseph(NODE *p,int number,int n) { int i,j; NODE *q=NULL; for(i=1; i<=number; i++) { for(j=1; jnext; } q=p->next; p->next=q->next; p=p->next; printf(\"第%3d个出圈的人是：%3d\\n\ free(q); } scanf(\"\\n\"); p->next=NULL; } （3）主程序执行 主程序运行，调用函数，程序接受数据后，输出出圈列数。 printf(\"请输入总人数n和密码m:\\n\"); scanf(\"%d\ scanf(\"%d\ NODE *head=NULL; head=link(number); Joseph(head,number,n); system(\"PAUSE\"); return 0;3
4．界面设计 程序无需复杂的界面设计，包含输入提示功能和输出提示功能。 5.运行测试与分析 （1）输出提示 ，如图1.2所示。 （2）根据提示，输入圈内人数n和每个人持有的密码m 如图1.3所示。 （3）输出结果如图1.4所示 分析 6.实验收获及思考
4
通过该实验，我进一步增强了对于链表的理解，也对链表的操作和实现更为熟悉，熟练掌握了如何实现置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立不带头结点的单链表（头插入法建表）、建立带头结点的单链表（尾插入法建表），输出带头结点的单链表等操作。同时，锻炼了实际操作时的动手能力。 教师评分： 教师签字： 5
