数据结构课程设计汇本：地铁建设问题.doc

《数据结构课程设计汇本：地铁建设问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、软件学院课程设计报告书课程名称数据结构设计题目地铁建设问题专业班级学号姓名指导教师2014年1月17日目录1设计时间12设计目的13设计任务14设计容14.1总体设计14.2需求分析24.3详细设计24.4测试与分析44.4.1测试44.4.2分析64.5附录65总结与展望10参考文献11成绩评定111设计时间2014年1月15日2设计目的设计各辖区之间最短地铁，使修建费用最少3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计容(1)输入各个辖区名称和各辖区间直接

2、距离（地铁铺设费用与距离成正比）。(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输出应该建设的地铁线路及所需建设总里程。4.1总体设计图4-1算法图4.2需求分析（1）本程序设计计算城市各辖区间修建地铁的最短路程。（2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入结束。（3）输入各辖区间距离时，先输入两辖区名称，再输入距离。（4）最后计算最短距离来得出最少费用。4.3详细设计采用邻接矩阵存储构造无向图intcreatgraph(Graph*g){inti=0,j,m,k,p;chara[10],b[10];printf("请输入

3、所有的辖区，以#为输入结束标志");scanf("%s",g->V[i]);while(strcmp("#",g->V[i])!=0){i++;scanf("%s",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)!=0

4、

5、strcmp("##",b)!=0

6、

7、m!=0)

8、{k=locatevex(g,a);p=locatevex(g,b);if(k==-1){printf("没有%s这个辖区",a);return0;}if(p==-1){printf("没有%s这个辖区",b);return0;}g->R[k][p]=g->R[p][k]=m;scanf("%s%s%d",a,b,&m);}return1;}普利姆算法生成最小树structtree//构造最小生成树//{intweizhi;intlowcost;};intminimun(structtree*a,Graphg){inti,k,m=0;for(i=0;

9、i#inclu

10、de#include#include#defineINFINITY10000#defineM20typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;intlocatevex(Graph*g,chara[10]){inti;for(i=0;ivexnum;i++){if(strcmp(a,g->V[i])==0)returni;}if(i==g->vexnum)return-1;}intcreatgraph(Graph*g){inti=

11、0,j,m,k,p;chara[10],b[10];printf("请输入所有的辖区，以#为输入结束标志");scanf("%s",g->V[i]);while(strcmp("#",g->V[i])!=0){i++;scanf("%s",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

12、("##",a)!=0

13、

14、strcmp("##",b