地铁建设问题数据结构大学课程方案设计

1、课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2013年 1 月目录1 设计时间 12 设计目的 13 设计任务14 设计内容14.1 需求分析14.2 总体设计24.3 详细设计44.4 测试与分析11测试11分析134.5 附录145 总结与展望20参考文献22成绩评定 221 设计时间2013年 1月 16日至 2013年 1月 21日2 设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C 语言的算法

2、转换成C 程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3 设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。1. 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）；2. 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路；3. 输出应该建设的地铁线路及所需建设总里程。4 设计内容4.1 需求分析1、程序所能达到的功能：(1) 根据输入的辖区信息

3、，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。(2)根据普利姆算法计算最小生成树。(3) 输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比）。(4)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(5)输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见测试部分。3、输出的形式及内容：包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见 测试部分。4、测试数据：四个城市 abcd及其之间的距离权值，详见测试部分。4.2 总体设计数据类型的定义1.图的邻接矩阵存储数据类型定义：typedef s

4、tructchar VM10 。int RMM 。int vexnum。Graph。）2.辅助数组数据类型定义：typedef structint adjvex。int lowcost 。closedgeMAX 。基本操作：CreateCity(&G)操作结果：构造一个无向图G；LocateDistri(Graph g,int u)操作结果：找出目标城市的位置；Min(Graph g,closedge closedge)操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam1)操作结果：用普里姆算法找到连接各辖区的最短路；主程序的流程主程序的流程如图1 所示：图 1各

5、程序模块之间的层次（调用）关系各程序模块之间的层次（调用）关系如图2 所示：图 24.3 详细设计预处理#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#define INFINITY 10000#define M 20typedef struct /创建图的结构体char VM10 。 /顶点数组，用来存储辖区的值即辖区的名称int RMM 。 /邻接矩阵，邻接矩阵的元素值为辖区之间的距离int vexnum。 /辖区的个数Graph 。str

