兰州道路交通网络信息查询课程设计.doc

兰州理工大学2011年春季学期 数据结构 课程设计题 目：兰州道路交通网络信息查询 专业班级：计算机五班 姓 名： 梁业洪 学 号： 09240505指导教师： 李睿 成 绩： _目录中文摘要1序言21 采用类C语言定义相关数据类型32 各模块流程图及伪码算法43 函数的调用关系图54 调试分析65 测试结果7设计总结8参考文献9致谢10附录：源程序111中文摘要在本设计实验中，我所采用的是邻接矩阵作为数据的存储结构，用不同的功能模块对两地距离和道路交通进行编辑。兰州道路交通网络信息查询等程序的目的是为人们提供各种信息查询服务：即查询任意两地之间的一条最短的简单路径，还有两地之间的距离等。最短路径的输出有各种方法，此程序中采用迪杰斯特拉算法。迪杰斯特拉算法用于求解一个有向图（也可以是无向图）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。*序言我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。图是一种复杂的非线性结构，在人工智能，工程，数学，物理，化学，计算机学科等领域中，都有着广泛的应用。我们用最短路径问题，通过一个人们熟悉的交通咨询系统实例来验证迪杰斯特拉算法。兰州道路交通网络信息查询是以半州道路为背景，设计出的一个简单的能够实现兰州道路交通网络信息查询功能的C语言程序系统，对兰州道路交通信息进行编辑，为旅客提供了两地之间的最短路径及距离。查询的实现以用户和计算机对话的方式进行，要注意人机交互的屏幕界面，由用户先择要查询的地点，输入要查询路径的起点和终点。1 采用类C语言定义相关数据类型函数有：Void Create UGN();/*造图函数*/Void ShortwstPath();/*最短路径函数*/Void narrate();/*说明函数*/Void introduce();/*介绍函数*/Void output();/*输出函数*/Void main()/*主函数*/类有：ArcCell;/*定义边的类型*/VertexType;/*定义顶点的类型*/MGraph;/*定义图的类型*/全局变量有：MGraph G;/*把图定义为全局变量*/int P2626;long int D26;*问题描述 在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差，旅行或者做其他出行时，不仅关心节省交通费用，而且对里程和所需时间也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示站点，边表示站之间的交通关系。这个系统可以回答旅客提出的各种问题。需求分析设计一个交通咨询系统，能让旅客咨询从一个站点到另一个站顶点之间的最短路径或最短距离等。对于不同咨询要求，可查询站之间的路程或所走的距离。该设计共三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个站点之间的最短路径问题。2各模块流程图及伪码算法1其功能模块图如下：开始选择服务1或2输入地点编号查询地点信息输入开始地点编号结束输入结束地点编号结束2伪码算法如下：Void ShortwstPath(mum) /*最短路径函数*/Int mum;int v,w,I,t;Int final 26;Int min;for (v=0;v26;+v)/*初始化*/ finalv=0; /*标志数组初始化*/ Dv=G.arcsnumv.adj; for(w=0;w33;+w) Pvw=0;/*设空路径*/ if(Dv20000)/*v,v0间有边存在*/ Pvnum=1;Pvv=1;/*到v的最短路径上包含v0及v*/ /*if*/ Dnum=0; finalnum=1;/*初始化，v0顶点属于B集*/ /*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到B集*/ for(i=0;i33;+i)/*其余G.vexnum-1各顶点*/ min=20000; for(w=0;w33;+w) if(!finalw)/*w顶点在V-S中*/ if(Dwmin)v=w;min=Dw;/*w顶点离v0更近*/ finalv=1;/*离v0顶点最近的v加入B*/ for(w=0;w33;+w)/*更新当前最短路径及距离*/ if(!finalw&(min+G.arcsvw.adj)Dw) Dw=min+G.arcsvw.adj;/*修改D和P数组*/ for(t=0;t33;t+) Pwt=Pvt; Pww=1; /*if*/ /*for*/*函数调用关系图造图函数Creati UDN ()主函数main()说明函数narrate ()介绍函数introduce ()迪杰斯特拉算法Dijdstra ()最短路径函数ShortwstPath ()输出函数output ()首先用一个数组来定义邻接矩阵，并定义当前顶点数，顶点用来表示地点，数组的值用来表示路径长度。然后给各个顶点赋予初值，亦即兰州各个地方的名称，并确定各个地方之间的距离，还要标注各个地方的简单信息，让旅客一目了然，并用迪杰斯特拉算法来实现最短路径的求解。之后在主函数main()中调用各个子函数，显示两地点之间的最短路径、某地点相关信息。整个程序功能就这样实现了。4调试分析1调试中遇到的问题及对问题的解决方法遇到的问题：在调试时，有时会把值输错，导致超出范围，输出错误结果或程序直接结束。或者有时候还会在错误的环境下运行，例如在win-TC中调试运行时，中文不能正常显示，而到visual c+中运行就可以正常显示。解决方法：首先注意值的范围，输入在范围内的任意值。其次注意运行环境，有中文的一定要在中文运行环境中进行。2 算法的时间复杂度和空间复杂度时间复杂度O(n2).空间复杂度O(n2).*测试结果我对程序进行了测试，选择运行程序选择Y或y,然后回车，得到如下结果：若要查询地点信息，输入服务项目编号1然后回车，得到如下结果：选择你要查询的地点编号，例如要查询兰州交通大学，输入对应编号0然后回车，得到结果如下：若要查询两地之间的最短路径和最短距离，则在选择服务项目时选择2并回车，得到如下结果：输入要查询的开始地点，例如要查询兰州交通大学到兰州理工大学西校区的最短路径，输入开始地点兰州交通大学的编号0回车，得到结果如下：输入要查询的结束地点，例如查询兰州交通大学到兰州理工大学西校区，输入兰州理工大学西校区的编号回车，得到结果如下：*设计总结：在这次数据结构课程设计中,我的题目是: 兰州道路交通网络信息查询,通过对该题目的设计,我加深了对图的建立和对迪杰斯特拉算法的理解,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。两到三周的时间虽然很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各科知识融会，组织，来配合学习，总之,这段时间中我收益很大，学到很多。在课程设计时我遇到了很多的问题，但在同学的帮助和对各种资料的查阅中，最终将问题解决，这培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。在以后的学习中我会更注意各方面的能力的协调和发展。参考文献1 谭浩强.c语言程序设计. 清华大学出版社.2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3算法与数据结构。*致谢：在这两到三周的时间里，时间虽短却很充实，感谢指导老师和所有帮助过我的同学们。*源程序#include string.h#include stdio.htypedef struct ArcCellint adj;char *info;ArcCell; /*定义边的类型*/typedef struct VertexTypeint number;char *place;VertexType; /*定义顶点的类型*/typedef structVertexType vex26;ArcCell arcs2626;int vexnum,arcnum;MGraph; /*定义图的类型*/MGraph G; /*把图定义为全局变量*/int P2626;long int D26;void CreateUDN(v,a) /*造图涵数*/int v,a; int i,j;G.vexnum=v;G.arcnum=a;for(i=0;iG.vexnum;+i) G.vexi.number=i;G.vex0.place=兰州交通大学;G.vex1.place=甘肃政法学院;G.vex2.place=兰州师范大学;G.vex3.place=师大附中;G.vex4.place=西站;G.vex5.place=公交公司;G.vex6.place=小西湖;G.vex7.place=兰州理工大本部;G.vex8.place=西湖公园;G.vex9.place=文化宫;G.vex10.place=西关十字;G.vex11.place=陆军总院;G.vex12.place=石油大厦;G.vex13.place=中山桥;G.vex14.place=兰州剧院;G.vex15.place=南关十字;G.vex16.place=五泉山;G.vex17.place=广场西口;G.vex18.place=广场东口;G.vex19.place=兰州大学;G.vex20.place=火车站;G.vex21.place=市政府;G.vex22.place=雁滩;G.vex23.place=杨家桥;G.vex24.place=龚家湾;G.vex25.place=兰州理工大西校区;for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) G.arcsij.adj=23000;G.arcs01.adj=G.arcs10.adj=500;G.arcs12.adj=G.arcs21.adj=600;G.arcs23.adj=G.arcs32.adj=960;G.arcs34.adj=G.arcs43.adj=2320;G.arcs45.adj=G.arcs54.adj=1200;G.arcs56.adj=G.arcs65.adj=780;G.arcs67.adj=G.arcs76.adj=1006;G.arcs68.adj=G.arcs86.adj=574;G.arcs89.adj=G.arcs98.adj=540;G.arcs910.adj=G.arcs109.adj=670;G.arcs116.adj=G.arcs611.adj=640;G.arcs612.adj=G.arcs126.adj=802;G.arcs1213.adj=G.arcs1312.adj=625;G.arcs1314.adj=G.arcs1413.adj=487;G.arcs1014.adj=G.arcs1410.adj=280;G.arcs1415.adj=G.arcs1514.adj=511;G.arcs1516.adj=G.arcs1615.adj=1389;G.arcs1517.adj=G.arcs1715.adj=956;G.arcs1718.adj=G.arcs1817.adj=479;G.arcs1819.adj=G.arcs1918.adj=1876;G.arcs1920.adj=G.arcs2019.adj=765;G.arcs2021.adj=G.arcs2120.adj=5969;G.arcs1321.adj=G.arcs2113.adj=895;G.arcs2122.adj=G.arcs2221.adj=2067;G.arcs2223.adj=G.arcs2322.adj=9625;G.arcs2324.adj=G.arcs3123.adj=800;G.arcs2425.adj=G.arcs2524.adj=329; void narrate() /*说明函数*/int i,k=0;printf(n*欢迎使用该程序!*n);printf(n以下是选项:nn);for(i=0;i32的数字编号！nn); break; void ShortwstPath(num) /*最短路径函数*/int num; int v,w,i,t; int final26; int min; for(v=0;v26;+v)/*初始化*/ finalv=0; /*标志数组初始化*/ Dv=G.arcsnumv.adj; for(w=0;w26;+w) Pvw=0;/*设空路径*/ if(Dv23000)/*v,v0间有边存在*/ Pvnum=1;Pvv=1;/*到v的最短路径上包含v0及v*/ /*if*/ Dnum=0; finalnum=1;/*初始化，v0顶点属于B集*/ /*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到B集*/ for(i=0;i26;+i)/*其余G.vexnum-1各顶点*/ min=23000; for(w=0;w26;+w) if(!finalw)/*w顶点在V-S中*/ if(Dwmin)v=w;min=Dw;/*w顶点离v0更近*/ finalv=1;/*离v0顶点最近的v加入B*/ for(w=0;w26;+w)/*更新当前最短路径及距离*/ if(!finalw&(min+G.arcsvw.adj)Dw) Dw=min+G.arcsvw.adj;/*修改D和P数组*/ for(t=0;t26;t+) Pwt=Pvt; Pww=1; /*if*/ /*for*/void output(place1,place2) /*输出函数*/int place1;int place2; int a,b,c,d,q=0; a=place2; if(a!=place1) printf(n最短路径从 %s 到 %sn,G.vexplace1.place,G.vexplace2.place