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

管道铺设施工的最佳选择一、问题描述题目内容：在意联通网表示的村庄之间管道的连接，设计一个将所有村庄连接起来的管道构成的最小生成树。基本要求：实现村庄之间管道总长最短。测试数据：村庄村庄距离村庄村庄距离AB32.8DE67.3AC44.6DF98.7AH12.1EF85.6AI18.2EG10.5BC5.9FI79.2CD21.3GH52.5CD41.1HI8.7CG56.4二、需求分析此程序无需输入数据，直接从文件序所需要的数据，以此数据构建联通网，并输出由此联通网生成的最小树，即为管道铺设施工的最佳选择。三、概要设计抽象数据类型：图的邻接矩阵存储表示：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;主程序模块：void main()定义联通网；读入数据初始化联通网；处理数据并输出结果；四、详细设计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_num=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);iss1G.vexsi;G.vexnum=line;line=0;for (i=1; i=G.vexnum; +i)for (int j=1; jv1v2weight;G.arcsv1-A+1v2-A+1.adj = weight;G.arcsv2-A+1v1-A+1.adj = weight;G.arcnum=line;cout初始化的邻接矩阵：n ;for (i=1; i=G.vexnum; +i)coutsetfill( );coutsetw(8)char(i+A-1);coutendlendl;for (i=1; i=G.vexnum; +i) / 输出邻接矩阵coutchar(i+A-1);for (int j=1; j=G.vexnum; +j)coutsetfill( );coutsetw(8)G.arcsij.adj;coutendl;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)min=max_num;for(int i=1;i=G.vexnum;i+) /找出符合条件的权重最小的边for(int j=1;jG.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.arcsk2k1.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)coutsetfill( );coutsetw(8)char(i+A-1);coutendlendl;for (i=1; i=G.vexnum; +i)/ 输出处理后的邻接矩阵coutchar(i+A-1);for (int j=1; j=G.vexnum; +j)coutsetfill( );coutsetw(8)G.arcsij.adj;coutendl;cout最小生成树（普里姆算法）：n;cout顶点t顶点t边的权重n;for (i=1; i=G.vexnum; +i)for (int j=1; j=G.vexnum; +j)if(G.arcsji.adj0)coutchar(i+A-1)tchar(j+A-1)tG.arcsij.adjendl;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 文件输入相关的信息即可。为了简化问题，突出重点，算法没有设计对读入的数据判错的功能。七、测试结果村庄村庄距离村庄村