《c语言 数据结构 实验3——约瑟夫问题》由会员分享，可在线阅读，更多相关《c语言 数据结构 实验3——约瑟夫问题（6页珍藏版）》请在金锄头文库上搜索。
1、Fly制作 版权所有云南大学数学与统计学实验教学中心实 验 报 告课程名称：数据结构与算法学期：20012-2013学年第二学期成绩：指导教师： XXX学生姓名：XXX学生学号： 201019100XX实验名称：线性表的应用 实验要求： 选作实验学时：2学时实验编号：3实验日期： 第7-8周完成日期：2012-4-2学院： 数学与统计学院专业 ： 信息与计算科学年级： 2010级一、实验目的在实验一的基础上，用线性链表解决一个应用问题约瑟夫问题（Joseph）的求解。二、实验内容 问题描述：编号为1，2，n的n个人，按顺时针方向围坐在一圈，每人持有一个密码（正整数），一开始，任选一个正整数作为
2、报数的上线值m，从第一个人开始，顺时针方向自1开始报数，报到m时停止报数，第m的人出列，并将他的密码作为新的m值，从他开始顺时针方向的下一个人开始重新从1起报数，如此下去，直到所有的人全部出列为止。试设计一个C程序，求出列顺序。三、实验环境Windows XP程序设计语言 C四、实验过程1实验要求：基本要求：利用单循环链表存贮结构摸拟此过程，按照出列的顺序打印出出列序号及各个人的编号。测试数据：设n=20，且m的值固定，即每个人的密码一致。实现提示：（1）对m的值应从键盘临时输出，程序测试时可临时改变m的值（m=3, m=2）以验证程序的输出结果。 （2）可以利用实习1的最后一题的循环链表（为
3、方便，不设头结点）作为本题开始的循环链表。 （3）请注意，空表及非空表的判断。附加要求：按上述“问题描述”中的要求，即每个人的密码m不同，实现约瑟夫问题(Joseph)的求解。输出时应输出序号、出列人的编号、出列人的密码值。2 实验设计流程图（以下内容请同学认真填写）3程序设计代码及解释：（必须给出必要的程序注解，以保证可读性）#include#include#define NULL 0typedef struct Nodeint num;int Cipher;struct Node* next;Node,*LinkList;Node* creat(LinkList LA,int n) /构建
4、链表LinkList p1,p2;int i,k=0;p1=p2=(LinkList)malloc(sizeof(Node);printf(Please Input the Cipher of person:n);scanf(%d,&p1-Cipher);for(i=n;i0;-i)k=k+1;if(k=1)p1-num=k;LA=p1;else p2-next=p1;p2=p1;if(i-1=0) break;else p1=(LinkList)malloc(sizeof(Node); p1-num=k+1; scanf(%d,&p1-Cipher);p2-next=LA;return LA
5、;void JosephProblem(LinkList L,int n,int m)LinkList p1,p2;int count=0;int countPerson=0;p1=L;p2=L;while(p2-next != L)p2=p1;p1=p1-next;while(countPersonnum,p1-Cipher); /打印出列密码，出列序号 printf(n); m=p1-Cipher; p2-next=p1-next; /删除出列节点 p1=p1-next; count=0; /计数器归零 countPerson+=1; else p2=p1; /p2为前躯， p1=p1-n
6、ext; /p1转向后继main() /主函数LinkList LA,head;int n,m;printf(Please Input the num of person:n);scanf(%d,&n); /输入有几个人来参与LA=(LinkList)malloc(sizeof(Node);head=creat(LA,n); /构建链表printf(Please Input the record:n);scanf(%d,&m); /输入初始密码printf(The result of JosephProblem:n);printf(num Ciphern);JosephProblem(head
7、,n,m); /解决约瑟夫环的问题system(pause);system(cls);4实验（程序运行）结果的粘贴：（请粘贴你的程序运行结果）五、实验总结（以下内容请同学结合你的实验过程认真总结）1遇到的问题及分析： 对于链表中p1 、p2来表达前躯后继时遇到了难题，对这个这两个指针进行了曲解； else p1=p1-next; p2=p2-next;分析，针对于约瑟夫环的问题，不能以上面的程序来设计，同样以上程序并不能用来表达前躯后继的问题。分析后得到了一下程序： else p2=p1; p1=p1-next;2解决方案（列出遇到的问题和解决办法，列出没有解决的问题）：遇到的问题:1、编程中
8、的问题，由于编写c 用的是vs2010平台，与以前学的东西的写法有了很大的不同；2、链表的不能熟悉掌握，以及混淆。例如上一问中提到的前躯后继的问题。解决办法：1、 上网查询。2、 通过调试然后对问题的分析从而得到解决。为解决问题：如何用递归来解决？约瑟夫环在现实生活中有什么重要的运用。3体会和收获。C 的编写是结构化模块化的，只有这样我们才能清晰明了的列出问题，分析问题，解决问题。通过对约瑟夫环的解决。对于链表又有了进一步的认识。六、参考文献 数据结构 C语言版 严蔚敏、吴伟民编著 清华大学出版社出版（国家级规划教材）数据结构题集 C语言版 严蔚敏、吴伟民编著 清华大学出版社出版 数据结构扬秀金 西安电子科技大出版社 （高等学校电子信息类教材） 数据结构实用教程 C/C+描述 徐孝凯编著清华大学出版社出版数据结构 许卓群、张乃孝等编著 高等教育出版社出版算法与数据结构 付清祥、王小东编著 电子工业出版社出版数据结构极其应用教程严蔚敏、陈文博编著 清华大学出版社出版 七、教师评语：第 6 页 共 6 页
