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

1、个人资料整理 仅限学习使用软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师个人资料整理 仅限学习使用2018 年 1 月个人资料整理 仅限学习使用目 录1设计时间12设计目的13设计任务14设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析114.4.1测试114.4.2分析134.5附录145总结与展望20参考文献22成绩评定22个人资料整理 仅限学习使用1设计时间2018年1月16日至2018年1月21日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计 的技术基础。数据结构是实践性很强的课程。课

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

3、路及所需建设总里程。4设计内容4.1需求分析1、程序所能达到的功能：(1根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵 存储。(2根据普利姆算法计算最小生成树。(3输入各个辖区代号，名称和各辖区间直接距离地铁铺设费用与距离成正比)个人资料整理 仅限学习使用（4根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。（5输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见4.4.1测试部分。3、输出的形式及内容：包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见4.4.1测试部分。4、测试数据：四个城市ab

4、cd及其之间的距离权值，详见4.4.1测试部分。4.2总体设计4.2.1 数据类型的定义1.图的邻接矩阵存储数据类型定义：typedef structchar VM10。int RMM。int vexnum。Graph。）2.辅助数组数据类型定义：typedef structint adjvex。int lowcost。closedgeMAX。4.2.2 基本操作：CreateCity(&G个人资料整理 仅限学习使用操作结果：构造一个无向图G;LocateDistri(Graph g,int u操作结果：找出目标城市的位置；Min(Graph g,closedge closedge操作

5、结果：求出点与点之间的最短路径；Prim(G,Gdistrinam1操作结果：用普里姆算法找到连接各辖区的最短路;4.2.3 主程序的流程主程序的流程如图1所示：个人资料整理 仅限学习使用int RMM/邻接矩阵，邻接矩阵的元素值为辖区之间的距离in4.2.4 各程序模块之间的层次 调用）关系图24.3详细设计4.3.1 预处理#include #include #include #include #define INFINITY 10000#define M 20typedef struct创建图的结构体char VM10。/顶点数组，用来存储辖区的值即辖区的名称各程序模块之间的层次调用）关

6、系如图2所示：个人资料整理 仅限学习使用g-Rij=INFINITY/初始化int vexnum。/辖区的个数Graph。struct treeint weizhi。int lowcost。4.3.2 创建辖区无向图的算法int creatgraph(Graph *g /创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵int i=0,j,m,k,p。char a10,b10oprintf(*欢迎使用本程序解决地铁建设问题*n0printf(*请按照提示依次输入相关信息*n0printf(*请输入所有的辖区，以0作为结束标志*n。scanf(%s,g-Vi。/输入结点值while(strcmp

7、(0,g-Vi!=0i+oscanf(%s”,g-Vi。g-vexnum=i。for(i=0。ivexnum。i+for(j=0。jvexnum。j+个人资料整理 仅限学习使用printf(*请输入辖区之间的路程，以0 0 0为结束标志*n”。scanf(%s%s%d,a,b,&m。/输入辖区结点及辖区之间的距离while(strcmp(0,a!=0 | strcmp(0,b!=0 | m!=0k=locatevex(g,a。p=locatevex(g,b。/查找a,b在图中的位置if(k=-1printf(*对不起，输入错误，没有 $这个辖区*n,a。return 0。if(p=-1

8、printf(*对不起，输入错误，没有 $这个辖区*n,b。return 0。g-Rkp=g-Rpk=m。/k至U p和p到k之间的距离相同scanf(%s%s%d,a,b,&m。输入辖区结点及辖区之间的距离return 1。struct treeint weizhi。int lowcosto个人资料整理 仅限学习使用int minimun(struct tree *a,Graph g求出第k辖区，止匕时i辖区与k辖区之间的距离最短int i,k,m=0。for(i=0。iif(m=0 & ai.lowcost!=0m=1ok=ioif(m=1 & ai.lowcost

9、!=0if(ai.lowcostk=ioreturn k。4.3.3 定位函数int locatevex(Graph *g,char a10 /查找辖区u在辖区图中的位置int i。for(i=0。ivexnum。i+/循环执行条件是当u=Vi时停止，求i值个人资料整理 仅限学习使用if(strcmp(a,g-Vi=0return i。if(i=g-vexnumreturn -1。4.3.4 求最小生成树的结点算法int minimun(struct tree *a,Graph g求出第k辖区，止匕时i辖区与k辖区之间的距离最短int i,k,m=0。for(i=0。iif(m=0 &

10、 ai.lowcost!=0m=1ok=ioif(m=1 & ai.lowcost!=0if(ai.lowcostk=io个人资料整理 仅限学习使用return k。4.3.5 PRIM 算法及输出void MiniSpanTree_PRIM(Graph g,char a10struct tree closedgeM。int i,j,k,money=0。k=locatevex(&g,a。for(i=0。iif(i!=kclosedgei.lowcost=g.Rki。/两辖区k, i之间的距离closedgei.weizhi=k。/与辖区i相邻的最近的辖区设为辖区kclosedg

11、ek.lowcost=0。/初始化,U=uprintf(*根据您的输入建立邻接表为：*n0for(i=0oifor(j=0ojprintf(|%d| ,g.R皿,。个人资料整理 仅限学习使用printf(nn。printf(*得到应建设地铁的辖区及之间权值为：*n0for(i=1oik=minimun(closedge,g。求出最小生成树T的下一个结点，第k结点money+=closedgek.lowcost。printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost。/输出生成树的边closedgek.lowcost=0。

12、/第k顶点并入U集for(j=0ojif(g.Rkj新顶点并入集后，选择新的边，将小的边放到辅助数组中closedgej.weizhi=k。closedgej.lowcost=g.Rkj。printf(*据统计地铁的总建设路程为：%d *n,money。4,3,6 主函数模块void main(个人资料整理 仅限学习使用int ioGraph g。char a10oi=creatgraph(&g。if(iprintf(*请输入起始地点为：*n。scanf(%s,a。MiniSpanTree_PRIM(g,a。printf(*感谢使用本程序，谢谢！*n04.4测试与分析4.4.1测试测试

13、数据:1.以图3为例个人资料整理 仅限学习使用2.输入城市区域名称，如图4所示:图43.根据需要，依次输入各个区域代号和边的权值，如图5所示:讦请输入辖区之间的路程，以 000为结束标志*ah9 a c 3 ad? a a B b c 8 b d S b b 9 c d 4 c c 0 dd 00。4.根据提示，输入地铁站的起始地点如图6所示:清输入起始地点为：M揉*5.输出最终结果，如图7所示:个人资料整理 仅限学习使用4*根据您的输入建立邻接表为:NM：B!：9： ；3： ：7：；9； ：6： ：8： ：5：131 IBI 101 M：!7! !E!：4|阳；到应建设地铁的辖区及之间权值为

14、:班 Ql=b d 5P = d c 4二二姬统过地铁的总建设路程为:思谢使用本程序Oi4.4.2 分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。最首要的任务就是选择 合适的计算思路，并加以实现。经过查阅，我发现解决此类问题的核心思想就是最 小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验 过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料，询问同 学老师，结合之前上机实验的经验，我理清思路。经过编写，调试，最终完成了程 序的设计。2.算法的时间复杂度和空间复杂度的分析本程序算法的时

15、间复杂度为0何八3,空间复杂度为O(2n表达是求值，主要是 运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3.针对可能出现的输入错误，作出相应的应对措施：如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图8所示：12MM MBLXMMJOCHM KHJtlCK个人资料整理 仅限学习使用*欢迎使用本科摩空考电铁建设问题*1青接照桎示快发输入相去信息* f 请输入所宥的辖区，阳作为结束标志一0者请输入辖区之间的路程，以 00。为结束标志 Xa b 7b c 3 h f 2时不起，输入错误,校有f这个辖区*一4.5附录源程序：#include #include #in

16、clude #include #define INFINITY 10000#define M 20typedef struct创建图的结构体char VM10。/顶点数组，用来存储辖区的值即辖区的名称int RMM。/邻接矩阵，邻接矩阵的元素值为辖区之间的距离int vexnum。/辖区的个数Graph。int locatevex(Graph *g,char a10 /查找辖区u在辖区图中的位置int i。for(i=0。ivexnum。i+/循环执行条件是当u=Vi时停止，求i值个人资料整理 仅限学习使用g-Rij=INFINITY/初始化if(strcmp(a,g-Vi=0return i

17、。if(i=g-vexnumreturn -1。int creatgraph(Graph *g /创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵int i=0,j,m,k,p。char a10,b10oprintf(*欢迎使用本程序解决地铁建设问题*n0printf(*请按照提示依次输入相关信息*n0printf(*请输入所有的辖区，以0作为结束标志*n。scanf(%s,g-Vi。/输入结点值while(strcmp(0,g-Vi!=0i+oscanf(%s”,g-Vi。g-vexnum=i。for(i=0。ivexnum。i+for(j=0。jvexnum。j+个人资料整理 仅限学习使

18、用printf(*请输入辖区之间的路程，以0 0 0为结束标志*n”。scanf(%s%s%d,a,b,&m。/输入辖区结点及辖区之间的距离while(strcmp(0,a!=0 | strcmp(0,b!=0 | m!=0k=locatevex(g,a。p=locatevex(g,b。/查找a,b在图中的位置if(k=-1printf(*对不起，输入错误，没有 $这个辖区*n,a。return 0。if(p=-1printf(*对不起，输入错误，没有 $这个辖区*n,b。return 0。g-Rkp=g-Rpk=m。/k到p和p到k之间的距离相同scanf(%s%s%d,a,b,&a

19、mp;m。/输入辖区结点及辖区之间的距离return 1。struct treeint weizhi。int lowcosto个人资料整理 仅限学习使用int minimun(struct tree *a,Graph g求出第k辖区，止匕时i辖区与k辖区之间的距离 最短int i,k,m=0。for(i=0。iif(m=0 & ai.lowcost!=0m=1ok=ioif(m=1 & ai.lowcost!=0if(ai.lowcost k=ioreturn k。void MiniSpanTree_PRIM(Graph g,char a10struct tree closed

20、geM。int i,j,k,money=0。k=locatevex(&g,a。for(i=0。iif(i!=k个人资料整理 仅限学习使用closedgei.lowcost=g.Rki。两辖区k, i之间的距离closedgei.weizhi=k。/与辖区i相邻的最近的辖区设为辖区kclosedgek.lowcost=0。/初始化,U=uprintf(*根据您的输入建立邻接表为：*n0for(i=0oifor(j=0ojprintf(|%d| ,g.Rij。printf(nn。printf(*得到应建设地铁的辖区及之间权值为：*n0for(i=1oik=minimun(closedge,

21、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=0ojif(g.Rkj新顶点并入集后，选择新的边，将小的边放到辅助 数组中closedgej.weizhi=k。closedgej.lowcost=g.Rkj。printf(*据统计地铁的总建设路程为：%d *n,money。void main(int ioGraph g。char a10oi=creatgraph(&g。if(iscanf(%s,a。MiniSpanTree_PRIM(g,a。printf(*感谢使用本程序，谢谢！*nn 。printf(I*请输入起始地点为：*n个人资料整理 仅限学习使用5总结与展望5.1 对于本程序的总结与展望虽然在规定的时间内基本上完成了课程设计所要求的学习任