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

软 件 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2015 年 1 月目录1 设计时间32 设计目的33设计任务34 设计内容34.1需求分析34.2总体设计44.3详细设计44.4测试与分析54.4.1测试54.4.2分析64.5 附录75 总结与展望11参考文献12成绩评定121 设计时间 2015年1月19日2012年1月23日2 设计目的通过课程设计，加深对数据结构这一课程所学内容的进一步理解与巩固，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。提高程序开发功能，能运用合理的控制流程编写清晰高效的程序。训练C程序调试能力，能将一个中小型各级组织系统联调通过。开发一个中小型系统，掌握系统研发全过程。培养分析问题、解决实际问题的能力。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4 设计内容 设计思路：(1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。如:北京到大连的直接距离是100公里.(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输出应该建设的地铁线路及所需建设总里程。本程序中用到的所有抽象数据类型的定义；typedef char InfoTypetypedef char VertexTypeMAX_NAMEtypedef struct VRType adj; InfoType *info; 、 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph;typedef struct VertexType adjvex; VRType lowcost;minsideMAX_VERTEX_NUM;4.1需求分析 输出应该建设的地铁线路及所需建设总里程。要求输出建设地铁的最短路线，再利用其最短路线上的权值把总的里程计算出来，已达到最省的费用，实现该地铁的建设。4.2总体设计1.首先要了解本题中的要求，要用已经学的邻接矩阵，根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。2. 根据普利姆算法计算最小生成树。假设WN=(V,E) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。3.了解了这些就可以实现它的基本操作，然后构建一个邻接矩阵，输入各个辖区构成一个无向连通图，并把直接距离当作权值来标记，之后，进行普里姆的算法，使其生成最小生成树，并带有权值了，把这些辖区输出，并把最小路径和最少的费用输出，这样就完成了操作。本题出现的调用函数是：i=creatgraph(&g);MiniSpanTree_PRIM(g,a);k=locatevex(&g,a);minimun(struct tree *a,Graph g)；开始主程序流程图：主函数 建设界面 普里姆的构建及使用邻接矩阵的建立及存储MiniSpanTree_PRIMcreatgraphminimunlocatevex主函数结束 图14.3详细设计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; char a10,b10; printf(所有的辖区，以0为结束n); scanf(%s,g-Vi); while(strcmp(0,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(辖区之间的路程，以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.4测试与分析4.4.1测试邻接矩阵的建立及存储：图2普里姆算法： 图34.4.2分析1.调试过程中遇到的问题及其解决方法（1）问题:在 for 循环语句中,循环变量使用控制错误 解决方法: 在 for 循环语句中,应该意识到:循环变量的执行次数总是比循环体的执行次数多一次;即最后一次的循环体执行完毕之后,循环变量又执行了一次,但是循环体却没有再执行了。（2）问题：二位数组在使用的时候数组未初始化：导致最后输出的时候的邻接矩阵出现错误；解决方法：根据输出的窗口从代码中分析发现错误，二维数组初始化之后，所得到的邻接矩阵正确输出。2.复杂度分析分析普里姆算法，假设网中有n个定点，则第一个进行初始化的循环语句的频率为n，第二个循环语句的频率为n-1。其中有两个内循环：其一是在closedgev.lowcost中求最小值，其频率为n-1;其二是重新选择具有最小代价的变量，其频度为n。由此，普里姆算法的时间复杂度为O(n*n),与网中的遍数无关。利用PRIM算法生成最小生成树时，求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。3.思路探索开始分析问题时，我把问题想得过于简单，结合老师讲过得算法和书上得算法设计得，但本题不是这样的，这个实际问题中有权值，而且这还是本题的关键，开始的时候造成了不少的麻烦，然后经过同学间得讨论，才看出来我的错误来，及时改了过来。还有在普里姆的操作上，可谓是麻烦重重，书上的算法根本行不通，（因为上面的是C+）后来我反复的来看书也整的一知半解的，通过老师的帮助，我又开始重做，在最后才做出来。由于开始时对于问题的错误分析，浪费了不少时间。 其实，由于自己的马虎也浪费了不少的时间在不必要的地方，如：字母的大小写，自负的定义上，但还好最后这些都克服了，对我来说对数据结构又有了进一步的了解，继续学习，丰富自己！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; char a10,b10; printf(所有的辖区，以0为结束n); scanf(%s,g-Vi); while(strcmp(0,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(辖区之间的路程，以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 总结与展望通过这一周的课程设计，加深了我对数据结构这门课程所学内容的进一步的理解与掌握；同时，通过对地铁建设问题的开发，使得我将计算机课程所学知识与实际问题很好地相联接在了一起。初步的了解了我们所学的课本知识在实际中的应用。同时业培养了我开发一个中小型程序的能力。在这次对地铁建设问题的开发过程中使我更加体会到细心耐心在程序设计中的重要性，和同学的合作交流业让自己学到了更多，发现自己在实际问题分析中的不足。通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了数据结构与算法这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例，如何能在计算机中表示一个双向权值不同的图，这就是一件很巧妙的事情，经过了思考和老师同学的帮助，我用edgesij=up和edgesji=up就能实现了一个双向图信息的存储。对整个程序而言，Dijkstra算法始终都是核心内容，其实这个算法在实际思考中并不难，也许我们谁都知道找一个路径最短的方法，及从顶点一步一步找最近的路线并与其直接距离相比较，但是，在计算机中实现