交通咨询系统设计报告

重庆科技学院《数据结构》课程设计报告学院:_电气与信息工程学院_专业班级:计科2学生姓名:学号:设计地点（单位）___计算机基础自主学习中心____设计题目:________交通咨询系统设计_______完成日期：2012年7月6日指导教师评语:___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________成绩（五级记分制）:________________指导教师（签字）:________________重庆科技学院课程设计任务书设计题目：交通咨询系统的设计学生姓名课程名称数据结构课程设计专业班级计地点计算机基础自主学习中心起止时间2012.6.25-2012.7.6设计内容及要求人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。可以用一个图结构来表示交通网络，图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。设计一个交通咨询系统，能让旅客咨询从任一个城市到另一个城市之间的最短路径（里程）、最少交通费用或最少时间等问题。该设计的内容主要分两部分：一是建立交通网络图的存储结构；二是实现求两个城市顶点之间的最短路径算法。要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值。程序可实现求任两个城市之间的最短里程、最少时间或最少费用的路线。建立图的存储结构时要求从文本文件中读入顶点和边的信息。设计参数测试数据要求：交通图中顶点数不少于16个，边数不少于20，每条边有三个权值（里程、交通费用、时间）。进度要求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．程杰，大话数据结构，清华大学出版社，2011.63．（美）StephenPrata,CPrimerPlus中文版（第五版），人民邮电出版社，2005.2其它说明1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。系主任：雷亮指导教师：黄永文/王双明/熊茜/彭军/王成敏2012年6月20日摘要在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。对于这样一个人们关心的问题，可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。关键词：数字结构C语言交通咨询最短路径目录1设计内容和要求..........................................................11.1问题描述.......................................................11.2需求分析........................................................12课程需求分析............................................................22.1算法思路.......................................................22.2数据结构体.....................................................22.3基本操作.......................................................32.4算法应用.......................................................32.5程序设计流程图.................................................43功能模块详细设计........................................................53.1测试数据.......................................................53.2程序调试.......................................................64课程总结与体会........................................................195参考文献...............................................................206致谢...................................................................21重庆科技学院《数据结构》课程设计报告11设计内容和要求1.1问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）里程最少。1.2需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1）在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。（3）程序的功能包括：提供对城市信息的编辑，对两城市间时间、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。重庆科技学院《数据结构》课程设计报告22课程需求分析2.1算法思路(1)数据存储。城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文件。建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中，用fread和fwrite函数操作。(2)数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间、旅费、里程。(3)数据的存储结构。采用邻接矩阵作为数据的存储结构，提高空间的存储效率。(4)用不同的功能模块对城市信息和交通信息进行编辑，可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可。(6)主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2.2数据结构体typedefstructlu/*交通信息数据类型*/{intdistance;/*城市间里程*/intcost;/*城市间旅费*/inttime;/*城市间时间*/}lu,lujin[max][max];typedefstructcity/*城市数据类型*/{charname[20];/*城市名称*/}citys[max];typedefstruct/*网络图的数据类型*/{citysclist;/*城市信息*/lujinarcs;/*边的信息*/intc_n,l_n;/*边和顶点数目*/}Graph;typedefstruct/*最短路径*/{charadjvex;intmincost;/*最少旅费*/重庆科技学院《数据结构》课程设计报告3intmindistance;/*最短里程*/intmintime;/*最少时间*/}closedge;2.3基本操作voidzairu(Graph*G);/*导入文件中的信息，能否是程序运行*/voidAdminister(GraphG);/*管理员操作界面，由主函数调用*/voidshow(GraphG);/*显示系统中的全部城市信息和交通信息*/intinsertcity(Graph*G);/*增加城市信息*/intinsertlu(Graph*G);/*增加交通信息*/intLocated(Graph*G,char*p);/*返回邻接矩阵的位置下标，系统中的关键*/voidbaocun(GraphG);/*将城市信息、交通信息保存在文件中*/intserchlu(Graph*G);/*搜索交通信息*/voidmindistance(Graph*G,intv0,intv1);/*最少里程计算，迪杰斯特拉算法*/voidmincost(Graph*G,intv0,intv1);/*最少旅费计算，迪杰斯特拉算法*/voidmintime(Graph*G,intv0,intv1);/*最少时间计算，迪杰斯特拉算法*/2.4算法应用在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：一般情况下，假设S为以求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为x）或者是弧(v,k)，或者是中奖只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。但是，这是不可能的。因为我们是按照路径长度递增的次序来产生各最短路径的，故长度比此路径段的所有路径均已产生，它们的终点必定在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必是iviDMinj|][{][D}SV其中，D[i]或者是弧ivv,上的权值，或者是D[k])(Svk和弧ikvv,上的权值之和。（1）假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧vvi,vj上的权值。若vi,vj存在，则置arcs[i][j]为∞(在计算机上可用允许的最大值代替)。重庆科技学院《数据结构》课程设计报告4S为已找到从v出发的最短路径的终点的集合，他的初始状态为空集。那么，从v出发到图上其余个顶点(终点)vi可能达到的最短路径长度的初值为：VvivGVexLocatearciDi])[,([][（2）选择jv，使得}S|][D{][VviMiniDijv就是当前求得的一条从v出发的最短路径的终点。令}{jSS(3)修改从v出发到集合V-S上任一顶点kv可达的最短路径长度。如果][]][[][kDkjarcsiD则修改][kD为]][[][][kjarcsjDkD(4)重复操作(2)、(3)共n-1次。由此求得从v到图上其余各点的最短路径是依路径长度递增的序列。2.5程序设计流程图：图2.1程序设计流程图交通咨询系统管理员用户添加城市查询最少花费路线查询最短时间路线查询最短里程路线退出添加交通路线返回上一级菜单返回上一级菜单显示所有交通路线重庆科技学院《数据结构》课程设计报告53功能模块详细设计3.1测试