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

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

1、精品名师归纳总结课程设计报告课程名称数据结构课题名称图的遍历和生成树求解实现院系信息科学与工程学院专业运算机科学与技术班级 11 计本 3 班王占凤安徽省巢湖学院运算机与信息工程学院学生姓名 李威学联系方号 11011183式指导教师2021 年 6 月 13 日可编辑资料 - - - 欢迎下载精品名师归纳总结目录一. 问题描述： 21. 图的遍历和生成树求解实现 22. 基本功能 23. 输入输出 2二、 概要设计 21. 设计思路： 22. 数据结构设计： 33. 软件结构设计： 4三、 具体设计 41. 定义程序中全部用到的数据及其数据结构，及其基本操作的实现。 4邻接矩阵定义 :52.

2、 主函数和其他函数的伪码算法。 5主函数： 53. 主要函数的程序流程图。 151. 实际完成的情形说明。 182. 程序的性能分析，包括时空分析。 183. 上机过程中显现的问题及其解决方案。184. 程序中可以改进的的方说明。18五、 测试结果 19可编辑资料 - - - 欢迎下载精品名师归纳总结六、 用户手册 22七、体会与自我评判22源代码： 22一. 问题描述：1. 图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和

3、下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结 点）相关。而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。2. 基本功能1) 先任意创建一个图。2) 图的 DFS,BFS的递归和非递归算法的实现3) 最小生成树（两个算法）的实现，求连通重量的实现4) 要求用邻接矩阵、邻接表等多种结构储备实现3. 输入输出输入数据类型为整型和字符型，输出为整型和字符二、 概要设计1. 设计思路 ：a. 图的邻接矩阵储备：依据所建无向图的结点数n, 建立 n*n 的矩阵，其中元素全

4、是无穷大（ int_max ），再将边的信息存到数组中。其中无权图的边用1 表示，无边用 0 表示。有全图的边为权值表示，无边用表示。b. 图的邻接表储备：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行储备。c. 图的广度优先遍历：假设从图中的某个顶点v 动身，在拜访了 v 之后依次拜访 v 的各个未曾拜访过的邻接点，然后再拜访此邻接点的未被拜访的邻接点，并使“先被拜访的顶点的邻接点”先于“后被拜访的顶点的邻接点”被访问，直至图中全部已被拜访的顶点的邻接点都被拜访到。如此时图中仍有未被拜访的，就另选未被拜访的重复以上步骤，是一个非递归过程。可编辑资料 -

5、 - - 欢迎下载精品名师归纳总结d. 图的深度优先遍历：假设从图中某顶点v 动身，依依次拜访 v 的邻接顶点，然后再连续拜访这个邻接点的系一个邻接点，如此重复，直至全部的点都被拜访，这是个递归的过程。e. 图的连通重量：这是对一个非强连通图的遍历，从多个结点动身进行搜寻，而每一次从一个新的起始点动身进行搜寻过程中得到的顶点拜访序列恰为其连通重量的顶点集。本程序利用的图的深度优先遍历算法。2. 数据结构设计：ADT Queue数据对象： D=ai | a i ElemSet,i=1,2,3 ， n,n 0 数据关系： R1=| a i-1 ,a i D,i=1,2,3, ， n 基本操作：In

6、itQueue&Q操作结果：构造一个空队列 Q。QueueEmptyQ初始条件： Q为非空队列。操作结果：如 Q为空队列，就返回真，否就为假。EnQueue&Q,e初始条件： Q为非空队列。操作结果：插入元素 e 为 Q的新的队尾元素。DeQueue&Q,e初始条件： Q为非空队列。操作结果：删除 Q的队头元素，并用 e 返回其值。ADT Queue ADT Graph数据对象 V： V是具有相同特性的数据元素的集合，称为顶点集。数据关系 R： R=VRVR=|v,wV 且 P（ v，w）, 表示从 v 到 w的弧， 谓词 P（ v,w）定义了弧 的意义或信息 基本操作 P： CreatGra

7、ph&G,V,VR。初始条件： V 是图的顶点集， VR是图中弧的集合。操作结果：按 V和 VR的定义构造图 G。BFSTraverseG,visit。初始条件：图 G存在， Visit是定点的应用函数。可编辑资料 - - - 欢迎下载精品名师归纳总结操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数 Visit一次且仅一次。一旦visit（）失败，就操作失败。DFSTraverseG,visit。初始条件：图 G存在， Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶可编辑资料 - - - 欢迎下载精品名师归纳总结点失DFStra_fenG调用函数

