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

软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2015年1月2目录1设计时间...............................................32设计目的...............................................33设计任务...............................................34设计内容...............................................34.1需求分析..........................................44.2总体设计..........................................44.3详细设计..........................................54.4测试与分析........................................54.4.1测试.........................................94.4.2分析........................................104.5附录.............................................115总结与展望............................................15参考文献................................................17成绩评定................................................1731设计时间2015年1月19日—2012年1月23日2设计目的通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。提高程序开发功能，能运用合理的控制流程编写清晰高效的程序。训练C程序调试能力，能将一个中小型各级组织系统联调通过。开发一个中小型系统，掌握系统研发全过程。培养分析问题、解决实际问题的能力。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容设计思路：(1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。如:北京到大连的直接距离是100公里.(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3)输出应该建设的地铁线路及所需建设总里程。本程序中用到的所有抽象数据类型的定义；typedefcharInfoTypetypedefcharVertexType[MAX_NAME]typedefstruct{VRTypeadj;InfoType*info;、}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,4arcnum;}MGraph;typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_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(structtree*a,Graphg)；5主程序流程图：图14.3详细设计typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;intlocatevex(Graph*g,chara[10]){inti;for(i=0;ig-vexnum;i++){if(strcmp(a,g-V[i])==0)主函数邻接矩阵的建立及存储建设界面普里姆的构建及使用creatgraphMiniSpanTree_PRIMlocatevexminimun主函数开始结束6returni;}if(i==g-vexnum)return-1;}intcreatgraph(Graph*g){inti=0,j,m,k,p;chara[10],b[10];printf(所有的辖区，以0为结束\n);scanf(%s,g-V[i]);while(strcmp(0,g-V[i])!=0){i++;scanf(%s,g-V[i]);}g-vexnum=i;for(i=0;ig-vexnum;i++)for(j=0;jg-vexnum;j++)g-R[i][j]=INFINITY;printf(辖区之间的路程，以000为结束标志\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);return0;7}if(p==-1){printf(没有%s这个辖区\n,b);return0;}g-R[k][p]=g-R[p][k]=m;scanf(%s%s%d,a,b,&m);}return1;}structtree{intweizhi;intlowcost;};intminimun(structtree*a,Graphg){inti,k,m=0;for(i=0;ig.vexnum;i++){if(m==0&&a[i].lowcost!=0){m=1;k=i;}if(m==1&&a[i].lowcost!=0){if(a[i].lowcosta[k].lowcost)k=i;8}}returnk;}voidMiniSpanTree_PRIM(Graphg,chara[10]){structtreeclosedge[M];inti,j,k,money=0;k=locatevex(&g,a);for(i=0;ig.vexnum;i++){if(i!=k){closedge[i].lowcost=g.R[k][i];closedge[i].weizhi=k;}}closedge[k].lowcost=0;for(i=1;ig.vexnum;i++){k=minimun(closedge,g);money+=closedge[k].lowcost;printf(%d:%s%s%d\n,i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost);closedge[k].lowcost=0;for(j=0;jg.vexnum;j++){9if(g.R[k][j]closedge[j].lowcost){closedge[j].weizhi=k;closedge[j].lowcost=g.R[k][j];}}}printf(总费用为：%d\n,money);}4.4测试与分析4.4.1测试邻接矩阵的建立及存储：图2普里姆算法：10图34.4.2分析1.调试过程中遇到的问题及其解决方法（1）问题:在for循环语句中,循环变量使用控制错误解决方法:在for循环语句中,应该意识到:循环变量的执行次数总是比循环体的执行次数多一次;即最后一次的循环体执行完毕之后,循环变量又执行了一次,但是循环体却没有再执行了。（2）问题：二位数组在使用的时候数组未初始化：导致最后输出的时候的邻接矩阵出现错误；解决方法：根据输出的窗口从代码中分析发现错误，二维数组初始化之后，所得到的邻接矩阵正确输出。112.复杂度分析分析普里姆算法，假设网中有n个定点，则第一个进行初始化的循环语句的频率为n，第二个循环语句的频率为n-1。其中有两个内循环：其一是在closedge[v].lowcost中求最小值，，其频率为n-1;其二是重新选择具有最小代价的变量，其频度为n。由此，普里姆算法的时间复杂度为O(n*n),与网中的遍数无关。利用PRIM算法生成最小生成树时，求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。3.思路探索开始分析问题时，我把问题想得过于简单，结合老师讲过得算法和书上得算法设计得，但本题不是这样的，这个实际问题中有权值，而且这还是本题的关键，开始的时候造成了不少的麻烦，然后经过同学间得讨论，才看出来我的错误来，及时改了过来。还有在普里姆的操作上，可谓是麻烦重重，书上的算法根本行不通，（因为上面的是C++）后来我反复的来看书也整的一知半解的，通过老师的帮助，我又开始重做，在最后才做出来。由于开始时对于问题的错误分析，浪费了不少时间。其实，由于自己的马虎也浪费了不少的时间在不必要的地方，如：字母的大小写，自负的定义上，但还好最后这些都克服了，对我来说对数据结构又有了进一步的了解，继续学习，丰富自己！4.5附录#includestdio.h#includestdlib.h#includemalloc.h#includestring.h#defineINFINITY10000#defineM20typedefstruct{charV[M][10];intR[M][M];intvexnum;}Graph;12intlocatevex(Graph*g,chara[10]){inti;for(i=0;ig-vexnum;i++){if(strcmp(a,g-V[i])==0)returni;}if(i==g-vexnum)return-1;}intcreatgraph(Graph*g){inti=0,j,m,k,p;chara[10],b[10];printf(所有的辖区，以0为结束\n);scanf(%s,g-V[i]);while(strcmp(0,g-V[i])!=0){i++;scanf(%s,g-V[i]);}g-vexnum=i;for(i=0;ig-vexnum;i++)for(j=0;jg-vexnum;j++)g-R[i][j]=INFINITY;printf(辖区之间的路程，以000为结束标志\n);scanf(%s%s%d,a,b,&m);while(strcmp(0,a)!=0||strcmp(0,b)!=0||m!=0)13{k=locatevex(g,a);p=locatevex(g,b);if(k==-1){printf(没有%s这个辖区\n,a);return0;