《交通咨询系统设计报告》由会员分享，可在线阅读，更多相关《交通咨询系统设计报告（25页珍藏版）》请在金锄头文库上搜索。
1、重庆科技学院数据结构课程设计报告 学 院:_电气与信息工程学院_ 专业班级: 计科2 学生姓名: 学 号: 设计地点（单位）_ _ 计算机基础自主学习中心 _ _ _设计题目:_ 交通咨询系统设计_ _ _ _ 完成日期：2012年 7 月 6 日 指导教师评语: _ _ _ _ 成绩（五级记分制）:_ _ 指导教师（签字）:_ _ 重庆科技学院课程设计任务书设计题目：交通咨询系统的设计学生姓名课程名称数据结构课程设计专业班级计地 点计算机基础自主学习中心起止时间2012.6.25-2012.7.6设计内容及要求人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。可以用一个图
2、结构来表示交通网络，图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。设计一个交通咨询系统，能让旅客咨询从任一个城市到另一个城市之间的最短路径（里程）、最少交通费用或最少时间等问题。该设计的内容主要分两部分：一是建立交通网络图的存储结构；二是实现求两个城市顶点之间的最短路径算法。要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值。程序可实现求任两个城市之间的最短里程、最少时间或最少费用的路线。建立图的存储结构时要求从文本文件中读入顶点和边的信息。设计参数 测试数据要求：交通图中顶点数不少于16个，边数不少于20，每条边有三个权值（里程、交通费用、时间）
3、。进度要求2012.6.25 完成任务的讲解、并接受课程设计任务，选定课程设计的题目2012.6.26 了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验证、并确定解决办法2012.6.27-2012.6.29 程序设计及编码，上机调试2012.7.02 对程序进行调试，设计测试用例进行测试2012.7.03 整理课程设计的过程、并进行总结，完善程序功能2012.7.04 编写课程设计报告初稿2012.7.05 完善课程设计报告、并准备答辨2012.7.06 提交课程设计报告和程序，进行答辨参考资料1严蔚敏 吴伟民， 数据结构，清华大学出版社，2007.32程杰 ，大话数据结构，清
4、华大学出版社，2011.63（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2其它说明1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。系主任：雷亮 指导教师：黄永文/王双明/熊茜/彭军/王成敏 2012年 6月 20日摘要在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。对于这样一个人们关心的问题，可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统
5、。图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。关键词：数字结构C语言交通咨询最短路径目录1 设计内容和要求11.1 问题描述11.2需求分析12 课程需求分析22.1 算法思路22.2 数据结构体22.3 基本操作32.4 算法应用32.5 程序设计流程图43 功能模块详细设计53.1 测试数据53.2 程序调试54 课程总结与体会195参考文献206 致谢211 设计内
6、容和要求1.1 问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）里程最少。1.2需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1） 在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。 （2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。（3） 程序的功能包括：提供对城市信息的编辑
7、，对两城市间时间、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。 2 课程需求分析2.1 算法思路(1) 数据存储。城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文件。建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中，用fread和fwrite函数操作。 (2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间、旅费、里程。 (3) 数据的存储结构。采用邻接矩阵作为数据的存储结构，提高空间的存储效率。(4) 用不同的功能模块对城市信息和交通信息进行编辑，可
8、用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可。 (6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2.2 数据结构体typedef struct lu /* 交通信息数据类型 */ int distance; /*城市间里程*/ int cost; /*城市间旅费*/int time; /*城市间时间*/lu,lujinmaxmax;typedef struct city /*城市数据类型*/char name20;/*城市名称*/citysmax;typedef struct /*网络图的数据类型*/ cit
9、ys clist; /*城市信息*/lujin arcs; /*边的信息*/int c_n,l_n; /*边和顶点数目*/Graph;typedef struct /*最短路径*/char adjvex;int mincost;/*最少旅费*/int mindistance;/*最短里程*/int mintime;/*最少时间*/closedge;2.3 基本操作void zairu(Graph *G);/*导入文件中的信息，能否是程序运行*/void Administer(Graph G);/*管理员操作界面，由主函数调用*/void show(Graph G);/*显示系统中的全部城市信息
10、和交通信息*/int insertcity(Graph *G); /*增加城市信息*/int insertlu(Graph *G); /*增加交通信息*/int Located(Graph *G, char *p);/* 返回邻接矩阵的位置下标，系统中的关键*/void baocun(Graph G);/*将城市信息、交通信息保存在文件中*/int serchlu(Graph *G);/*搜索交通信息*/void mindistance(Graph *G, int v0, int v1);/*最少里程计算，迪杰斯特拉算法*/void mincost(Graph *G, int v0, int
11、v1);/*最少旅费计算，迪杰斯特拉算法*/void mintime(Graph *G, int v0, int v1);/*最少时间计算，迪杰斯特拉算法*/2.4 算法应用在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：一般情况下，假设S为以求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为x）或者是弧(v,k)，或者是中奖只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。但是，这是不可能的。因为我们是按照路径长度递增的次序来产生各最短路径的，故长度比此路径段的所有路径均已产生，它们的终
12、点必定在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必是其中，Di或者是弧上的权值，或者是Dk和弧上的权值之和。（1）假设用带权的邻接矩阵arcs来表示带权有向图，arcsij表示弧上的权值。若存在，则置arcsij为(在计算机上可用允许的最大值代替)。S为已找到从v出发的最短路径的终点的集合，他的初始状态为空集。那么，从v出发到图上其余个顶点(终点)vi可能达到的最短路径长度的初值为： （2）选择，使得就是当前求得的一条从v出发的最短路径的终点。令(3)修改从v出发到集合V-S上任一顶点可达的最短路径长度。如果则修改为(4)重复操作(2)、(3)共n-1次。由此求得从v到图上其余各点的最短路径是依路径长度递增的序列。2.5 程序设计流程图：交通咨询系统管理员用户添加城市查询最少花费路线查询最短时间路线查询最短里程路线退出添加交通路线返回上一级菜单返回上一级菜单显示所有交通路线图2.1程序设计流程图3 功能模块详细设计3.1 测试数据表3.1城市信息北京天津石家庄济南重庆成都郑州徐州九江武汉广安无锡表3.2交通信息表起始目的旅费（元）时间（小时）里程（公里）重庆广安501300重庆成都1002500广安