8、 Visit一次且仅一次。一旦visit（） 败，就操作失败。可编辑资料 - - - 欢迎下载精品名师归纳总结量。ADT Graph。初始条件：图 G存在，存在图的深度优先遍历算法。操作结果：从多个顶点对图进行深度优先遍历，得到连通分可编辑资料 - - - 欢迎下载精品名师归纳总结3. 软件结构设计：main0creatMGraph_LGcre atadjgra,G1ljjzprintG2adjprintgra,G3BFSTravers egra45DFStragraDFSTraverse_fengra6MiniSpanTree_PRIMg, G.vexnum7MiniSpanTREE_KRU

9、SCALG,gra函数名creatMGraph_LG creatadjgra,GljjzprintGadjprintgra,G BFSTraversegraDFStragraDFSTraverse_fengra MiniSpanTree_PRIMg,G.vexnum MiniSpanTREE_KRUSCALG,gra返回值类型int int void void void int int intvoid三、 具体设计1. 定义程序中全部用到的数据及其数据结构，及其基本操作的实现。可编辑资料 - - - 欢迎下载精品名师归纳总结邻接矩阵定义 : typedef struct ArcCellVRTy

10、pe adj 。/VRType 是顶点关系类型。对无权图，用1 或 0 表示相邻否。对带权图，就为权值类型InfoType *info。/ 该弧相关信息的指针ArcCell,AdjMatrixmaxmax。typedef structVertexType vexsmax。/ 顶点向量AdjMatrix arcs。/ 邻接矩阵int vexnum,arcnum 。/ 图的当前顶点数和弧数MGraph_L。邻接表的定义 :typedef struct ArcNode/弧结点int adjvex。/ 该弧指向的顶点的位置struct ArcNode *nextarc。/ 指向下一条弧的指针InfoT

11、ype *info。/ 该弧相关信息的指针ArcNode。typedef struct VNode/邻接链表顶点头接点VertexType data。/ 顶点信息ArcNode *firstarc。/ 指向第一条依附该顶点的弧的指针VNode,AdjList。typedef struct/图的定义AdjList verticesmax。int vexnum,arcnum 。/ 图的当前顶点数和弧数ALGraph。队列定义 :typedef struct QNodeQElemType data。struct QNode *next。QNode,*QueuePtr 。可编辑资料 - - - 欢迎下

12、载精品名师归纳总结typedef structQueuePtr front。/ 队头指针QueuePtr rear 。/ 队尾指针LinkQueue 。2主函数和其他函数的伪码算法。主函数：int mainint s。char y=y。cout|菜单 |endl。cout|-【0、创建一个无向图 -|endl。cout|-【1、显示该图的邻接矩阵 -|endl。cout|-【2、显示该图的邻接表 -|endl。cout|-【3、广度优先遍历 -|endl。cout|-【4、深度优先遍历 -|endl。cout|-【5、最小生成树MiniSpanTree_PRIM 算法-|endl。cout|-

13、【6、最小生成树MiniSpanTree_KRUSCAL算法-|endl。cout|-【7、连通重量 -|endl。cout| |endl。whiley=ycout 请挑选菜单： s。ifs=0可编辑资料 - - - 欢迎下载精品名师归纳总结+o。ifo=2n=0。l=0 。o=0。switchscase 0:cout创建一个无向图： endl 。MGraph_L G。creatMGraph_LG 。ALGraph gra 。creatadjgra,G。break。case 1:cout邻接矩阵显示如下： endl 。ljjzprintG。break。case 2:cout邻接表显示如下： e

14、ndl 。adjprintgra,G。break。case 3:cout广度优先遍历： 。BFSTraversegra。coutendl。break。case 4:cout 深度优先遍历： 。DFStragra。coutendl。break。case 5:ifn=0cout0cout如该图为非强连通图 含有多个连通重量 时，最小生成树不存在 endl 。break 。elseint i,gmaxmax。fori=0。i.=G.vexnum 。+iforint j=0。j.=G.vexnum 。+j gi+1j+1=G.arcsij.adj。cout 普利姆算法 :endl 。MiniSpanT

15、ree_PRIMg,G.vexnum 。break 。case 6:ifn=0cout0cout该图为非强连通图 含有多个连通重量 ，最小生成树不存在 endl 。break 。elsecout 克鲁斯卡尔算法 :endl 。MiniSpanTREE_KRUSCALG,gra。break。case 7:cout连通重量 :endl 。DFSTraverse_fengra。break。coutendly。ify=n break。return 0。邻接矩阵储备：int creatMGraph_LMGraph_L &G/创建图用邻接矩阵表示char v1,v2。可编辑资料 - - - 欢迎下载精品名

