兰州道路交通网络信息查询课程方案

1、兰州理工大学2018年春季学期 数据结构课程设计 题目：兰州道路交通网络信息查询专业班级：计算机五班姓名：梁业洪学号：09240505指导教师：李睿成绩：目录中文摘要1序言21. 采用类C语言定义相关数据类型 32. 各模块流程图及伪码算法 43. 函数的调用关系图54. 调试分析65. 测试结果7设计总结8参考文献9致谢10附录：源程序111中文摘要在本设计实验中，我所采用的是邻接矩阵作为数据的存储结构 ，用不同的功能模块对两地距离和道路交通进行编辑。 兰州道路交通网络信息查询等程序的目的是为人们提供各种信息查 询服务：即查询任意两地之间的一条最短的简单路径，还有两地之 间的距离等。最短路径

2、的输出有各种方法，此程序中采用迪杰斯特 拉算法。迪杰斯特拉算法用于求解一个有向图 也可以是无向图）的 一个点 称之为原点）到其余各点 称之为周边点）的最短路径问题 。*序言我们在对一些问题进行求解时，会发现有些问题很难找到规律 ，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速 度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从 所有可能的情况中，删除那些不符合条件的解。图是一种复杂的非 线性结构，在人工智能，项目，数学，物理，化学，计算机学科等 领域中，都有着广泛的应用。我们用最短路径问题，通过一个人们 熟悉的交通咨询系统实例来验证迪杰斯特拉算法。兰州道路交通网络信息查询是以

