地铁建设问题_数据结构课程设计(25页).doc

-地铁建设问题_数据结构课程设计-第 22 页软 件 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师 2013 年 1 月目 录1 设计时间12 设计目的13设计任务14 设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析114.4.1测试114.4.2分析134.5 附录145 总结与展望20参考文献22成绩评定221 设计时间2013年1月16日至2013年1月21日2 设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。1. 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）；2. 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路；3. 输出应该建设的地铁线路及所需建设总里程。4 设计内容 4.1需求分析1、程序所能达到的功能：(1)根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。(2)根据普利姆算法计算最小生成树。(3)输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比）。(4)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。(5)输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见4.4.1测试部分。3、输出的形式及内容： 包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见4.4.1测试部分。4、测试数据： 四个城市abcd及其之间的距离权值，详见4.4.1测试部分。4.2总体设计4.2.1数据类型的定义1.图的邻接矩阵存储数据类型定义：typedef struct char 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)操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam1)操作结果：用普里姆算法找到连接各辖区的最短路；4.2.3主程序的流程主程序的流程如图1所示： 图14.2.4各程序模块之间的层次（调用）关系各程序模块之间的层次（调用）关系如图2所示：图24.3详细设计4.3.1预处理#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h>#define INFINITY 10000#define M 20 typedef struct /创建图的结构体 char VM10; /顶点数组，用来存储辖区的值即辖区的名称 int RMM; /邻接矩阵，邻接矩阵的元素值为辖区之间的距离 int vexnum; /辖区的个数Graph; struct tree int weizhi; int lowcost;4.3.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;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 | 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); /输入辖区结点及辖区之间的距离 return 1;struct tree int 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;4.3.3定位函数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; 4.3.4求最小生成树的结点算法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;4.3.5 PRIM算法及输出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相邻的最近的辖区设为辖区k closedgek.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结点 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);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测试与分析4.4.1测试测试数据：1.以图3为例图 32.输入城市区域名称，如图4所示：图 43.根据需要，依次输入各个区域代号和边的权值，如图5所示：图 54.根据提示，输入地铁站的起始地点如图6所示：图 65.输出最终结果，如图7所示：图 74.4.2分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。最首要的任务就是选择合适的计算思路，并加以实现。经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。经过编写，调试，最终完成了程序的设计。2.算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为O(n3)，空间复杂度为O(2n) 表达是求值，主要是运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3.针对可能出现的输入错误，作出相应的应对措施：如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图8所示：图84.5 附录源程序：#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h>#define INFINITY 10000#define M 20 typedef struct /创建图的结构体 char VM10; /顶点数组，用来存储辖区的值即辖区的名称 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,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->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 | 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); /输入辖区结点及辖区之间的距离 return 1;struct tree int 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;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相邻的最近的辖区设为辖区k closedgek.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结点 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);printf("*感谢使用本程序，谢谢！*nn ");5 总结与展望5.1对于本程序的总结与展望虽然在规定的时间内基本上完成了课程设计所要求的学习任务，但是由于个人能力以及时间上的局限性，造成设计的程序还存在着很多需要改进的地方。比如没有很完整多样的输入与输出的报错处理程序，不能很好的应对程序在使用过程中出现的各种错误和突发事件；还有在辖区之间权值的输入过程中必须输入每个辖区与自身的“0”权值，否则会造成输出错误的邻接表等等问题。我希望在今后的学习生活中，在老师的教导下，更加刻苦努力地学习相关知识，进一步完善这个程序。5.2对于数据结构课程设计的总结此次课程设计让我更加深入了解大一学到的C语言和这个学期学到的数据结构课程。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。程序设计时，不能怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，这正是实践操作的意义所在。在具体操作中巩固这学期所学的数据结构的理论知识，达到课程设计的基本目的，也发现自己的不足之出，如程序逻辑的理解力不够强等等。与此同时，我也体会到C语言所具有的语句简洁，使用灵活，执行效率高等特点。特别是对图这种数据结构有了深刻的理解。参考文献1 严蔚敏，吴伟民编著.北京：清华大学出版社，2007 2 谭浩强编著.C程序设计（第二版）.北京：清华大学出版社，20043 谭浩强编著.C程序设计题解与上机指导（第二版）.北京：清华大学出版社，19994 姚诗斌.数据库系统基础.计算机工程与应用，1981年第8期5 谭浩强，张基温，唐永炎编著.C语言程序设计教程.北京：高等教育出版社，19926 丁峻岭编著.C语言程序设计.中国铁道出版社，2003成绩评定成绩 教师签字