16、师归纳总结int i,j,w。cout 请输入顶点和弧的个数 G.vexnumG.arcnum。cout 输入各个顶点 endl 。fori=0。iG.vexsi。fori=0。iG.vexnum。+iforj=0。jG.vexnum。+jG.arcsij.adj=int_max。G.arcsij.info=NULL。forint k=0。kG.arcnum。+kcout 输入一条边依附的顶点和权 v1v2w。/ 输入一条边依附的两点及权值i=localvexG,v1。/ 确定顶点 V1 和 V2 在图中的位置j=localvexG,v2。G.arcsij.adj=w。G.arcsji.adj

17、=w。fori=0。i.=G.vexnum 。+iforj=0。j.=G.vexnum 。+jifG.arcsij.adj.=1&G.arcsij.adj=1cout这是一个有权图 endl 。else cout这是一个无权图 endl 。cout 图 G邻接矩阵创建胜利！ endl 。return G.vexnum 。邻接矩阵的输出：void ljjzprintMGraph_L G /邻接矩阵的输出可编辑资料 - - - 欢迎下载精品名师归纳总结int i,j。ifn=0fori=0。i.=G.vexnum 。+iforj=0。j.=G.vexnum 。+j可编辑资料 - - - 欢迎下载精

18、品名师归纳总结 。ifG.arcsij.adj=int_maxcout0else coutG.arcsij.adj 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结elsecoutendl 。可编辑资料 - - - 欢迎下载精品名师归纳总结fori=0。i.=G.vexnum 。+iforj=0。j.=G.vexnum 。+j可编辑资料 - - - 欢迎下载精品名师归纳总结 。ifG.arcsij.adj=int_maxcoutelse coutG.arcsij.adj 。可编辑资料 - - - 欢迎下载精品名师归纳总结coutadjvex=j

19、。arc-nextarc=gra.verticesi.firstarc。gra.verticesi.firstarc=arc。可编辑资料 - - - 欢迎下载精品名师归纳总结邻接表输出：gra.vexnum=G.vexnum。gra.arcnum=G.arcnum 。cout 图 G邻接表创建胜利！ endl 。return 1。可编辑资料 - - - 欢迎下载精品名师归纳总结void adjprintALGraph gra,MGraph_L G /邻接表输出int i。fori=0。i.=gra.vexnum 。+iArcNode *p 。couti,G.vexsi。p=gra.vertic

20、esi.firstarc。whilep.=NULLcoutadjvexnextarc 。coutEnd。coutnext=NULL 。return 1。可编辑资料 - - - 欢迎下载精品名师归纳总结Status EnQueueLinkQueue &Q,QElemType e/入队, 插入元素 e 为 Q的新的队尾元素可编辑资料 - - - 欢迎下载精品名师归纳总结出队：QueuePtr p 。p=QueuePtrmallocsizeofQNode。if.preturn 0。/ 储备安排失败p-data=e 。p-next=NULL。Q.rear-next=p。Q.rear=p 。return

21、 1。可编辑资料 - - - 欢迎下载精品名师归纳总结Status DeQueueLinkQueue &Q,QElemType &e/出队，如队列不空，就删除 Q的队头元素，用 e 返回，并返回真，否就假QueuePtr p 。ifQ.front=Q.rearreturn 0。p=Q.front-next。e=p-data 。Q.front-next=p-next。ifQ.rear=pQ.rear=Q.front。freep。return 1。判定队为空：Status QueueEmptyLinkQueue Q/判定队为空可编辑资料 - - - 欢迎下载精品名师归纳总结ifQ.front=Q.

22、rear return 1。return 0。广度优先遍历：void BFSTraverseALGraph graint i,e。LinkQueue q 。fori=0。i.=gra.vexnum 。+ivisitedi=0。InitQueueq。fori=0。i.=gra.vexnum 。+i if.visitedivisitedi=1。cout=0。we=nextadjvexgra,gra.verticese,weif.visitedwevisitedwe=1。coutgra.verticeswe.data。EnQueueq,we。深度优先遍历：int DFSALGraph gra,int

23、 ivisitedi=1。可编辑资料 - - - 欢迎下载精品名师归纳总结int we1 。cout=0。we=nextadjvexgra,gra.verticesi,wewe1=we。 ifvisitedwe=0DFSgra,we 。we=we1。return 1。int DFStraALGraph graint i,jfori=0。i.=gra.vexnum。+ivisitedi=0。forj=0。j.=gra.vexnum。+jifvisitedj=0DFSgra,j。return 0。连通重量：int DFSTraverse_fenALGraph graint i,j。fori=0。i

