约瑟夫环-joseph环-数据结构与算法课程设计报告

《约瑟夫环-joseph环-数据结构与算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称joseph环学生姓名朱玉庭学号0804012029专业班级08计本(2)指导教师王昆仑、张贯虹2010年06月08号一、问题分析和任务定义：约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。二、数据结构的选择和概要设计：选择带为指针的单循环链表

2、来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。三、详细设计和编码：本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下：typedefstructNode{intkey;//每个人持有的密码intnum;//这个人的编号structNode*next;//指向下一个结点}Link;当生成单循环链表时，就需要用到课本上创建单循环链

3、表的有关内容了，可以先通过子函数Link*InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link*Creater(Link*L,intn)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数voidOutput(Link*L,intn,intm)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;i<=n;i++)，因为一个用n个人，所以结果要输出n个编号，这个循环每循环一次输出一个编号即printf("%d",q->nu

4、m)，并将该编号下的密码赋值给m即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;jnext;q=p->next;用以找到相应的结点，并用指针q指向它，当完成了编号的输出和密码的赋值后，删除q指向的结点，将两个循环适当结合，即可输出正确的结果序列，其中的人数n和初始密码在主函数中确定。四、上机调试：（1）有2个玩家，初始密码为21；（2）有3个玩家，初始密码为5：（3）有5个玩家，初始密码为8：（4）有7个玩家，初始密码为10：一、测试结果及分析：（1）程序运行后，只能执行一部分

5、，错误情况如下：错误原因如下：调用子函数时，传递给形参的并不是L的地址，而是传递的内容，以至在对链表进行初始化时，语句L->next=p不能执行，for循环不了，故程序只能运行一部分，将程序略作修改，建空链表时，不用形参即可，修改如下：（2）程序运行时，结果输不出来，错误情况如下：错误原因如下：两个形参中的L不能联系在一起，因为在进入约瑟夫环的函数Creater（L，n）后，L的地址虽然变化了，但是不会对主函数中L的地址造成影响，故在调用输出函数Output（L，n，m）时，其中的L的地址不是Creater（L，n）中改变后的地址

6、，所以不能联系到一起，将程序略作修改，在生成约瑟夫环的函数中返回一个指针，将此返回的指针代入到输出函数Output中即可，修改如下：一、用户使用说明：进入程序运行界面后，根据提示输入相应的信息，第一步输入的是总人数n，第二步输入初始密码m，紧接着依次输入n个学生的密码，输入完成后，即可显示出最终结果。示例：请先输入总人数：3请确定开始时的报数上限值：5第1个人的密码：4第2个人的密码：6第3个人的密码：2结果序列为：213二、参考文献：[1]王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。[2]何钦铭，颜晖.C

7、语言程序设计.北京：高等教育出版社，2008年1月。[3]郑莉，董渊.C++语言程序设计（第三版）.北京：清华大学出版社，2004年1月。[4]谭浩强.C语言设计（第三版）.北京：清华大学出版社，2006年3月。[5]百度。三、附录：#include"stdio.h"#include"stdlib.h"typedefstructNode{intkey;//每个人持有的密码intnum;//这个人的编号structNode*next;//指向下一个节点}Link;voidMenu(){printf("tt************

8、********************************");printf("ttt**Joseph环---课程设计**");printf("tt**************************************