数据结构课设计

数据结构课设计《数据结构》课程设计班级：091001姓名：王安心学号：091001112指导教师：史延新完成日期：2021年6月30日题目一：Joseph环（P79）问题描述：编号为1,2,3，...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据：m的初值为20；n=7,7个人的密码依次为：3,1,7,2,4,8,4，首先m值为6（正确的出列顺序为6,1，4,7，2,3,5)一．需求分析1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。3.程序执行的命令包括：1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束4.测试数据(1)m=20,n=7,7个人的密码依次为3，1，7，2，4，8，4(2)m=20,n=1(3)m=20,n=0前面一组为常规数据，后面两组为边缘数据二、概要设计为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：ADTLinkList{数据对象：D={ai|ai∈termset,i=1,2,……n,n=0}，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={|ai-1,ai∈D,i=2,……n}基本操作：LinkListEvaluList(intn);//对单向循环链表进行尾插入赋值intsize(LinkListL);//求链表的节点个数StatusScanList(LinkListL);//遍历单向循环链表StatusJoseph(LinkList&L,intm);//约瑟夫环的实现}此抽象数据类型中的一些常量如下：#defineTRUE1#defineFALSE0#defineOK1typedefintStatus;typedefdoubleElemType;单向循环链表中节点的定义如下所示：typedefstructLNode{intnumber;intdata;structLNode*next;}LNode,*LinkList;三、详细设计#includeusingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1typedefintStatus;typedefdoubleElemType;//-----------------------------------//定义单向循环链表typedefstructLNode{intnumber;intdata;structLNode*next;}LNode,*LinkList;//-----------------------------------LinkListEvaluList(intn);//对单向循环链表进行尾插入赋值intsize(LinkListL);//求链表的节点个数StatusScanList(LinkListL);//遍历单向循环链表StatusJoseph(LinkList&L,intm);//约瑟夫环的实现//-------------------------------------------------voidmain(){intm,n;coutcinmn;coutLinkListL=EvaluList(n);coutScanList(L);coutJoseph(L,m);}//---------对单向循环链表进行尾插入赋值----------------LinkListEvaluList(intn){if(n==0)returnNULL;intkey;coutcinkey;LinkListL=newLNode;L-data=key;L-number=1;L-next=L;for(inti=2;i{LinkListp=newLNode;intkey;coutcinkey;p-data=key;p-number=i;p-next=L-next;L-next=p;L=L-next;}coutL=L-next;returnL;}//---------------求链表的节点个数-------------------intsize(LinkListL){if(L==NULL)return0;inti=1;LinkListp=L-next;while(p!=L){i++;p=p-next;}returni;}//---------------遍历单向循环链表--------------------StatusScanList(LinkListL){LinkListp=L;if(p==NULL){coutreturnFALSE;}coutcoutp=p-next;while(p!=L){coutcoutp=p-next;}coutreturnTRUE;}//----------------约瑟夫环的实现-----------------------StatusJoseph(LinkList&L,intm){if(L==NULL){coutreturnFALSE;}LinkListp=L;while(p-next!=L)p=p-next;for(intn=size(L);n0;n--){coutfor(inti=1;ip=p-next;coutnext-numbernext-data;LinkListq=p-next;p-next=q-next;free(q);}returnOK;}四、调试分析1.当执行输入人数时，输入0程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理2.在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号3.在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点4.程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函数5.考虑到时间问题，密码采用对剩余节点取余来减少遍历次数6.当程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次指向时应该让变化的指针指向尾节点，这样可以减少当密码为1时程序的设计量五、测试结果（第一组为常规数据，二、三两组为边缘数据）题目二:图遍历演示(P150)问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。基本要求：以邻接多重表为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。测试数据：教科书图7.33。忽略里程，起点为北京。一．需求分析很多问题都是建立在图的遍历的基础上实现的，所以必须有一个程序能够实现将图进行广度和深度遍历，必须对图的所有节点进行访问。以无向图为例，以无向图的邻接表和邻接矩阵为存储结构，分别实现对图进行广度和深度遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应的生成树的边集。二、源程序图的邻接矩阵表示：#include#include#defineMAX30#defineN30#defineM10#defineNULL0typedefstructebox{intivex,jvex;//该边依附两个顶点的位置structebox*ilink,*jlink;//分别指向依附这两个顶点的下一条边}ebox,*pebox;typedefstructvexbox{char*data;peboxfirstedge;//指向第一条依附该顶点的边}vexbox,*pvexbox;typedefstructamlgraph//邻接多重表{vexboxadjmulist[MAX];}amlgraph,pamlgraph;typedefstructQNode//链式队列{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;LinkQueueInitQueue()//构造一个空队列Q{LinkQueueQ;Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front-next=NULL;returnQ;}intDeQueue(LinkQueue*Q)//队列不为空时，删除队头元素{QueuePtrp;inte;p=Q-front-next;e=p-data;Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;free(p);returne;}voidEnQueue(LinkQueue*Q,inte)//插入e为新的队尾元素{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;}intQueueEmpty(LinkQueueQ)//判定队列是否为空{if(Q.front==Q.rear)return1;elsereturn0;}intvisited[MAX]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};voidinitgraph(amlgraph&G,intn)//？{for(inti=0;iG.adjmulist[i].firstedge=NULL;}voidSCANF(charname[N][M],intn,amlgraph&G){inti;printf(请输入结点名称：\n);for(i=0;i{scanf(%s,name[i]);G.adjmulist[i].data=name[i];}}voidCreateGraph(intn,amlgraph&G)//构造邻接多重表{peboxp1,p2;inti,j,k,m;intmark;initgraph(G,n);printf(请输入边的数量:);scanf(%d,&m);for(k=0;k{printf(请输入第%d条边的两个顶点:,k+1);scanf(%d%d,&i,&j);p1=(pebox)malloc(sizeof(ebox));p1-ivex=i;p1-jvex=j;p1-ilink=NULL;p1-jlink=NULL;p2=G.adjmulist[i].firstedge;if(p2==NULL)G.adjmulist[i].firstedge=p1;else{mark=0;while(mark==0){if(p2-ivex==i&&p2-ilink==NULL)mark=1;elseif(p2-jve