数据结构课程设计：地铁建设问题

软件学院课程设计报告书课程名称 数据结构设计题目 地铁建设问题专业班级学 号姓 名指导教师2014年1月17日目录1设计时间...............................错误!未定义书签。2设计目的...............................错误!未定义书签。3设计任务...............................错误!未定义书签。4设计内容...............................错误!未定义书签。总体设计.................................错误!未定义书签。需求分析.................................错误!未定义书签。详细设计.................................错误!未定义书签。测试与分析...............................错误!未定义书签。测试.....................................错误!未定义书签。分析.....................................错误!未定义书签。附录....................................错误!未定义书签。5总结与展望.............................错误!未定义书签。参考文献.................................错误!未定义书签。成绩评定.................................错误!未定义书签。设计时间2014年1月15日设计目的设计各辖区之间最短地铁，使修建费用最少设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。设计内容输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。输出应该建设的地铁线路及所需建设总里程。总体设计图4-1算法图需求分析（1）本程序设计计算城市内各辖区间修建地铁的最短路程。（2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以 #输入结束。（3）输入各辖区间距离时，先输入两辖区名称，再输入距离。（4）最后计算最短距离来得出最少费用。详细设计采用邻接矩阵存储构造无向图int creatgraph(Graph*g){int i=0,j,m,k,p;chara[10],b[10];printf( "请输入所有的辖区，以

#为输入结束标志

\n");scanf( "%s",g->V[i]);while(strcmp("#",g->V[i])!=0){i++;scanf( "%s",g->V[i]);}g->vexnum=i;for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)g->R[i][j]=INFINITY;printf( "请输入辖区和辖区之间的路程，以scanf( "%s%s%d",a,b,&m);

##为结束标志\n");while(strcmp("##",a)!=0||strcmp( "##",b)!=0||m!=0){k=locatevex(g,a);p=locatevex(g,b);if(k==-1){printf(return

"没有%s这个辖区\n",a);0;}if(p==-1){printf(return

"没有%s这个辖区\n",b);0;}g->R[k][p]=g->R[p][k]=m;scanf("%s%s%d",a,b,&m);}return 1;}普利姆算法生成最小树struct

tree

owcost!=0){m=1;k=i;}if(m==1&&a[i].lowcost!=0){if(a[i].lowcost<a[k].lowcost)k=i;}}return k;}测试与分析测试图4-1正确测试结果图4-2错误测试结果分析调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入下一个输入。且不能输入与本次输入无关的数据或者超出本次输入限制的数据，否则显示错误，将重新输入。附录#include<>#include<>#include<>#include<>#defineINFINITY10000#defineM20typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;int locatevex(Graph *g,chara[10]){int i;for(i=0;i<g->vexnum;i++){if(strcmp(a,g ->V[i]) ==0)return i;}if(i==g->vexnum)return -1;}int creatgraph(Graph{

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

\n");i++;scanf( "%s",g->V[i]);}g->vexnum=i;for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)g->R[i][j] =INFINITY;printf( "请输入辖区和辖区之间的路程，以 ##为结束标志\n");scanf( "%s%s%d",a,b,&m);while(strcmp("##",a)!=0|| strcmp("##",b)!=0|| m!=0){k =locatevex(g,a);p =locatevex(g,b);if(k==-1){printf(return

"没有%s这个辖区\n",a);0;}if(p==-1){printf(return

"没有%s这个辖区\n",b);0;}g->R[k][p] =g->R[p][k] =m;scanf("%s%s%d",a,b,&m);}return 1;}struct tree owcost !=0){m=1;k=i;}if(m==1&&a[i] .lowcost!=0){if(a[i] .lowcost<a[k].lowcost)k=i;}}return k;}voidMiniSpanTree_PRIM(Graphg,{struct treeclosedge[M];int i,j,k,money =0;k=locatevex( &g,a);if(k==-1){

chara[10])printf(return

"没有%s这个辖区，无法求解\n",a);0;}for(i=0;i<;i++){if(i!=k){closedge[i]closedge[i]}

.lowcost=[k][i];.weizhi=k;}closedge[k] .lowcost=0;for(i=1;i<;i++){=minimun(closedge,g);money+=closedge[k].lowcost;printf( "%d:%s%s%d\n",i,[closedge[k]

.weizhi],[k],closedge[k]

.lowcost);closedge[k] .lowcost=0;for(j=0;j<;j++){if[k][j] <closedge[j] .lowcost){closedge[j] .weizhi=k;closedge[j] .lowcost=[k][j];}}}printf( "总费用为：%d\n",money);}voidmain(){int i,k;Graphg;chara[10];printf("请选择功能：1（铁路建设）0（退出）\n");scanf("%d",&k);while(k){=creatgraph(&g);if(i){printf("请输入从哪里开始：");scanf( "%s",a);MiniSpanTree_PRIM(g,a);}printf( "请选择功能：1（铁路建设）scanf( "%d",&k);

0（退出）\n");}}总结与展望本程序，本次编译涉及数据结构最小生成树以及图的构造等编译。先要构造结构体，在定义时应要注意尽量将赋值空间增大，以防止调试时输入数据超出运算范围。再进行函数的编译调用，构造无向图用邻接矩阵进行存储，这些编译代码，书上都有介绍，但不可尽抄，书上的只是一个模板，根据程序设计任务将变量进行修改，构造图之后，运用最小生成树原理，用普利姆算法对整个程序变量进行编译，最后进入主函数，就直接调用函数进行运算输入的数据，输出运算结果。这次程序的编译让我对图的遍历理解的更加深入， 最小生成树问题不仅可以运算本次程序对地铁建造最少费用问题，更可以运用于一系列的最短距离等问题，解决甚多复杂问题！极其具有实用性！参考文献[1]屈辉立,