《数据结构课程设计：地铁建设问题》由会员分享，可在线阅读，更多相关《数据结构课程设计：地铁建设问题（12页珍藏版）》请在金锄头文库上搜索。
1、软件学院课程设计报告书课程名称数据结构设计题目 地铁建设问题专业班级 学号姓名指导教师 2014年1月17日目录1设计时间12设计目的13设计任务14设计内容14.1总体设计14.2需求分析24.3详细设计24.4测试与分析44.4.1 测试44.4.2 分析54.5附录55总结与展望9参考文献10成绩评定101设计时间2014年1月15日2设计目的设计各辖区之间最短地铁，使修建费用最少3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁 建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容(1) 输入各个辖区名称和各辖区间直接距离(地铁铺设费用与
2、距离成正比)。(2) 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3) 输出应该建设的地铁线路及所需建设总里程。4.1总体设计箭I五 衽争淄答起点.片点 和亘揍芥巨禹普利姆算法计算最小生 成材输I出戴蛇路和总里程图4-1算法图4.2需求分析(1) 本程序设计计算城市内各辖区间修建地铁的最短路程。(2) 运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入结束。(3) 输入各辖区间距离时，先输入两辖区名称，再输入距离。(4) 最后计算最短距离来得出最少费用。4.3详细设计采用邻接矩阵存储构造无向图int creatgraph(Graph *g)int i=0,j,m,k,p;cha
3、r a10,b10;printf(请输入所有的辖区，以#为输入结束标志n);scanf(%s,g-Vi);while(strcmp(#”,g-Vi)!=0)i+;scanf(%s,g-Vi);g-vexnum=i;for(i=0;ivexnum;i+)for(j=0;jvexnum;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)
4、printf(没有、这个辖区n,a);return 0;if(p=-1)printf(没有、这个辖区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;ig.vexnum;i+)if(m=0 & ai.lowcost!=0)m=1;k=i;if(m=1 & ai.lowcost!=0)if(ai.lowcost.i 土古
5、束标e lasdFsdf a.sdf AC泱0E1F这卜辖区解肄!谿瞿铁端饵器*图4-2错误测试结果4.4.2分析调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束 本次输入进入下一个输入。且不能输入与本次输入无关的数据或者超出本次输入限制的数据，否则显示错误，将 重新输入。4.5附录#include #include #include #include #define INFINITY 10000#define M 20typedef structchar VM10;int RMM;int vexnum;Graph;int locatevex(Graph *g, ch
6、ar a10)int i;for (i=0;ivexnum;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;ivexnum;i+)for (j=0;jvexnum;j+)g-Rij = INFINITY;prin
7、tf(-请输入辖区和辖区之间的路程，以#为结束标志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
8、minimun(struct tree *a,Graph g)int i,k,m=0;for (i=0;ig. vexnum;i+)if (m=0 & ai. lowcost!=0)m=1;k=i;if (m1 & ai. lowcost!0)if(ai. lowcostak. lowcost)ki;return k;void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,k,money0;klocatevex(&g,a);if (k-1)printf(没有%，这个辖区，无法求解n,a);return 0;fo
9、r (i=0;ig. vexnum;i+)if(i !k)closedgei. lowcostg. Rki;closedgei.weizhik;closedgek. lowcost=0;for (i=1;ig. vexnum;i+)kminimun(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;jg. vexnum;j+)if (g. Rkjclosedgej. lowc
10、ost)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总结与展望本程序，本次编译涉及数据
11、结构最小生成树以及图的构造等编译。先要构造结构体， 在定义时应要注意尽量将赋值空间增大，以防止调试时输入数据超出运算范围。再进行函 数的编译调用，构造无向图用邻接矩阵进行存储，这些编译代码，书上都有介绍，但不可 尽抄，书上的只是一个模板，根据程序设计任务将变量进行修改，构造图之后，运用最小 生成树原理，用普利姆算法对整个程序变量进行编译，最后进入主函数，就直接调用函数 进行运算输入的数据，输出运算结果。这次程序的编译让我对图的遍历理解的更加深入，最小生成树问题不仅可以运算本次 程序对地铁建造最少费用问题，更可以运用于一系列的最短距离等问题，解决甚多复杂问 题！极其具有实用性！参考义献1屈辉立，陈可明，石武信.JSP网站编程教程M.第1版，北京:北京希望电子出版社,2005 白勇.用B/S模式构建在线考试系统J,重庆电力高等专科学校学报,2003,10(4): 100130.3 严蔚敏.吴伟民编著，数据结构。一北京：清华大学出版社，20074 姚诗斌.数据库系统基础。计算机工程与应用，1981年第8期成绩评定成绩教师签字
