数据结构课程设计全国交通咨询模拟毕业论文.doc

《数据结构课程设计全国交通咨询模拟毕业论文.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计全国交通咨询模拟毕业论文.doc（133页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 .数据结构课程设计报告题目：全国交通咨询模拟目录一、实验题目1二、实验目的1三、实验环境1四、需求分析1五、总体设计1六、主程序流程3七、概要设计5八、调试分析7九、经验体会8十、用户说明9附录一、核心算法伪代码18附录二、测试数据20附录二、源代码21133 / 133一、实验题目从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。二、实验目的1. 充分了解并掌握最短路径问题与其应用。2.根据有向图的存储结构解决实际问题。三、实验环境此系统实现的主要操

2、作平台是VC+6.0,操作系统是WINDOWS7.四、需求分析1通过对题目的分析知，是要让我们能够通过利用所学的数据结构的基本知识和技能来解决程序设计问，因此在搞程序设计之前先好好的把书复习一遍，弄清楚各个知识之间的联系。2由题目的分析知全国交通咨询管理系统是有对城市信息的增加、删除、修改、保存、查询、有错时提示出错信息等功能，最后对数据进行保存并退出操作系统。由此可知需要将函数模块化，将它做为一个独立的函数体去实现它的功能。它可以分为四大功能模块，每个模块需要去各个击破。其中可能用到C语言的指针与链表，因此，要先去复习一下C语言课本。3根据这些功能和基本要求，可充分运用我们所学的数据结构的基

3、本知识和技能去逐步的解决。其中将函数进行模块化。在数据结构中，通过队列，栈，图的声明来实现系统的各种功能的存储各城市之间乘火车的消耗价格，时间，乘飞机的价格，时间，以与中转站最少。利用指针和结点来实现城市与城市之间各种操作，而这些知识点都是我们学习数据结构必须掌握和学会运用的。五、总体设计(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是

4、城市之间所耗费的时间（要包括中转站的等候时间）或旅费。(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里采用邻接表作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面。(5) 最优决策功能模块(fast or province)。 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名与对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代

5、表的城市有交通联系的城市(代码、里程、航班、列车车次)。 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队列)中只有出发地城市，随着对栈(队列)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队列)中，则进栈(队列)，直

