数据结构课程设计地铁建设问题.doc
. . 软 件 学 院课程设计报告书课程名称 数据结构 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 10 / 12目录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)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输出应该建设的地铁线路与所需建设总里程。4.1总体设计图4-1算法图4.2需求分析（1）本程序设计计算城市各辖区间修建地铁的最短路程。（2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入完毕。（3）输入各辖区间距离时，先输入两辖区名称，再输入距离。（4）最后计算最短距离来得出最少费用。4.3详细设计采用邻接矩阵存储构造无向图int creatgraph(Graph *g)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("请输入辖区和辖区之间的路程，以#为完毕标志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->Rkp=g->Rpk=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;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 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 typedefstructchar VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char a10)int i;for(i=0;i<g->vexnum;i+)if(strcmp(a,g->Vi)=0)return i; 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->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("请输入辖区和辖区之间的路程，以#为完毕标志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->Rkp=g->Rpk=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;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 k;void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,k,money=0; k=locatevex(&g,a);if(k=-1) printf("没有%s这个辖区，无法求解n",a);return 0;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); money+=closedgek.lowcost; printf("%d:%s %s %dn",i,g.V closedgek.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,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 总结与展望本程序，本次编译涉与数据结构最小生成树以与图的构造等编译。先要构造结构体，在定义时应要注意尽量将赋值空间增大，以防止调试时输入数据超出运算围。再进行函数的编译调用，构造无向图用邻接矩阵进行存储，这些编译代码，书上都有介绍，但不可尽抄，书上的只是一个模板，根据程序设计任务将变量进行修改，构造图之后，运用最小生成树原理，用普利姆算法对整个程序变量进行编译，最后进入主函数，就直接调用函数进行运算输入的数据，输出运算结果。这次程序的编译让我对图的遍历理解的更加深入，最小生成树问题不仅可以运算本次程序对地铁建造最少费用问题，更可以运用于一系列的最短距离等问题，解决甚多复杂问题！极其具有实用性！参考文献1 屈辉立,可明,石武信.JSP编程教程M.第1版, :希望电子,2005 2 白勇.用B/S模式构建在线考试系统J,电力高等专科学校学报,2003,10(4): 100130. 3 严蔚敏.吴伟民编著，数据结构。：清华大学，20074 诗斌.数据库系统基础。计算机工程与应用，1981年第8期成绩评定成绩 教师签字
