《2022年数据结构课程方案地铁建设问题 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构课程方案地铁建设问题 .pdf(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、个人资料整理仅限学习使用软 件 学 院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2018年 1 月精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 24 页个人资料整理仅限学习使用目录1 设计时间 12 设计目的 13 设计任务 14 设计内容 14.1 需求分析 14.2 总体设计 24.3 详细设计 44.4 测试与分析11 4.4.1测试 114.4.2分析 134.5 附录 145 总结与展望20 参考文献22 成绩评定22 精选学习资料 - - - - - - - - - 名师归纳总结 -
2、 - - - - - -第 2 页,共 24 页个人资料整理仅限学习使用1 设计时间2018年 1 月 16 日至 2018年 1 月 21 日2 设计目的数据结构是计算机专业的核心课程,是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C 语言的算法转换成C 程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工作者工作作风的训练,将起到显著的促进作用。3 设计任务某城市要在各个辖区
3、之间修建地铁,由于地铁建设费用昂贵,因此需要合理安排地铁建设线路,使市民可以沿地铁到达各个辖区,并使总费用最小。1. 输入各个辖区名称和各辖区间直接距离根据输入的辖区信息,建立图模型,使用的数据结构是无向图,采用邻接矩阵存储。(2根据普利姆算法计算最小生成树。(3 输入各个辖区代号,名称和各辖区间直接距离根据辖区距离信息,计算出应该在哪些辖区建立地铁线路。(5输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容:包括城市名称、城市间距离权值、起始地点,详见4.4.1 测试部分。3、输出的形式及内容:包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程,详见4.4.1 测试部分
4、。4、测试数据:四个城市 abcd 及其之间的距离权值,详见4.4.1 测试部分。4.2 总体设计4.2.1 数据类型的定义1.图的邻接矩阵存储数据类型定义:typedef struct char VM10 。int RMM 。int vexnum。Graph。)2.辅助数组数据类型定义:typedef struct int adjvex。int lowcost。 closedgeMAX 。4.2.2 基本操作:CreateCity(&G 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 24 页个人资料整理仅限学习使用操作结果:构造一个
5、无向图G;LocateDistri(Graph g,int u 操作结果:找出目标城市的位置;Min(Graph g,closedge closedge 操作结果:求出点与点之间的最短路径;Prim(G,G.distrinam1 操作结果:用普里姆算法找到连接各辖区的最短路;4.2.3 主程序的流程主程序的流程如图1 所示:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 24 页个人资料整理仅限学习使用图 1 4.2.4 各程序模块之间的层次 调用)关系各程序模块之间的层次 调用)关系如图 2 所示:图 2 4.3 详细设计4.3.1
6、预处理#include #include #include #include #define INFINITY 10000 #define M 20 typedef struct /创建图的结构体 char VM10 。 /顶点数组,用来存储辖区的值即辖区的名称 int RMM 。 /邻接矩阵,邻接矩阵的元素值为辖区之间的距离精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 24 页个人资料整理仅限学习使用 int vexnum。 /辖区的个数Graph。struct tree int weizhi。 int lowcost。 。4.3.
7、2 创建辖区无向图的算法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(0,g-Vi!=0 i+。 scanf(%s,g-Vi 。 g-vexnum=i。 for(i=0。ivexnum。i+ for(j=0。jvexnum。j+ g-Rij
8、=INFINITY。/初始化精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 24 页个人资料整理仅限学习使用 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(*对不起,输入错误,没有 %s这个辖区 *n,a 。return 0。 i
9、f(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 tree int weizhi。 int lowcost。 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 24 页个人资料整理仅限学习使用int minimun(struct tree *a,Graph g /求出第 k 辖区,此时 i 辖区与 k 辖区之
10、间的距离最短 int i,k,m=0。 for(i=0。i if(m=0 & ai.lowcost!=0 m=1。 k=i。 if(m=1 & ai.lowcost!=0 if(ai.lowcost k=i。 return k。 4.3.3 定位函数int locatevex(Graph *g,char a10 /查找辖区 u在辖区图中的位置 int i。for(i=0。ivexnum。i+/循环执行条件是当u=Vi 时停止,求 i 值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 24 页个人资料整理仅限学习使用 if(strcmp(
11、a,g-Vi=0 return i。 if(i=g-vexnum return -1。 4.3.4 求最小生成树的结点算法int minimun(struct tree *a,Graph g /求出第 k 辖区,此时 i 辖区与 k 辖区之间的距离最短 int i,k,m=0。for(i=0。i if(m=0 & ai.lowcost!=0 m=1。k=i。 if(m=1 & ai.lowcost!=0 if(ai.lowcost k=i。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 24 页个人资料整理仅限学习使用return
12、k。 4.3.5PRIM 算法及输出void MiniSpanTree_PRIM(Graph g,char a10 struct tree closedgeM。 int i,j,k,money=0。 k=locatevex(&g,a。for(i=0。i if(i!=k closedgei.lowcost=g.Rki 。 /两辖区 k,i 之间的距离closedgei.weizhi=k。 /与辖区 i 相邻的最近的辖区设为辖区k closedgek.lowcost=0。/初始化, U=u printf(*根据您的输入建立邻接表为:*n。 for(i=0。i for(j=0。j printf(|%
13、d| ,g.Rij 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 24 页个人资料整理仅限学习使用 printf(nn 。 printf(*得到应建设地铁的辖区及之间权值为:*n 。 for(i=1。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
14、=0。 /第 k 顶点并入 U 集 for(j=0。j if(g.Rkj /新顶点并入集后,选择新的边,将小的边放到辅助数组中 closedgej.weizhi=k。 closedgej.lowcost=g.Rkj 。 printf(*据统计地铁的总建设路程为:%d *n,money。 4,3,6 主函数模块void main( 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 24 页个人资料整理仅限学习使用 int i。 Graph g。 char a10。 i=creatgraph(&g。 if(i printf(*请输入起始地点
15、为: *n。 scanf(%s,a。 MiniSpanTree_PRIM(g,a。 printf(*感谢使用本程序,谢谢!*n。 4.4 测试与分析4.4.1 测试测试数据:1.以图 3为例精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页,共 24 页个人资料整理仅限学习使用图 3 2.输入城市区域名称,如图4所示:图 4 3.根据需要,依次输入各个区域代号和边的权值,如图5所示:图 5 4.根据提示,输入地铁站的起始地点如图6所示:图 6 5.输出最终结果,如图7所示:精选学习资料 - - - - - - - - - 名师归纳总结 - -
16、 - - - - -第 14 页,共 24 页个人资料整理仅限学习使用图 7 4.4.2 分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初,我对于整个算法的思路的理解并不清晰。最首要的任务就是选择合适的计算思路,并加以实现。经过查阅,我发现解决此类问题的核心思想就是最小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料,询问同学老师,结合之前上机实验的经验,我理清思路。经过编写,调试,最终完成了程序的设计。2.算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为O(n3,
17、空间复杂度为O(2n 表达是求值,主要是运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3.针对可能出现的输入错误,作出相应的应对措施:如输入辖区之间的权值时,当输入错误的辖区时会有报错提示,如图8 所示:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 24 页个人资料整理仅限学习使用图 8 4.5 附录源程序:#include #include #include #include #define INFINITY 10000 #define M 20 typedef struct /创建图的结构体 char VM
18、10 。 /顶点数组,用来存储辖区的值即辖区的名称 int RMM 。 /邻接矩阵,邻接矩阵的元素值为辖区之间的距离 int vexnum。 /辖区的个数Graph。int locatevex(Graph *g,char a10 /查找辖区 u在辖区图中的位置 int i 。 for(i=0。ivexnum。i+/循环执行条件是当u=Vi 时停止,求 i 值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页,共 24 页个人资料整理仅限学习使用 if(strcmp(a,g-Vi=0 return i。 if(i=g-vexnum return
19、 -1。 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(0,g-Vi!=0 i+。scanf(%s,g-Vi 。 g-vexnum=i。 for(i=0。ivexnum。i+ for(j=0。jvexnum。j+ g-Rij=INFINIT
20、Y。/初始化精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页,共 24 页个人资料整理仅限学习使用 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(*对不起,输入错误,没有%s这个辖区 *n,a 。return 0。 if(p=-1 pr
21、intf(*对不起,输入错误,没有%s这个辖区 *n,b 。return 0。 g-Rkp=g-Rpk=m 。/k 到 p 和 p 到 k 之间的距离相同scanf(%s%s%d,a,b,&m。 /输入辖区结点及辖区之间的距离 return 1。 struct tree int weizhi。 int lowcost。 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 24 页个人资料整理仅限学习使用int minimun(struct tree *a,Graph g /求出第 k 辖区,此时 i 辖区与 k 辖区之间的距离最短 in
22、t i,k,m=0。 for(i=0。i if(m=0 & ai.lowcost!=0 m=1。k=i。 if(m=1 & ai.lowcost!=0 if(ai.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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页,共 24 页个人资料整理仅限学习使用 if(i!=k closedg
23、ei.lowcost=g.Rki 。 /两辖区 k,i 之间的距离closedgei.weizhi=k。 /与辖区 i 相邻的最近的辖区设为辖区k closedgek.lowcost=0。/初始化, U=u printf(*根据您的输入建立邻接表为:*n。 for(i=0。i for(j=0。j printf(|%d| ,g.Rij 。 printf(nn 。 printf(*得到应建设地铁的辖区及之间权值为:*n 。 for(i=1。i k=minimun(closedge,g。 /求出最小生成树 T 的下一个结点,第k 结点 money+=closedgek.lowcost。 printf
24、(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost。 /输出生成树的边精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页,共 24 页个人资料整理仅限学习使用 closedgek.lowcost=0。 /第 k 顶点并入 U 集 for(j=0。j if(g.Rkj /新顶点并入集后,选择新的边,将小的边放到辅助数组中 closedgej.weizhi=k。closedgej.lowcost=g.Rkj 。 printf(*据统计地铁的总建设路程为:%d *n,money。 v
25、oid main( int i 。 Graph g。 char a10。 i=creatgraph(&g。 if(i printf(*请输入起始地点为: *n。scanf(%s,a。MiniSpanTree_PRIM(g,a。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页,共 24 页个人资料整理仅限学习使用 printf(*感谢使用本程序,谢谢! *nn 。 5 总结与展望5.1 对于本程序的总结与展望虽然在规定的时间内基本上完成了课程设计所要求的学习任务,但是由于个人能力以及时间上的局限性,造成设计的程序还存在着很多需要改进的地方。比
26、如没有很完整多样的输入与输出的报错处理程序,不能很好的应对程序在使用过程中出现的各种错误和突发事件;还有在辖区之间权值的输入过程中必须输入每个辖区与自身的“ 0”权值,否则会造成输出错误的邻接表等等问题。我希望在今后的学习生活中,在老师的教导下,更加刻苦努力地学习相关知识,进一步完善这个程序。5.2 对于数据结构课程设计的总结此次课程设计让我更加深入了解大一学到的C 语言和这个学期学到的数据结构课程。课设题目要求不仅要求对课本知识有较深刻的了解,同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。程序设计时,不能怕遇到错误,在实际操作过程中犯的一些错误还会有意外的收获,这正是
27、实践操作的意义所在。在具体操作中巩固这学期所学的数据结构的理论知识,达到课程设计的基本目的,也发现自己的不足之出,如程序逻辑的理解力不够强等等。与此同时,我也体会到C 语言所具有的语句简洁,使用灵活,执行效率高等特点。特别是对图这种数据结构有了深刻的理解。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页,共 24 页个人资料整理仅限学习使用参考文献1 严蔚敏,吴伟民编著. 北京:清华大学出版社,2007 2 谭浩强编著 .C 程序设计 第二版) . 北京:清华大学出版社,2004 3 谭浩强编著 .C 程序设计题解与上机指导第二版) . 北京:清华大学出版社,1999 4 姚诗斌 . 数据库系统基础. 计算机工程与应用,1981 年第 8 期5 谭浩强,张基温,唐永炎编著.C 语言程序设计教程. 北京:高等教育出版社,1992 6 丁峻岭编著 .C 语言程序设计. 中国铁道出版社,2003 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页,共 24 页个人资料整理仅限学习使用成绩评定成绩教师签字精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页,共 24 页
限制150内