数据结构课程设计(管道铺设施工的最佳选择)

1、管道铺设施工的最佳选择一、问题描述题目内容：在意联通网表示的村庄之间管道的连接，设计一个 将所有村庄连接起来的管道构成的最小生成树。基本要求：实现村庄之间管道总长最短。测试数据：二、需求分析此程序无需输入数据，直接从文件序所需要的数据，以此数据 构建联通网，并输出由此联通网生成的最小树，即为管道铺设施工 的最佳选择。三、概要设计抽象数据类型：图的邻接矩阵存储表示：const max_vertex_num=30; /最大顶点个数typ edef struct arccell double adj;/对无权图，用1, 0表示相邻否，对带权图，则为权 bool kind;/为1表示可供选择，否则不行

2、arccell, adj matrix max _vertex_nu m max_ver tex_num; t ypedef str uct char vcxsmax _vertex_nu m;/描述定点的数组adjmatrix arcs;in t vexnum, arcnum;/图的当前顶点数和边数 mgra ph;主程序模块：v oidmain () 定义联通网；读入数据初始化联通网；处理数据并输岀结果；1、图的邻接矩阵const m ax_vertex_num=30; /最大顶点个数 typed ef struct arccelldouble adj;/对无权图，用1, 0表示相邻否，对

3、带权图,则为权值 bool k ind;/为1表示可供选择，否则不行arccel 1, adjmatri x max_vert ex_num ma x_vertex_n um; typede f structchar vex s max_vert ex_num ; / 描述定点的数组adjma trix arcs;int vex num, arcnum ;/图的当前顶点数和边数mgraph;2、构建图的邻接矩阵d ouble max_num=1000;v oid create mgraph (mgr/采用邻接矩阵存储表示，构造无向图g ifstre am ini ("vex. txt

4、")； 读取顶点的信息 ifstream in2(z，edge. txt") ;/ 读取边的信息 int line=0;/用作顶点和边的数目的计数器 string s 1, s2;for (i nt i二1 ;get 1 ine(ini, s 1) ; i+, 1 in e+) istri ngstream i ssl (si);is sl>>g. vexs i;g. vex num二1 ine; 1 ine二0;for .vexnum; +i)for (in g vexnum;+j) if(i!=j) g. arcs i j. adj =max_num ;g.

5、 arcsij. kind 二0;elseg . arcsi j adj = 0;g. arcsijkind =1;char v 1, v2;double weight;f or (int k=l ;getline(i n2, s2) ;k+, line+) i stringstre am iss2(s2 );iss2>>vl >>v2>>weig ht;g. arcs vl, a' +1 v2-' a' +1 adj = weig ht;g. arcs v2-' a' +1 vl，a' +1. adj = w

6、eig ht; g. arcn um二line;co初始化的邻接矩阵：n ；f or (i=l; i ; +i)cou ('');cout' -1);cout dl ;for (i=xnum; +i) /输出邻接矩阵r (i+，a' -1);for (int vexnum; +j) etfill;rcsij adj;3、生成最小数并输出结果void prim(mgraph g)doubl e mi n;int kl, k2, num =1;g. ar csl 1. a dj = 1;for (int i=l; i ; i+)g. arc si 1. kind 二

7、 1;wh i le(num !=g. vexnum) min=max_nu m;for (int i=l; i exnum; i+)/找出符合条件的权重最小的边fo r (int j=l;m;j+)if(m in>g. arcsij. adj g. arcsij. kind =arcsii.adj! = 1 | g.arcsjj adj!二1 ) min=g a rcsi j adj ;kl=i;k2=j;g. arc skl k2. adj 二-g. a rcskl k2 . adj;/ 将找到的边的权重设 为其负值g. ar cskl k2. kind = g. arcsk2 k

8、1. kind 二0;/ 将该条边设置为不可选fo r (int j=l;m;j+)if(j != k2)g. arcsjkl .kind二1 ;/把矩阵中kl列代表的边(出该条边意外)设为可选g. a rcskl kl . adj=l; /这一步是为了接下来能够方便找出符合要求 的权重最小的边num+;co = = = = = =过算法处理后的邻接矩阵：n for g. vexnum; +i) ')；har (i+，a' -1);for (i二l;um; +i)输出处理后的邻接矩阵 ar (i+，a' t );for (int vexnum; +j) setfill

9、; arcsij. adj;coutco (普里姆算法)：n； n ;for (i二xnum; +i)for (int j exnum; +j ) if(g. arcs ji adj har (i+，a' -char (j+' a' ndl;4、主函数void main()mgrap h g;crc atcmgraph(g); prim (g);5、图的相关数据cdgc. tx t :a b 32. 8a c 44. 6 ah 12. 1 a t 12.8 b c 5.9 c d 21.3 c e 41. 1 cg 56.4 d e67. 3 d f 98.7 e f 85. 6 e g 10. 5 f i 79.2 g h52. 5 h i & 7 vex.txt：abcdefghi五、调试分析该程序通过普里姆算法实现，主要由两个部分组成，一个 是读入图的数据构建邻接矩阵，一个是通过邻接矩阵生成图的 最小树。在生成最小树是需要特别注意选取权重最小的边，包 括正确的选取范围和对已选的边予以标记。六、用户手册按照已有规则在指定的txt文件输入相关的信息即可