飞机航班售票系统的数据结构课程设计报告

徐州工程学院课程设计报告课程名称数据结构课程设计专业电子信息科学与技术班级学生姓名学号设计题目飞机航班售票系统指导教师设计起止时间2009年6月25日至2009年6月26日成绩一、问题描述创建一个飞机航班售票系统，要求有输入航班信息、查询航班信息的功能。飞机的航班信息在运行时由人输入。具体实现功能要求如下1、要求有输入功能，信息由使用者输入。2、要求有航班查询功能，通过查询飞机的航班号，可以得到本次航班的起点站、终点站、起飞时间、到达时间、航班期、票价等信息。3、可以通过单独查询起点站来查询是否有符合要求的航班号。4、可以通过单独查询终点站来查询是否有符合要求的航班号。5、可以通过单独查询起飞时间来查询是否有符合要求的航班号。6、可以通过单独查询到达时间来查询是否有符合要求的航班号。7、查询结束后可以选择退出系统二、基本要求在此程序设计中要求做到以下要求或者运用到以下知识点（1）熟练掌握根据问题需求抽象出逻辑结构进而选择合适的物理结构的方法（2）掌握设计和调试应用程序的方法及技巧（3）掌握实用程序的开发与调试技术（4）线性结构和非线性结构（5）逻辑结构和物理结构（6）各种物理存储结构实现方式下各种运算的实现三、算法思想程序中运用了折半查找、排序等算法。折半查找折半查找的全过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或者找不到该记录为止。折半查找过程是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时（表明查找不成功）为止。折半查找在查找有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，和给定值进行比较的关键字的个数恰为该结点在判定树上的层次数。因此，折半查找成功时进行比较的关键字个数最多不超过树的深度，而具有N个结点的判定树的深度为LOG2N1，所以折半查找法在查找成功时和给定值进行比较的关键字的个数至多为LOG2N1。折半查找的平均查找长度是是多少假定有序表的长度N2K1，（反之，HLOG2（N1），则描述折半查找的判定树是深度为H的满二叉树。树中层次为1的结点有1个，层次为2的结点有2个层次为H的结点有2K1个。假设表中每个记录的查找概率相等（PI1/N），则查找成功时的平均查找长度ASLBSN1/NLOG2N11对任意的的N，当N较大时，可有下列近似结果ASLBSLOG2（N1）1折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。排序排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意排列，重新排列成一个按关键字有序的序列。在排序过程中通常要进行一下两种操作1、比较两个关键字的大小2、将记录从一个位置移动到另一个位置前一个操作对大多数排序方法来说都是必要的，后一个操作可以通过改变记录的存储方式来避免。待排序的记录序列可有下列3种存储方式1、待排序的一组记录存放在地址连续的一组存储单元上。2、一组待排序记录存放在静态链表中，记录之间的次序关系由指针指示，则实现排序不需要移动记录。3、待排序记录本身存储在一组地址连续的存储单元内，同时另一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束之后再按照地址向量中的值调整记录的存储位置。四、模块划分五、数据结构顺序表线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的机内表示称作线性表的顺序存储结构货顺序映像，通常，称这种存储结构的线性表为顺序表。它的特点是为表中相邻的元素AI和AI1赋以相邻的存储位置LOC（AI）和LOC（AI1）。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的起始位置，线性表中任一数据元素都可随机存取所以线性表的顺序存储结构是一种随机存取的存储结构。存储地址数据元素在线性内存状态表中的位序B1BL2BI1LIBN1LNBNL空闲空闲BMAXLEN1L空闲由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序结构存储。由于线性表的长度可变，且所需的最大存储空间随问题不同而不同，则在C语言中可用动态非配的一维数组。链式表线性链表的链式存储结构特点是用一组任意的存储单元存储线性表的数据元素（这组存储元素可以使连续的，也可以是不连续的）。因此，为了表示每个数据元素AI与其直接后继数据元素AI1之间的逻辑关系，对数据元素AI来说，除了储存期本身的信息以外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素AI的存储映像，称为结点。它包括两个域其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。N个结点链结成一个链表，即为线性表（A1，A2，A3，AN）的链式存储结构。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。六、源程序A1A2AIANINCLUDEINCLUDEDEFINEMAXSPACE100DEFINEKEYLEN7DEFINERADIX_N10DEFINERADIX_C26TYPEDEFCHARKEYTYPETYPEDEFSTRUCTCHARSTART6CHAREND6CHARSCHE10CHARTIME15CHARTIME25CHARMODEL4INTPRICEINFOTYPETYPEDEFSTRUCTKEYTYPEKEYSKEYLENINFOTYPEOTHERSINTNEXTSLNODETYPEDEFSTRUCTSLNODESLMAXSPACEINTKEYNUMINTLENGTHSLLISTTYPEDEFINTARRTYPE_NRADIX_NTYPEDEFINTARRTYPE_CRADIX_CVOIDDISTRIBUTESLNODESL,INTI,ARRTYPE_NF,ARRTYPE_NEINTJ,PFORJ0J2IDISTRIBUTELSL,I,FN,ENCOLLECTLSL,I,FN,EN/保存输入的信息FORI1I0IDISTRIBUTE_CLSL,I,FC,ECCOLLECT_CLSL,I,FC,ECVOIDARRANGESLLISTSLNODETEMPPLSL0NEXTFORI1I1PRINTF“航班信息查询系统N“PRINTF“N“PRINTF“1航班号N“PRINTF“2起点站N“PRINTF“3终点站N“PRINTF“4起飞时间N“PRINTF“5到达时间N“PRINTF“0退出系统N“PRINTF“N“PRINTF“请选择05“SCANF“D“,PRINTF“N“SWITCHICASE1PRINTF“输入要查询的航班号字母要大写“SCANF“S“,KEYKBINSEARCHL,KEYPRINTF“N“IFK0PRINTF“无此航班信息，可能是输入错误N“ELSEPRINTF“航班号起点站终点站航班期起飞时间到达时间机型票价N“PRINTF“8S7S6S11S9S7S5S4DN“,LSLKKEYS,LSLKOTHERSSTART,LSLKOTHERSEND,LSLKOTHERSSCHE,LSLKOTHERSTIME1,LSLKOTHERSTIME2,LSLKOTHERSMODEL,LSLKOTHERSPRICEPRINTF“N“BREAKCASE2PRINTF“输入要查询的航班起点站名“SCANF“S“,KEYSEQSEARCHL,KEY,IBREAKCASE3PRINTF“输入要查询的航班终点站名“SCANF“S“,KEYSEQSEARCHL,KEY,IBREAKCASE4PRINTF“输入要查询的航班起飞时间“SCANF“S“,KEYSEQSEARCHL,KEY,IBREAKCASE5PRINTF“输入要查询的航班到达时间“SCANF“S“,KEYSEQSEARCHL,KEY,IBREAKCASE0PRINTF“NNN再见NNN“VOIDINPUTDATASLLISTCHARYNYWHILEYNY|YNYPRINTF“航班号起点站终点站航班期起飞时间到达时间机型票价N“SCANF“SSSSSSSD“,LSLIKEYS,LSLIOTHERSSTART,LSLIOTHERSEND,LSLIOTHERSSCHE,LSLIOTHERSTIME1,LSLIOTHERSTIME2,LSLIOTHERSMODEL,IGETCHARRADIXSORTLARRANGEL/将输入的信息排序PRINTF“继续输入吗Y/N“SCANF“C“,LLENGTHI1VOIDMAINSLLISTLLKEYNUM6LLENGTH0INPUTDATAL/调用输入函数SEARCHCONL/调用查找函数七、测试例子及结果分析八、心得体会本次课程设计终于结束了。通过这次课程设计，我加深了对查找（尤其是折半查找）和排序的概念的理解，并能够熟练地将它们运用到实际操作中。通过此次课程设计了解了查找、排序的时