6、至栈(队列)为空，本题采用队列实现。 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈(队列)，再逐一出栈栈(队列)中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)与最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达与旅费，或者最少需要多少旅费才能到达与时间。(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。详细设计思想： 本题所要求的交通系统是一个有向带权图结构，考虑到要求该系统有动态增加飞机和列车航班的功能，因而采用邻接表的形式存储：

7、对每个顶点建立一个单链表，单链表中的子结点表示以该顶点连接的弧，单链表中子结点的顺序可以按权值递增的顺序排列，表头结点按顺序存储。题目中提到要提供三种策略，最快到达，最省钱到达和最少中转次数策略，前两种策略采用迪杰斯特拉算法思想，其中最快到达的权值为到达两城市所需的最短时间，最省钱到达的权值为到达两城市所需的费用，后一种采用广度优先算法的思想，只需求的两城市所在的层数，就可以求的到达两城市所需的最少中转次数。 迪杰斯特拉（Dijkstra）算法的基本思想是：设置两个顶点的集合S和TVS，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，

8、然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。下面讨论基于邻接表的存储结构求两点间最短路径的方法： 根据迪杰斯特拉(Dijkstra)算法所依据的原理：若按长度递增的次序生成从源点V0到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径

9、）。 按照这一思想，构造以下算法： 设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

10、中的所有顶点：do 由邻接表中该表头结点开始依次找单链表的下一子结点(沿链域指针依次访问)；if(该子结点S)/IS该子结点的邻接点序号=TRUE if（子结点链域指针指向NULL）F=TRUE；S=S-该表头结点；break；else continue；else break；while(); 如F=FALSE,则U=U+该子结点；如果S=空集，则结束； (4)下一次短路径的终点必U。比较U中子结点到V0的dist值（其值为U中结点的弧的权值+其表头结点的dist值），由dist值最小的子结点的邻接点域确定次短路径的终点VX， PATH VX=PATH该子结点的表头结点+VX（集合的并计算）。

11、distVX=VX所属子结点的弧的权值+其表头结点的dist值。U=；如果VX为所要找的顶点，则结束；回到2执行。广度优先搜索遍历图类似于树的按层次遍历，其基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。六、主程序流程退出显示交通系统PrintGraph用户咨询UserDemand管理员管理Administer主函数ma

12、in（）返回上一级菜单列车车次编辑Administer飞机航班编辑Administer城市编辑cityedit管理员管理Administer初始化交通系统initgraph返回上一级菜单最少中转次数TransferDispose最少旅行时间TimeDispose用户咨询UserDemand最少旅行费用ExpenditureDisposeUserDemand显示城市显示飞机航班显示列车车次返回上一级菜单显示交通系统PrintGraph文档键盘初始化交通系统initgraph删除城市新增城市城市编辑cityedit删除航班新增航班飞机航班编辑planeedit删除车次新增车次火车列次编辑train

13、edit七、概要设计系统用到的抽象数据类型定义：1ADT Graph数据对象V：一个集合，该集合中的所有元素具有一样的特性数据关系R：R=VRVR=|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数据元素：可以是任意类型的数据，但必须属于同一

14、个数据对象关系：队列中数据元素之间是线性关系。基本操作：（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下有且仅有一个前驱。基本操作：（1）CreateTimeTree(p,i,j,&

15、Q,infolist arcs)；（2）CopyTimeTree(p,q)；（3）VisitTimeTree(p)；ADT TimeTree系统中子程序与功能要求：1 Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程序。2initgraph(ALGraph *G)：初始化交通系统的子程序3createcityfile( )：创建城市文件的子程序4createplanefile( )：创班文件的子程序5createtrainfile( )：创建列车时刻表文件的子程序6LocateVertex(ALGraph *G,char

16、*v)：提供城市名在城市交通系统中相应编号7CreateGraph(ALGraph *G)：创建城市交通系统8cityedit(ALGraph *G)：提供城市编辑功能9EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能10DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功能11flightedit(ALGraph *G)：提供航班编辑功能12EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功能13DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的功能14：tra

17、inedit(ALGraph *G):提供列车车次的编辑功能15EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次的功能16DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车次的功能17UserDemand(ALGraph G)：提供用户咨询的界面18DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序19InitQueue(LinkQueue *Q)：初始化队列20EnterQueue(LinkQueue *Q,int x)：入队操作21DeleteQueue(LinkQueue *Q

18、,int *x)：出队操作22IsEmpty(LinkQueue *Q)：队列判空操作23TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM, (*arcs)MAX_VERTEX_NUM ,ALGraph G,ALGraph G,int v0,int v1)：提供最少中转次数决策的功能 24MinExpenditure(infolist arcs,float *expenditure, float *route)：提供两个城市之间最少费用的功能 25ExpenditureDispose(int k, infolist (*arcs)MAX_V

19、ERTEX_NUM,ALGraph G, int v0,int v1,float *D,int *final)：提供最少费用决策的功能26MinTime(infolist arcs,float *time,float *route)：提供两个城市之间最短时间的功能27TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM)：提供两个之间相隔一个以上城市的城市间的最短时间的功能28CreateTimeTree(TimeTree p,int i,int j,LinkQueue*Q,infolist(*arcs)MAX_VERTEX_NUM

20、)：创建时间树29CopyTimeTree(TimeTree p,TimeTree q)：复制时间树30VisitTimeTree(TimeTree p)：访问时间树31DestoryTimeTree(TimeTree p)：销毁时间树32TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM, ALGraphG,int v0,int v1,float *D,int *final)：提供最少时间决策的功能33：PrintGraph(ALGraph *G)：显示整个城市交通系统八调试分析调试过程中遇到的问题是如何解决的以与对设计与实现的回顾讨论和分析：

