2022年数据结构约瑟夫环课程方案 .pdf
个人资料整理仅限学习使用摘要：约瑟夫问题是由古罗马著名的史学家Josephus 提出的问题演变而来，所以通常称为 Josephus 问题。改进约瑟夫问题的描述是：编号为1，2， n 的 n个人按顺时针方向围坐一圈, 每人有一个密码Kilink=head解决问题的核心步骤：先建立一个具有n 个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。关键词： 约瑟夫环；双向循环链表；数据结构；删除结点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页个人资料整理仅限学习使用目录1 需求分析 21.1 功能分析2 1.2 设计平台2 2 概要设计 22.1 类 LinkList3 2.2 类 Joseph3 2.3 类异常处理3 3 详细设计和实现33.1 创建结点Node3 3.2 创建双向循环链表4 3.3 从链表中删除结点5 4 调试与操作说明54.1 调试情况5 4.2 操作说明6 总结 8致谢 9参考文献 10精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 14 页个人资料整理仅限学习使用1 需求分析1.1 功能分析本次选做的课程设计是改进约瑟夫(Joseph 环问题。我选择了和薛晶两个人来完成本次课程设计的作业。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front 始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand(函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。1.2 设计平台Windows2000以上操作系统； Microsoft Visual C+ 6.0 2 概要设计已知 n 个人link=head。解决问题的核心步骤：首先建立一个具有n个链结点，无头结点的循环链表。然后确定第1 个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist , Joseph 。2.1 类 LinkList 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 14 页个人资料整理仅限学习使用主要功能是创建结点，每个结点数值域包括data,password , 还有指示前驱结点的指针 llink , 和指示后继结点的指针rlink 。2.2 类 Joseph 主要功能是实现创建双向循环链表及一些相应的操作。2.3 类异常处理在 C+程序中，可以使用try-throw-catch 结构处理程序异常。采用这一程序结构能够将使用和实现分离：类和函数的实现者使用throw 语句易地错误类别通知使用者。使用者根据获悉的错误类别采取相应的措施，这就是异常处理。3 详细设计和实现改进约瑟夫环问题的基本思路和原问题基本一致，只是一个采用单循环链表，另一个采用双向循环链表来解决问题。第一步是定义结构变量结点linklist ，并在该结点下定义结点的元素域: data,password ，指针域 : lLink 和rLink。然后建立一个由n 个链结点，无表头结点的双向循环链表。并由构造函数对结点赋值，由随机函数rand(产生每个结点的 password 。由于每个结点的password是由随机函数产生的，也就是每个结点的password是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报password个数后，报到的那个结点被删除，它的password被记录下，由它的下一个结点开始逆方向报数如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到问题上，还需要创建一个Joseph类，由构造函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在Joseph类中定义一个 GetWinner(函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。3.1 创建结点 Node 链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。因此需要创建双向链表结点。由于每一个结点有一个密码和一个序号，所以可以将精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 14 页个人资料整理仅限学习使用结点结构体定义为：struct Node int data。int password。DNode* llink 。DNode* rlink 。 图 3.1 结点 Dnode3.2 创建双向循环链表创建一个空双向循环链表，双向循环链表和每个结点包括三个域: Element，lLink,rLink . 其中 element为元素域， rLink 域为指向后继结点的指针，新增的lLink 域用以指向前驱结点。双向链表也可以带表头结点，并且也可以构成双向循环链表。此时，表头结点的rLink ，lLink 分别指向双向循环链表的头结点( 或表头结点 和尾结点。一个结点的 lLink 域的指针指向它左边结点的后部，这并不意味着该结点的 lLink 域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是等价的，都是指该存储块的起始位置。图 3.2 单表头的双向循环链表每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值 password赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不rLink password data first llink 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 14 页个人资料整理仅限学习使用带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为front，front 始终指向头结点，并定义指针current记录当前的结点。并根据具体情况移动llink-rlink=q-rlink 。q-rlink-llink=q-llink。delete q。来删除当前的那个结点q，通过循环来一次次删除当前的结点，直到链表中剩下最后一个结点。具体程序如下：#include #include #include typedef struct node /定义单循环链表中节点的结构 int num 。/ 序列号即个人的编号int cipher。/ 个人所持有的密码struct node *next。linklist。class YSFH 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 14 页个人资料整理仅限学习使用 public: linklist *Creat(int n。linklist *Select1(int m。linklist *head。/ 头指针指示有 n 个结点的单循环链表creat protected: linklist *Select(linklist *head,int m。private: linklist *p。/ 存放人员信息linklist *r。/ 临时存放 linklist *q。int k。 。/* 建立单循环链表函数 */ linklist *YSFH:Creat(int n linklist *head。linklist *p。p=(linklist *malloc(sizeof(linklist。head=p。p-num=1 。printf(随机产生第 1 个人的密码 : 。p-cipher=rand(%10 。 if(p-cipher=0 p-cipher=rand(%10 。 printf(%dn,p-cipher。r=p。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 14 页个人资料整理仅限学习使用p-next=p 。for(int k=2。k p=(linklist *malloc(sizeof(linklist。p-num=k 。/ 给每人一个编号printf(随机产生第 %d个人的密码 : ,k。 p-cipher=rand(%10。 if(p-cipher=0 p-cipher=rand(%10 。 printf(%dn,p-cipher。r-next=p 。r=p。 p-next=head 。return(head 。 /* 决定出列编号 */ linklist *YSFH:Select1(int m return Select(head,m。 linklist *YSFH:Select(linklist *head,int m q=head。k=1。p=q-next 。/q 为 p 的前驱指针 ,p 指向当前报数的人精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 14 页个人资料整理仅限学习使用printf(出列的序号依次为 : 。/ 在 head 中的第一个结点起循环记数找第m个结点while(q!=p k=k+1。/ 报一次数 if(k%m=0/所报数等于报数上限值时 printf(%d ,p-num。/ 输出该结点的 num值m=p-cipher 。/ 把该结点的 cipher( 密码值赋给 m q-next=p-next 。/ 对应的节点从链表中删除free(p 。k=0。p=q-next 。 else q=p。p=p-next 。/p 指向当前报数的人 head=p。return(head 。 void main( int n,m 。m!=0。 YSFH Y 。printf(输入总人数 n: 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 14 页个人资料整理仅限学习使用scanf(%d,&n 。Y.head=Y.Creat(n 。printf(随机产生第一次的报数上限值m: 。m=rand(%10 。 if(m=0 m=rand(%10 。 printf(%dn,m。Y.head=Y.Select1(m 。printf(%dn,Y.head-num。 4 调试与操作说明4.1 调试情况这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在随机设置每个结点的password 时也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。4.2 操作说明精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 14 页个人资料整理仅限学习使用生成界面如图 4.1 ，4.2 所示：图 4.1 生成界面：图 4.2 生成界面当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页个人资料整理仅限学习使用总结为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页个人资料整理仅限学习使用致谢这次的课程设计，我们两人一个小组去完成我们自己的课程，但是还是得到了来自很多方面的帮助。在此首先要感谢淮阴工学院计算机工程系提供给我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做实验，正是这种良好的实验环境让我们整个实验过程心情都非常愉快。再次要感谢指导老师们的辛勤指导，每当我们遇到疑难问题时，是他们一次次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检验自己机会。只有在真正实战的时候才会发现书到用时方恨少的真谛。有时感觉自己那么一次次举手请教，可问题又那么幼稚简单。老师是那么的耐心与不厌其烦，直到我们点头说懂得的时候老师才离开。最后也要感谢同学们的帮助，有了他们的支持使我遇到任何困难都不是一个人在战斗。感谢所有在我课程设计过程中帮助过我的人！精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 14 页个人资料整理仅限学习使用参 考 文 献1张乃孝 , 裘宗燕 . 数据结构 C+与面向对象的途径 . 北京：高等教育出版社，1998 2 周云静数据结构习题解读与上机指导北京：冶金工业出版社，2004 3 陈慧南数据结构 C+语言描述北京：人民邮电出版社，2005 4 严蔚敏，吴伟民数据结构北京：清华大学出版社，1997 5 Adam Drozdek数据结构与算法北京：清华大学出版社，2006 6 徐孝凯数据结构实验北京：中央广播电视大学出版社，2001 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页
