约瑟夫环的课程设计实验报告

《约瑟夫环的课程设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告　学　　院　　　专　　业　2005--7　班　　　课程设计(论文)题目　　约瑟夫　　二、课程设计(论文)工作自2007年1月8日起至2007年1月12日止。三、课程设计(论文)地点:软件学院机房四、课程设计(论文)内容要求：1．本课程设计的目的1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关

2、参考资料，提高学生进行程序设计的基本能力。2．课程设计的任务及要求1）基本要求：1. 分析题目，查阅相关资料；2. 算法设计、数据结构设计；3. 编写代码并调试；4. 完成课程设计报告。年月日-27-目录一、问题描述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．5二、基本要求．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．5三、测试数据．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．6四、算法思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．

3、．7五、模块划分．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．8六、数据结构．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．11七、源程序．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．12八、测试情况．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．26正文一、问题描述约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺

4、时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序，以及密码顺序。-27-二、基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。-27-三、测试数据数目次值项数1234测试结果1出队密码顺序顺序测试结果2出队密码顺序顺序测试结果3出队密码顺序顺序测试结果4出队密码顺序顺序参与人数4351269上限值5811第一人的密码36151381511

5、第二人的密码475941121325第三人的密码612662431236第四人的密码18125366561第五人的密码38416412第六人的密码51210558第七人的密码9879第八人的密码2415248第九人的密码5420327第十人的密码553第十一人的密码11920第十二人的密码131111★注（由于表格有限，特在此注明）：当输入的人数大于30时，系统提示“输入数字无效”重新输入；当输入的上限值大于10时，系统提示“输入数字无效”重新输入；；当输入的密码大于10时，系统提示“输入数字无效”

6、重新输入。（有两组数字的方格中，下面的数字为有效数值）-27-四、算法思想为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个

7、具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。-27-五、模块划分（1）创建单循环链表模块；voidCreatLinkList(LinkList*L)//构建单循环链表{(*L)=(LinkList)malloc(sizeof(Node));if((*L)==NULL){printf("memoryallocationfailed,goodbye")

8、;exit(1);}}voidInitLinkList(LinkList*L,intpersonNumber)//初始化单循环链表{Node*p,*q;//定义结构体类型指针变量inti;p=(*L);//初始化第一个结点,并赋值给pp->data=1;p->password=GetPassword();//调用GetPassword()输入密码for(i=2;i<=personNumber;i++){q=(LinkList)malloc(sizeof(Node));