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

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

1、 摘要：约瑟夫问题是由古罗马著名的史学家 Josephus 提出的问题演变而来，所以通常称为 Josephus 问题。改进约瑟夫问题的描述是：编号为 1，2，n 的 n个人按顺时针方向围坐一圈,每人有一个密码 Ki（整数），留作其出圈后应报到Ki 后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p-link=head 解决问题的

2、核心步骤：先建立一个具有 n 个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。关键词：约瑟夫环；双向循环链表；数据结构；删除结点 目 录 1 需求分析.3 1.1 功能分析.3 1.2 设计平台.3 2 概要设计.3 2.1 类 LinkList.3 2.2 类 Joseph.4 2.3 类异常处理.4 3 详细设计和实现.4 3.1 创建结点 Node.4 3.2 创建双向循环链表.5 3.3 从链表中删除结点.6 4 调试与操作说明.10 4.1 调试情况.10 4.2 操作说明.10 总 结.错误!未定义书签。致 谢.13 参 考 文

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

4、数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。1.2 设计平台 Windows2000 以上操作系统；Microsoft Visual C+6.0 2 概要设计 已知 n 个人（以编号 1，2，3.n 分别表示）围成一圈。从编号为1 的人开始报数，数到 m 的那个人出列；他的下一个人又从1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入 n,m,k 三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构

5、，就是将一个链表的尾元素指针指向队首元素。p-link=head。解决问题的核心步骤：首先建立一个具有 n 个链结点，无头结点的循环链表。然后确定第 1 个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist,Joseph。2.1 类 LinkList 主要功能是创建结点，每个结点数值域包括 data,password,还有指示前驱结点的指针 llink,和指示后继结点的指针 r

6、link。2.2 类 Joseph 主要功能是实现创建双向循环链表及一些相应的操作。2.3 类异常处理 在 C+程序中，可以使用 try-throw-catch 结构处理程序异常。采用这一程序结构能够将使用和实现分离：类和函数的实现者使用 throw 语句易地错误类别通知使用者。使用者根据获悉的错误类别采取相应的措施，这就是异常处理。3 详细设计和实现 改进约瑟夫环问题的基本思路和原问题基本一致，只是一个采用单循环链表，另一个采用双向循环链表来解决问题。第一步是定义结构变量结点linklist，并在该结点下定义结点的元素域:data,password，指针域:lLink 和 rLink。然后建

7、立一个由 n 个链结点，无表头结点的双向循环链表。并由构造函数对结点赋值，由随机函数 rand()产生每个结点的 password。由于每个结点的 password 是由随机函数产生的，也就是每个结点的 password 是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报 password 个数后，报到的那个结点被删除，它的 password 被记录下，由它的下一个结点开始逆方向报数如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到问题上，还需要创建一个 Joseph 类，由构造函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在 Jos

8、eph 类中定义一个 GetWinner()函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。3.1 创建结点 Node 链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。因此需要创建双向链表结点。由于每一个结点有一个密码和一个序号，所以可以将结点结构体定义为：struct Node rLink password data llink int data;int password;DNode*llink;DNode*rlink;图 3.1 结点 Dnode 3.2 创建双向循环链表 创建一个空双向循环链

9、表，双向循环链表和每个结点包括三个域:Element，lLink,rLink.其中 element 为元素域，rLink 域为指向后继结点的指针，新增的 lLink域用以指向前驱结点。双向链表也可以带表头结点，并且也可以构成双向循环链表。此时，表头结点的 rLink，lLink 分别指向双向循环链表的头结点(或表头结点)和尾结点。一个结点的 lLink 域的指针指向它左边结点的后部，这并不意味着该结点的lLink 域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是等价的，都是指该存储块的起始位置。图 3.2 单表头的双向循环链表 每当结点计数到某一结点时，将他的前驱结

10、点接到他的后继结点，然后将他的密码值 password 赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为 front，front 始终指向头结点，并定义指针 current 记录当前的结点。并根据具体情况移

11、动（顺逆时针）。first 为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的 data 值就可以。最后通过函数调用来输出顺序。要解决约瑟夫环问题，首先一点就是必须有一个环，所以第一步我们必须建立一个双向循环链表。而建立一个双向循环链表必须有一个空的双向循环链表，然后运用尾插法建立一个双向循环链表，这样约瑟夫环就创建出来了，接下来就是处理约瑟夫环问题。3.3 从链表中删除结点 在双向循环链表中，一个结点的前驱结点地址保存在该结点的lLink 域中，这样可以方便地实现在一个指定结点之前插入一个新结点的操作，也可以方便地删除某个指定结点

12、。函数通过代码：q-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 public:linklist*Creat(int n);linklist*Select1(int m);

13、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

14、()%10;if(p-cipher=0)p-cipher=rand()%10;printf(%dn,p-cipher);r=p;p-next=p;for(int k=2;knum=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);lin

15、klist*YSFH:Select(linklist*head,int m)q=head;k=1;p=q-next;/q 为 p 的前驱指针,p 指向当前报数的人 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

16、-next;/p 指向当前报数的人 head=p;return(head);void main()int n,m;m!=0;YSFH Y;printf(输入总人数 n:);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 调试情况 这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写

17、好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在随机设置每个结点的 password 时也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。在调试的过程中

18、，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。4.2 操作说明 生成界面如图 4.1，4.2 所示：图 4.1 生成界面 ：图 4.2 生成界面 当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。总结 为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前

19、只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放

20、弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。致 谢 这次的课程设计，我们两人一个小组去完成我们自己的课程，但是还是得到了来自很多方面的帮助。在此首先要感谢淮阴工学院计算机工程系提供给我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做实验，正是这种良好的实验环境让我们整个实验过程心情都非常愉快。再次要感谢指导老师们的辛勤指

21、导，每当我们遇到疑难问题时，是他们一次次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检验自己机会。只有在真正实战的时候才会发现书到用时方恨少的真谛。有时感觉自己那么一次次举手请教，可问题又那么幼稚简单。老师是那么的耐心与不厌其烦，直到我们点头说懂得的时候老师才离开。最后也要感谢同学们的帮助，有了他们的支持使我遇到任何困难都不是一个人在战斗。感谢所有在我课程设计过程中帮助过我的人！参 考 文 献 1 张乃孝,裘宗燕.数据结构 C+与面向对象的途径.北京：高等教育出版社，1998 2 周云静数据结构习题解析与上机指导北京：冶金工业出版社，2004 3 陈慧南数据结构C+语言描述北京：人民邮电出版社，2005 4 严蔚敏，吴伟民数据结构北京：清华大学出版社，1997 5 Adam Drozdek数据结构与算法北京：清华大学出版社，2006 6 徐孝凯数据结构实验北京：中央广播电视大学出版社，2001