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

1、.管道铺设施工的最佳选择一、问题描述题目内容：在意联通网表示的村庄之间管道的连接，设计一个将所有村庄连接起来的管道构成的最小生成树。基本要求：实现村庄之间管道总长最短。测试数据：村庄村庄距离村庄村庄距离AB32.8DE67.3AC44.6DF98.7AH12.1EF85.6AI18.2EG10.5BC5.9FI79.2CD21.3GH52.5CD41.1HI8.7CG56.4二、需求分析此程序无需输入数据，直接从文件序所需要的数据，以此数据构建联通网，并输出由此联通网生成的最小树，即为管道铺设施工的最佳选择。三、概要设计抽象数据类型：图的邻接矩阵存储表示：const MAX_VERTEX_NU

2、M=30; /最大顶点个数typedef struct ArcCell double adj; /对无权图,用1,0表示相邻否,对带权图，则为权值 bool kind; / 为1表示可供选择，否则不行ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; / 描述定点的数组 AdjMatrix arcs; int vexnum,arcnum; / 图的当前顶点数和边数MGraph;主程序模块：void main()定义联通网；读入数据初始化联通网；处理数据并输出结果；四、详细设计

3、1、图的邻接矩阵const MAX_VERTEX_NUM=30; /最大顶点个数typedef struct ArcCell double adj; /对无权图,用1,0表示相邻否,对带权图，则为权值 bool kind; / 为1表示可供选择，否则不行ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; / 描述定点的数组 AdjMatrix arcs; int vexnum,arcnum; / 图的当前顶点数和边数MGraph;2、构建图的邻接矩阵double max_nu

4、m=1000;void CreateMGraph(MGraph &G) / 采用邻接矩阵存储表示，构造无向图G ifstream in1("vex.txt");/ 读取顶点的信息 ifstream in2("edge.txt");/ 读取边的信息 int line=0; / 用作顶点和边的数目的计数器 string s1,s2;for(int i=1;getline(in1,s1);i+,line+)istringstream iss1(s1);iss1>>G.vexsi;G.vexnum=line;line=0;for (i=1;

5、i<=G.vexnum; +i)for (int j=1; j<=G.vexnum; +j)if(i!=j)G.arcsij.adj = max_num;G.arcsij.kind = 0;elseG.arcsij.adj = 0;G.arcsij.kind = 1;char v1,v2;double weight;for(int k=1;getline(in2,s2);k+,line+)istringstream iss2(s2);iss2>>v1>>v2>>weight;G.arcsv1-'A'+1v2-'A'

6、+1.adj = weight;G.arcsv2-'A'+1v1-'A'+1.adj = weight;G.arcnum=line;cout<<"初始化的邻接矩阵：n "for (i=1; i<=G.vexnum; +i)cout<<setfill(' ');cout<<setw(8)<<char(i+'A'-1);cout<<endl<<endl;for (i=1; i<=G.vexnum; +i) / 输出邻接矩阵cout&

7、lt;<char(i+'A'-1);for (int j=1; j<=G.vexnum; +j)cout<<setfill(' ');cout<<setw(8)<<G.arcsij.adj;cout<<endl;3、生成最小数并输出结果void prim(MGraph G) double min; int k1,k2,num=1; G.arcs11.adj = 1;for(int i=1;i<=G.vexnum;i+)G.arcsi1.kind = 1;while(num != G.vexnum)

8、min=max_num;for(int i=1;i<=G.vexnum;i+) /找出符合条件的权重最小的边for(int j=1;j<=G.vexnum;j+)if(min>G.arcsij.adj && i!=j && G.arcsij.kind = 1 && (G.arcsii.adj!=1 | G.arcsjj.adj!=1)min=G.arcsij.adj;k1=i;k2=j;G.arcsk1k2.adj = -G.arcsk1k2.adj; / 将找到的边的权重设为其负值G.arcsk1k2.kind = G.arc

9、sk2k1.kind = 0; / 将该条边设置为不可选for(int j=1;j<=G.vexnum;j+)if(j != k2)G.arcsjk1.kind = 1; / 把矩阵中 k1 列代表的边（出该条边意外）设为可选G.arcsk1k1.adj=1; / 这一步是为了接下来能够方便找出符合要求的权重最小的边num+;cout<<"=n"cout<<"通过算法处理后的邻接矩阵：n "for (i=1; i<=G.vexnum; +i)cout<<setfill(' ');cout&l

10、t;<setw(8)<<char(i+'A'-1);cout<<endl<<endl;for (i=1; i<=G.vexnum; +i)/ 输出处理后的邻接矩阵cout<<char(i+'A'-1);for (int j=1; j<=G.vexnum; +j)cout<<setfill(' ');cout<<setw(8)<<G.arcsij.adj;cout<<endl;cout<<"最小生成树（普里姆算法）

11、：n"cout<<"顶点t"<<"顶点t"<<"边的权重n"for (i=1; i<=G.vexnum; +i)for (int j=1; j<=G.vexnum; +j)if(G.arcsji.adj<0)cout<<char(i+'A'-1)<<"t"<<char(j+'A'-1)<<"t"<<G.arcsij.adj<<en

12、dl;4、主函数void main() MGraph G; CreateMGraph(G); prim(G);5、图的相关数据edge.txt ：A B 32.8A C 44.6A H 12.1A I 12.8B C 5.9C D 21.3C E 41.1C G 56.4D E 67.3D F 98.7E F 85.6E G 10.5F I 79.2G H 52.5H I 8.7vex.txt ：ABCDEFGHI五、调试分析该程序通过普里姆算法实现，主要由两个部分组成，一个是读入图的数据构建邻接矩阵，一个是通过邻接矩阵生成图的最小树。在生成最小树是需要特别注意选取权重最小的边，包括正确的选取范围和对已选的边予以标记。六、用户手册按照已有规则在指定的 txt 文件输入相关的信息即可。为了简化问题，突出重点，算法没有设计对读入的数据判错的功能。七、测试结果村庄村庄距离村庄村庄距离AB32.8CE41.1AH12.1EG10.5B