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

《兰州道路交通网络信息查询课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、兰州理工大学2011年春季学期数据结构课程设计题目：兰州道路交通网络信息查询专业班级：计算机五班姓名：梁业洪学号：09240505指导教师：李睿成绩：_______________目录中文摘要……………………………………………………1序言…………………………………………………………21．采用类C语言定义相关数据类型……………………32．各模块流程图及伪码算法……………………………41．函数的调用关系图……………………………………52．调试分析………………………………………………63．测试结果………………………………………………7设

2、计总结……………………………………………………8参考文献……………………………………………………9致谢…………………………………………………………10附录：源程序………………………………………………111中文摘要在本设计实验中，我所采用的是邻接矩阵作为数据的存储结构，用不同的功能模块对两地距离和道路交通进行编辑。兰州道路交通网络信息查询等程序的目的是为人们提供各种信息查询服务：即查询任意两地之间的一条最短的简单路径，还有两地之间的距离等。最短路径的输出有各种方法，此程序中采用迪杰斯特拉算法。迪杰斯特拉算法用于求解一个有向图（也可以

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

4、现兰州道路交通网络信息查询功能的C语言程序系统，对兰州道路交通信息进行编辑，为旅客提供了两地之间的最短路径及距离。查询的实现以用户和计算机对话的方式进行，要注意人机交互的屏幕界面，由用户先择要查询的地点，输入要查询路径的起点和终点。1．采用类C语言定义相关数据类型函数有：VoidCreateUGN();/*造图函数*/VoidShortwstPath();/*最短路径函数*/Voidnarrate();/*说明函数*/Voidintroduce();/*介绍函数*/Voidoutput();/*输出函数*/Voidmain()/*

5、主函数*/类有：ArcCell;/*定义边的类型*/VertexType;/*定义顶点的类型*/MGraph;/*定义图的类型*/全局变量有：MGraphG;/*把图定义为全局变量*/intP[26]26[];longintD[26];*问题描述在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差，旅行或者做其他出行时，不仅关心节省交通费用，而且对里程和所需时间也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示站点，边表示站之间的交通关系。这个系统可以回

6、答旅客提出的各种问题。需求分析设计一个交通咨询系统，能让旅客咨询从一个站点到另一个站顶点之间的最短路径或最短距离等。对于不同咨询要求，可查询站之间的路程或所走的距离。该设计共三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个站点之间的最短路径问题。2各模块流程图及伪码算法1其功能模块图如下：开始选择服务1或2输入地点编号查询地点信息输入开始地点编号结束输入结束地点编号结束2伪码算法如下：VoidShortwstPath(mum)/*最短路径函数*/Intmum;{intv,w,I,t;Intfinal[

7、26];Intmin;for(v=0;v<26;++v)/*初始化*/{final[v]=0;/*标志数组初始化*/D[v]=G.arcs[num][v].adj;for(w=0;w<33;++w)P[v][w]=0;/*设空路径*/if(D[v]<20000)/*v,v0间有边存在*/{P[v][num]=1;P[v][v]=1;/*到v的最短路径上包含v0及v*/}/*if*/}D[num]=0;final[num]=1;/*初始化，v0顶点属于B集*//*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到B集*/for

8、(i=0;i<33;++i)/*其余G.vexnum-1各顶点*/{min=20000;for(w=0;w<33;++w)if(!final[w])/*w顶点在V-S中*/if(D[w]