数据结构_约瑟夫环_课程设计

《数据结构_约瑟夫环_课程设计》由会员分享，可在线阅读，更多相关《数据结构_约瑟夫环_课程设计（16页珍藏版）》请在毕设资料网上搜索。

1、 数据结构 课程设计报告 设计题目： 班 级： 组 长： 姓名（学号） 组 员：姓名（学号） 指导教师： 完成日期： 成绩： 目目 录录 1 需求分析 3 1.1 功能分析 3 1.2 设计平台 3 2 概要设计 4 2.1 类 LinkList . 6 2.2 类 Joseph . 6 2.3 类异常处理 6 3 详细设计和实现 6 3.1 创建结点 Node . 8 3.2 创建双向循环链表 9 3.3 从链表中删除结点 . 10 4 调试与操作说明 . 14 4.1 调试情况 . 14 4.2 操作说明 . 14 5 设计总结 . 15 参 考 文 献 16 附录. 16 1 需求分析需

2、求分析 1.11.1 功能分析功能分析 本次选做的课程设计是改进约瑟夫(Joseph)环问题。约瑟夫环问题是一个古 老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单 循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样 也能方便地解决。 在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我 们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。 进行 操作时，用一个指针 current 指向当前的结点，指针 front 始终指向头结点。然后 建立双向循环链表，因为每个人的密码是通过 rand()函数随机生成的，所以指定 第一个人

3、的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后 一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。 1、 本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设 n 30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表 和非空表的界限。 2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示 “提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输 入数据和运算结果显示在其后。 3、 程序执行的命令包括： 1） 构造约瑟夫环；2）执行约瑟夫环，并输出出列人的

4、序号以及相应的 密码； 3）结束。 4、测试数据 1）m 的初始值为 20； 2）n=7，7 个人的密码依次为：3、1、7、2、4、8、4。 3）首先 m 值为 6，正确的出列顺序应为 6、1、4、7、2、3、5。 1.21.2 设计平台设计平台 Windows2000 以上操作系统；Microsoft Visual C+ 6.0 2 概要设计概要设计 已知 n个人（以编号 1，2，3.n分别表示）围成一圈。从编号为 1 的人开 始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人 又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的 实际场景，有一种是要通过输入 n,m,k 三个正整数，来求出列的序列。这个问题 采用的是典型的循环链表的数据结构， 就是将一个链表的尾元素指针指向队首元 素。 p-link=head。解决问题的核心步骤：首先建立一个具有 n个链结点，无头 结点的循环链表。然后确定第 1 个报数人的