数据结构课程设计--交通咨询系统设计
23页1、信息科学与工程学院课程设计任务书题 目:交通咨询系统设计学 号:姓 名:年 级:专 业:计算机应用与技术课 程:数据结构指导教师:职 称:完成时间:课程设计任务书及成绩评定课程设计的任务和具体要求设计一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短 路径(里程)或最低花费或最少时间等问题。对于不同的咨询要求,可输入城市间的路程 或所需时间或所需费用。本设计共分三部分,一是建立交通网络图的存储结构;二是解决单源最短路径问题;三 是实现任两个城市顶点之间的最短路径问题。指导教师签字: 日期:指导教师评语:成绩: 指导教师签字: 日期:课程设计所需软件、硬件等PC兼容机、Windows操作系统、Turbo C/Win t、Vc+软件等。课程设计进度计划起止日期工作内容备注参考文献、资料索引(序号、文献名称、编著者、出版单位)数据结构(C语言版)编著严蔚敏吴伟民清华大学出版社1997数据结构中国石油大学出版社一、需求分析 设计一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一城市顶点之 间的最短路径(里程)或最低花费或最少时间等问题。对于不同的咨询要求,可 输入城市间的
2、路程或所需时间或所需费用。本设计共分三部分,一是建立交通网络图的存储结构;二是解决单源最短路 径问题;三是实现任两个城市顶点之间的最短路径问题。1.1.1建立图的存储结构 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下 的n阶方阵:设G二(V, E)是一个图,结点集为V二匕,v2,V”L(w ),当(v ,v ) 或 G EG 的邻接矩阵 A = (a ) , a = Jj nxn1 jz j ,ij nxn可 |0或, 当(v , v )或 Eijij当邻接矩阵的行表头、列表头顺序一定时,一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示,除了需用一个二维数组存储顶点之间的相邻关系的邻接 矩阵外,通常还需要使用一个具有n个元素的一维数组来存储顶点信息,其中下 标为i的元素存储顶点i的信息。因此,图的邻接矩阵的存储结构定义如下:#defi nf MVNum 50 /最大顶点数typedef structVertexType vexsMVNum;/顶点数组,类型假定为char型Adjmatrix arcsMVNumMVNum;/邻接矩阵,假定为 int 型MGraph;
3、1.1.2单源最短路径 最短路径的提法很多。在这里先讨论单源最短路径问题:即已知有向图(带 权),我们希望找出从某个源点Se V到G中其余各顶点的最短路径。为了叙述方便,我们把路径上的开始点称为源点,路径的最后一个顶点为终 点。那么,如何求得给定有向图的单源最短路径呢?迪杰斯特拉D ijkstra )提 出按路径长度递增产生诸点的最短路径算法,称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是:设G二(V,E)是一个有向图,结点集为,V二v ,v , .,v , cost是表示G的邻接矩阵,costij表示有向1 2 n边i,j的权。若不存在有向边i,j,则costij的权为无穷大(这里取值 为32767)。设S是一个集合,其中的每个元素表示一个顶点,从源点到这些顶 点的最短距离已经求出。设顶点v为源点,集合S的初态只包含一个元素,即1顶点v。数组dist记录从源点到其他顶点当前的最短距离,其初值为1disti=costv i,i=1,2,n。从S之外的顶点集合V-S中选出一顶点1w,使distw的值最小。于是从源点到达w只通过S中顶点,把w加入集合S 中,调整dist中记录的
《数据结构课程设计--交通咨询系统设计》由会员大米分享,可在线阅读,更多相关《数据结构课程设计--交通咨询系统设计》请在金锄头文库上搜索。
小学教师年度考核个人总结参考模板.doc
202_年第二学期工作总结范文
初三班主任工作总结标准格式.doc
新《数字电子技术》课程标准
九年级数学(上)旋转章节测试题
教师生产产假请假条.doc
小班社会光盘行动教案
蛋鸭养殖技术汇编(完整版)资料
数码钢琴突出优点及发展
芝山事业编招聘考试2010-2021历年《公共基础知识》(综合应用能力)真题汇总(摘选200题)及答案解析_0
《老山界》教学设计[985]
辞旧迎新节对联大全
产品品质保证协议书
2023年山东省临沂市平邑县平邑街道孙家村社区工作人员考试模拟题含答案
人的可持续发展与教育转型
分离苯甲苯筛板式精馏塔设计04451
建团100周年金句80句_建团100周年说说3篇建团100周年系列活动
“勾”与“钩”的用法比较
店面房屋租赁合同参考范本(6篇).doc
幼儿教师教育笔记《让孩子在实践中总结经验》
2022-08-07 17页
2023-01-02 2页
2023-09-29 25页
2024-01-12 10页
2022-12-07 8页
2022-12-30 9页
2022-11-24 7页
2023-11-21 30页
2022-10-20 12页
2024-01-10 16页