1、 课程设计说明书 NO.1 沈 阳 大 学 约瑟夫（约瑟夫（Joseph）环）环 1.课程设计的目的课程设计的目的 本次课程设计通过设计一完整的程序，可以掌握数据结构的应用、算法的编写、类 C 语言的算法转换成 C 程序并用 TC 上机调试的基本方法。应用对数据结构理论学习， 通过上机实践的方式将理论知识与实践更好的结合起来，巩固所学知识。 数据结构是实践性很强的课程，课程设计是加强学生实践能力的一个有力手段。本 次课程设计的目的就是要达到理论与实际的应用相结合学会数据的组织方法，能把现实 世界中的实际问题在计算机内部表现出来，能够提高学生的思维能力和专业素质的提 高，对学生基本程序设计素质的
2、培养和为以后工作打下了坚实的基础。 本次课程设计是利用利用单向循环链表存储结构解决 Joseph 环问题，编号是 1， 2，,n的 n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数） 。一开始 任选一个正整数作为报数上限值 m,从第一个仍开始顺时针方向自 1 开始顺序报数， 报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一 个人开始重新从 1 报数，如此下去，直到所有人全部出列为止，本次课程设计将设计一 个程序来求出出列顺序。 2.2.设计设计方案论证方案论证 2.12.1 设计思路及设计思路及方法方法 为了记录退出的人的先后顺序，采用一个顺序
3、表进行存储。程序结束后再输出依次 退出的人的编号顺序。由于只记录各个结点的 data 值就可以。最后通过函数调用来输 出顺序。第一步是定义结构变量结点 linklist，并在该结点下定义结点的元素 域:data,password，指针域:lLink 和 rLink。然后建立一个由 n 个链结点，有表头结点的 单向循环链表。并由构造函数对结点赋值，由随机函数 rand()产生每个结点的 password。 由于每个结点的 password 是由随机函数产生的， 也就是每个结点的 password 是后知的， 所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报 password 个数后，报
4、 到的那个结点被删除，它的 password 被记录下，由它的下一个结点开始逆方向报 数如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到 课程设计说明书 NO.2 沈 阳 大 学 问题上，还需要创建一个 Joseph类，由构造函数来初始化，输入所有的人数，也就是表 长，然后指定由第几个人开始报数。在 Joseph 类中定义一个 GetWinner()函数，由它来 实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了 一个人之后，再按逆时针顺序报数，如此交替进行。 创建一个空单向循环链表，单向循环链表和每个结点包括三个域:Element， lLink,rLink.其中 element 为元素域，rLink 域为指向后继结点的指针，新增的 lLink 域用以指向前驱结点。单向链表带表头结点，并且也可以构成单向循环链表。此时，表 头结点的 rLink，lLink 分别指向双向循环链表的头结点(或表头结点)和尾结点。 一个结点的 lLink 域的指针指向它左边结点的后部，这并不意味
