数据结构课程设计城市交通咨询系统、航班信息的查询与检索.doc

《数据结构课程设计城市交通咨询系统、航班信息的查询与检索.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计城市交通咨询系统、航班信息的查询与检索.doc（27页珍藏版）》请在三一办公上搜索。

1、课程设计题目： 城市交通咨询系统一、课程设计的原始资料及依据在交通网络非常发达，交通工具和交通方式不断更新的今天，人们的出差、旅游或做其他的出行时，不仅关心节省交通运费问题，而且对里程和所需要时间等问题感兴趣。可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。这个交通咨询系统可用回答旅客提出的各种问题。 二、课程设计主要内容及要求1. 建立交通网络图的存储结构。2. 画出主要的功能结构图和主要模块的流程图。3. 使用迪杰斯特拉算法：求一个城市到其它所有城市最短路径。4. 使用弗洛伊德算法：求任意两个城市间最短路径。 三、对课程设计说明

2、书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手

3、写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。 四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。 五、时间进度安排六、主要参考资料（文献）1郭翠英.C语言课程设计案例精编.北京：中国水利水电出版社.2004.3 2谭浩强.C语言程序设计.北京:清华大

4、学出版社.1999.12 3张翔.C语言函数大全.北京:清华大学出版社.2002.44浦滨.C游戏编程从入门到精通.北京: 北京希望电子出版社.2002.5 5陈天洲.C语言高级程序设计. 北京:人民邮电出版社.20026杨旭.C语言程序设计案例教程.北京: 人民邮电出版社.20057 王为青C语言高级编程及实例剖析北京:人民邮电出版社2008028徐慧.C语言实例解析精粹.北京:人民邮电出版社.2006.049 姚大鹏 栾好利 张翼英 等编著.C语言程序设计教程习题与上机实训指导.中国水利水电出版社.200510 王为青C语言实例解析北京:人民邮电出版社200802 课程设计题目：航班信息的

5、查询与检索一、课程设计的原始资料及依据当今乘飞机旅行的人越来越多，使愈来愈多的人选择了飞机为长距离出行的交通工具，这就使航空公司以及机场的工作量愈来愈大，需要用电脑来解决问题，人们需要关心了解各类航班的班次、时间、价格及机型等信息。在这个飞行航班数据的信息模型中，航班号是关键字。查阅有关程序设计的案例资料，进一步理解程序设计模块化的思想，并利用此思想，根据对程序设计学习编写一个航班信息的查询与检索系统。通过本设计可以加深理解利用程序设计思想开发一个系统的整个流程，提高分析问题、解决问题和实际动手的能力。二、课程设计主要内容及要求1. 建立：建立一个线性表的存储结构。2. 录入功能：输入航班信息

6、。3. 排序：按航班号进行排序。3. 查询功能：输入航班号显示相应数据元素。输入起点站显示相应数据元素。输入终点站显示相应数据元素。输入起飞时间显示相应数据元素。输入到达时间显示相应数据元素。4. 退出：退出查询系统。三、对课程设计说明书撰写内容、格式、字数的要求1. 课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书

7、写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、

8、数量、质量等方面的要求 1完成“任务书”中指定的操作功能，运行稳定。 2课程设计说明书。五、时间进度安排 六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.2007 2谭浩强.C程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.05 5李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002.04 沈阳工程学院课程设计报告 摘要摘 要 新世纪需要具有丰富的现代科学知识，能够独立解决面临的任务，充满活力，又有创新意

9、识的新型人才。近年来，我国在计算机应用，计算机软件和电子类相关专业的人才培养方面取得了长足的进展，每年的计算机相关专业毕业生都有数十万人。但是毕业生走进企业、公司、政府机构或研究单位之后，往往深刻地感觉到缺乏实际开发项目的经验，不善于综合运用所学理论，对知识的把握缺乏融会贯通能力。作为新世纪的大学生，我们应当站在时代发展的前列，掌握现代科学技术知识，调整自己的知识结构和能力结构，以适应社会发展的要求。开展数据结构课程设计有助于提高我们的实际动手操作能力以及项目开发能力。本次数据结构课程设计城市交通咨询这个题目，在存储方式上是运用了图的结构，在编写程序的过程中遇到了许多问题。例如：如何定义图的存

10、储结构，怎样实现单源路径最短等一系列问题，但经过讨论和改正，使程序达到预期的要求。航班信息查询与检索要求对航班信息进行查找和排序。需要利用二分法对排好序的航班号快速进行查找，而如何进行排序使用哪种方法排序引起了我们的热切讨论，最后决定使用基数排序法。在为期两周的数据结构课程设计学习中，先要学习数据结构课程的目的掌握数据结构存储的方法，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法结构存储是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上和运用何种存储的方法

