约瑟夫环-数据结构.doc

1、数据结构期末试验报告学院： 专业： 学号：班级：姓名： 2010.12.12Joseph约瑟夫环上机实验报告实验名称：joseph约瑟夫环题目要求的约瑟夫环操作：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。实验要求：1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。2）建立输入处理输入数据，输入m的

2、初值，n ，输入每个人的密码，建立单循环链表。3）建立一个输出函数，将正确的输出序列4）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？实验过程：1.基本算法以及分析：本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下typedef struct Node int Index; 在当前环中所处的位置，即编号int Password; 在当前环中的所带的密码struct Node *next; JosephuNode; 程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个

3、环上所带的密码。然后，开始调用JosephuNode *Creat_Node函数，利用单循环链表建立起约瑟夫环，tail-next = head;就是将最后一个结点的后继指向头结点，函数结尾 return head; 将约瑟夫环的头指针返回，并将它赋值head，然后主函数继续调用Josephu函数，通过讲head和Password引入函数，以建立两个嵌套循环输出并实现如下功能：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他

4、在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。2.程序源代码： 约瑟夫环#include #include typedef struct Node int Index;int Password; struct Node *next; JosephuNode; / 使用单循环链表创建约瑟夫环JosephuNode *Creat_Node(int numbers) int i,pass; JosephuNode *head, *tail; head = tail = (JosephuNode *)malloc(sizeof(JosephuNode); /申请头结点for

5、 (i = 1; i Index = i;printf(tt请输入第%d号所带密码: ,i); /输入当前结点所带密码scanf(%d,&pass);tail-Password=pass;tail-next = (JosephuNode *)malloc(sizeof(JosephuNode); /申请一个新结点tail = tail-next; /指针指向下一个结点 tail-Index = i;printf(tt请输入第%d号所带密码: ,i);scanf(%d,&pass);tail-Password=pass;tail-next = head; /将尾结点指针指向表头return he

6、ad;/Creat_Node/ 约瑟夫环void Josephu(JosephuNode *head,int Password) int i,j;JosephuNode *tail; for (i = 1; tail != head; +i) for (j = 1; j next; tail-next = head-next; printf(ntt第%d个出局的人的编号是：%dt密码是：%d,i,head-Index,head-Password);Password=head-Password;free(head); head = tail-next; i =head-Password; j=h

7、ead-Index;printf(ntt第7个出局的人的编号是：%dt密码是：%dn,j,i);free(head); /Josephu/void main() int numbers, Password;char stop;JosephuNode *head;printf(tt- 约瑟夫环问题 -n);printf(tt例如：输入约瑟夫问题的人数和起始密码：7,20n);printf(tt-n);doprintf(tt开始.ntt输入约瑟夫环问题的人数和起始密码：);scanf(%d,%d, &numbers, &Password);head=Creat_Node(numbers);prin

8、tf(tt-n);printf(tt输出结果如下n);Josephu(head,Password);printf(tt-n);printf(tt是否继续进行？是Y(y),否N(n)t);getchar();scanf(%c,&stop);getchar();printf(tt-n);while(stop=y|stop=Y); 3.运行结果程序开始的欢迎界面：输入约瑟夫环的人数7 初始密码20输入密码：3 1 7 2 4 7 4输入y程序继续运行，n 则退出4.心得体会此程序目前的缺点在于，结点密码数据类型定义的存储类型是int型，不能超过-21474836482147483648，一旦超过则程序输出结果有误，另一个缺点就是程序运行当中，一旦中途输入出现错误，则无法返回，必须将当前操作结束等到下个主函数的循环开始，或者直接退出重新运行此程序。优点则在于程序运行速度较快，不会出现输出结果有误的问题经过这次集中上机的实验，从开始选题到自己上手还是编写程序的过程中