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

《数据结构课程设计(管道铺设施工的最佳选择)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、型：图的邻接矩阵存储表示：constMAX_VERTEX_NUM=30;//最大顶点个数typedefstructArcCell{doubleadj;//对无权图,用1,0表示相邻否,对带权图，则为权值boolkind;//为1表示可供选择，否则不行}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//描述定点的数组AdjMatrixarcs;intvexnum,arcnum;//图的当前顶点数和边数

3、}MGraph;主程序模块：voidmain(){定义联通网；读入数据初始化联通网；处理数据并输出结果；}四、详细设计1、图的邻接矩阵constMAX_VERTEX_NUM=30;//最大顶点个数typedefstructArcCell{doubleadj;//对无权图,用1,0表示相邻否,对带权图，则为权值boolkind;//为1表示可供选择，否则不行}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM

4、];//描述定点的数组AdjMatrixarcs;intvexnum,arcnum;//图的当前顶点数和边数}MGraph;2、构建图的邻接矩阵doublemax_num=1000;voidCreateMGraph(MGraph&G){//采用邻接矩阵存储表示，构造无向图Gifstreamin1("vex.txt");//读取顶点的信息ifstreamin2("edge.txt");//读取边的信息intline=0;//用作顶点和边的数目的计数器strings1,s2;for(inti=1;getline(in1,s1);i+

5、+,line++){istringstreamiss1(s1);iss1>>G.vexs[i];}G.vexnum=line;line=0;for(i=1;i<=G.vexnum;++i)for(intj=1;j<=G.vexnum;++j){if(i!=j){G.arcs[i][j].adj=max_num;G.arcs[i][j].kind=0;}else{G.arcs[i][j].adj=0;G.arcs[i][j].kind=1;}}charv1,v2;doubleweight;for(intk=1;getline(in

6、2,s2);k++,line++){istringstreamiss2(s2);iss2>>v1>>v2>>weight;G.arcs[v1-'A'+1][v2-'A'+1].adj=weight;G.arcs[v2-'A'+1][v1-'A'+1].adj=weight;}G.arcnum=line;cout<<"初始化的邻接矩阵：";for(i=1;i<=G.vexnum;++i){cout<

7、=1;i<=G.vexnum;++i){//输出邻接矩阵cout<

8、num!=G.vexnum){min=max_num;for(inti=1;i<=G.vexnum;i++)//找出符合条件的权重最小的边for(intj=1;j<=G.vexnum;j++)if(min>G.arcs[i][j].adj&&i!=j&&G.ar