数据结构课程设计报告约瑟夫环完整版1.docx

《数据结构课程设计报告约瑟夫环完整版1.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告约瑟夫环完整版1.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计报告约瑟夫环完整版1 * 实践教学 * 兰州理工大学 软件职业技术学院 2022年春季学期 算法与数据结构课程设计 题目：约瑟夫环 专业班级: 姓名: 学号： 指导教师： 成绩： 摘要 约瑟夫环问题是典型的线性表的应用实例,其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库.而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用 MRST公司的icosoft Visual C+6.开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间

2、内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词:单循环链表；c语言；约瑟夫环; 序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表,其特点是无须增加存储容量,仅对表的链接方式稍作改变,使表处理更加灵活,约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例,了解单链表和单循

3、环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题,了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础. ?目录 摘要. 错误!未定义书签。序言?错误!未定义书签。 目录?错误!未定义书签。 正文 (3) 一、问题描述. 错误!未定义书签。 二、逻辑设计. 错误!未定义书签。 三、详细设计. 错误!未定义书签。 13 四、程序代码? 五、程序调试与测试. 错误!未定义书签。设计总结. 错误!未定义书签。参考文

4、献. 错误!未定义书签。致谢. 错误!未定义书签。附录. 错误!未定义书签。 ?正文 一、问题描述 约瑟夫环问题描述的是：设编号为1,2，,n的n(n0)个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到时停止报数,报m的人出圈，将他的密码作为新的m值,从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析： 二、逻辑设计 、循环链表抽象数据类型定义 t p def struct LN d /定义单循环链表中节点的结

5、构 ?nt nu ;/编号 ?in wd ；/ass ord s ruct LNod next;/指向下一结点的指针 No e; 2、本程序包含一下几个模块 （1)构造结点模块 L ode cr a e de(int _num,int m_pw ） 图2 约瑟夫环原理演示图 ?Node p; p=（Lde ）aloc(sieof（Lode）)；/生成一个结点 pnum=m_num;/把实参赋给相应的数据域 pd=mpw； ?pnext=NULL;/指针域为空 ?etrn p； （2）创建链表模块 void teist(LNoe ppHead，int n） （3）出队处理模块 vi（Noe pp

6、Had，int m_pwd） (4）约瑟夫环说明输出模块 oi istution（) （5）菜单模块 voimn（） (6）主函数模块 nt m（) 函数的调用关系图如下： 三、详细设计 1.主函数 图4 主函数数据流程图 根据流程图，主函数程序如下： int mi() int n，m,x; ?LNodpHed=NUL; ? menu(）; ?fr(；;) prf（n请选择要执行的操作：)； ?scnf（”%d”，&x); ste（c”）； witc（x) case 1： ?rintf（”*); pritf(约瑟夫环:”); pritf（”编号为,2,4，n的n个人按顺时针方向围坐一圈，每人持

7、有一个密n); prinf(码（正整数）一开始任选一个正整数作为报数的上限值m，从第一个人开始n”）; rntf(按顺时针方向自开始顺序报数,报到m时停止报m的人出列,将他的密码n”）； rnf（m作为新的值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，n”)； prin（直到所有人全部出列为止编程打印出列顺序）; printf（*n）; main（）； ?bre； cs 2: rit（请输入总人数n：）; scanf(”，n）; rnf（请输入开始上限数:”）; ?scnf（”%,&m); ? createList(&pd,n); prif（n)； prif(出队顺序:）； ? j

8、ose(ped，m）； printf（”n约瑟夫环游戏结束!”）； main（); ?rea; ? cae 0: ? exit（0）； ?efau： sysem（cls”); ?prntf(”n您选择的操作有误，请重新选择。nnn）； ?mi（）； ? ? etun 0； 2.链表的创建 图5 创建链表函数的数据流程图 /创建单向循环链表pHad，人数个数为n,并输入每个人的密码值，若建立失败则生成头结点，让c指向他,若建立成功则插入结点，cr指向的数据元素为p，后续为空的节点,再把P插入循环链表Hed中 根据流程图,创建链表函数程序如下： id ceateLis（LNoe *ppead,int n） ?int i，m_wd； LNe *,cur;/cu:浮标指针 ?fo(i=1;=n;i） ? ?pritf(输入第d个人的密码：，)； ?scnf（”%”，_pwd)；/输入持有密码 ?p=catNoe（，m_wd）；调用构造结点函数 ?if（*ppHd=NULL）/如果头结点为空 ?