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

软 件 学 院课程设计报告书课程名称 数据结构 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2013年 1 月目录1 设计时间.22 设计目的.23 设计任务.24 设计内容.24.1需求分析.24.1.1程序所能达到的功能.24.1.2输入、输出的形式和输入值的范围.24.1.3测试数据.34.2总体设计.34.2.1抽象数据类型定义.34.2.2主程序的流程、模块之间的调用关系.44.3详细设计.54.3.1 数据类型、函数的伪码算法.54.3.2函数的调用关系图.94.4测试与分析.104.4.1测试.104.4.2分析.114.5 附录.115 总结与展望.16参考文献.17成绩评定.171 设计时间2012年1月21日2012年1月25日2 设计目的1.通过这次设计，在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解2.训练程序设计方法以及上机操作等基本技能，积累编程经验3.培养用计算机解决实际问题的能力3 设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4 设计内容 4.1需求分析 4.1.1程序所能达到的功能 城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要编写程序合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（1）使用结构体数组，存储辖区名称（2）建立辖区间直接距离的无向图，用邻接矩阵存储辖区间直接距离信息（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线（3）输出应该建设的路线，以及所需建设的总里程信息4.1.2输入、输出的形式和输入值的范围输出的形式和输入值的范围输入数字和字母，字母为辖区名，数字为辖区间直接距离，名称个数o， 0线路个数o(o-1),直接距离m，0m10000输出的形式1：辖区名 辖区名 路程2：辖区名 辖区名 路程3：辖区名 辖区名 路程总费用为：路程的和4.1.3测试数据正确输入：辖区个数：4名称 a b c d 线路起止辖区及直接距离：a b 3、a c 5、a d 4、b c 2、b d 3、c d 2、0 0 0 开始辖区：a 输出为：1：a b 32：b c 23：c d 2总费用：7错误输入：辖区个数：4名称 a b c d 线路及之间距离：as b 3输出为：没有as 这个辖区4.2总体设计4.2.1抽象数据类型定义1抽象数据类型图的定义ADT Graph数据对象v：v是具有相同特性的数据元素的集合，成为顶点集。数据关系R： R=VR VR=|v,wV且P（v，w），表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息 基本操作P： CreateGraph（&G,V,VR）； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 ADT Graph4.2.2主程序的流程、模块之间的调用关系主程序的流程开始输入辖区个数和辖区名称输入各辖区之间路程判断输入是否正确NY建立无向图，邻接矩阵存储普利姆算法计算最小生成树输出路线和总费用结束模块之间的调用关系（1）主函数main（）调用int creatgraph(Graph *g)建立无向图，用邻接矩阵存储；（2）void MiniSpanTree_PRIM(Graph g,char a10)调用int minimun(struct tree *a,Graph g)和int locatevex(Graph *g,char a10)生成树，判断辖区名称输入是否正确；（3）主函数main（）调用void MiniSpanTree_PRIM(Graph g,char a10) 计算最小生成树，输出最优线路和总里程。4.3详细设计4.3.1 数据类型、函数的伪码算法1结构体类型typedef struct char VM10; int RMM; int vexnum; Graph; 2函数算法创建无向图int locatevex(Graph *g,char 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,o,e; char a10,b10; printf(设置辖区的个数: );/城市中辖区的个数 scanf(%d,&o); for(i=0;iVi); g-vexnum=o;for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY; printf(辖区之间的路程，以0 0 0为结束标志n); scanf(%s%s%d,a,b,&m); while(strcmp(0,a)!=0 | strcmp(0,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;ig.vexnum;i+) if(m=0 & ai.lowcost!=0) m=1; k=i;if(m=1 & ai.lowcost!=0) if(ai.lowcostak.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); for(i=0;ig.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; closedgei.weizhi=k; closedgek.lowcost=0; for(i=1;ig.vexnum;i+) k=minimun(closedge,g); money+=closedgek.lowcost; printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); closedgek.lowcost=0; for(j=0;jg.vexnum;j+) if(g.Rkjclosedgej.lowcost) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf(总费用为：%dn,money);4.3.2函数的调用关系图locatevexminimuncreatgraphmainMiniSpanTree_PRIM结束4.4测试与分析4.4.1测试1正确的输入2错误的输入4.4.2分析 调试过程中遇到的问题及其解决方法 （1）问题: 用for循环语句控制输入辖区名称及输出辖区名称时候的个数名不对应解决方法: 数组下标时从零开始的，并且在 for 循环语句中,循环变量的执行次数总是比循环体的执行次数多一次，所以应该注意修改使其相对应 （2）问题：用循环控制各辖区及其之间的距离没有考虑清楚解决方法：用输入0 0 0 判定辖区及其直接距离数据输入完毕 （3）问题：普利姆算法理解不透彻，用其计算最小生成树输出结果的时候出现问题 解决方法：上网查阅资料及阅读课本询问同学，并在以前程序上加以修改，最终得以运行。4.5 附录#include #include #include #include #define INFINITY 10000#define M 20 typedef struct char VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char 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,o,e; char a10,b10; printf(设置辖区的个数: );/城市中辖区的个数 scanf(%d,&o); for(i=0;iVi); g-vexnum=o;for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY; printf(辖区之间的路程，以0 0 0为结束标志n); scanf(%s%s%d,a,b,&m); while(strcmp(0,a)!=0 | strcmp(0,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;ig.vexnum;i+) if(m=0 & ai.lowcost!=0) m=1; k=i;if(m=1 & ai.lowcost!=0) if(ai.lowcostak.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); for(i=0;ig.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; closedgei.weizhi=k; closedgek.lowcost=0; for(i=1;ig.vexnum;i+) k=minimun(closedge,g); money+=closedgek.lowcost; printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); closedgek.lowcost=0; for(j=0;jg.vexnum;j+) if(g.Rkjclosedgej.lowcost) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf(总费用为：%dn,money);void main() int i; Graph g; char a10; i=creatgraph(&g); if(i) printf(从哪里开始：); scanf(%s,a); MiniSpanTree_PRIM(g,a); 5 总结与展望这次课程设计任务是我在大学以来的遇到的第一次课程设计，刚开始看到题目的时候看起来不是很难，但是在实际编程操作中遇到了很多的问题，不过，在不断地遇到和解决问题的过程中，学到了很多的知识。通过这一周的课程设计，加深了我对数据结构这门课程所学内容的进一步的理解与掌握。同时，通过设计程序解决地铁建设问题，让我明白学习知识不仅仅是要学习课本上的内容，还要从实际生活中学习课外的知识，把书本上的知识与现实生活好好的结合在一起。并且在查阅资料和完成设计的同时，我初步的了解了我们所学的课本知识在实际中的应用。同时，这次课程设计进一步锻炼了我的编写程序的能力，和同学的合作交流也让自己学到了更多，发现自己在实际问题分析中的不足。在编写程序的过程中，我更深切的认识到了认真、仔细、耐心的重要性，比如，就不能忽略循环时的控制变量。在本次课程设计中，主要运用了图的知识解决实际问题。同过这次的应用实践，让我体会到了图之所以能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，也就是想要把生活中的信息用计算机表达出来，首先就得把他们数