11、，通过思考和大量的阅读，来构造一个完整的程序。数据结构存储的设计直接关系到程序的好坏。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词 图，数据结构，最短路径，查找，排序。 沈阳工程学院课程设计报告 目录目录 第一章 问题分析 . 11.1引言 . 11.2背景 . 11.3分析 . 11.3.1 城市交通咨询系统 . 11.3.2 航班信息的查询与检索 . 2第二章 原理与运行环境 . 32.1数据结构理论 . 32.1.1城市交通咨询数据结构理论 . 32.1.2航班信息查询与检索数据结构理论 . 42.2 运行环境. 4第三章 系统分析与设计 . 83.1城市交通咨询系

12、统系统分析与设计 . 83.1.1系统的功能 . 83.1.2系统模块分析及其流程图 . 93.2航班信息的查询与检索 . 123.2.1系统的功能 . 123.2.2 系统模块分析及其流程图 . 12第四章 系统功能实现 . 174.1城市交通咨询系统功能实现 . 174.1.1定义主函数 . 174.1.2对城市间数据的存储 . 194.1.3定义迪杰斯特拉算法 . 194.1.4定义费洛伊德算法 . 214.2 航班信息查询与检索系统功能实现. 224.2.1定义相关数据类型 . 224.2.2 实现排序各函数说明 . 244.2.3 航班信息的查询 . 26结论 . 30致谢 . 31

13、参考文献 . 32 沈阳工程学院课程设计报告 第一章 问题分析第一章 问题分析 1.1引言 数据结构的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不

14、掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课程设计主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。通过本次课程设计，相信我们一定能加强对数据结构这门课程的学习，尤其在动手实践上会有很大的进步。 1.2背景 在交通网络非常发达，交通工具和交通

15、方式不断更新的今天，人们的出差、旅游或做其他的出行时，由于不同目的的旅客对交通工具有不同的要求。可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。这个交通咨询系统可用回答旅客提出的各种问题。交通是社会经济和社会生活的大动脉，良性运作的交通系统是国民经济和人们正常工作、生活的根本保证。随着时代的发展及社会的进步，愈来愈多的人们开始采用新的代步工具。乘坐飞机旅行的人越来越多，人们需要了解各类航班的班次、时间、价格及机型等信息。这就需要一个专门的系统供人们查询各类航班的信息。 1.3分析 1.3.1 城市交通咨询系统 该设计共分三个部分，一

16、是建立交通网络图的存储结构;二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。1建立图的存储结构要实现设计要求，首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻1沈阳工程学院课程设计报告 第一章 问题分析 关系的矩阵。一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息。2单源最短路径最短路径问题的提法很多。在这里先讨论单源最短路径问题：即已知带权图，我们希望找出从某个源点S到G中其余各顶点的最短距离。此处要用到迪杰斯特拉算法，即按路径长度递增产生诸顶点的算法

17、。3任意一对顶点间的最短路径要解决这个问题，我们可以依次把有向图网络中每个顶点做为源点重复执行迪杰斯特拉算法n次，即可求得每对顶点之间的最短距离。这里用到另一种算法，称为费洛伊德算法。 1.3.2 航班信息的查询与检索 对于本设计可采用基数排序法对于一组具有结构特点的航班进行排序，利用二分法对排好序的航班记录按航班号实现快速查找，按其他方式的查找可采用最基本的顺序查找方法进行，因为它们用到的比较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等。其中航班号的格式比较特别开头为航班公司名称的缩写，用两个大写字母表示，后四位为航班号，这种航班号关

18、键字分为两部分，即字母和数字。其余七项输入内容不涉及项目核心，因此除票价为数值型外，均定义为字符串型即可。2沈阳工程学院课程设计报告 第二章 原理与运行环境第二章 原理与运行环境 2.1数据结构理论 2.1.1城市交通咨询数据结构理论 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个肢解前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中的多个元素（及其孩子结点）有关，但只能和上一层中一个元素（即其双亲结点）相关；而在图形结构中，结点之间的关系可以是任意的，图中任意的两个数据元素之间都可能有关。

19、由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本次课程设计的城市交通咨询系统实验分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。建立图的存储结构首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。Wij，若(vi,vj)或E(G);Ai，j=0或，当不满足上述条件时。一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵

20、外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息单源最短路径初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE；Dv1=0；/S集初始时只有源点，源点到源点的距离为0；while（S集中顶点数<n）开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；任意一对顶点间最短路径假设求从顶点vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径vi，v1和v1，vj是否存在。如果存在，则比较路径vi，vj和

21、vi，v1，vj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径vi，v2，vj，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么vi，v2，vj可分解为vi，v2和v2，vj，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径vi，v2，vj的长度。将该长度与前一次中求出的从vi到vj的中间顶3沈阳工程学院课程设计报告 第二章 原理与运行环境 点序号不大于2的最短路径。依次类推，直至顶点vn加入当前从vi到vj的最短路径出从vi到vj的中间顶