21、在调试的过程中碰到了一下问题：a. 函数中的形参变量太多，总是不经意就出错了；b. 文件操作中经常遇到读入错误或找不到文件；解决方案：a. 对引用形参了解的不是很透彻，导致错误，通过查阅相关书籍和请教编程能力较高的人，最终解决问题。b. 通过参考谭浩强编著的C程序设计中的文件操作，文件格式和相关文件路径的设置，然后向计本的同学提问，最终解决问题。算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想：基本操作时间复杂度空间复杂度void Administer(ALGraph *G)O(1)O(1)void cityedit(ALGraph *G)O(n)O(n)voi

22、d CopyTimeTree(TimeTree p,TimeTree q)O(n)O(1)void createcityfile()O(n)O(n)void CreateGraph(ALGraph *G)O(n)O(n)void createplanefile()O(1)O(1)void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM)O(n)O(n)void createtrainfile()O(1)O(1)int DeleteplaneArc(ALGraph *G)O(n)O

23、(n)void DeleteQueue(LinkQueue *Q,int *x)O(1)O(1)int DeletetrainArc(ALGraph *G)O(n)O(n)void DeleteVertex(ALGraph *G)O(n)O(n)void DemandDispose(int n,ALGraph G)O(1)O(1)void DestoryTimeTree(TimeTree p)O(n)O(1)void EnterplaneArc(ALGraph *G)O(n)O(n)void EnterQueue(LinkQueue *Q,int x)O(1)O(1)void Entertra

24、inArc(ALGraph *G)O(1)O(1)void EnterVertex(ALGraph *G)O(n)O(n)void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final)O(n)O(1)void flightedit(ALGraph *G)O(1)O(1)void initgraph(ALGraph *G)O(1)O(n)void InitQueue(LinkQueue *Q)O(1)O(1)int IsEmpty(LinkQueue

25、 *Q)O(1)O(1)int LocateVertex(ALGraph *G,char *v)O(n)O(1)void MinExpenditure(infolist arcs,float *expenditure,int *route)O(n)O(n)void MinTime(infolist arcs,int *time,int *route)O(n)O(n)void PrintGraph(ALGraph *G)O(1)O(n)int save(ALGraph *G)O(1)O(1)void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM

26、,ALGraph G,int v0,int v1,int (*T)2,int *final)O(n)O(n)void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM)O(n)O(n)void trainedit(ALGraph *G)O(1)O(1)void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1)O(n)O(n)void UserDemand(ALGraph G)O(1)O(1)void VisitTimeTre

27、e(TimeTree p)O(n)O(n)九、经验体会 通过本次课程设计，我学到了一种程序设计方法，就是结构化程序设计方法，在程序设计过程中，：(1)自顶向下；(2)逐步细化；(3)模块化设计(4)结构化编码。这种设计方法的过程是将问题求解由抽象逐步具体化的过程，而且，用这种方法便于验证算法的正确性。让我兴奋的是真切的感受到了模块化设计的魅力，让复杂的问题变得如此简单，没有真切实践过的人是无法体会到其中的神奇。 本次课程设计所使用的是较为复杂的抽象数据类型图，而且在弧的基础上增加了许多信息，如添加了时间，费用等等，这无疑给编程加大了难度，同时也是相当的具有挑战性。在编程的过程中，我用到了全局数

28、组，我将数组放在工程的头文件里面，编译的时候报错，说是多重定义。最终放弃了创建工程，而选择了单个文件进行编译和运行，结果顺利通过。同时，在文件操作方面我也曾遇到问题，因为我们的C语言文件操作老师讲得并不是很仔细，我自己看起来也有难度，最后通过向计本的同学请教最终解决了文件操作方面的问题。总之，这次课程设计是对这一个学期以来对数据结构学习成果的一个验证，同时也是理论与实践很好的结合，既对学过的数据结构进行了巩固，也对我的编程能力奠定了坚实的基础。十用户使用说明 1运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：

29、用户咨询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出程序。2管理员管理界面包括5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的增加和删除，具体使用见说明4；选项三：航班编辑界面，可进行航班的增加和删除，具体使用见说明5；选项四：列车车次编辑界面，可进行列车车次的增加和删除，具体使用见说明6；选项五：返回上一级菜单，可返回主界面。 3初始化城市交通系统界面包括两

30、个选项：选项一：通过键盘初始化城市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间，则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下，且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。4城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户

