数据结构课程设计航班查询系统实验
报告
目录
一、概述 (1)
二、系统分析 (1)
1.航班信息的查询与检索 (1)
2.航班信息查询与检索数据结构理论 (1)
三、概要设计 (2)
1.系统的功能 (2)
2.系统模块分析及其流程图 (3)
四、详细设计 (6)
1.各函数说明 (6)
2.定义相关数据类型 (9)
3. 航班信息的查询 (10)
五、运行由于测试 (14)
六、总结与心得 (18)
参考文献 (18)
附录 (18)
一、概述
随着信息产业的飞速发展,信息化管理及查询已经进入并应用到各行各业,影响着人们的价值观念和生活方式。
因此,要提高企业信息化建设,利用先进的办公自动化系统来实现企业内部信息管理、共享及交流,从而提高企业综合实力。
本次设计是针对航班的查询系统,该设计要求对飞机航班信息进行排序和查询。
可按航班的航班号、起点站、终点站等信息进行航班信息的查询。
二、系统分析
1.航班信息的查询与检索
进入系统后,首先提示输入航班的信息,包括:航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价等,票价为整型,其它为字符型。
当输入完一个信息后会提示是否继续输入,重复以上步骤输入全部的信息。
进入主菜单后会给出用户操作的界面,根据提示进行航班信息的查询。
2.航班信息查询与检索数据结构理论
针对在本该类系统中的数据的处理情况,本系统采用二分查找法、基数排序法、最高位优先法。
二分查找法也称为折半查找法,它充分利用了元素间的次序关系,采用
分治策略,可在最坏的情况下用O(log n)完成搜索任务。
它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。
如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。
如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。
对航班号的排序是采用的基数排序法。
基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。
最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。
再将各组连接起来,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。
三、概要设计
1.系统的功能
本任务要求对飞机航班信息进行排序和查找。
可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
本设计主要是对排序
以及查找等概念进行综合练习。
以链式基数排序为主线,用到二分查找和顺序查找等知识,还有建立静态链表等相关概念。
2.系统模块分析及其流程图
(1)航班排序
对输入系统内的航班首先要进行排序,我们采用的基数排序,从低位到高位依次对关键字进行分配和收集,分两段实现其算法流程图。