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

兰州理工大学 2011年春季学期 数据结构 课程设计 题 目：兰州道路交通网络信息查询 专业班级：计算机五班 姓 名： 梁业洪 学 号：指导教师： 李睿 成 绩： _______________ 目录 中文摘要……………………………………………………1 序言…………………………………………………………2 采用类C语言定义相关数据类型……………………3 各模块流程图及伪码算法……………………………4 函数的调用关系图……………………………………5 调试分析………………………………………………6 测试结果………………………………………………7 设计总结……………………………………………………8 参考文献……………………………………………………9 致谢…………………………………………………………10 附录：源程序………………………………………………11 1中文摘要 在本设计实验中，我所采用的是邻接矩阵作为数据的存储结构，用不同的功能模块对两地距离和道路交通进行编辑。 兰州道路交通网络信息查询等程序的目的是为人们提供各种信息查询服务：即查询任意两地之间的一条最短的简单路径，还有两地之间的距离等。最短路径的输出有各种方法，此程序中采用迪杰斯特拉算法。迪杰斯特拉算法用于求解一个有向图（也可以是无向图）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。 *序言 我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先有哪些信誉好的足球投注网站查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。图是一种复杂的非线性结构，在人工智能，工程，数学，物理，化学，计算机学科等领域中，都有着广泛的应用。我们用最短路径问题，通过一个人们熟悉的交通咨询系统实例来验证迪杰斯特拉算法。 兰州道路交通网络信息查询是以半州道路为背景，设计出的一个简单的能够实现兰州道路交通网络信息查询功能的C语言程序系统，对兰州道路交通信息进行编辑，为旅客提供了两地之间的最短路径及距离。 查询的实现以用户和计算机对话的方式进行，要注意人机交互的屏幕界面，由用户先择要查询的地点，输入要查询路径的起点和终点。 采用类C语言定义相关数据类型 函数有： Void Create UGN();/*造图函数*/ Void ShortwstPath();/*最短路径函数*/ Void narrate();/*说明函数*/ Void introduce();/*介绍函数*/ Void output();/*输出函数*/ Void main()/*主函数*/ 类有： ArcCell;/*定义边的类型*/ VertexType;/*定义顶点的类型*/ MGraph;/*定义图的类型*/ 全局变量有： MGraph G;/*把图定义为全局变量*/ int P[26]26[]; long int D[26]; *问题描述 在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差，旅行或者做其他出行时，不仅关心节省交通费用，而且对里程和所需时间也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示站点，边表示站之间的交通关系。这个系统可以回答旅客提出的各种问题。 需求分析 设计一个交通咨询系统，能让旅客咨询从一个站点到另一个站顶点之间的最短路径或最短距离等。对于不同咨询要求，可查询站之间的路程或所走的距离。该设计共三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个站点之间的最短路径问题。 2各模块流程图及伪码算法 1其功能模块图如下： 2伪码算法如下： Void ShortwstPath(mum) /*最短路径函数*/ Int mum; {int v,w,I,t; Int final [26]; Int min; for (v=0;v26;++v)/*初始化*/ { final[v]=0; /*标志数组初始化*/ D[v]=G.arcs[num][v].adj; for(w=0;w33;++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(i=0