图生成树实验报告--上海电机学院

《图生成树实验报告--上海电机学院》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1课程设计内容11.1课程设计目的11.2课程设计耍求11.3课程设计背景12概要设计22.1程序功能模块结构图22.2菜单界面说明22.3读入文件说明22.4输出孩子链表结构说明23详细设计33.1邻接矩阵的定义和孩子链表表示法定义33.1从文件中读入无向图的结点和边的信息并创建无向图43.2输出图的邻接矩阵存储结构73.3深度优先遍历83.4创建树的孩子链表存储结构93.5输出树的孩了链表存储结构104遇到的问题与解决方案12小结13参考文献141课程设计内容1.1课程设计目的课程设计题目

2、：图生成树随机输入一个无向图，通过深度优先遍历或广度优先遍历输出该图的生成树，并将该生成树以二叉链表形式或孩了链表表示法存储。若使用二叉链表存储，则对此存储结构进行遍历，如果使用孩子链表表示法，则输出生成树的孩子链表存储结构。1.2课程设计要求程序要求实现的功能有：（1）输入的顶点与弧的信息通过邻接表或邻接矩阵构建一个无向图；（2）通过图的DFS或BFS过程得到该无向网的一棵生成树。（3）使用孩子链表表示法或二叉链表存储结构存储生成树。（4）对存储树的二义链表进行遍历或者输出生成树的孩子链表存储结

3、构；1.3课程设计背景无向图的生成树是在网络和回路分析中经常遇到的重要问题，功能强大、可靠的网络需要有效地传输流量，提供兀余和故障的快速恢复功能。在第2层网络中，路由协议不可用，牛成树协议通过从软件层面修改网络物理拓扑结构来构建一个无环路逻辑转发拓扑结构，提供了物理线路的兀余连接，消除了网络风暴，从而提高网络的稳定性和减少网络故障的发生率。生成树协议（SpanningTreeProtocol）是在网络有环路时，通过一定的算法将交换机的某些端口进行阻塞，从而使网络形成一个无环路的树状结构。在实践中理

4、解面向对象语言的设计方式。2概要设计2.1程序功能模块结构图2.2菜单界面说明本次课程设计，按照要求，需要的完成的有创建图的存储结构，图生成树，树的存储。为了使菜单更加美化以及程序功能更加完善，木代码增加了输出邻接矩阵功能、输出图生成树的定义、清屏以及退岀程序的功能。2.3读入文件说明为了使程序具有更大的适用件和方便程序调试，本课程设计代码采取从文件屮读入图的顶点和边的信息来创建图的存储结构，为了使生成树的根节点为第一个读入的顶点，在创建树的存储结构中同样使用从同一个文件屮读入各顶点建立定点数组。

5、2.4输出孩子链表结构说明由孩了链表存储结构的输出要清楚地显示图的存储结构则需要将图的孩了链表输出。和图的邻接表结构输出类似，故采用同样的方法输出孩子链表。3详细设计3.1邻接矩阵的定义和孩子链表表示法定义要想创建图的邻接矩阵存储结构和生成树的孩子链表存储结构，必须先进行和关的定义。邻接矩阵和孩了链表表示法定义代码如下：typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[ma

6、xSize];AdjMatrixarcs;intvexnum,arcnum;JAGraph;〃树的孩子链表表示法定义〃权值〃指向该边相关信息的指针〃描述顶点的数组〃邻接矩阵〃图的当前顶点数和边数typedefstructCTNode{intchild;〃结点的编号structCTNode*next;〃指针域，指向下一个孩子结点}*ChildPtr;typedefstruct{chardata;ChildPtrfirstchild;}CTBox;typedefstruct〃结点的信息〃指向孩子链表的

7、首个表结点〃树结构CTBoxnodes[maxSize];〃头结点数组intn;〃树的总结点数和树根}Ctree;3.1从文件中读入无向图的结点和边的信息并创建无向图为了节省调试时间，以及方便调试工作，木代码采用了从文件中读取无向图的顶点和边的信息的方法，采用邻接矩阵存储图的方法创建无向图。无向图结点和边信息g.dat文件如下图3-1所示：图3Tg.dat文件读入文件构建无向图的结果如下图3-2所示：八rir图3-2创建图实现以上操作的实现代码如下：607568114511BCEDCFCFAMAn

8、BBBEEDP：我的文栏2专业课C&C_辭结构数摇结也朗I漳三次设计—Ah.—图生成树（无向图）1・创建图的邻接矩阵存储结构2•输出图的邻接矩阵存储结构3•深度优先遍历斗•创建树的孩子链表存储结构5•输出树的孩子链表存储结构6•生成树的定义了•清屏@•退出程序请输入菜单项：1请输入图中顶点的个数和边数：69请输入图中6个顶点的标志：图中的6个顶点依次为：FCBDAE请输入第1条弧：请输入第2条弧：请输入第3条弧：请输入第坤条弧：请输入第5条弧：请输入第6条弧：请输入第了条弧：