3、半州道路为背景，设计出的一 个简单的能够实现兰州道路交通网络信息查询功能的 C语言程序系 统，对兰州道路交通信息进行编辑，为旅客提供了两地之间的最短 路径及距离。的屏幕界面，由用户先择要查询的地点，输入要查询路径的起点和 终点。1.采用类C语言定义相关数据类型函数有：Void Create UGN(。/* 造图函数 */Void ShortwstPath(。/* 最短路径函数 */Void narrate(。 /* 说明函数 */Void introduce(。/* 介绍函数 */Void output(。/* 输出函数 */Void main(/* 主函数 */类有：ArcCell 。/*定

4、义边的类型 */VertexType。/* 定义顶点的类型 */MGraph。/* 定义图的类型 */全局变量有：MGraph G。/* 把图定义为全局变量 */int P2626 。long int D26 。*问题描述在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差，旅行或者做其他出行时，不仅关心节省交通费用，而且对 里程和所需时间也感兴趣。对于这样一个人们关心的问题，可用一 个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统 。图中顶点表示站点，边表示站之间的交通关系。这个系统可以回 答旅客提出的各种问题。需求分析设计一个交通咨询系统，能让旅客咨询从一个站点到另一

5、个站顶点 之间的最短路径或最短距离等。对于不同咨询要求，可查询站之间 的路程或所走的距离。该设计共三部分，一是建立交通网络图的存 储结构；二是解决单源最短路径问题；最后再实现两个站点之间的 最短路径问题。2各模块流程图及伪码算法1其功能模块图如下：2伪码算法如下：Void ShortwstPath(mum /*最短路径函数 */Int mum。int v,w,l,t。Int fin al 26。Int min。for (v=0。v/* 初始化 */finalv=0。/*标志数组初始化*/Dv=G .arcsnumv.adj。for(w=0。 wPvw=0 。 /* 设空路径 */ if(Dv/

6、*v,v0 间有边存在 */Pvnum=1。Pvv=1。/* 到v的最短路径上包含 vO及v*/ /*if*/Dnum=O 。finalnum=1。/*初始化，vO顶点属于B集*/*开始主循环，每次求得vO到某个v顶点的最短路径，并加v到B集*/for(i=0。i/* 其余 Gvexnum-1 各顶点 */min=2OOOO。for(w=O 。 wif(!finalw/*w 顶点在 V-S中 */if(Dwv=w。min=Dw。/*w 顶点离 v0更近 */finalv=1。/*离v0顶点最近的v加入B*/for(w=O 。 w/* 更新当前最短路径及距离 */ if(!finalw&(min

7、+G .arcsvw.adj for(t=0。t Pwt=Pvt。Pww=1。“*if*/*for*/*函数调用关系图首先用一个数组来定义邻接矩阵，并定义当前顶点数，顶点用来表示地点，数组的值用来表示路径长度。然后给各个顶点赋予初值，亦即兰州各个地方的名称，并确定各个地 方之间的距离，还要标注各个地方的简单信息，让旅客一目了然，并用迪杰斯特拉算法来实现最短路径的求解。之后在主函数main(中调用各个子函数，显示两地点之间的最短路径、某地点相关信息。整个程序功能就这样实现了。4.调试分析1调试中遇到的问题及对问题的解决方法遇到的问题：在调试时，有时会把值输错，导致超出范围，输出错误结果或程序直接

8、 结束。或者有时候还会在错误的环境下运行，例如在win-TC中调试运行时，中文不能正常显示，而到visual c+中运行就可以正常显示。解决方法：首先注意值的范围，输入在范围内的任意值。其次注意运行环境，有中文 的一定要在中文运行环境中进行。2.算法的时间复杂度和空间复杂度时间复杂度0(n2.空间复杂度0(n2.*测试结果我对程序进行了测试，选择运行程序选择 丫或y,然后回车，得到如下结果：若要查询地点信息，输入服务项目编号1然后回车，得到如下结果:选择你要查询的地点编号，例如要查询兰州交通大学，输入对应编号0然后回车，得到结果如下：曲 C: DocuAent s and Sett ingsA

9、.dAiistTat orJ面,0命111101客 eze 以下是选歪i兰州交通大学g甘肃政法学院 兰州师范大学 师大附申西站公交公司知小西湖 兰州理工大本部石油大厦中山桥兰州剧院南关十字五泉山广场西口广场东口兰州大学火车站市政府雁滩杨家桥龚家湾兰州理工太西校区文化宫西关十字陆军总院西湖公园；请输入服务顶最想路径查询:世点信息2隠想查询哪个地方的详细信息?请输入地点编号冷那兰州交通大学前兰州铁道学院。择2并回车，得到如下结果:输入要查询的开始地点，例如要查询兰州交通大学到兰州理工大学 西校区的最短路径，输入开始地点兰州交通大学的编号 0回车，得到 结果如下：输入要查询的结束地点，例如查询兰州交

10、通大学到兰州理工大学西校区，输入兰州理工大学西校区的编号回车，得到结果如下：5公交必司6小西湖 7兰州理工大本部9文化宫 10西关十字11陆军总院8西湖公园石油大厦中山桥14兰州剧院南关十字五泉山广场西口18广场东口兰州大学火车站帀政府22雁滩畅家桥兰州理工天曲校区24；请输入膈务顶目1地由坯绍2最短路径查询Pat C: DacuAent s and你好I如果侬想用该程序请输入汕，pr以下是选项：0兰州交通大学“甘肃政法学院紇兰州师范大学师大附中/4西站:请输入开始地点:请输入结東地点G5最短距离21Fi03n- 兰州交H大学-一 ；益交公司一 市政府二一最短路径从兰州交通大学到兰州理工大西校

11、区甘审政迭学院-一一兰创师范大書-一一师大附中-一-洒站 -A小西湖石抽大魅中山桥. 爨遽杨家擀龚家浩兰州理工大西校区设计总结:在这次数据结构课程设计中，我的题目是：兰州道路交通网络信 息查询,通过对该题目的设计，我加深了对图的建立和对迪杰斯特拉 算法的理解，对课本中所学的各种数据结构进一步理解和掌握，学会 了如何把学到的知识用于解决实际问题，锻炼了自己动手的能力。两到三周的时间虽然很短暂，但其间的内容是很充实的，在其 中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼 了自己分析问题，解决问题的能力，并学会了如何将所学的各科知 识融会，组织，来配合学习，总之，这段时间中我收益很大，学

12、到很 多。在课程设计时我遇到了很多的问题，但在同学的帮助和对各种资料 的查阅中，最终将问题解决，这培养了我自主动手，独立研究的能 力，为今后在学习工作中能更好的发展打下了坚实的基础。在以后 的学习中我会更注意各方面的能力的协调和发展。参考文献1 谭浩强 .c 语言程序设计 . 清华大学出版社 .2严蔚敏，吴伟民数据结构题集C语言版）清华大学出版社3 算法与数据结构。*致谢：在这两到三周的时间里，时间虽短却很充实，感谢指 导老师和所有帮助过我的同学们。*源程序#include string.h#include stdio.htypedef struct ArcCellint adj 。char

13、*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.vex

14、num=v 。G.arcnum=a。for(i=0 。 iG.vexi.number=i 。G.vex0.place= 兰州交通大学 。G.vex1.place= 甘肃政法学院 。G.vex2.place= 兰州师范大学 。G.vex3.place= 师大附中 。G.vex4.place= 西站 。G.vex5.place= 公交公司 。 G.vex6.place= 小西湖 。 OOOS=pe (!soJB-0 f 0=DJO) ! o=!)JO) hH=9oe|d g3x9A-0h 叙灣叢 soeid JxsA-g h 蚪灣帥 u=9OB|d e3X9A-0 h产eoE|d乙乙xe/v。h釧

15、迎单 产eg|d乙xe/vp h WY 产eg|d0乙xe/vp h 秦1血箕 u=9OB|d 6MX9A-0 h 口 WJ H=9oe|d 8MxsA-0 h 口 MB J H=9oe|dzi,x9A-0h E沓圧 产eg|d9|Jxe/v9 h 古亠沃卑 ll=9oe|d g|,x9A-0 關喝血天.oeid xsAO J 蚪E 申 H=9oe|d ei,x9A-0 HH=9oe|d 3|,x9A-0h 剝冒寿乌 ll=9oe|d n,x9A-0 h 古亠沃厘 ll=9oe|d oMx9A-0h MW 产eg|d6xe/v9 h 国H=9oe|d 8xsA-0 H 混伞工琵1血三 u=9O

16、B|d zX9A-0G.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

17、。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 .

18、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

19、=800 。G.arcs2425.adj=G .arcs2524.adj=329 。void narrate( /* 说明函数 */int i,k=0 。printf(n欢迎使用该程序*n 。printf(n 以下是选项 :nn 。 for(i=0 。 iprintf(%d %-10s,i,G .vexi.place 。 k=k+1 。if(k%4=0 printf(nn void introduce(int b 。printf( 您想查询哪个地方的详细信息?请输入地点编号 : 。scanf(%d,&b 。getchar(。printf(n 。switch(b case 0:printf(0:

20、 兰州交通大学 nn前兰州铁道学院。nn。break。case 1:printf(1: 甘肃政法学院 nn 兰州的一所重要的学校。 nn 。 break。case 2:printf(2: 兰州师范大学 nn 兰州一所重要的师范类学校。 nn 。 break。case 4:printf(4: 兰州西站 nn 火车西站兼购物市场，车多人多。 nn break。case 5:printf(5: 公交公司 nn 公交车的管理公司。 nn 。 break。case 6:printf(6: 小西湖 nn 购物市场。 nn 。 break。case 7: printf(7: 兰州理工大学 nn 前甘肃工业大

21、学 ,在甘肃省内稳做第三把交 椅。 nn 。 break。case 8:printf(8: 西湖公园 nn 一所免费的公共公园。 nn 。 break。case 9:printf(9: 文化宫 nn甘肃文化的集结地。nn。break。case 10:printf(10: 西关什字 nn 兰州市中心。 nn 。 break。case 11:printf(11: 陆军总院 nn 医院，兰州市医疗设施先进的医院。 nn 。 break。case 12: printf(12: 石油大厦 nn 一座立在黄河旁边的大厦，是一座写字楼 。 nn 。 break。case 13: printf(13: 中山桥

22、 nn 黄河第一桥，主要构架为钢铁所造，历史 悠久。 nn 。 break。case 14:printf(14: 兰州剧院 nn 兰州历史悠久，规模较大的电影院。 nn 。 break。case 15:printf(15: 南关 nn 政府部门所在地，市中心。 nn 。 break。case 16:printf(16: 五泉山 nn兰州市的一座公园，比较著名。nn。 break。case 17:printf(17: 广场西口 nn 东方红广场西面的口子，东方红广场是兰 州最大，最繁华的广场。nn。break。case 18: printf(18: 广场东口 nn 东方红广场东面的口子，东方红广

23、场是兰 州最大，最繁华的广场。 nn。 break。case 19:printf(19: 兰州大学 nn 兰州市排名第一的高校。 nn。 break。case 20:printf(20: 兰州火车站 nn 火车站，转运枢纽。 nn 。 break。case 21: printf(21: 市政府 nn 兰州市市政府，兰州市的管理地方。 nn 。 break。case 23:printf(23: 杨家桥 nn 七里河区西面的一个重要交通枢纽。 nn 。 break。case 24:printf(24: 龚家湾 nn 一个集市。 nn 。 break。case 25:printf(25: 兰州理工大

24、西校区 nn 兰州理工大学的分校区。 nn 。 break。 default:printf( 目的地编号输入错误！请输入 0- 32的数字编号！ nn 。 break。void ShortwstPath(num /* 最短路径函数 */ int num 。 int v,w,i,t 。int final26 。int min 。for(v=0 。 v/* 初始化 */finalv=0 。 /* 标志数组初始化 */Dv=G .arcsnumv.adj 。for(w=0 。 wPvw=0 。/* 设空路径 */ if(Dv/*v,v0 间有边存在 */Pvnum=1 。 PVV=1 。 /* 到

25、v的最短路 径上包含V0及v*/*if*/Dnum=0 。finalnum=1。/*初始化，V0顶点属于B集*/*开始主循环，每次求得V0到某个v顶点的 最短路径，并加v到B集*/for(i=0 。 i/* 其余 G.Vexnum-1各顶点 */min=23000。for(w=0 。 wif(!finalw/*w 顶点在 V-S 中 */if(Dwv=w 。 min=Dw。/*w 顶点 离v0更近*/finalv=1。/*离vO顶点最近的v加入B*/for(w=0 。 w/* 更新当前最短路径 及距离 */if(!finalw&(min+G .arcsvw.adjDw=min+G.arcsvw.adj 。/* 修改 D和