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

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

2、个辖区，并使总费用最小。4 设计容(1) 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比） 。(2) 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3) 输出应该建设的地铁线路及所需建设总里程。4.1 总体设计专业资料.图 4-1 算法图4.2 需求分析（1 ）本程序设计计算城市各辖区间修建地铁的最短路程。（2 ）运行时，输入辖区的名称，各辖区之间用空格键隔开，以# 输入结束。（3 ）输入各辖区间距离时，先输入两辖区名称，再输入距离。专业资料.（4 ）最后计算最短距离来得出最少费用。4.3 详细设计采用邻接矩阵存储构造无向图int creatgraph(Graph *g)

3、int i=0,j,m,k,p;char a10,b10;printf( "请输入所有的辖区，以 # 为输入结束标志 n" );scanf( "%s" ,g->Vi);while (strcmp( "#" ,g->Vi)!=0)i+;scanf( "%s" ,g->Vi);g->vexnum=i;for (i=0;i<g->vexnum;i+)for (j=0;j<g->vexnum;j+)g->Rij=INFINITY;printf( "请输入辖区和

4、辖区之间的路程，以# 为结束标志 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);return0;if (p=-1)printf( " 没有 %s这个辖区 n" ,b);return0;g->Rkp=g-&g

5、t;Rpk=m;scanf( "%s%s%d" ,a,b,&m);return1;普利姆算法生成最小树structtree/ 构造最小生成树 /int weizhi;int lowcost;专业资料.int minimun(struct tree *a,Graph g)int i,k,m=0;for (i=0;i<g.vexnum;i+)if (m=0 && ai.lowcost!=0)m=1;k=i;if (m=1 && ai.lowcost!=0)if (ai.lowcost<ak.lowcost)k=i;return

6、k;4.4 测试与分析测试专业资料.图 4-1 正确测试结果图 4-2 错误测试结果分析调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入下一个输入。且不能输入与本次输入无关的数据或者超出本次输入限制的数据，否则显示错误，将重新输入。专业资料.4.5附录#include< stdio .h>#include< stdlib.h>#include< malloc .h >#include< string.h>#defineINFINITY10000#defineM 20typedefstructcharVM10;

7、intRMM;intvexnum;Graph;int locatevex(Graph*g,char a10)int i;for (i= 0;i< g -> vexnum;i + )if (strcmp(a,g -> Vi) = 0)returni;if (i= g -> vexnum)return- 1;专业资料.int creatgraph(Graph*g)int i= 0,j,m,k,p;char a10,b10;printf( "请输入所有的辖区，以 # 为输入结束标志 n" );scanf( "%s" ,g -> V

8、i);while (strcmp( "#" ,g -> Vi) != 0)i+ ;scanf( "%s" ,g -> Vi);g -> vexnum = i;for (i= 0;i < g -> vexnum;i + )for (j= 0;j< g -> vexnum;j + )g -> Rij = INFINITY;printf( "请输入辖区和辖区之间的路程，以# 为结束标志 n" );scanf( "%s%s%d" ,a,b,& m);while (st

9、rcmp( "#" ,a)!= 0 | strcmp( "#" ,b)!= 0 | m != 0)k= locatevex(g,a);p = locatevex(g,b);if (k=- 1)专业资料.printf( " 没有 %s这个辖区 n" ,a);return0;if (p=- 1)printf( " 没有 %s这个辖区 n" ,b);return0;g -> Rkp = g -> Rpk = m;scanf( "%s%s%d" ,a,b, & m);return1;

10、structtree/ 构造最小生成树 /int weizhi;int lowcost;int minimun(struct tree *a,Graph g)int i,k,m = 0;专业资料.for (i= 0;i < g .vexnum;i + )if (m = 0 &&ai .lowcost != 0)m = 1;k= i;if (m = 1 &&ai .lowcost != 0)if (ai .lowcost < ak .lowcost)k= i;returnk;void MiniSpanTree_PRIM(Graph g,char a10

11、)structtree closedgeM;int i,j,k,money= 0;k= locatevex(& g,a);if (k=- 1)专业资料.printf( " 没有 %s这个辖区，无法求解 n" ,a);return0;for (i= 0;i < g .vexnum;i + )if (i!= k)closedgei.lowcost = g .Rki;closedgei.weizhi = k;closedgek.lowcost = 0;for (i= 1;i< g .vexnum;i + )k= minimun(closedge,g);mone

12、y += closedgek.lowcost;printf( "%d:%s%s%dn" ,i,g .Vclosedgek.weizhi ,g .Vk,closedgek.lowcost);closedgek.lowcost = 0;for (j= 0;j< g .vexnum;j + )if (g .Rkj < closedgej.lowcost)专业资料.closedgej.weizhi = k;closedgej.lowcost = g .Rkj;printf( " 总费用为： %dn" ,money);void main()int i,

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