《数据结构约瑟夫环课程设计报告》由会员分享，可在线阅读，更多相关《数据结构约瑟夫环课程设计报告（9页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告一、 需求分析1、 本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。3、 程序执行的命令包括：1） 构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。4、测试数据 1）m的初始值为20； 2）n=7，7个人的密码依次为：3、1、7、
2、2、4、8、4。 3）首先m值为6，正确的出列顺序应为6、1、4、7、2、3、5。二、概要设计为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。1）、单向循环链表的抽象数据类型定义为：ADT List数据对象：D=aiaiElemset,i=1,2,n,n0数据关系：R1=a(i-1),aia(i-1),aiD,i=2,n基本操作： InitList(&L) 操作结果：构造一个空的链表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返
3、回L中数据元素个数。 GetElem(L,i,&e) 初始条件：线性表L已存在，1iListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 ListInsert(&L,I,e) 初始条件：线性表L已存在，1iListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelete(&L,i,&e) 初始条件：线性表L已存在且非空，1iListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit() 初始条件：线性表L已存在。 操作结果：依次对L的每个数据
4、元素调用函数visit()。一旦visit()失败，则操作失败。 ADT List2)约瑟夫环的抽象数据类型定义为：ADT Set 数据对象：D=aiai为用户输入的数字密码，i=1,2,n,1n7 数据关系： 基本操作： CreatSet(&L，s) 初始条件：L为单向循环链表。 操作结果：对链表中的数据域进行赋值。 DeleteSet(&L,i,&e) 初始条件：线性表L已存在且非空，1iListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 PrintSet(L) 初始条件：链表L已存在。 操作结果：按输出次序显示每个人的密码。 ADT Set3)
5、本程序包含四个模块： 1、主程序模块： Void main() 初始化； Do接受命令；处理命令； while (“命令”=”退出”)； 2、约瑟夫环单元模块实现约瑟夫环的抽象数据类型； 3、单向循环链表单元模块实现单向循环链表的抽象数据类型； 4、结点结构单元模块定义单向循环链表的结点结构。 各模块之间的调用关系如下： 结点结构单元模块 单向循环链表单元模块 约瑟夫环单元模块 主程序模块三、 详细设计1、 元素类型、结点类型和指针类型Typedef char ElemType; /元素类型Typedef struct NodeType ElemType data; ElemType *nex
6、t; ElemType, *LinkTypet; /结点类型，指针类型 void FreeNode(LinkType &p)/释放p所指结点LinkType Copy(LinkType p)/复制生成和指针p所指结点有同值元素的新结点并返回，/若分配空间失败，则返回空指针。新结点的指针域为NULLS=(LinkType)malloc(sizeof(Node Type);If(!s) return NULL;s-data=p-data;s-next=NULL;return s;ElemType Elem(LinkType p) /若指针p!=NULL,则返回p所指结点的数据元素LinkType
7、SuccNode(LinkType p ) /若指针p!=NULL,则返回指向p所指结点的后继元素的指针， /否则返回NULL2、根据单向循环链表的基本操作特点，有序表采用有序链表实现。链表设头、尾两个指针和表长数据域，但此链表中并未设头结点。Typedef structLinkType head,tail; /分别指向线性链表的头结点和尾结点Int size; /指向链表的当前长度 creatList_L /有序链表类型 有序链表的基本操作设置如下： Int ListLength(creatList_L); /返回链表的长度 LinkType GetElem(creatList_L) /若L
8、存在且0pnum = 1;printf(请输入第1个人的密码:);scanf(%d,&tail-password);for(i = 2;i num = i;printf(请输入第%d个人的密码:,i);scanf(%d,&p-password);tail-next = p;tail = p;tail-next = head; return tail;3、约瑟夫环利用单向循环链表类型来实现； typedef struct LNode； 其中部分代码如下：void ListDelete_L(LinkList L,int key,int n)int i; LinkList q; while( n0)
9、 for (i = 1; i next; q =L-next;printf(第%d个人出列,密码%dn,q-num,q-password);L-next =q-next;key = q-password; free(q); n-; 4、主函数 void main()LinkList s;int n,m;printf(请输入总人数N和上限数M:);scanf(%d%d,&n,&m);printf(请输入%d个人的密码n,n);s=creatList_L(n);printf(序号 密码n);ListDelete_L(s,m,n);5、函数的调用关系图反映了演示程序的层次结构：四、调试分析 1、由于
10、刚开始对单项循环链表是用的不熟练，在程序中的一句语句for (j = 1; j 1。在对程序改正后，这一现象也就不再存在。 2、本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较顺利。 3、本实习作业采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素结点、单项循环链表、约瑟夫环和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。五、用户手册1、本程序的运算环境为Windows操作系统，执行文件为：CLD.exe。2、进入演示程序后即显示文本方式的用户界面： 3、接受其他命令后即执行相应运算和显示相应结果。 六、测试结果七、附录/*LinkList是指向这个结构的一个指针，也可以去定义变量，定义出来的是指向这个结构的指针变量#include#includetypedef struct LNode / 建立一个结构体 typedef 类型定义int password; / 密码int num; /编号 数据域struct LNode *next; /指针域LNode,*LinkList; /线性表的单链表存储结构LinkList creatList_L(int n) int i ; LinkList tail,head;
