数据结构课程设计约瑟夫环问题3

1、二、上交内容课程设计报告（用课程设计报告本手写成书面形式，不少于300字0），包括数据结构课程设计报告姓名：学号：完成日期：（一）问题描述及分析：（二）数据结构描述：（三）主要算法流程描述：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。（四）使用说明：如何运行，如何输入测试数据，会出现的输出结果等，给出实例。（五）调试分析说明：调试过程中遇到的主要问题有哪些？如何解决的。有何结论？测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时

2、存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。（六）课设总结：总结可以包括:课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。1、约瑟夫环问题问题描述编号是，,n的口个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值从第一个人开始顺时针方向自开始顺序报数，报到时停止报数。报的人出列，将他的密码作为新的值，从他在顺时针方向的下一个人开始重新从报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。基本要求利用单向循环链表存储结构模

3、拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。测试数据的初值为0个人的密码依次为，首先则正确的输出是什么？要求：输入数据：首先输入待处理人员数及他们的密码，然后输入的初值，建立单循环链表。输出形式：建立一个输出函数，将正确的出列序列输出。，需求分析，.程，序存储结构本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即个人的编号和密码），模拟约瑟夫环的显示过程，按照出列的顺序印出各人的编号。程序执行方式演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为

4、结束标志。相应的输入数据和运算结果显示在其后。，.程，序执行的命令，构）造单向循环链表；，按）照出列的顺序印出各人的编号。，.测，试数据的初值为；=个人的密码依次为：，个人的密码序列号为，5，6，7,则正确的出列顺序为6，7，5概要设计3.1单向循环链表的抽象数据类型定义LiSt数据对象：=ia正整数，=1,n,n$O数据关系：1=i,1i,i-1E,=1,n基本操作：InitList(&L)操作结果：构造一个空的线性表L。ListInsert(&L,i,e)初始条件：线性表L已存在，lWiWListLength(L)+l.操作结果：在L中第i个位置之前插入新的数据无素e,L长度加1。List

5、Delete(&L,i,&e)初始条件：线性表L存在非空，lWiWListLength(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。3.,程序包含三个模块1)主程序模块：Voidm(a)in初始化；接受命令；处理命令；hi(“命令”二“退出”)；,)有序表单元模块实现有序表的抽象数据类型。3)输出函数模块有序表的输出详细设计4.1源程序头文件名清单：内存空间分配头文件输入输出函数头文件函数中字符串转短整形函数的头文件元素类型，结点类型和指针类型定义结构体intdata;用来存储人的序号，/d;用来存储人的密码定义结点创2建循环链表函数及创建输入密码函数参数传递人数创建一个带

6、头结点的链表创建输出函数传递报数上限值和人数用一个搜索循环链表删除结点释放动态申请的结点空间主函数请输入的初值（即初始密码）：请输入总人数（即的值）：请输入各人密码：密码的初原序列号为则输正输确初的出列顺序为测试约瑟夫环问题值输入界面约瑟夫环最初界面完成了的初值输入该值的作用为一开始任选的作为报数上限整数，从第一个人开始按顺时针方向自开始顺序报数，报到时停止报数。报的人出列，将他的密码作为新的值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止。最初界面如图和输入值之后的界面图所示。其运行结果为：请输入的初值（即初值密码）：输入值后其结果为请输入总人数（即的值）：输

7、入值后又出现请输入密码：，4,3,35,6,7,2,1而后输出结果为则正确的出列顺序（为各密码的序号）为其运行后窗口所有的结果为：请输入的初值（即初始密码）：请输入总人数（即的值）：请输入各人密码：密码原序列号为：则正确的的出列顺序（为各密码的序号）为：六、测试结果第一组：的初值为0=个人的密码依次为：，出列顺序为，5第二组：的初值为；=个人的密码依次为：，3出列顺序为，。第三组的初值为；=个人的密码依次为：，3476，出列顺序为，5四、调试分析，、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于，溢，出，；，、早期的循环过程中没

8、有进行优化，导致循环次数过多，浪费时间；、为了输出时美观，分别在和函数主体内做了两次，输入非零的判断，浪费了资源；、算法的时空分析为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是循环，复杂度为（）当大于时：在数据输入中，链表的创建是循环，时间复杂度为（）在约瑟夫环实现程序中，为循环。时间复杂度为（）当时，复杂度为（）。，、温馨提醒用户根据提示，先输入起始密码，然后输入人数，再根据人数，分别输入每个人的密码，数值均不能为；否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于，则，第五位自动转换为下一个

9、数字的起始位，依此类推）。当个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。数据结构的课程设计，今天终于算是完工了，好久都没编过这么大的了，虽然里面不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。看着自己的成果，真的很高兴，很有成就感。课程设计的主要目的本课程设计是计算机科学与技术专业、软件工程专业的专业技术实践课。本实践课的主要目的是：使学生学会利用在课堂中学过的理论知识，解决相应的实际问题。深入理解和灵活掌握所学的内容，培养学生理论和实践相结合的能力，培养学生分析问题、解决问题的能力，同时在实验步骤规范化、程序设计方法等方面受到比

10、较系统和规范的训练。通过实践设计，使学生进一步加深对课程设计的规范化及对复杂程序设计步骤的理解。做什么事情，都要对认真，既然是该你做的事，肯定是你应该有这个能力，即使能力不够，也是应该借这个机会来培养。所以放心大胆地做，对自己有信心，就有动力。有人说，世上的事就怕认真二字。确实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思考，慢慢地进步，真的是天下无难事。这就是我这次课程设计中得到的最大的体会，受益匪浅。通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在实习中遇到得问题，我