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

软 件 学 院 课程设计报告书 课程名称 数据结构 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2014 年月 1 设计时间 2014年1月15日 2 设计目的 设计各辖区之间最短地铁，使修建费用最少 3设计任务 某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。 4 设计内容 (1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。 (2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。 (3)输出应该建设的地铁线路及所需建设总里程。 4.1总体设计设计int creatgraph(Graph *g) { int i=0,j,m,k,p; char a[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;ig-vexnum;i++) for(j=0;jg-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(没有%s这个辖区\n,a); return 0; } if(p==-1) { printf(没有%s这个辖区\n,b); return 0; } g-R[k][p]=g-R[p][k]=m; scanf(%s%s%d,a,b,m); } return 1; } struct tree //构造最小生成树// { int weizhi; int lowcost; }; int minimun(struct tree *a,Graph g) { int i,k,m=0; for(i=0;ig.vexnum;i++) { if(m==0 a[i].lowcost!=0) { m=1; k=i; } if(m==1 a[i].lowcost!=0) { if(a[i].lowcosta[k].lowcost) k=i; } } return k; } 4.4测试与分析 4.4.1测试 图4-1正确测试结果 图4-2错误测试结果 4.4.2分析 调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入下一个输入。 且不能输入与本次输入无关的数据或者超出本次输入限制的数据，否则显示错误，将重新输入。 4.5 附录 #include stdio.h #include stdlib.h #include malloc.h #include string.h #define INFINITY 10000 #define M 20 typedef struct{ char V[M][10]; int R[M][M]; int vexnum; }Graph; int locatevex(Graph *g,char a[10]) { int i; for(i=0;ig-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; char a[10],b[10]; printf(请输入所有的辖区，以#为输入结束标志\n); sca