31、输入的是已有的城市名，程序将提示出错；选项二：删除城市，可在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出错。 5航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达城市与费用、时间等信息；选项二，删除航班，可删除两个城市间的一条航班，选择该项后用户需输入要删除航班的编号，起始城市，到达城市的信息，若航班不存在或编号、城市输入有误，程序将提示错误。 6列车车次编辑界面包括两个选项：选项一：增加列车车次，可在两个城市之新增列车车次，选择该项后用户需输入新增列车的编号，起始城市，到达城市与费用、时间等信息；选

32、项二，删除列车车次，可删除两个城市间的一条列车车次，选择该项后用户需输入要删除车次的编号，起始城市，到达城市的信息，若列车次不存在或编号、城市输入有误，程序将提示错误。7用户咨询界面包括四个选项：选项一：最少费用咨询；选项二：最少时间咨询；选项三：最少中转次数咨询；选项三：返回上级菜单，可返回主界面。选择选项一、二、三都要求用户输入咨询信息，包括起始城市，到达城市和交通工具。输入完毕后城市提示用户是否确认，若不确认则要求用户重新输入咨询信息，若确认则给出用户所需的最优决策信息。十一测试结果：1. 个人信息界面：2. 操作主界面：3. 管理员界面：4. 交通系统初始化方式选择界面：5. 城市编辑

33、界面：6. 飞机航班编辑：7. 列车车次编辑：8. 显示交通系统主界面：9. 显示城市：10. 显示飞机航班：11 用户咨询：12. 选择旅行起始城市：13. 选择旅行到达城市：14. 选择旅行的交通工具：15. 最少旅行费用：附录1、创建交通系统核心算法的伪代码intCreatGraph(ALGraph *G)if(打开城市文件，文件指针返回值为空）输出错误文件信息；程序返回值为0；while(文件不为空）将文件指针所指的字符串读到城市名数组cityi中；i+;关闭文件；j=0;while(jvexnum=i;打开航班信息文件plane.txt;将文件中的容以块为单位读到缓冲区数组a中；关闭

34、文件；a的计数变量k=0;弧的计数变量arc_num=0;while(kverticesi.planfirstarc;m=0;while(q!=NULL)if(弧q中的邻接顶点与j相等）将数组ai中的容都复制到弧q中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组ai中的容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;k+;G-planarcnum=arc_num;打开列车信息文件plane.txt;将文件中的容以块为单位读到缓冲区数组a中；关闭文件；a的计数变量k=0;弧的计数变量arc_num=0;while(kverticesi

35、.trainfirstarc;m=0;while(q!=NULL)if(弧q中的邻接顶点与j相等）将数组ai中的容都复制到弧q中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组ai中的容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;k+;G-trainarcnum=arc_num;返回；2、测试数据 航班时刻表机号 出发地到达地出发时间到达时间费用632016：2018：0017：2519：05680元2104乌鲁木齐乌鲁木齐8：0010：459：5511：401150元20115：2512：3517：0014：15930元23237

36、：1510：159：3511：351320元17310：2012：3511：4514：00830元330414：1516：2515：4517：55890元82乌鲁木齐乌鲁木齐9：3013：0512：1515：501480元47237：0511：258：4513：05810元 列车时刻表车次出发地到达地出发时间到达时间车费2713：1521：2405：4113：4221：1205：1313：3021：3978元82元82元78元417：1115：2000：3509：4015：0800：1309：2817：3790元100元100元90元5908：2003：3903：1622：53182元1340

37、3：5219：2418：5610：28162元32306：1816：3116：1402：27102元87307：1321：4221：1711：46134元1169：3618：5418：3203：4898元37313：1500：3500：1511：35116元74717：4115：1314：4712：19210元371乌鲁木齐乌鲁木齐11：4200：3523：5411：23114元21818：5001：3411：5118：35178元3、源代码#define MAX_VERTEX_NUM 18#define NULL 0 /空值为0#define MAX_ARC_SIZE 100 /最大弧长10

38、0#define MAX_ROUTE_NUM 5 #include#include#include#include#define False 0#define True 1#define INFINITY 10000typedef 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 cityname10;ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Node