地铁建设问题

《地铁建设问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件学院课程设计报告书课程名称数据结构设计J目题目建设问颍软件11-02专业班级学号姓名指导教师2013年1月20日目录1•设计时间22.设计目的23.设计任务24.设计内容24.1需求分析24.2总体设计24.2.1主函数流程图24.3详细设计343.2函数调用关系343.3主要模块的算法描述34.4测试与分析34.41测试344.2分析44.5附录45•总结与展望7参考文献8成绩评定81设计时间2012年1月5日2设计目的设计各辖区Z间最短地铁，使修建费用最少3设计任务某城市要在各个辖区之间修建地铁，由

2、于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容(1)输入各个辖区名称和各辖区间宜接距离(地铁铺设费用与距离成正比)。(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输岀应该建设的地铁线路及所需建设总里程。4.14.2需求分析(1)本程序设计计算城市内各辖区间修建地铁的最短路程。(2)运行时，输入辖区的名称，各辖区Z间用空格键隔开，以#输入结束。(3)输入各辖区间距离时，先输入两辖区名称，再输入距离。(4)最后计算最短距离来得出最少费

3、用。4.3详细设计P163采用邻接矩阵存储构造无向图P175普利姆算法生成最小树4.4测试与分析4.4.1测试4.4.2分析调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入卜一个输入。且不能输入与木次输入无关的数据或者超出木次输入限制的数据，否则显示错谋，将重新输入。4.5附录#include#include#include#include#defineINFINITY10000#define

4、M20typedefstruct{charV[M][10];intR

5、M][M

6、;intvexnum;}Graph;intlocatevex(Graph*g,chara[10]){inti;for(i=0;ivexnum;i++){if(strcmp(a,g->V[i])==O)returni;}if(i==g・>vexnum)return-1;}intcreatgraph(Graph*g){inti=0,j,m,k,p;chara[10],b[10];printf(”请输入所有的辖区，以#为输入结

7、束标忐”)；scanf(u%sH,g->V[i]);while(strcmp(H#n,g->V[i])!=0){i++；scanf(n%sn,g->V[i]);}g->vexnum=i;for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)g・>R[i][j]二INFINITY;printf(”请输入辖区和辖区之间的路程，以##为结束标志”);scanf(,'%s%s%d',,a,b,&m);while(strcmp("##",a)!=OIIstrcmp(H

8、##",b)!=OIIm!=0){k=locatevex(g,a);p=locatevex(g,b);if(k==-l){primfC没有％$这个辖区",a);return0;}if(p==-l){primfC没有％$这个辖区",b);return0;}g->R[k]fp]=g->R[pl[k]=m;scanf(H%s%s%d",a,b,&m);}return1;}structtree〃构造最小生成树〃{intweizhi;intlowcost;}；intminimun(structtree*a,G

9、raphg){inti,k,m=0;for(i=0;i

10、intf("没有％$这个辖区，无法求解",a);return0;}for(i=0;i