郑州师范学院软件工程专业数据结构课程设计报告设计题目：班级：组长：姓名（学号）组员：姓名（学号）…指导教师：完成日期：成绩：目录1需求分析 (1)1.1功能分析 (1)1.2设计平台 (1)2概要设计 (2)2.1类LinkList (4)2.2类Joseph (4)2.3类异常处理 (4)3详细设计和实现 (4)3.1创建结点Node (5)3.2创建双向循环链表 (6)3.3从链表中删除结点 (7)4调试与操作说明 (11)4.1调试情况 (11)4.2操作说明 (11)5设计总结 (12)参考文献 (13)附录 (13)1需求分析1.1功能分析本次选做的课程设计是改进约瑟夫(Joseph)环问题。
约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。
此问题仅使用单循环链表就可以解决此问题。
而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。
在建立双向循环链表时，因为约瑟夫环的大小由输入决定。
为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。
进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。
然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。
1、本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。
程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。
可设n ≤30。
此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。
2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。
3、程序执行的命令包括：1）构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；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.2设计平台Windows2000以上操作系统；Microsoft Visual C++ 6.02概要设计已知n个人（以编号1，2，3...n分别表示）围成一圈。
从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到一圈的人全部出列。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。
这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。
p->link=head。
解决问题的核心步骤：首先建立一个具有n个链结点，无头结点的循环链表。
然后确定第1个报数人的位置。
最后不断地从链表中删除链结点，直到链表为空。
改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。
本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist, Joseph。
为实现上述程序功能，应以单向循环链表表示约瑟夫环。
为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。
1）、单向循环链表的抽象数据类型定义为：ADT List{数据对象：D={ai｜ai∈Elemset,i=1,2,…,n,n≥0}数据关系：R1={＜a(i-1),ai＞｜a(i-1),ai∈D,i=2,…n}基本操作：InitList(&L)操作结果：构造一个空的链表L。
DestroyList(&L)初始条件：线性表L已存在。
操作结果：销毁线性表L。
ListLength(L)初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)。
操作结果：用e返回L中第i个数据元素的值。
ListInsert(&L,I,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
ListTraverse(L,visit())初始条件：线性表L已存在。
操作结果：依次对L的每个数据元素调用函数visit()。
一旦visit()失败，则操作失败。
}ADT List2)约瑟夫环的抽象数据类型定义为：ADT Set{数据对象：D={ai｜ai为用户输入的数字密码，i=1,2,…,n,1≤n≤7}数据关系：{}基本操作：CreatSet(&L，s)初始条件：L为单向循环链表。
操作结果：对链表中的数据域进行赋值。
DeleteSet(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
PrintSet(L)初始条件：链表L已存在。
操作结果：按输出次序显示每个人的密码。
}ADT Set3)本程序包含四个模块：1、主程序模块：V oid main(){初始化；Do{接受命令；处理命令；} while (“命令”=”退出”)；}2、约瑟夫环单元模块——实现约瑟夫环的抽象数据类型；3、单向循环链表单元模块——实现单向循环链表的抽象数据类型；4、结点结构单元模块——定义单向循环链表的结点结构。
各模块之间的调用关系如下：结点结构单元模块↓单向循环链表单元模块↓约瑟夫环单元模块↓主程序模块2.1类LinkList主要功能是创建结点，每个结点数值域包括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()函数，由它来实现获得最后的胜利者。
并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。
主要功能实现的程序流程图及核心代码。
算法流程图：点。
所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。
设头指针为front，front始终指向头结点，并定义指针current记录当前的结点。
并根据具体情况移动（顺逆时针）。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。
程序结束后再输出依次退出的人的编号顺序。
由于只记录各个结点的data值就可以。
最后通过函数调用来输出顺序。
要解决约瑟夫环问题，首先一点就是必须有一个环，所以第一步我们必须建立一个双向循环链表。
而建立一个双向循环链表必须有一个空的双向循环链表，然后运用尾插法建立一个双向循环链表，这样约瑟夫环就创建出来了，接下来就是处理约瑟夫环问题。
3.3从链表中删除结点在双向循环链表中，一个结点的前驱结点地址保存在该结点的lLink域中，这样可以方便地实现在一个指定结点之前插入一个新结点的操作，也可以方便地删除某个指定结点。
函数通过代码：q->llink->rlink=q->rlink;q->rlink->llink=q->llink;delete q;来删除当前的那个结点q，通过循环来一次次删除当前的结点，直到链表中剩下最后一个结点。
具体程序如下：#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct node //定义单循环链表中节点的结构{int num;//序列号即个人的编号int cipher;//个人所持有的密码struct node *next;}linklist;class YSFH{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("%d\n",p->cipher);r=p;p->next=p;for(int k=2;k<=n;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("%d\n",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指向当前报数的人printf("出列的序号依次为:");//在head中的第一个结点起循环记数找第m个结点while(q!=p){k=k+1;//报一次数if(k%m==0)//所报数等于报数上限值时{printf("%d ",p->num);//输出该结点的num值m=p->cipher;//把该结点的cipher(密码)值赋给mq->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("%d\n",m);Y.head=Y.Select1(m);printf("%d\n",Y.head->num);}4调试与操作说明4.1调试情况这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。