数据结构设计报告

西安工業大學数据结构课程设计报告班级：081001姓名：巩雪学号：08100124指导教师：史延新完成日期：2010-12-24题目1.Joseph环1.问题描述：编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限（开始）值m(m＜n)，从第一个人开始沿顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，然后在从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：建立输入处理输入数据，输入m、n、的初值和每个人的编号，建立单循环链表。输出形式：建立一个输出函数，将正确的序列输出。测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？2需求分析:1．本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）初始密码和每个人的密码为1～20，人数为1～7，先输入初始密码m，再输入人数n，接下来输入n个正整数，数与数之间用逗号隔开，作为这n个人的密码。2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。3．程序执行的命令包括：1)构造单向循环链表；2）提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4．测试数据m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，3，5）。3.概要设计1．单向循环链表的抽象数据类型定义为：ADTList｛数据对象：D=｛ai|ai∈正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛<ai-1，ai>|，ai-1，ai∈D,I=1，2，......，n｝基本操作：InitList(&L)操作结果：构造一个最大长度ms内容为空的有序表L。ClearList(&L)初始条件：线性表L已经存在。操作结果：将L重置为空表。EmptyList(L)初始条件：线性表L已经存在。操作结果：若L为空表返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已经存在。操作结果：返回L中数据元素个数。GetElem(L,pos,&e)初始条件：线性表L已经存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e)初始条件：线性表L已经存在。操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。ListInsert(L,i,e)初始条件：线性表L已经存在。操作结果：在L中的第i个元素的位置之前插入新元素e,L的长度加1。ListDelete(L,pos,e)初始条件：线性表L已经存在，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L)初始条件：线性表L已经存在。操作结果：依次对L的每个数据元素进行访问。}ADTSqList本程序包含以下模块：（1）主程序模块：其中又包括建立线性表和模拟约瑟夫环处理两大过程voidmain(){初始化；输入数据；执行功能；显示结果；}（2）线性表模块：实现线性表的抽象数据类型（3）元素结构单元模块：定义线性表每个元素的结构（2）各功能模块——实现顺序表的各项功能。各模块的调用关系：主程序↓各功能模块4.详细设计（1）定义了一个结构体typedefstructNode{intnum;//表示该元素的编号intcipher;-----//表示该元素的顺序位置structNode*next;}node,*hu;--------//结点类型，指针类型（2）设定了init(intn)函数来模拟所输入的N个数以线性循环单链表的形式进入和输出：init(intn){inti;-----------\设定第i个数intcipher；--------//定义元素的顺序位置huL;------------//定义指向下一个元素的指针节点Lif(n=1)----------//定义循环的输入的条件{scanf(%d,&cipher);H=(hu)malloc(sizeof(node));---------//生成头结点;H-number=1;H-cipher=cipher;H-next=H;for(i=1;in;i++){scanf(%d,&cipher);L=(hu)malloc(sizeof(node));----------//生成副结点;L-number=i+1;L-cipher=cipher;L-next=H-next;H-next=L;H=L;}H=H-next;------------//循环单链表的生成;}elseprintf(TheN'svaluethatyouinputtedisinvalid!);}（3）按照约瑟夫的思想进行程序的循环,使顺序出列并重新排列：Joseph(intm,huh){inti;//---------定义第i个数hul;------//定义副节点指针Ll==h;-------//初始化Li=1;--------//初始化iwhile(i!=m)//-------循环出列的条件{i=i+1;l=h;h=h-next;}printf(%3d,h-number)-------;//输出第i个满足条件的值m=h-cipher;//------给m重新赋值为出列的下一个位置l-next=h-next;free(h);--------/释放h节点h=l-next;if(h!=l)Joseph(m,h);//---------如果h不等于1则继续调用Joseph(m,h)else{printf(%3d,h-number);free(h);----------/释放h节点}}(4)主程序利用循环链表来输入和循环输出并用约瑟夫函数来模拟输出过程main(){intm;---------定义循环的长度intn;---------所输入的数的总个数inti;-----------定义第i个查阅的数clrscr();printf(PleaseinputthestartingvalueofM(theupperlimitworthofM):);------//输入M的上限scanf(%d,&m);---//-输入m的值printf(Pleaseinputtheman'sfigurewhohaveahandin:);scanf(%d,&n);-----//输入总个数nprintf(Pleaseinputthecipherfromnumber1tonumber%d:,n);-------//输入n个数init(n);--------//调用init（n）printf(TheorderofDequeueis:);Joseph(m,H);}5.调试结果6．调试分析：a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：调试时没有运行结果，后来发现没有在主程序里加上getch（）函数，加上后正确。m的初值(上限值)为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，m值为6结果为：6，1，4，7，2，3，5。b．算法的时空分析：在init（）中共循环了n次。在约瑟夫函数中最坏的情况下要n次，所以时间复杂度为0（n）改进方法：我认为要使用双向循环链表可以更好的降低事件复杂度，而循环链表就能很好的节省空间。题目2图遍历的程序设计一．需求分析1.本演示程序以邻接多重表为存储结构，实现连通无向图的深度和广度优先遍历。2．对一个交通网（25个城市）进行，以一个作为起点进行图的两种遍历。即深度优先遍历和广度优先遍历。最后输出每种遍历下的结点访问序列和相应生成树的边集。3.测试数据（附后）。二．概要设计1.抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,wV,v,w表示v和w之间存在路径}基本操作P:CreatGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合.操作结果:按V和VR是定义构造图G.DestroyGraph(&G)初始条件:图G存在操作结果:销毁图GLocateVex(G,u)初始条件:图G存在,u和G中顶点有相同的特征操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回。其他信息。GetVex(G,v)初始条件:图G存在,v是G中顶点操作结果:返回v的值FirstAjvex(G,v)初始条件:图G存在,v是G中顶点操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空。NextAjvex(G,v,w)初始条件:图G存在,v是G中顶点,w是v的邻接顶点操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空。DeleteVexx(&G,v)初始条件:图G存在,v是G中顶点操作结果:删除顶点v已经其相关的弧DFSTraverse(G,visit())初始条件:图G存在,visit的顶点的应用函数操作结果:对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败BFSTraverse(G,visit())初始条件:图G存在,visit的顶点的应用函数操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败}ADTGraph2、设定栈的抽象数据类型：ADTStack{数据对象：D={ai|ai∈CharSet，i=1，2，……，n，n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。Push(&S,e);初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,e);初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。}ADTStack3、设定队列的抽象数据类型：ADTQueue{数据对象:D={ai|ai属于Elemset,i=1,2….,n,n=0}数据关系:R1={ai-1,ai|ai-1,ai属于D,i=1,2,…,n}约定ai为端为队列头,an为队列尾基本操作:InitQueue(&Q)操作结果:构造一个空队列QDestryoQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。EnQueue(&Q,e)初始条件:队列Q已经存在操作结果:插入元素e为Q的新的队尾元素DeQueue(&Q,&E)初始条件:Q为非空队列操作结果:删除Q的队尾元素,并用e返回其值QueueEmpty(Q)初始条件:队列已经存在操作结果:若队列为空,则返回TRUE,否则返回FLASE}ADTQueue三．详细设计1.顶点,边和图类型#defineMAXQUEUE70/*伫列的最大容量*/structnode/*图形顶点结构宣告*/{intvertex;/*顶点资料*/structnode*nextnode;/*指下一顶点的指标*/};typedefstructnode*graph;/*图形的结构新型态*/structnodehead[61];/*图形顶点结构数组*/intvisited[61];/*遍历记录数组*/intqueue[MAXQUEUE];/*伫列的数组宣告*/intfron