数据结构课程设计：地铁

1、 数据结构课程设计：地铁建设问 题 软 件 学 院 课程设计报告书 课程名称 数据结构 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2014 年 1月17日 1 目录 1 设计时间 . 0 2 设计目的 . 0 3设计任务 . 0 4 设计内容 . 0 4.1总体设计 . 0 4.2需求分析 . 1 4.3详细设计 . 1 4.4测试与分析 . 3 4.4.1测试 . 3 4.4.2分析 . 4 4.5 附录 . 4 5 总结与展望 . 8 参考文献 . 9 成绩评定 . 11 1 设计时间 日1月15年2014 设计目的2 设计各辖区之间最短地铁，使修建费用最少 设计任务3因

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

3、细设计4.3 采用邻接矩阵存储构造无向图 creatgraph(Graph *g) int i=0,j,m,k,p;in a10,b10;cha);为输入结束标屜请输入所有的辖区，print,g-Vi);scanf,g-Vi)!=0)whil(strcmpi+;,g-Vi);scanfg-vexnum=i; 1 (i=0;ivexnum;i+) for (j=0;jvexnum;j+) for g-Rij=INFINITY; ); 为结束标志屜屮printf(请输入辖区和辖区之间的路程，以# ,a,b,&m); scanf(層 ,b)!=0 | m!=0) ,a)!=0 | strcmp(?尣

4、while(strcmp(?尣 p=locatevex(g,b); k=locatevex(g,a); (k=-1) if ,a); 屜屮没有%s这个辖区 printf( 0; return (p=-1) if ,b); 这个辖区屜屮%s printf( 没有 0; return g-Rkp=g-Rpk=m; ,a,b,&m);scanf 1;retur普利姆算法生成最小/构造最小生成struc tree/ weizhi;in lowcost;in; 2 tree *a,Graph g) structint minimun( i,k,m=0; int(i=0;ig.vexnum;i+) for

5、 (m=0 & ai.lowcost!=0) if m=1; k=i; (m=1 & ai.lowcost!=0) if (ai.lowcoststrin#includ INFINITY 10000#defin M 20 #defin structtypede VM10; cha RMM; in 4 vexnum; intGraph; a10) g,charint locatevex(Graph * i; int) vexnum;i+ for(i=0;i 0) =Vi)if(strcmp(a,g- i; return vexnum) -(i=g if1; - return g) *int cr

6、eatgraph(Graph 0,j,m,k,p; = int i a10,b10; char ); 屜屮#为输入结束标志 printf(请输入所有的辖区，以Vi); -屳,g scanf(0) !=-Vi) while(strcmp(?,g ; + iVi); -屳,g scanf( i; vexnum= g-) vexnum;i+0;i for(i=) vexnum;j+ for(j=0;jINFINITY; = g -Rij);屜请输入辖区和辖区之间的路程，#为结束标 printm); scanf,a,b0)!| ?,b!0| whil(strcmp?,a!0 strcmp locate

7、vex(g,b);locatevex(g,a); 1)(=i,a);屜没%这个辖 print 0;retur 1)(i= ,b);屜%这个辖 printf 0;retur m;RpkRkp-5 m); &scanf(層,a,b, 1; return / 构造最小生成树struct tree / weizhi; int lowcost; int ; a,Graph g) *struct tree int minimun( 0; =int i,k,m ) +.vexnum;i(i=0;ig for 0) lowcost!=.=0 & ai if(m 1; m= i; k= 0) lowcost!=

8、& ai. if(m=1 lowcost) .lowcostak(ai if.i; = k k; return a10) charvoid MiniSpanTree_PRIM(Graph g tree closedgeM;struc0;in i,j,k,mone g,a);locatevex 1)(= i ,a);屜%这个辖区，无法求 printf 0;retur )vexnum;+0;fo ( k)! i(Rki; closedgeilowcosk;weizh closedgei 6 0; = closedgek.lowcost) +g.vexnum;ifor(i=1;i minimun(c

9、losedge,g); = klowcost; .+=closedgek money %d:%s %s printf(lowcost); .Vk,closedgek.V closedgek.weizhi ,g搥屜屮,i,g0; =.lowcost closedgek) vexnum;j+0;jg.for (j= lowcost) closedgej.(g.Rkj if k; weizhi= closedgej.Rkj; .lowcost.=g closedgej ,money); 搥屜屮 printf(总费用为： main() void i,k; int Graph g; a10; char

10、); （退出）屜屮请选择功能： 1（铁路建设） 0 printfk); scanf(k) whil g); creatgraph(i)i 请输入从哪里开始 printf,a); scanf MiniSpanTree_PRIM(g,a); );（退出屜 printf请选择功能 （铁路建设k); scanf 7 总结与展望5 本程序，本次编译涉及数据结构最小生成树以及图的构造等编译。先要构造结构体，再进行函在定义时应要注意尽量将赋值空间增大，以防止调试时输入数据超出运算范围。数的编译调用，构造无向图用邻接矩阵进行存储，这些编译代码，书上都有介绍，但不可尽抄，书上的只是一个模板，根据程序设计任务将变量进行修改，构造图之后，运用最小生成树原理，用普利姆算法对整个程序变量进行编译，最后进入主函数，就直接调用函数 进行运算输入的数据，输出运算结果。最小生成树问题不仅可以运算本次这次程序的编译让我对图的遍历理解的更加深入，解决甚多复杂问更可以运用于一系列的最短距离等问题，程序对地铁建造最少费用问题，