数据结构课程设计全国交通咨询系统.docx

郑州工业应用技术学院课程设计任务书题目 全国交通资询系统 主要内容：设计了一个方便用户查询交通咨询系统。该系统所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。该系统可以进行城市，列车车次和飞机航班的编辑的基本信息输入操作。程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。基本要求：1、掌握C语言的变量及函数的灵活使用；2、熟练掌握图的深度、广度优先遍历算法思想及其程序实现；3、掌握C语言中文件的基本操作；4、掌握VC+6.0软件的熟练使用。主要参考资料：1 李春葆.数据结构程序设计M.北京:清华大学出版社,2002,03 2 王黎,袁永康.Microsoft.NET战略M.北京:清华大学出版社,2002,013 谭浩强.C程序设计第二版M.北京:清华大学出版社,2003,034 任哲.MFC Windows程序设计M.北京:清华大学出版社,2004,06 完 成 期 限： 2016.12.052017.01.05 指导教师签名： 课程负责人签名： 摘 要随着高科技的飞速发展，列车、飞机、动车、高铁的出现极大的减少了人们花在旅途上的时间。对于城市间错综复杂交通网的管理，是一项庞大而复杂的工作。在此基础上，如何实现交通网智能化的管理达到帮助乘客选择经济高效的交通工具是目前仍处空白。尤其乘客交通工具的择优选择是一个令人懊恼的工作，一个原因就是各种交通工具的查询十分分散和繁琐。即使有互联网的帮忙，但是没有一个统一的归类、没有一个精细的算法、系统的软件帮助，人们仍然无法获得最优方式。为此开发一个交通择优系统是十分必要的。采用计算机对城市间的交通工具进行系统录入和管理，进一步提高了交通部门针对城市间客运网络的管理效率，实现交通运营网络的系统化、规范化和自动化。同时使乘客能通过网络进行称心的交通工具的选择，这也是交通网络优选智能决策的体现。交通信息的咨询和管理是交通部门管理工作中异常重要的一个环节，因此，运用交通资询管理系统对春运时减轻乘客购票压力、舒缓紧张的城际拥堵有重要意义。关键字：错综复杂；智能化；最优方式；择优系统 目 录摘 要I目 录II第一章 概述11.1 性能需求11.2 功能需求2第二章 概要设计32.1 功能模块设计32.2 算法分析与设计3第三章 详细设计53.1 管理员功能模块设计53.2 计算最少费用功能模块设计93.3 测试与分析17第四章 全国交通咨询系统的运行204.1 程序主界面204.2 管理员登录主界面204.3 用户界面登录界面234.4 显示交通系统界面26结束语29参考文献30附录31第一章 概述数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.1 性能需求在现代，随着高科技的飞速发展，列车、飞机、动车、高铁的出现极大的减少了人们花在旅途上的时间。对于城市间错综复杂交通网的管理，是一项庞大而复杂的工作，况且，受经济危机的影响，也使人们愈发珍惜包里的人民币。在此基础上，如何实现交通网智能化的管理达到帮助乘客选择经济高效的交通工具是目前仍处空白。尤其乘客交通工具的择优选择是一个令人懊恼的工作，一个原因就是各种交通工具的查询十分分散和繁琐。即使有互联网的帮忙，但是没有一个统一的归类、没有一个精细的算法、系统的软件帮助，人们仍然无法获得最优方式。显然，靠传统的交通信息咨询、管理方式已不能适应时代的发展，同时也很难旅客的需求。今天这种传统的管理方法必然会被以计算机为基础的交通信息总揽、智能咨询所代替。同时这种传统的管理方式反映出很多问题：第一，当要查询某两个城市之间的全部交通方式要各种查找，很繁琐；第二，随着周围经济环境的变化，每次查询的票价和线路又会由于各种原因而产生变化，网站更新的不及时或者票价的错误都会造成乘客陷入麻烦；第三，随着动车、高铁等各种新型交通方式的加入，一个庞大的信息统计如果占用大量人力、物力、存储资源，显然不能适应时代需要。基于以上情况，开发一个交通择优系统是十分必要的。开发一个交通择优系统，采用计算机对城市间的交通工具进行系统录入和管理，进一步提高了交通部门针对城市间客运网络的管理效率，实现交通运营网络的系统化、规范化和自动化。同时使乘客能通过网络进行称心的交通工具的选择，这也是交通网络优选智能决策的体现。交通信息的咨询和管理是交通部门管理工作中异常重要的一个环节，因此，运用交通资询管理系统对春运时减轻乘客购票压力、舒缓紧张的城际拥堵有重要意义。1.2 功能需求设计了一个方便用户查询交通咨询系统，这个系统功能比较强大。该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。1、在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据；2、程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地；3、程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。第二章 概要设计2.1 功能模块设计交通咨询管理系统通过主控模块进入系统并提示相应功能供用户选择。用户选择后进入到各个功能模块，实现管理员管理、用户咨询、交通信息总览功能，管理员管理时可依据不同对系统信息进行增减，使用户在咨询时得到依据最少旅行时间、旅行费用、最少中转站的购票依据，为用户购票选择提供智能决策。也可通过显示模块对系统中存储的全部信息进行总览和查询。基于此，提供以上功能。如下图2.1所示： 最少中转站 主控模块系统初始化城市编辑飞机航班编辑显示飞机航班显示城市交通咨询管理系统用户资询模块管理员管理模块交通信息总览模块最少旅行时间最少旅行费用列车车次编辑显示列车车次 图2.1 交通咨询查询系统模块图2.2 算法分析与设计系统用到的抽象数据类型定义：1ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性数据关系R：R=VR VR=|P(x,y)(x,y属于V) 基本操作：（1）initgraph(&G)；（2）CreateGraph(&G)；（3）EnterVertex(&G)；（4）DeleteVertex(&G)；（5）EnterplaneArc(&G)；（6）DeleteplanArc(&G)；（7）EntertrainArc(&G)；（8）DeletetrainArc(&G)；ADT Graph2ADT LinkQueue数据元素：可以是任意类型的数据，但必须属于同一个数据对象关系：队列中数据元素之间是线性关系。基本操作：（1）InitQueue(&Q)；（2）IsEmpty(&Q)；（3）EnterQueue(&Q,x)；（4）DeleteQueue(&Q,&y)； ADT LinkQueue3ADT TimeTree 数据对象D：一个集合，该集合中的所有元素具有相同的特性 数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则R=H，H为如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H中没有前驱；（2）除root以外，D中每个结点在关系H下有且仅有一个前驱；（3）CreateTimeTree(p,i,j,&Q,infolist arcs)；（4）CopyTimeTree(p,q)；（5）VisitTimeTree(p)； ADT TimeTree第三章 详细设计3.1 管理员功能模块设计设计思想：本系统的管理员模块，当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息。通过管理员模块的操作，我们可以对系统的相关信息进行修改与添加。如下图3.1所示：开始进入管理员界面是否进行初始化进入主菜单选择编辑项目进入编辑子菜单是否增加城市，航班或车次是否删除信息删除信息输入添加信息返回上一级菜单结束图3.1 管理员模块流程图详细功能：本系统实现并建立了有关图的3个文本文件(city.txt,plan.txt,train.txt),在交通系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息。当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或列车弧,修改信息完毕后返回上一级菜单。以下是管理员模块的主要代码：Administer(ALGraph *G) int i; printf( n); printf( 请选择管理员管理项目 n); printf( n); printf( 1 初始化交通系统 n); printf( 2 城市编辑 n); printf( 3 飞机航班编辑 n); printf( 4 列车车次编辑 n); printf( 5 返回上一级菜单 n); printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); while(i!=5) switch(i) case 1:initgraph(G); break; case 2:cityedit(G); break; case 3:flightedit(G); break; case 4:trainedit(G); break; printf( n);printf( 请选择管理员管理项目 n);printf( n);printf( 1 初始化交通系统 n);printf( 2 城市编辑 n);printf( 3 飞机航班编辑 n);printf( 4 列车车次编辑 n);printf( 5 返回上一级菜单 n);printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); initgraph(ALGraph *G)int i; printf( n); printf( 请选择初始化方式 n); printf( 1 键盘 n); printf( 2 文档 n); printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); switch(i) case 1:createcityfile(); createplanefile(); createtrainfile(); CreateGraph(G); break; case 2:CreateGraph(G); break; cityedit(ALGraph *G)int i; char q; printf( n); printf( 请选择城市编辑项目 n); printf( n); printf( 1 增加城市 n); printf( 2 删除城市 n); printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); if(i=1) EnterVertex(G); if(i=2) DeleteVertex(G);flightedit(ALGraph *G)int i; char q; printf( n); printf( 请选择飞机航班编辑项目 n); printf( n); printf( 1 新增航班 n); printf( 2 删除航班 n); printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); if(i=1) EnterplaneArc(G); if(i=2) DeleteplaneArc(G);trainedit(ALGraph *G)int i; char q;printf( n);printf( 请选择列车车次编辑项目 n);printf( n);printf( 1 新增车次 n);printf( 2 删除车次 n);printf( n); printf( 你的选择是：); scanf(%d,&i); system(cls); getchar(); if(i=1) EntertrainArc(G); if(i=2) DeletetrainArc(G);3.2 计算最少费用功能模块设计设计思想：本系统设计计算最少费用功能模块，是根据图的广度遍历算法来实现整个功能的。并通过键盘输入所要查询的起始地与目的地，并选择交通方式，算出最佳路径，可以以费用为权值计算最少费用。如下图3.2所示：开始输入起始地输入目的地是否为文档中的城市提示输入错误选择交通方式返回上一级菜单是否存在两地车次提示不存在车次显示最佳路径结束图3.2 计算最少费用模块流程图详细功能：计算最少中转次数、费用功能实现是依据克鲁斯卡尔算法，以费用为权值来得出最佳路径。根据管理员输入的城市信息构建网状结构，以起始地作为第一个连通分量，然后寻找到其他连通分量的最少费用，连通城市并列入队列，连通目的地后，输入队列（即费用最少的路径）。以下是信息总览模块的主要代码：TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1)int visitedMAX_VERTEX_NUM,v,w,n=1; LinkQueue Q; ArcNode *t; Node *p,*q,*r,*s; p=(Node *)malloc(G.vexnum*sizeof(Node); for(v=0;vadjvex=v0; q-next=NULL; pv0.next=q; EnterQueue(&Q,v0); while(!IsEmpty(&Q) DeleteQueue(&Q,&v); if(k=1) t=G.verticesv.trainfirstarc; else t=G.verticesv.planefirstarc; while(t!=NULL) w=t-adjvex; if(!visitedw) visitedw=1; q=&pw; s=pv.next; while(s!=NULL) r=(Node *)malloc(sizeof(Node); r-adjvex=s-adjvex; q-next=r; q=r; s=s-next; r=(Node *)malloc(sizeof(Node); r-adjvex=w; r-next=NULL; q-next=r; if(w=v1) q=pw.next; r=q-next; printf(n旅行路线是:n); while(r!=NULL) if(k=1) printf(乘坐No.%d列车车次在%d:%d从%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).stata0.number,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); else printf(乘坐No.%d飞机航班在%d:%d从%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).stata0.number,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); q=r; r=r-next; n+; printf(最少中转次数是%d次nn,n-2); for(v=0;vnext; free(s); pv.next=NULL; free(p); return; EnterQueue(&Q,w); t=t-nextarc; for(v=0;vnext; free(s); pv.next=NULL; free(p); if(k=1) printf(n不存在列车车次从%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname); else printf(n不存在飞机航班从%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname);MinExpenditure(infolist arcs,float *expenditure,int *route)int i; *expenditure=arcs.stata0.expenditure; if(*expenditureINFINITY) *route=0; else *route=-1; for(i=1;i=arcs.last;i+) if(arcs.statai.expenditure*expenditure) *expenditure=arcs.statai.expenditure; *route=i; ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final)int v=-1,w,i,route; float m,expenditure; Node *p,*q,*r,*s; p=(Node *)malloc(G.vexnum*sizeof(Node); for(v=0;vG.vexnum;v+) *(final+v)=False; MinExpenditure(*(*(arcs+v0)+v),M+v,&route); pv.next=NULL; if(*(M+v)adjvex=v0; s-adjvex=v; s-route=route; pv.next=q; q-next=s; s-next=NULL; *(M+v0)=0; *(final+v0)=True; for(i=1;iG.vexnum;i+) m=INFINITY; v=-1; for(w=0;wG.vexnum;w+) if(*(final+w)=False) if(*(M+w)next; printf(n旅行路线是:n); while(r!=NULL) if(k=1) printf(乘坐No.%d列车车次在%d:%d从%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.number,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); else printf(乘坐No.%d飞机航班在%d:%d从%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.number,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); q=r; r=r-next; printf(最少旅行费用是%f元nn,m); for(v=0;vnext; free(s); pv.next=NULL; free(p); return; else if(v!=-1) *(final+v)=True; for(w=0;w-1) MinExpenditure(*(*(arcs+v)+w),&expenditure,&route); if(*(M+w)m+expenditure) *(M+w)=m+expenditure; q=pw.next; while(q!=NULL) s=q; q=q-next; free(s); q=&pw; s=pv.next; while(s!=NULL) r=(Node *)malloc(sizeof(Node); r-adjvex=s-adjvex; r-route=s-route; q-next=r; q=r; s=s-next; r=(Node *)malloc(sizeof(Node); r-adjvex=w; r-route=route; r-next=NULL; q-next=r; for(v=0;vnext; free(s); pv.next=NULL; free(p); if(k=1) printf(n不存在列车车次从%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname); else printf(n不存在飞机航班从%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname);3.3 测试与分析1、考虑到道路网多是稀疏网，故采用了邻接表作存储结构，其空间复杂度位O(e)，此时的时间复杂度也为O（e）。构建邻接表的时间复杂度位O(n+e)，输出路径的时间复杂度为O（n2）。由此，本交通资询系统的时间复杂度位O（n2）。2、本程序在求最短路径时使用了迪杰斯特拉算法，主要考虑在本程序的初级阶段，并不需要大量的查询，更多会是图信息的添加和修改，重在算法的理解和掌握，因此采用了算法复杂度相对较低的迪杰斯特拉算法。当然，从性能上来说，当交通图基本稳定，而且城市信息基本完善的时候，使用佛洛伊德把所有的最短路径信息存储起来可能会更方便一点，后续的查询的时间复杂度也会相对降低。由此可见，在选用算法时，不能单纯地只考虑算法的时间复杂度，有时还必须综合考虑各种因素。表1-1 航班时刻表 机 号 出 发 地 到 达 地出发时间到达时间费 用 6320北京上海上海北京16：2018：00 17：2519：05680元2104北京乌鲁木齐乌鲁木齐 北京8：0010：459：5511：401150元201北京西安 西安 北京15：2512：3517：0014：15930元2323西安广州 广州 西安7：1510：159：3511：351320元173拉萨昆明 昆明拉萨10：2012：3511：4514：00830元3304拉萨武汉 武汉拉萨14：1516：2515：4517：55890元82乌鲁木齐昆明 昆明乌鲁木齐 9：3013：0512：1515：501480元4723武汉广州广州武