《数据结构约瑟夫环课程设计报告》由会员分享,可在线阅读,更多相关《数据结构约瑟夫环课程设计报告(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;