资源描述：
《学位论文-—数据结构约瑟夫环.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构课程设计报告设计题目：班级：组长：姓名（学号）组员：姓名（学号）…指导教师：完成日期：成绩：目录1需求分析31.1功能分析31.2设计平台32概要设计32.1类LinkList32.2类Joseph42.3类异常处理43详细设计和实现43.1创建结点Node43.2创建双向循环链表53.3从链表中删除结点64调试与操作说明104.1调试情况104.2操作说明105设计总结11参考文献12附录121需求分析1.1功能分析本次选做的课程设计是改进约瑟夫(Joseph)环问题。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问
2、题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。1、本演示程序中，利用单向循环链表
3、存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。3、程序执行的命令包括：1）构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。4、测试数据1）m的初始值为20；2）n=7，7个人的密码依次为：3、1、7、2、4、8、4。3）首先m
4、值为6，正确的出列顺序应为6、1、4、7、2、3、5。1.2设计平台Windows2000以上操作系统；MicrosoftVisualC++6.02概要设计已知n个人（以编号1，2，3...n分别表示）围成一圈。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head。解决问题的核心
5、步骤：首先建立一个具有n个链结点，无头结点的循环链表。然后确定第1个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist,Joseph。为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。1）、单向循环链表的抽象数据类型定义为：ADTList{数据对象：D={ai｜ai∈Elemset,
6、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≤ListLeng
7、th(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()失败，则操作失败。}ADTList2)约瑟夫环的抽象数据类型定义为：ADTSet{数据对象：D={ai｜ai为用户输入的数字密码，i=1,2,…,n,1≤n≤7
8、}数据关系：{}基本操作：CreatSet(&L，s)初始条件：L为单向循环链表。操作结果：对链表中的数据域