24、.=gra.vexnum。+ivisitedi=0。forj=0。j.=gra.vexnum。+jifvisitedj=0DFSgra,j。可编辑资料 - - - 欢迎下载精品名师归纳总结coutadjvex=jArc-nextarc=gra.verticesi.firstarcGra.verticesi.firstarc=arcForwe=firstadjvexgra,gra,vert icese;we=0;we=nextadjvexgra,gra.verticese,weNO输入v1,v2,wi=localvexG,v1 i=localvexG,v1 G.arcsij.adj=wG.arc

25、sji.adj=wReturn G.vexnumIf.visitedweYESGra.vexnum=G.vexnum Gra.arcnum=G.arcnumVisitedwe=1; Enqueueq,we终止终止终止图的邻接矩阵储备图的邻接表储备图的广度优先遍历可编辑资料 - - - 欢迎下载精品名师归纳总结开头Int lowcostmax Prevexmax Int I,j,k,minFori=2;i=n;i+Lowcosti=g1i Prevexi=1Lowcost1=0Fori=2;i=n;i+Min=inf K=0Forj=2;j=n;j+Iflowcostjmin& &lowcost

26、j.=0YESMin=lowcostjK=jLowcostk=0Forj=2;j=n;j+NOIfgkj0 为有权图，此时输出的时候用代替10000。n=0 为无权图，此时输出的时候用 0 代替 10000.b. 程序中有的功能对某些图是不适用的，比如无权图没有最小生成树，非强连通图没有最小生成树等。所以在程序中又新增了全局变量l,l0时表示为非强连通图，就在求最小生成树时报错。C. 当程序先创建一个有权图后， n 的值会大于 1，其次次创无权图时也会被程序认为有权图，所以在程序中在定义全局变量o（初值为 0）, 来判定创建了几次图，当其次次创建图，即 o=2 时，全部全局变量在开头全归零。4

27、. 程序中可以改进的的方说明。当建立一个图时先得求其连通重量，从而确定全局变量l 的值，从而才能判定该图是否有最小生成树。可编辑资料 - - - 欢迎下载精品名师归纳总结五、测试结果创建一个无权图：可编辑资料 - - - 欢迎下载精品名师归纳总结创建一个费强连通的有权图：可编辑资料 - - - 欢迎下载精品名师归纳总结创建一个有权连通图：可编辑资料 - - - 欢迎下载精品名师归纳总结六、用户手册a. 先选 0 创建一个图。 b. 挑选 y 连续操作。 c. 依据菜单编码挑选操作。七、体会与自我评判在做这个程序的时候你第一必需知道图的一些概念，图是一种较线性表和树更为复杂的数据结构。在线性表中

28、，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关。而在图形结构 中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。当我们拿到一个图时，我们对该图的遍历就要有一些方法，所以有了深度优先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后依据我们人脑中的方法把它写成电脑算法。对一个图我们仍定义了连通重量，所以将图存到电脑中时，我们对连通分量得有个算法。求图的最小生成树有两种算法，普利姆是从结点动身查找

29、权最小的边，知道全部结点都练通了。而克鲁斯卡尔算法就是从边动身，查找使图连通的权值最小边的方法。算法的实现从人脑到电脑的转变是比较复杂的一件事，要求做到具体到实现该方法的每一个步骤，然后再将每一个步骤通过代码实现。这要求我们要明确各个数据元素和个元素之间的关系，然后才能明确使用算法去调用这些数据。通过本次的课程设计，我对数据结构有了肯定的熟悉，明白了数据结构中数据，数据关系，及对其操作的方法。但同时也发觉在自己有许多的不足，在使用语言和如何精炼语言需要进行更多的训练。源代码：#include 可编辑资料 - - - 欢迎下载精品名师归纳总结#include using namespace st

30、d。#define int_max 10000/ 最大值static int n=0 。/全局变量，判定有权图和无权图static int o=0 。/全局变量，清除 BUGstatic int l=0 。/ 全局变量，清除 BUG #define inf 9999/ 最小值的最大值#define max 20/ 最大顶点个数typedef int VRType,QElemType,Status 。typedef char InfoType,VertexType 。/|邻| 接矩阵 |/-邻接矩阵定义 -typedef struct ArcCellVRType adj。/VRType 是顶点关系类型。对无权图，用1 或 0