6、uct treeint weizhi 。int lowcost。 。创建辖区无向图的算法int creatgraph(Graph *g) /创建辖区无向图，图中含有n 个结点，创建辖区邻接矩阵int i=0,j,m,k,p 。char a10,b10。printf("*欢迎使用本程序解决地铁建设问题*n")。printf("*请按照提示依次输入相关信息*n")。printf("* 请输入所有的辖区，以0 作为结束标志 *n") 。scanf("%s",g->Vi) 。 /输入结点值while(strcmp(&

7、quot;0",g->Vi)!=0)i+ 。scanf("%s",g->Vi) 。g->vexnum=i 。for(i=0 。 i<g->vexnum 。i+)for(j=0 。j<g->vexnum 。j+)g->Rij=INFINITY。/初始化printf("* 请输入辖区之间的路程，以0 0 0 为结束标志 *n") 。scanf("%s%s%d",a,b,&m)。 /输入辖区结点及辖区之间的距离while(strcmp("0",a)!=0

8、| strcmp("0",b)!=0 | m!=0)k=locatevex(g,a)。 p=locatevex(g,b)。/ 查找 a,b 在图中的位置if(k=-1)printf("*对不起，输入错误，没有%s 这个辖区 *n",a) 。return 0。if(p=-1)printf("*对不起，输入错误，没有%s 这个辖区 *n",b)。return 0。g->Rkp=g->Rpk=m。/k 到 p 和 p 到 k 之间的距离相同scanf("%s%s%d",a,b,&m)。 /输入辖区结点

9、及辖区之间的距离return 1。struct treeint weizhi 。int lowcost。 。int minimun(struct tree *a,Graph g) / 求出第 k 辖区，此时 i 辖区与 k 辖区之间的距离最短int i,k,m=0 。for(i=0 。 i<g.vexnum。i+)if(m=0 && ai.lowcost!=0)m=1。k=i 。if(m=1 && ai.lowcost!=0)if(ai.lowcost<ak.lowcost)k=i 。return k。定位函数int locatevex(Graph

10、*g,char a10) /查找辖区 u 在辖区图中的位置int i 。for(i=0 。i<g->vexnum 。 i+)/ 循环执行条件是当u=Vi 时停止，求 i 值if(strcmp(a,g->Vi)=0)return i。if(i=g->vexnum)return -1。求最小生成树的结点算法int minimun(struct tree *a,Graph g) / 求出第 k 辖区，此时 i 辖区与 k 辖区之间的距离最短int i,k,m=0 。for(i=0 。i<g.vexnum。 i+)if(m=0 && ai.lowcost!

11、=0)m=1。k=i 。if(m=1 && ai.lowcost!=0)if(ai.lowcost<ak.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 。i<g.vexnum。 i+)if(i!=k)closedgei.lowcost=g.Rki 。 /两辖区 k，i 之间的距离closedgei.weizhi=k 。 / 与辖区 i 相邻

12、的最近的辖区设为辖区kclosedgek.lowcost=0。/初始化， U=uprintf("*根据您的输入建立邻接表为:*n")。for(i=0 。 i<g.vexnum。i+)for(j=0 。j<g.vexnum。 j+)printf("|%d| ",g.Rij) 。printf("nn") 。printf("*得到应建设地铁的辖区及之间权值为:*n") 。for(i=1 。 i<g.vexnum。i+)k=minimun(closedge,g)。 /求出最小生成树T 的下一个结点，第k

13、结点money+=closedgek.lowcost。printf("%d:%s%s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost) 。 / 输出生成树的边closedgek.lowcost=0。 /第 k 顶点并入 U 集for(j=0 。j<g.vexnum。j+)if(g.Rkj<closedgej.lowcost)/新顶点并入集后，选择新的边，将小的边放到辅助数组中closedgej.weizhi=k 。closedgej.lowcost=g.Rkj 。printf("*据统计地铁的总建设路

14、程为：%d *n",money)。4,3,6 主函数模块void main()int i 。Graph g。char a10。i=creatgraph(&g)。if(i)printf("*请输入起始地点为： *n")。scanf("%s",a)。MiniSpanTree_PRIM(g,a)。printf("*感谢使用本程序，谢谢！*n")。4.4 测试与分析测试测试数据：1.以图 3 为例图 32.输入城市区域名称，如图4 所示：图 43.根据需要，依次输入各个区域代号和边的权值，如图5 所示：图 54.根据提示，输

15、入地铁站的起始地点如图6 所示：图 65.输出最终结果，如图7 所示：图 7分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。最首要的任务就是选择合适的计算思路，并加以实现。经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。经过编写，调试，最终完成了程序的设计。2.算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为 O(n3)，空间复杂度

16、为 O(2n) 表达是求值，主要是运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3.针对可能出现的输入错误，作出相应的应对措施：如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图8 所示：图 84.5 附录源程序：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#define INFINITY 10000#define M 20typedef struct /创建图的结构体char VM10 。 /顶点数组，用来存

17、储辖区的值即辖区的名称int RMM 。 /邻接矩阵，邻接矩阵的元素值为辖区之间的距离int vexnum。 /辖区的个数Graph 。int locatevex(Graph *g,char a10) /查找辖区 u 在辖区图中的位置int i 。for(i=0 。i<g->vexnum。 i+)/ 循环执行条件是当u=Vi 时停止，求 i 值if(strcmp(a,g->Vi)=0)return i。if(i=g->vexnum)return -1。int creatgraph(Graph *g) /创建辖区无向图，图中含有n 个结点，创建辖区邻接矩阵int i=0,

18、j,m,k,p 。char a10,b10。printf("*欢迎使用本程序解决地铁建设问题*n")。printf("*请按照提示依次输入相关信息*n")。printf("* 请输入所有的辖区，以0 作为结束标志 *n") 。scanf("%s",g->Vi) 。 /输入结点值while(strcmp("0",g->Vi)!=0)i+ 。scanf("%s",g->Vi) 。g->vexnum=i 。for(i=0 。 i<g->vexnu

19、m 。i+)for(j=0 。j<g->vexnum 。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)。 / 查找 a,b 在图中的位置 if(k=-1)printf(&

20、quot;*对不起，输入错误，没有%s 这个辖区 *n",a) 。return 0。if(p=-1)printf("*对不起，输入错误，没有%s这个辖区 *n",b)。return 0。g->Rkp=g->Rpk=m。/k 到 p 和 p 到 k 之间的距离相同scanf("%s%s%d",a,b,&m)。 /输入辖区结点及辖区之间的距离return 1。struct treeint weizhi 。int lowcost。 。int minimun(struct tree *a,Graph g) / 求出第 k 辖区，此时

21、 i 辖区与 k 辖区之间的距离最短int i,k,m=0 。for(i=0 。 i<g.vexnum。i+)if(m=0 && ai.lowcost!=0)m=1。k=i 。if(m=1 && ai.lowcost!=0)if(ai.lowcost<ak.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 。i<g.vexnum。i

22、+)if(i!=k)closedgei.lowcost=g.Rki 。 /两辖区 k，i 之间的距离closedgei.weizhi=k 。 / 与辖区 i 相邻的最近的辖区设为辖区kclosedgek.lowcost=0。/初始化， U=uprintf("*根据您的输入建立邻接表为:*n")。for(i=0 。 i<g.vexnum。i+)for(j=0 。 j<g.vexnum。j+)printf("|%d| ",g.Rij) 。printf("nn") 。printf("*得到应建设地铁的辖区及之间权值为:

23、*n") 。for(i=1 。 i<g.vexnum。i+)k=minimun(closedge,g)。 /求出最小生成树T 的下一个结点，第k 结点money+=closedgek.lowcost。printf("%d:%s%s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost) 。 / 输出生成树的边closedgek.lowcost=0。 /第 k 顶点并入 U 集for(j=0 。j<g.vexnum。j+)if(g.Rkj<closedgej.lowcost)/新顶点并入集后，选择新的边，将小的边放到辅助数组中closedgej.weizhi=k 。closedgej.lowcost=g.Rkj 。printf("*据统计地铁的总建设路程为：%d *n",money)。void main()int i 。Graph g。char a10。i=creatgraph(&g)。if(i)printf("*请输入起始地点为： *n")。scanf("%s",a)。MiniSpanTree_PRIM(g,a)。pr