《数据结构课程设计—地铁建设问题》由会员分享，可在线阅读，更多相关《数据结构课程设计—地铁建设问题（22页珍藏版）》请在金锄头文库上搜索。
1、.专业整理.软件学院课程设计报告书课程名称数据结构课程设计 设计题目 地铁建设问题 专业班级 学 号 姓 名指导教师2015年1月目录1设计时间4.2设计目的.4.3设计任务44设计内容4.4.1需求分析54.2总体设计54.3详细设计74.4测试与分析.7.4.4.1 测试1.24.4.2 分析1.34.5附录145总结与展望20参考文献22成绩评定23.学习帮手.1设计时间2015年1月19日一2012年1月23日2设计目的通过课程设计，加深对数据结构这一课程所学内容的进一步理解与巩固，加深对 结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。提高程序 开发功能，能运用合
2、理的控制流程编写清晰高效的程序。训练C程序调试能力，能将一 个中小型各级组织系统联调通过。开发一个中小型系统，掌握系统研发全过程。培养分析问题、解决实际问题的能力。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地 铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。4设计内容设计思路：(1) 输入各个辖区名称和各辖区间直接距离(地铁铺设费用与距离成正比)。如:北京 到大连的直接距离是100公里(2) 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(3) 输出应该建设的地铁线路及所需建设总里程 。本程序中用到的所有抽象数据类型的定义；typedef
3、char In foTypetypedef char VertexTypeMAX_NAMEtypedef structVRType adj;In foType *info; 、ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vex num,arcnum; MGraph;typedef structVertexType adjvex;VRType lowcost;mi nsideMAX_VERTEX_NUM;4.1需求分析输出
4、应该建设的地铁线路及所需建设总里程。要求输出建设地铁的最短路线,再利用其最短路线上的权值把总的里程计算出来，已达到最省的费用，实现该地铁的建设。4.2总体设计1首先要了解本题中的要求，要用已经学的邻接矩阵，根据输入的辖区信息，建立图 模型，使用的数据结构是无向图，采用邻接矩阵存储。2. 根据普利姆算法计算最小生成树。假设WN=(V,E)是一个含有n个顶点的连通 网，TV是WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。显然，在 算法执行结束时，TV=V，而TE是E的一个子集。在算法开始执行时，TE为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有其一个顶点
5、已 经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条 加在生成树上，直至生成树中含有n-1条边为止。3. 了解了这些就可以实现它的基本操作，然后构建一个邻接矩阵，输入各个辖区构成 一个无向连通图，并把直接距离当作权值来标记，之后，进行普里姆的算法，使其生成 最小生成树，并带有权值了，把这些辖区输出，并把最小路径和最少的费用输出，这样 就完成了操作。本题出现的调用函数是：i=creatgraph(&g);Mi niSpa nTree_PRIM(g,a);k=locatevex(&g,a);mi nimun( struct tree *a,Graph g)；主程序流程
6、图：”主函数图14.3详细设计typedef structchar VM10;int RMM;int vex num;Graph;int locatevex(Graph *g,char a10)int i;for(i=0;ivex nu m;i+)if(strcmp(a,g-Vi)=0)return i;if(i=g-vex num)return -1;int creatgraph(Graph *g)int i=O,j,m,k,p;char a10,b10;printf(所有的辖区,以0为结束n);sca nf(%s,g-Vi);while(strcmp(0,g-Vi)!=0)i+;sca n
7、f(%s,g-Vi);g-vex num=i;for(i=0;ivex nu m;i+)for(j=0;jvex nu m;j+)g-Rij=INFINITY;printf(辖区之间的路程，以0 0 0为结束标志n);sca nf(%s%s%d,a,b,&m);while(strcmp(O,a)!=O | strcmp(O,b)!=O | 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；s
8、can f(%s%s%d,a,b,&m);return 1;struct treeint weizhi;int lowcost;int minimun( struct tree *a,Graph g)int i,k,m=O;for(i=0;ig.vex nu m;i+)if(m=0 & ai.lowcost!=0)m=1;k=i;if(m=1 & ai.lowcost!=0)if(ai.lowcostak .lo wcost)k=i;return k;void Mi niSpa nTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,
9、k,m on ey=0;k=locatevex(&g,a);for(i=0;ig.vex nu m;i+)if(i!=k)closedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgeko wcost=0;for(i=1;ig.vex nu m;i+)k=minimun( closedge,g);mon ey+=closedgek .lo wcost;prin tf(%d:%s %s%dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost);closedgek .lo wcost=0;for(j=0;jg.vex
10、nu m;j+)if(g.Rkjclosedgej.lowcost)closedgej.weizhi=k;closedgej.lowcost=g.Rk|;printf（” 总费用为:%dn,money）;4.4测试与分析441测试邻接矩阵的建立及存储： ! F:CYuYnbi nwv?temp,exe丨=|回！ 2S所有的辖区，以0为结束fusEun shenyang dalibeijing 01I辖区之间的路程，加0功结束麻f usliun sKenyang 34fushun dalian 48 fushun bei j ing 76 shsnyang dalian shenyan? b e
11、 i j ing 78 ialian beij ing 89普里姆算法:事 F:CYuYanbrnwwtemp.exe=旦22所有的希山以。为塔束fuEhun shenyang dalian. Beijing 0渚区之间的踣程，我0 0 0为结東标羔 口sliLLti shenyan g 34fushun daLian 48beij iag 78sheny ang daliazi 56shenyang beij7Sdalian beijinff 33DOO起始地点：shenyangslieiLyarL f ushun 34 2;fu3hLin dalian 43 3 rlienyang b&i
12、 jing 总建役暮用为：isoPress any ieyeon+inuft442分析1. 调试过程中遇到的问题及其解决方法(1)问题:在for循环语句中，循环变量使用控制错误解决方法：在for循环语句中，应该意识到：循环变量的执行次数总是比循环体的执行次数多一次；即最后一次的循环体执行完毕之后，循环变量又执行了一次，但是循环体却没 有再执行了。(2)问题：二位数组在使用的时候数组未初始化：导致最后输出的时候的邻接矩阵出现 错误；解决方法：根据输出的窗口从代码中分析发现错误，二维数组初始化之后，所得到 的邻接矩阵正确输出。2. 复杂度分析分析普里姆算法，假设网中有n个定点，则第一个进行初始化的
13、循环语句的频率为n，第二个循环语句的频率为n-1。其中有两个内循环：其一是在closedgev.lowcost中 求最小值，其频率为n-1;其二是重新选择具有最小代价的变量，其频度为n。由此，普 里姆算法的时间复杂度为 0(n*n),与网中的遍数无关。利用PRIM算法生成最小生成树时，求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。3. 思路探索开始分析问题时，我把问题想得过于简单，结合老师讲过得算法和书上得算法设计得，但本题不是这样的，这个实际问题中有权值，而且这还是本题的关键，开始的时候 造成了不少的麻烦，然后经过同学间得讨论，才看出来我的错误来，及时改了过来。还 有在普里姆的操作上，可谓是麻烦重重，书上的算法根本行不通，(因为上面的是C+)后来我反复的来看书也整的一知半解的，通过老师的帮助，我又开始重做，在最 后才做出来。由于开始时对于问题的错误分析，浪费了不少时间。其实，由于自己的马 虎也浪费了不少的时间在不必要的地方，女口：字母的大小写，自负的定义上，但还好最 后这些都克服了，对我来说对数据结构又有了进一步的了解，继续学习，丰富自己！4.5附录#in elude #i nclude #in elude #i nclude #defi ne INFINITY
