1、计算机科学与技术专业数据结构课程设计报告郑州师范学院计算机科学与技术专业 数据结构 课程设计报告 设计题目： 约瑟夫环 班 级： B15软件工程（） 组 长： 组 员： 指导教师： 完成日期： 2016-1-7 成绩： 目 录1需求分析 31.1功能分析 31.2设计平台 32概要设计 32.1类LinkList 32.2类Joseph 42.3类异常处理 43详细设计和实现 43.1创建结点Node 43.2创建双向循环链表 53.3从链表中删除结点 64调试与操作说明 104.1调试情况 104.2操作说明 105设计总结 11参 考 文 献 12附录 12 1需求分析1.1功能分析本次选
2、做的课程设计是改进约瑟夫(Joseph)环问题。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通
3、过一系列的循环就可以解决改进约瑟夫环问题。1、 本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。3、 程序执行的命令包括：1） 构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。4、测试数据 1）m的初始值为20； 2）n=7，7个人的密码依次
4、为：3、1、7、2、4、8、4。 3）首先m值为6，正确的出列顺序应为6、1、4、7、2、3、5。1.2设计平台Windows2000以上操作系统；Microsoft Visual C+ 6.02概要设计已知n个人（以编号1，2，3.n分别表示）围成一圈。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p-link=head。解决问题的核心
5、步骤：首先建立一个具有n个链结点，无头结点的循环链表。然后确定第1个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist , Joseph。为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。1）、单向循环链表的抽象数据类型定义为：ADT List数据对象：D=aiaiElemset,i=1,2,n,n0数据关系：R1=a(i-1
6、),aia(i-1),aiD,i=2,n基本操作： InitList(&L) 操作结果：构造一个空的链表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem(L,i,&e) 初始条件：线性表L已存在，1iListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 ListInsert(&L,I,e) 初始条件：线性表L已存在，1iListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListD
7、elete(&L,i,&e) 初始条件：线性表L已存在且非空，1iListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit() 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。 ADT List2)约瑟夫环的抽象数据类型定义为：ADT Set 数据对象：D=aiai为用户输入的数字密码，i=1,2,n,1n7 数据关系： 基本操作： CreatSet(&L，s) 初始条件：L为单向循环链表。 操作结果：对链表中的数据域进行赋值。 DeleteS
8、et(&L,i,&e) 初始条件：线性表L已存在且非空，1iListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 PrintSet(L) 初始条件：链表L已存在。 操作结果：按输出次序显示每个人的密码。 ADT Set3)本程序包含四个模块： 1、主程序模块： Void main() 初始化； Do接受命令；处理命令； while (“命令”=”退出”)； 2、约瑟夫环单元模块实现约瑟夫环的抽象数据类型； 3、单向循环链表单元模块实现单向循环链表的抽象数据类型； 4、结点结构单元模块定义单向循环链表的结点结构。 各模块之间的调用关系如下： 结点结构单元
9、模块 单向循环链表单元模块 约瑟夫环单元模块 主程序模块2.1类LinkList主要功能是创建结点，每个结点数值域包括data,password,还有指示前驱结点的指针llink,和指示后继结点的指针rlink。2.2类Joseph主要功能是实现创建双向循环链表及一些相应的操作。2.3类异常处理在C+程序中，可以使用try-throw-catch结构处理程序异常。采用这一程序结构能够将使用和实现分离：类和函数的实现者使用throw语句易地错误类别通知使用者。使用者根据获悉的错误类别采取相应的措施，这就是异常处理。3详细设计和实现改进约瑟夫环问题的基本思路和原问题基本一致，只是一个采用单循环链表
10、，另一个采用双向循环链表来解决问题。第一步是定义结构变量结点linklist，并在该结点下定义结点的元素域:data,password，指针域:lLink和rLink。然后建立一个由n个链结点，无表头结点的双向循环链表。并由构造函数对结点赋值，由随机函数rand()产生每个结点的password。由于每个结点的password是由随机函数产生的，也就是每个结点的password是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报password个数后，报到的那个结点被删除，它的password被记录下，由它的下一个结点开始逆方向报数如此循环，直到循环链表里只剩下一个结点，那就是
11、问题所求的结果。具体到问题上，还需要创建一个Joseph类，由构造函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在Joseph类中定义一个GetWinner()函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。主要功能实现的程序流程图及核心代码算法流程图：3.1创建结点Node链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。因此需要创建双向链表结点。由于每一个结点有一个密码和一个序号，所以可以将结点结构体定义为：struct Node int data;int passwor
12、d;DNode* llink;DNode* rlink; 图3.1 结点Dnode3.2创建双向循环链表创建一个空双向循环链表，双向循环链表和每个结点包括三个域:Element，lLink,rLink.其中element为元素域，rLink域为指向后继结点的指针，新增的lLink域用以指向前驱结点。双向链表也可以带表头结点，并且也可以构成双向循环链表。此时，表头结点的rLink，lLink分别指向双向循环链表的头结点(或表头结点)和尾结点。一个结点的lLink域的指针指向它左边结点的后部，这并不意味着该结点的lLink域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是
13、等价的，都是指该存储块的起始位置。图3.2 单表头的双向循环链表每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值password赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为fr
14、ont，front始终指向头结点，并定义指针current记录当前的结点。并根据具体情况移动（顺逆时针）。为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的data值就可以。最后通过函数调用来输出顺序。要解决约瑟夫环问题，首先一点就是必须有一个环，所以第一步我们必须建立一个双向循环链表。而建立一个双向循环链表必须有一个空的双向循环链表，然后运用尾插法建立一个双向循环链表，这样约瑟夫环就创建出来了，接下来就是处理约瑟夫环问题。3.3从链表中删除结点在双向循环链表中，一个结点的前驱结点地址保存在该结点的lLink域中，这样可以方便地实现
15、在一个指定结点之前插入一个新结点的操作，也可以方便地删除某个指定结点。函数通过代码：q-llink-rlink=q-rlink;q-rlink-llink=q-llink;delete q;来删除当前的那个结点q，通过循环来一次次删除当前的结点，直到链表中剩下最后一个结点。具体程序如下：#include#include#includetypedef struct node /定义单循环链表中节点的结构 int num;/序列号即个人的编号 int cipher;/个人所持有的密码 struct node *next;linklist;class YSFHpublic: linklist *Cr
16、eat(int n); linklist *Select1(int m); linklist *head;/头指针指示有n个结点的单循环链表creatprotected: 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);
17、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; 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(he
18、ad);/*决定出列编号*/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指向当前报数的人 printf(出列的序号依次为:); /在head中的第一个结点起循环记数找第m个结点 while(q!=p) k=k+1;/报一次数 if(k%m=0)/所报数等于报数上限值时 printf(%d ,p-num);/输出该结点的num值 m=p-cipher;/把该结点的cipher(密码)值
19、赋给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: ); 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
20、.head-num);4调试与操作说明4.1调试情况这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在随机设置每个结点的password时
21、也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。4.2操作说明生成界面如图4.1，4.2所示：图4.1 生成界面图4.2生成界面当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。5设计总结通
22、过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一结点，增加一个结点等。 在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充
23、分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。参 考 文 献1张乃孝,裘宗燕.数据结构C+与面向对象的途径.北京：高等教育出版社，19982 周云静数据结构习题解析与上机指导北京：冶金工业出版社，20043 陈慧南数据结构C+语言描述北京：人民邮电出版社，20054 严蔚敏，
24、吴伟民数据结构北京：清华大学出版社，19975 Adam Drozdek数据结构与算法北京：清华大学出版社，20066 徐孝凯数据结构实验北京：中央广播电视大学出版社，2001附录源程序附下：#include #include #include#include #include#define NULL 0typedef struct Node int m;/密码int n;/序号struct Node *next;Node,*Linklist;Linklist create(int z) /生成循环单链表并返回,z为总人数 int i,mm;Linklist H,r,s;H=NULL;prin
25、tf(请按顺序依次为每个人添加密码：);for(i=1;in=i;s-m=mm;printf(%d号的密码%d,i,s-m);if(H=NULL)/从链表的第一个节点插入 H=s;r=H;else/链表的其余节点插入 r-next=s;r=s;/r后移/for结束r-next=H;/*生成循环单链表*/return H;void search(Linklist H,int m0,int z)/用循环链表实现报数问题 int count=1;/count为累计报数人数计数器int num=0;/num为标记出列人数计数器Linklistpre,p; p=H;printf(出列的顺序为:);whi
26、le(numnext;while(countnext=p-next;printf(%d ,p-n);m0=p-m;free(p);p=pre-next;count=1;num+;/while结束void clean()int system(const char *string);int inquiry;printf(请问需要清除上一次操作记录吗（1.清屏/2.不清屏）.?n);scanf(%d,&inquiry);if(inquiry =1)system(cls);void text()int m0,z,i, choose,k=1; /k用来阻止第一次进入程序清屏操作Linklist H; b
27、oolchooseFlag=false;while(1)if(k!=1)clean();k+; while(!chooseFlag)printf( 欢迎进入约瑟夫环问题系统n);printf( * 1.输入约瑟夫环数据 * n);printf( * 2.什么是约瑟夫环 * n);printf( * 3.退出系统 * n);printf(. n);printf(请输入相应的数字进行选择: ); scanf(%d,&choose);for(i=1;i=4;i+)if(choose=i) chooseFlag=true; break;else chooseFlag=false;if(!chooseF
28、lag) printf(Error Input!n); /end while(!chooseFlag)if(choose=1) /if 开始printf(Input how many people in it:);/z为总人数scanf(%d,&z);if(z=30)H=create(z);/函数调用printf(nInput the start code m0=);scanf(%d,&m0);search(H,m0,z);printf(nnn);elseprintf(超过最大输入人数n); break;else if(choose=2)printf(n约瑟夫环问题：设有n个人，其编号分别为1，2，3，n，安装编号顺序顺时针围坐一圈。选定一个正整数m，从第一个人开始顺时针报数，报到m时，则此人出列，然后从他的下一个人从1重新报数，依此类推，直到所有人全部出列为止，求出列的顺