22、点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。 2.1.2航班信息查询与检索数据结构理论 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，我们采用的基数排序法将航班号升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子

23、表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果x<an/2，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>an/2，则我们只要在数组a的右 半部继续搜索x。对航班号的排序是采用的基数排序法。基数排序法又称“桶子法”（bucket sort）或bi

24、n sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(Least Significant Digit f

25、irst)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 2.2 运行环境 在数据结构程序的运行环境为Visual C+ 6.0其工作环境如图2.1所示。 4沈阳工程学院课程设计报告 第二章 原理与运行环境 图2.1 Visual C+ 6.0 的工作环境 C与C+程序Visual C+6.0的材料如下：Visual C+6.0由Microsoft开发, 它不仅是一个C+ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境.Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Cl

26、ass Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。总体来讲，运行环境方便快捷。建立C语言源程序文

27、件。建立方法：选择菜单命令“文件” “新建”或直接点击对话框中的“新建”，选择Win32Console，并在右上方“工程名”称下键入工程名如图2-2所示。在工程建立完成后选择C+Source，并在“文件名”下键入文件名如图2.3所示。 5沈阳工程学院课程设计报告 第二章 原理与运行环境 图2.2 建立C语言源程序建立工程 程序的编辑与编译。编辑完成后，选择菜单栏中的“运行”“调试程序”即可对程序进行编译。当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，当然有时提示位置不一定很准

28、确。 图2.3 建立C语言源程序建立文件 程序的执行。单击工具栏上的“红色感叹号”按钮或Ctrl+F5，即可执行刚编写程序，6沈阳工程学院课程设计报告 第二章 原理与运行环境 如图2.4所示。 图2.4 对源程序进行编写 使用C与C+程序设计VC+6.0开发环境，对源程序执行编译。如图2.5所示。 图2.5 执行编写的程序7沈阳工程学院课程设计报告 第三章 系统分析与设计第三章 系统分析与设计 3.1城市交通咨询系统系统分析与设计 3.1.1系统的功能 本系统主要有两个功能，首先是找到已知源点所表示的城市到其余结点所表示的城市之间的最短距离和该距离下的最短路径并输出找到的最短距离和路径；第二个

29、功能是找到任意两个结点城市之间的最短距离并保存两城市之间的最短路径。按用户的需求输出所需要的两城市之间的最短路径与距离。(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程)存储于内存中。(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间的距离(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。(4) 选择功能模块。用费洛伊德算法找任意两城市间的最短距离与路径。 根据具体最优决策的要求，用Dijk

30、stra算法求出出发城市到其它各城市的最优值(最短距离)，首先，引进一个辅助向量，它的每个分量Di表示当前所找到的从始点v到每个终点vi的最短路径的长度。它的初态为： 输出结果。从目的城市出发，依次输出保存着最短路径的辅助数组中的值。(5) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。其主程序的流程图如图3.1所示。 8沈阳工程学院课程设计报告 第三章 系统分析与设计 图3.1主函数流程图3.1.2系统模块分析及其流程图 1.在找从已知城市到其余城市之间的最短距离和路径，我们用迪杰斯特拉算法实现，其流程图如图3.2所示。2.在找任意两个城

31、市间的最短路径及距离时我们用到了费洛伊德算法，其流程图如图3.3所示。9沈阳工程学院课程设计报告 第三章 系统分析与设计 N 图3.2迪杰斯特拉算法求最短路径10沈阳工程学院课程设计报告 第三章 系统分析与设计 图3.3 费洛伊德算法求最短路径11沈阳工程学院课程设计报告 第三章 系统分析与设计 3.2航班信息的查询与检索 3.2.1系统的功能 本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综合练习。以链式基数排序为主线，用到二分查找和顺序查找等知识，还有建立静态链表等相关概念。其主要功能模块图

32、如3.4所示。 图3.4航班信息查询与检索系统功能模块图 3.2.2 系统模块分析及其流程图1.航班排序对输入系统内的航班首先要进行排序，我们采用的基数排序，从低位到高位依次对关键字进行分配和收集，分两段实现其算法流程图如3.5所示。12沈阳工程学院课程设计报告 第三章 系统分析与设计 图3.5 基数排序 2.时间查找根据航班的起飞时间（到达时间）查找航班的信息，如图3.6所示。3.二分法查找功能二分法查找功能见图3.7。13沈阳工程学院课程设计报告 第三章 系统分析与设计 图3.6 时间查找 4.显示功能显示功能是将所求单词的所有行列信息依次显示在屏幕上。其功能流程图如图3.8所示。14沈阳工程学院课程设计报告 第三章 系统分析与设计