资源描述：
《数据结构约瑟夫环课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、课程设计报告一、需求分析1、本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。3、程序执行的命令包括：1）构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。4、测试数据1
2、）m的初始值为20；2）n=7，7个人的密码依次为：3、1、7、2、4、8、4。3）首先m值为6，正确的出列顺序应为6、1、4、7、2、3、5。二、概要设计为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。1）、单向循环链表的抽象数据类型定义为：ADTList{数据对象：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)操作结果：构造一个空的链
3、表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)初始条件：线性表
4、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}数据关系：{}基本操作：CreatSet(&L，s)初始条件：L为单向循环链表。操作结果：对链表中的
5、数据域进行赋值。DeleteSet(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。PrintSet(L)初始条件：链表L已存在。操作结果：按输出次序显示每个人的密码。}ADTSet3)本程序包含四个模块：1、主程序模块：Voidmain(){初始化；Do{接受命令；处理命令；}while(“命令”=”退出”)；}2、约瑟夫环单元模块——实现约瑟夫环的抽象数据类型；3、单向循环链表单元模块——实现单向循环链表的抽象数据类
6、型；4、结点结构单元模块——定义单向循环链表的结点结构。各模块之间的调用关系如下：结点结构单元模块↓单向循环链表单元模块↓约瑟夫环单元模块↓主程序模块三、详细设计1、元素类型、结点类型和指针类型TypedefcharElemType;//元素类型TypedefstructNodeType{ElemTypedata;ElemType*next;}ElemType,*LinkTypet;//结点类型，指针类型voidFreeNode(LinkType&p){//释放p所指结点}LinkTypeCopy(LinkTypep)
7、{//复制生成和指针p所指结点有同值元素的新结点并返回，//若分配空间失败，则返回空指针。新结点的指针域为NULLS=(LinkType)malloc(sizeof(NodeType));If(!s)returnNULL;s->data=p->data;s->next=NULL;returns;}ElemTypeElem(LinkTypep){//若指针p!=NULL,则返回p所指结点的数据元素}LinkTypeSuccNode(LinkTypep){//若指针p!=NULL,则返回指向p所指结点的后继元素的指针，//
8、否则返回NULL}2、根据单向循环链表的基本操作特点，有序表采用有序链表实现。链表设头、尾两个指针和表长数据域，但此链表中并未设头结点。Typedefstruct{LinkTypehead,tail;//分别指向线性链表的头结点和尾结点Intsize;//指向链表的当前长度}creatList_L//有序链表类型有序链表的基本操作
