建立n个城市间的最小生成树.docx

建立n个城市间的最小生成树.docx设计要求 -1 -问题重述 -1 -基本要求 -2 -概要设计 -2 - -2 -存储结构的设计本系统 -3 - -3 - -4 - -5 -模块设计 - 6 -1n个城市连接的最小生成树 -6 -2模块作用用途中的顶点表示 -6 - -6 -“”顺序存储结构存放结点信息 -7 -""邻接矩阵存储结构存放边的信息 -7 - -8 - -9 - -9 - -10 - -10 - -10 - 一10 -12 - -12 -测试结果及分析 -14 -测试结果 -14 -2结果分析 -16 -3错误分析 -16 -源程序 -17 -1设计要求1问题重述选择6-10个城市模拟在城市之间建立通信网络,只需要架设通信路线就可以,以最低的经济花费建设通信网,即用Prim算法或Kreskas算法生成一个网的最小生成树,并计算得到的最小生成树的代价。♦城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本上的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括那些城市间的道路,并显示得到的最小生成树的代价。♦表示城市间距离网的邻接矩阵♦最小生成树屮包括的边及其权值,并显示得到的最小生成树的代价。2概要设计为了实现以上功能,可以从以下主界面构造、存储结构采用、系统功能设置等三个方面进行分析设计。将图的结点信息存放在一个顺序表小,图的边信息存储在一个二维数组edge[MaxVertices][MaxVertices]中,这样就实现了用邻接矩阵存放城市间的距离网。在Mini算法的函数用两个参数,一个是图G为邻接矩阵存储结构的图;,以链接系统的各项子功能运行界而如图1所示c\*H:\kechengsheji2\Debug\ MMMMMXXXXXXXMMMMM欢迎来到城市最小生成树系统01234cDEF5¥吉点集2合为汕B CDE FG权值集2合为:3560100001000010000100003501000065401000010000601000005510000100004510000655505030251000040100005007010000100001000010000307001000010000100004525**********晴输入第一个城市:2 存储结构的设计本系统采用图结构类型,存储抽象n个城市模拟在城市Z间建立通信网络,其中各城市用邻接矩阵类型存储。,实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内,这样,线性表中逻辑上相邻的数据元素在物理存储地址上也相邻,数据元素间的逻辑上的前驱,后继逻辑关系就表现在数据元索的存储单元的物理前后位置关系上。数组冇静态数组和动态数组两种。静态数组存储空间的申请和释放冇系统自动完成,动态数组存储空间的中请和释放由用户调用系统函数完成。无论是静态数组述是动态数组,其功能都是向系统申请一块地址连续的有限空间,只是申请的方法不同,顺序表一般采用静态数组方法实现数据元素的存储。顺序表定义结构体如下:Typedefstruct{DataTypelist[Maxsize];Intsize;JSeqList;其中,DataType为数组(即数据元索)的数据类型,Maxsize表示数组的最大元素个数,list表示顺序表的数组名,size表示顺序表中当前存储的数据元素个数,它必须满足size<=Maxsize,SeqList是该结构体的名称。,图的信息包括两部分,图屮结点的信息和描述之间关系的边的信息。结点信息的描述问题,是一个简单的表存储结构问题。对于一个有n个节点的图,由于每个结点都可能与英他n・l个结点成为邻接结点,所以边Z间关系的描述问题,实际上是一个n如矩阵的计算机存储表示问题。在图的邻接矩阵存储结构中,节点信息使用一维数组存储,边的邻接矩阵使用二维数组存储,无向图的邻接矩阵一定是对称矩阵。当图屮结点数口较小且边较多时,采用图的邻接矩阵存储结构