全国交通咨询模拟数据结构优秀课程设计.doc
《全国交通咨询模拟数据结构优秀课程设计.doc》由会员分享,可在线阅读,更多相关《全国交通咨询模拟数据结构优秀课程设计.doc(52页珍藏版)》请在咨信网上搜索。
1、数据结构课程设计汇报 题目:全国交通咨询模拟 一需求分析1程序设计任务: 从中国地图平面图中选择部分城市,抽象为程序所需要图结点,并以城市间列车路线和飞机路线,作为图结点中弧信息,设计一个全国交通咨询模拟系统。利用该系统实现两种最优决议:最快抵达或最省钱抵达。2. 明确要求:(1)输入形式和输入值范围: 每条飞机弧或火车弧包含信息量很多,包含:起始城市、目标城市、出发时间、抵达时间、班次和费用。作为管理员要输入信息包含以上信息,而作为用户或用户,要输入信息有起始城市和目标城市,并选择何种最优决议。 (2)输出形式:按用户提供最优决议不一样而输出不一样信息,其中输出所搭飞机或火车班次及其起始地点
2、和终点、起始时间和出发时间还有相关最优信息,比如最快经多少时间抵达、最省钱多少钱抵达和最少经多少中转站抵达。(3)程序所能达成功效a.该系统有供用户选择菜单和交互性。能够对城市、列车车次和飞机航班进行编辑,添加或删除。b.建立一个全国交通咨询系统,该系统含有自动查找任意两城市间铁路、飞机交通最短路径和最少花费及中转次数最少等功效。c.初始化交通系统有两种方法,键盘和文档。二 设计概要1. 算法设计 (1)、总体设计 (1) 数据存放:城市信息(城市名、代码)、交通信息(城市间里程、各航班和列车时刻)存放于磁盘文件。提议把城市信息存于文件前面,交通信息存于文件后面,用fread和fwrite函数
3、操作。 (2) 数据逻辑结构:依据设计任务描述,其城市之间旅游交通问题是经典图结构,可看作为有向图,图顶点是城市,边是城市之间所花费时间(要包含中转站等候时间)或旅费。 (3) 数据存放结构:采取邻接表和邻接矩阵全部可作为数据存放结构,但当邻接边不多时,宜采取邻接表,以提升空间存放效率。这里采取邻接表作为数据存放结构。 (4) 用不一样功效模块对城市信息和交通信息进行编辑。添加、修改、删除功效可用菜单方法或命令提醒方法。只要能方便对城市信息和交通信息进行管理即可,但要注意人机界面。 (5) 最优决议功效模块(fast or province)。 读入城市信息和交通信息,用邻接表生成含权网络,表
4、头数组中元素存放城市名及对方城市抵达该元素所代表城市全部信息;表头数组中元素所对应单链表存放和该元素所代表城市有交通联络城市(代码、里程、航班、列车车次)。 依据具体最优决议要求,用Dijkstra算法求出出发城市到其它各城市最优值(最短时间或最小费用),搜索过程中所经过城市局部最优信息全部保留在邻接表表头数组中。其目标城市所代表元素中就保留了所需最优决议结果。这过程中,要用队列或栈保留局部最优决议值(局部最短时间或最省费用)变小城市,其对应初始值可为,并在表头数组对应城市元素中保留响应信息。开始时,栈(队列)中只有出发地城市,伴随对栈(队列)顶(首)城市有交通联络城市求得决议值(最短时间或最
5、小费用),若该值是局部最优值且该城市不在栈(队列)中,则进栈(队列),直至栈(队列)为空,本题采取队列实现。 输出结果:从目标城市出发,搜索到出发城市,所经过城市均入栈(队列),再逐一出栈栈(队列)中城市,输出保留在表头数组中对应城市信息(对方城市出发信息,里程、时间、费用等)及最终止果。即输出依次于何时何地乘坐几点飞机或火车于何时抵达何地;最终所需最快需要多长时间才能抵达及旅费,或最少需要多少旅费才能抵达立即间。 (6) 主程序能够有系统界面、菜单;也可用命令提醒方法;选择功效模块实施,要求在程序运行过程中能够反复操作。(2).具体设计思想: 本题所要求交通系统是一个有向带权图结构,考虑到要
6、求该系统有动态增加飞机和列车航班功效,所以采取邻接表形式存放:对每个顶点建立一个单链表,单链表中子结点表示以该顶点连接弧,单链表中子结点次序能够按权值递增次序排列,表头结点按次序存放。题目中提到要提供三种策略,最快抵达,最省钱抵达和最少中转次数策略,前两种策略采取迪杰斯特拉算法思想,其中最快抵达权值为抵达两城市所需最短时间,最省钱抵达权值为抵达两城市所需费用,后一个采取广度优先算法思想,只需求两城市所在层数,就能够求抵达两城市所需最少中转次数。 迪杰斯特拉(Dijkstra)算法基础思想是:设置两个顶点集合S和TVS,集合S中存放已找到最短路径顶点,集合T存放目前还未找到最短路径顶点。初始状态
7、时,集合S中只包含源点v0,然后不停从集合T中选择到顶点v0路径长度最短顶点u加入到集合S中,集合S每加入一个新顶点u,全部要修改顶点v0到集合T中剩下顶点最短路径长度值,集合T中各顶点新最短路径长度值为原来最短路径长度值和顶点u最短路径长度值加上u到该顶点路径长度值中较小值。此过程不停反复,直到集合T顶点全部加入到S中为止。下面讨论基于邻接表存放结构求两点间最短路径方法:依据迪杰斯特拉(Dijkstra)算法所依据原理:若按长度递增次序生成从源点V0到其它顶点最短路径,则目前正在生成最短路径上除终点以外,其它顶点最短路径均已生成(将源点最短路径看作是已生成源点到其本身长度为0路径)。根据这一
8、思想,结构以下算法:设S=S=U=,建立数组PATHn,用来存放V0到各终点最短路径,初值均置为空集。建立数组BOOL Fn,Fi表示序号为i表头结点单链表中全部子结点已或未全部找到,初值置为FALSE。建立数组float distn,disti表示序号为i表头结点到V0最短权值(这里是时间或费用),显然distV0=0,其它顶点dist初值置为。建立数组BOOL ISn,ISi表示序号为i顶点是否在S中,初值均置为FALSE。(1)VX=V0;最短最短路径为PATH0=V0 (2)S=S+VX;(集合并计算)ISVX=TRUE;S=S+VX ; (3)对S中全部顶点:do 由邻接表中该表头结
9、点开始依次找单链表下一子结点(沿链域指针依次访问);if(该子结点S)/IS该子结点邻接点序号=TRUE if(子结点链域指针指向NULL)F=TRUE;S=S-该表头结点;break;else continue;else break;while(); 如F=FALSE,则U=U+该子结点;假如S=空集,则结束; (4)下一次短路径终点必U。比较U中子结点到V0dist值(其值为U中结点弧权值+其表头结点dist值),由dist值最小子结点邻接点域确定次短路径终点VX, PATH VX=PATH该子结点表头结点+VX(集合并计算)。distVX=VX所属子结点弧权值+其表头结点dist值。U=
10、;假如VX为所要找顶点,则结束;回到2实施。 广度优先搜索遍历图类似于树按层次遍历,其基础思想是:首先访问图中某指定起始点Vi并将其标识为已访问过,然后由Vi出发访问和它相邻接全部顶点Vj、 Vk,并均标识为已访问过,然后再根据Vj、Vk次序,访问每一个顶点全部未被访问过邻接顶点,并均标识为已访问过,下一步再从这些顶点出发访问和它们相邻接还未被访问顶点,如此做下去,直到全部顶点均被访问过为止。2. 抽象数据类型本程序利用了相关图这种数据结构。ADT Graph 数据对象V:V是含有相同特征数据元素集合,称为顶点集。 数据关系R: R=VR VR=|v,wV且P(v,w),表示从v到w弧。 谓词
11、P(v,w)定义了弧意义或信息 基础操作P: CreateGraph(&G,V,VR); 初始条件:V是图顶点集,VR是图中弧集合。 操作结果:按V和VR定义结构图G。 DestroyGraph(&G); 初始条件:图G存在。 操作结果:销毁图G。 LocateVet(G,u); 初始条件:图G存在,u和G中顶点有相同特征。 操作结果:若G中存在顶点u,则返回该顶点在图中位置, 不然返回其它信息。 GetVex(G,v); 初始条件:图G存在,v是G中某个顶点。 操作结果:返回v值。PutVex(&G,v,value); 初始条件:图G存在,v是G中某个顶点。 操作结果:对v赋值value。F
12、irstAdjVex(G,v); 初始条件:图G存在,v是G中某个顶点。 操作结果:返回v第一个邻接顶点。若顶点在G中没有邻接 顶点,则返回“空”。NextAdjVex(G,v,w); 初始条件:图G存在,v是G中某个顶点,w是v邻接顶点, 操作结果:返回v(相对于w)下一个邻接顶点。若w是v 最终一个邻接点,则返回“空”。InsertVex(&G,v); 初始条件:图G存在,v和图中顶点有相同特征。 操作结果:在图G中添加新顶点v。DeleteVex(&G,v); 初始条件:图G存在,v是G中某个顶点。 操作结果:删除G中顶点v及相关弧。InsertArc(&G,v,w); 初始条件:图G存
13、在,v和w是G中两个顶点。 操作结果:在G中增添弧,若G是无向则还增加对称弧 。DeleteArc(&G,v,w); 初始条件:图G存在,v和w是G中两个顶点。 操作结果:在G中删除弧,若G是无向,则还删除对称 弧。DFSTraverse(G,Visit(); 初始条件:图G存在,Visit是顶点应用函数。 操作结果:对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。BFSTraverse(G,Visit(); 初始条件:图G存在,Visit是顶点应用函数。 操作结果:对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一
14、次且仅一次。一旦visit()失败,则操作失败。 ADT Graph其它抽象数据类型定义以下:typedef structint number; float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef struct ArcNodeint adjvex; struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar city
15、name10; ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct Node *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; Q
16、Node *rear;LinkQueue;typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree;struct arcint co; char vt10; char vh10; int bt2; int at2; float mo;aMAX_ARC_SIZE;基础操作:void Administer(ALGraph *G);void cityedit(ALGraph *G);void
17、CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int Delete
18、trainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)MAX_VER
19、TEX_NUM,ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void initgraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *tim
20、e,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 交通 咨询 模拟 数据结构 优秀 课程设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。