计本3班数据结构课程设计报告《图的遍历和生成树求解实现》.docx

《计本3班数据结构课程设计报告《图的遍历和生成树求解实现》.docx》由会员分享，可在线阅读，更多相关《计本3班数据结构课程设计报告《图的遍历和生成树求解实现》.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计本3班数据结构课程设计报告图的遍历和生成树求解实现文档视界计本3班数据构造课程设计报告（图的遍历和生成树求解实现）计本3班数据构造课程设计报告（图的遍历和生成树求解实现）目录一.问题描绘：21.图的遍历和生成树求解实现22.基本功能23.输入输出2二、概要设计21.设计思路：22.数据构造设计：33.软件构造设计：4三、具体设计41.定义程序中所有用到的数据及其数据构造，及其基本操作的实现；4邻接矩阵定义:52主函数和其他函数的伪码算法；5主函数：53.主要函数的程序流程图；151.实际完成的情况讲明；182.程序的性能分析，包括时空分析；183.上机经过中出现的问题及其解决方案；184.程

2、序中能够改良的地方讲明；18五、测试结果19六、用户手册22七、体会与自己评价22源代码：22一.问题描绘：1.图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据构造。在线性表中，数据元素之间仅有线性关系，每个数据元素只要一个直接前驱和一个直接后继；在树形构造中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素先任意创立一个图；2图的DFS,BFS的递归和非递归算法的实现3最小生成树要求用邻接矩阵、邻接表等多种构造存储实现3.输入输出输入数据类型为整型和字符型，输出为整型和字符二、概要设计1.设计思路：a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*

3、n的矩阵，其中元素全是无穷大d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的经过。e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索经过中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。2.数据构造设计：ADTQueue数据对象：D=ai|aiElemSet,i=1,2,3，n,n0数据关系：R1=i-1,aiD,i=1,2,3,，n基本操作：InitQueue(&Q操作结果：构造一个空队列Q。QueueE

4、mpty(Q初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。EnQueue(&Q,e初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,e初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。ADTQueueADTGraph数据对象V：V是具有一样特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且P表示从v到w的弧，谓词P的意义或信息基本操作P：CreatGraph(&G,V,VR。初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。BFSTraverse(G,visit(。

5、初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历经过中对每个顶点调用函数Visit一次且仅一次。一旦visit。初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历经过中对每个顶点调用函数Visit一次且仅一次。一旦visit初始条件：图G存在，存在图的深度优先遍历算法。操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。ADTGraph。3.软件构造设计：三、具体设计1.定义程序中所有用到的数据及其数据构造，及其基本操作的实现；邻接矩阵定义:typedefstructArcCellVRTypeadj。/VRType是

6、顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型InfoType*info。/该弧相关信息的指针ArcCell,AdjMatrixmaxmax。typedefstructVertexTypevexsmax。/顶点向量AdjMatrixarcs。/邻接矩阵intvexnum,arcnum。/图的当前顶点数和弧数MGraph_L。邻接表的定义:typedefstructArcNode/弧结点intadjvex。/该弧指向的顶点的位置structArcNode*nextarc。/指向下一条弧的指针InfoType*info。/该弧相关信息的指针ArcNode。typedefstru

7、ctVNode/邻接链表顶点头接点VertexTypedata。/顶点信息ArcNode*firstarc。/指向第一条依附该顶点的弧的指针VNode,AdjList。typedefstruct/图的定义AdjListverticesmax。intvexnum,arcnum。/图的当前顶点数和弧数ALGraph。队列定义:typedefstructQNodeQElemTypedata。structQNode*next。QNode,*QueuePtr。typedefstructQueuePtrfront。/队头指针QueuePtrrear。/队尾指针LinkQueue。2主函数和其他函数的伪码算

8、法；主函数：intmain(ints。chary=y。coutcouts。if(s=0+o。if(o=2n=0。l=0。o=0。switch(scase0:cout。ALGraphgra。creatadj(gra,G。break。case1:cout。break。case2:cout。break。case3:cout。cout。coutcout0cout时，最小生成树不存在inti,gmaxmax。for(i=0。i!=G.vexnum。+ifor(intj=0。j!=G.vexnum。+jgi+1j+1=G.arcsij.adj。cout。break。case6:if(n=0cout0cou

9、t，最小生成树不存在。break。case7:cout。break。couty。if(y=nbreak。return0。邻接矩阵存储：intcreatMGraph_L(MGraph_L&G/创立图用邻接矩阵表示charv1,v2。inti,j,w。coutG.vexnumG.arcnum。coutcinG.vexsi。for(i=0。ifor(j=0。jG.arcsij.adj=int_max。G.arcsij.info=NULL。for(intk=0。kcoutv1v2w。/输入一条边依附的两点及权值i=localvex(G,v1。/确定顶点V1和V2在图中的位置j=localvex(G,v

10、2。G.arcsij.adj=w。G.arcsji.adj=w。for(i=0。i!=G.vexnum。+ifor(j=0。j!=G.vexnum。+jif(G.arcsij.adj!=1&G.arcsij.adjn+=1。if(n=1cout/邻接矩阵的输出inti,j。if(n=0for(i=0。i!=G.vexnum。+ifor(j=0。j!=G.vexnum。+jif(G.arcsij.adj=int_maxcoutfor(j=0。j!=G.vexnum。+jif(G.arcsij.adj=int_maxcout/用邻接表存储图inti=0,j=0。ArcNode*arc。/,*tem,*p。for(i=0。i!=G.vexnum。+igra.verticesi.data=G.vexsi。gra.verticesi.firstarc=NULL。