航空信息查询系统 数据结构课程设计

1、目 录一、前言1二、需求分析22.1 任务分析22.2 程序所能达到的功能32.3 输入的形式和输出值的范围32.4 测试的数据及预测3三、概要设计43.1 抽象数据类型的定义43.2 主程序的流程4四、详细设计54.1 各函数对应的伪代码算法54.2 各函数调用关系图6五、调试分析85.1 调试过程中遇到的问题及其解决办法85.2 算法的时空分析85.3 经验和体会8六、用户使用说明8七、测试结果97.1 输入界面97.2 按航班号进行查询界面97.3 按起点站进行查询界面107.4 按终点站进行查询界面117.5 按起飞时间进行查询界面117.6 按到达时间进行查询界面127.7 退出航班

2、信息查询系统界面12八、总结13九、参考文献13十、附录（源程序代码）13航班信息查询系统一、前 言随着信息产业的飞速发展，信息化管理及查询已经进入并应用到各行各业，它影响着人们的价值观念和生活方式。因此，要提高企业信息化建设，我们可以利用先进的办公自动化系统来实现企业内部信息的交流、管理与共享，从而提高企业综合实力。因此在本次课程设计中，我们将针对航班信息查询系统，实现对飞机航班信息的排序和查询这两项人们最常用的功能。在查询中，为了加快计算机对数据信息的查询速度,需要先对数据信息按关键字排序，在保证服务质量的前提下，实现查询效率的提高和服务时间的缩短。在这个系统中，主要实现了以下几个功能，在

3、航班信息输入之后，首先先用基数排序关于关键字航班号进行排序，在基数排序的时候，主要使用了以数字和字符两种处理方法；排序之后，开始根据自己设计的要求进行一系列的查询，按照航班号进行查询，按照航班号、起始站、终点站、起飞时间、到达时间进行一系列的查询。21二、需求分析2.1 任务分析航班信息主要包括：航班号、起点、终点、班期、起飞时间、到达时间、机型、票价，所以我们要根据这些信息设计飞机票的结构体，然后本系统需要以航班号为关键字进行基数排序，所以要创建航班号和航班信息为一体的链表，此航班链表因为还要需要排序比较，所以还要设计以航班号数目为基础的结构体，同时在设计过程中的基数排序将航班号分成了字母和

4、数字两部分，所以还需要十个数字和二十六个字母的两个数组进行存储基数排序过程中的数据。实现基数排序不需要进行记录关键字间的比较。它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。现在来看基数排序,基数排序是借助“分配和搜集”两种操作对单逻辑关键字进行排序的一种内部排序方法。首先以静态链表存储n个待排序的航班信息记录(这里按航班号进行基数排序),并令表头指针指向第一个记录,第一趟分配对低数位关键字(个位数)进行,改变记录的指针值分配自n个队列中去,每个队列记录中的关键字的个位数相等。第一趟收集是改变所有非空队列的队尾记录的指针域,令其指向下一个非空队列的队头记录,重新将n个队列中的记录链

5、成一个链表,第二趟分配,第二趟收集及第三趟分配和第三趟收集分别是对十位数和对百位数进行的,其过程和个位相同,这样往返做,直到排序完毕。对排序好了的航班记录要对它进行查找,怎样才能实现快速查找,首选的是二分查找,按关键字航班号进行快速查找。二分查找的查找过程为:先确定待查找查找记录所在范围(区间),然后逐步缩小范围直到找到或找不到该记录为止,选用二分查找是根据排序好了的航班信息,航班信息表已经是有序的。因为二分查找的要求要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。在具体数值查找过程中，我们可以从第一个进行查找，直到找到需要的那个，而在对航班信息的查询中我们使用了二

6、分查找的函数，这样可以更快的查找到需要的航班号。2.2 程序所能达到的功能系统的主要运行过程可以包括以下几个方面： 录入航班信息 对录入的航班信息进行分配和基数排序 根据设计的要求进行选择需要的动作 根据具体的选择进行执行具体的动作 输出查询的结果 在确认执行完成后退出系统2.3 输入的形式和输出值的范围首先在我们的设计过程中通过讨论我们确定了一些常规的数字，航班号我们确定为6位，首先两位的字母位，然后是4位的数字位，至于起始地点和终止地点我们确定为8位，而班期我们确定为10位，起始时间和终止时间我们确定为10位，机型确定为4位，以上的所有的变量都是字符型，而后面的票价我们设定为整形数字。2.

7、4 测试的数据及预测我们将根据我们的航班信息表进行正确的输入和错误的输入及其相应的输出结果测试。(1) 航班信息的录入:程序运行后,首先进行系统初始化,然后进入输入子系统提示:航班号 起点站 终点站 班期 起飞时间 到达时间 机型 票价输入: BA1542 广州 西安 4.5 1022 1323 156 850提示: 继续输入吗? y/n :y显示: 航班号 起点站 终点站 班期 起飞时间 到达时间 机型 票价 CZ3869 北京 重庆 每日 0900 1102 856 1250提示: 继续输入吗? y/n :n录入完了就按n回车系统会自动进入排序处理系统,对录入的航班信息进行链式基数排序,完

8、成后自动进入航班信息系统查询界面,在排序过程中是很快的,因为数据量小,一下就进入了”航班信息查询系统”界面(2) 航班信息查询:进入查询界面,系统就会提供查询控制菜单显示: 选1进行按航班号二分查询，选2、3、4、 5分别按起点站、终点站、起飞时间、到达时间进行顺序查询，选0退出该系统。三、概要设计3.1 抽象数据类型的定义typedef struct char start8;/起点 char end8;/终点 char sche11;/班期 char time111;/起飞时间 char time211;/到达时间 char mode5;/机型 int price;/票价infotype;

9、/一张除航班号之外的飞机票信息typedef struct char keys6; /关键字，飞机票航班号 infotype others; /航班其他信息 int next; /下一航班的编号地址slnode; /某一特定航班信息typedef structslnode s1maxspace; /最多航班的信息int keynum; /每张航班的航班号位数int length; /链表长度sllist; /航班信息表3.2 主程序的流程根据以上分析,航班信息查询系统实现的初步解决思路:（1)（工作人员）录入航班信息（2)对航班信息进行有序的排序(航班信息录入后，系统自动进行排序，以提高用户查

10、询速度)（3)选择查询方式（4)根据提示输入关键字，进行查询（5)输出查询结果（6）退出系统整体直观图如下:航班信息查询系统按航班号查询退出系统输入航班信息按起点站查询按终点站查询按到达时间查询按起飞时间查询注：在工作人员输入航班信息后本系统将自动进行排序，以便用户查询，提高服务效率！四、详细设计4.1 各函数对应的伪代码算法（详见P9 附录（源程序代码）(1) 一趟分配函数:void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e);本函数是按关键字keysi建立RADIX个子表,使同一个子表中记录的keysi相同,f0.RADIX所指

11、的各子表中的第一个和最后一个记录(2) 一趟搜集函数:void Collect(SLNode *sl,int i,ArrType_n f, ArrType_n e);本函数是按关键字keysi从小到大将0.RADIX所指的各子表依次链接成一个链表.（3）链式基数排序函数:void RadixSort(SLList *L);本函数是按关键字从低位到高位依次对各关键字进行分配和搜集,分来年感段进行.(4) 二分查找函数:int BinSearch(SLList L,KeyType key);L为待查找的表,key 为待查找的关键字,按二分查找的思想实现查找（5）输入输出函数（包括主控菜单函数）主控

12、菜单格式如下：* 航班信息查询系统 * 1.航班号 * 2.起点站 * 3.终点站 * * 4.起飞时间 * 5.到达时间 * 0.退出系统 * 请选择（0-5）：(6) 主控函数设计:void main () 初始化; 录入数据; 排序处理; 接受查找要求及查找关键字; 查找处理; 输出查找结果; 4.2 各函数调用关系图 主函数BinSearch二分查找函数Arrange整理静态链表RadixSort链式基数排序函数SeqSearch顺序查找函数Collect字符收集函数Distribute字符分配函数基 基数排序函数4起飞时间3 终点站2起点站1航班号5到达时间程序运行结束0退出系统In

13、putData行班信息录入Display显示航班记录函数searchcon 显示主控采单函数Y/N请选择0-5五、调试分析5.1 调试过程中遇到的问题及其解决办法（1）问题1：当在起点站输入“Beijing”时，在进行信息查询时只显示“beijin”解决办法：将起点站、终点站的字符串长度拓展为八位。（2）问题2：航班信息录入完毕进行查询时，一条信息重复出现，比如：1022ggg 1022ggg(1022表示10:20，ggg为机型)解决办法：每输出一条信息后，使之自动换行，避免此类错误再次发生。5.2算法的时空分析针对在本该类系统中的数据的处理情况，本系统采用顺序查找、二分查找法和基数排序法。

14、二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(n)完成搜索任务，平均情况下的时间复杂度为O(Nlog2N)，而顺序查找的平均时间复杂度是O(n)，很明显，在已排好序的的情况下，折半查找可以大大节省查找时间，提高查询效率。对航班号的排序是采用的基数排序法。基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其平均时间复杂度为O (d(n+rd)，所需辅助存储空间是O(n+rd)，其中r为所采取的基数，而m为堆数，在

15、某些时候，基数排序法的效率高于其它的比较性排序法。5.3 经验和体会通过实验发现，实验结果和预测要求基本一致，说明自己设计的系统是完全可以成功的，不过该系统还有很多不足之处，如我们还有很多功能没有考虑到，如实验结果的保存和提取，同时管理员和用户没有区别，也是说明缺少管理员密码，如果加上管理员密码的话那会更好。六、用户使用说明（详见“P9 测试结果”）该系统在开始使用时需要先进行初始化，即要用户在开始使用时先输入各个航班的信息。然后有查询航班信息需要的使用者就可根据提示自行进行查询。该系统操作简单易懂，因此基本不需要耗费资源对使用者进行指导。七、测试结果 7.1输入界面 7.2 按航班号进行查询

16、界面 7.3 按航班起点站进行查询界面 7.4 按航班终点站进行查询界面 7.5 按航班起飞时间进行查询界面 7.6 按航班到达时间进行查询界面 7.7 退出航空信息查询系统界面八、总结通过该实验，实现了对于数据结构和C语言的练习，同时也让自己对以前学过的知识进行了回顾和整理，加深了自己的印象，然后该实验还锻炼了自己的能力，使自己更加的认真，细心，让自己培养了很好的代码检查能力，同时也使自己了解了怎么做一个系统，首先要对问题做好分析，它要实现是哪些功能，接着才考虑用什么样的算法来描述，而且要比较几种算法的优缺点，再做出选择，紧接着才是写核心代码，在写代码之前要先用伪码来对程序进行描述，这样便于

17、以后工作的进行，在写代码时要特别认真。最后才是调试。整个过程都要不断的重复调试，修改，不得不说，这是一个程序学习者的天堂。九、参考文献1 严蔚敏 吴伟民 数据结构(C语言版) 清华大学出版社2002年2 苏仕华等 数据结构程序设计 机械工业出版社 2006年3 谭浩强 张基温 唐永炎 C语言程序设计教程(第二版) 高等教育出版社 2006年十、附录（源程序代码）#include<stdio.h>#include <malloc.h>#include <string.h>#include <stdlib.h>#define RADIX 10#def

18、ine maxspace 100#define keylen 7#define RADIX_n 10#define RADIX_c 26typedef char KeyType;typedef struct char start8;/起点 char end8;/终点 char sche11;/班期 char time111;/起飞时间 char time211;/到达时间 char mode5;/机型 int price;/票价infotype; /一张除航班号之外的飞机票信息typedef struct char keys6; /关键字，飞机票航班号 infotype others; /航班

19、其他信息 int next; /下一航班的编号地址slnode; /某一特定航班信息typedef structslnode s1maxspace; /最多航班的信息int keynum; /每张航班的航班号位数int length; /链表长度sllist; /航班信息表typedef int arrtype_nRADIX_n; /关于数字排序链表的数组typedef int arrtype_cRADIX_c; /关于字母排序链表的数组int m=0,n=0;/实现排序的各函数说明void distribute(slnode *s1,int i,arrtype_n f,arrtype_n e

20、)/一趟关于数字分配函数，分配好各数据，本函数是按关键字keysi建立RADIX个子表,使同一个子表中记录的keysi相同,f0.RADIX所指的各子表中的第一个和最后一个记录int j,p;for(j=0;j<RADIX_n;j+) /*各子表初始化*/fj=0;ej=0;for(p=s10.next;p;p=s1p.next)j=s1p.keysi%48; /*将数字字符转换成对应的数值性数字，48指0数字所在的ASCII码的位置*/if(!fj) fj=p;else s1ej.next=p;ej=p; /*将p指向的结点插入到第j个结点*/void collect(slnode *

21、s1,arrtype_n f,arrtype_n e)/一趟数字字符搜集函数，串联起各数据，本函数是按关键字keysi从小到大将0.RADIX所指的各子表依次链接成一个链表.int j,t;for(j=0;!fj;j+); /*找到第一个非空子表*/s10.next=fj; /*sl0.next指向第一个非空子表中的一个结点*/t=ej; while(j<RADIX_n-1)for(j=j+1;j<RADIX_n-1 && !fj;j+); /*找下一个非空子表*/if(fj) /*连接两个非空字表*/s1t.next=fj;t=ej;s1t.next=0; /*t

22、指向最后一个非空子表*/void Distribute_c(slnode *s1,int i,arrtype_c f,arrtype_c e)/一趟关于字母分配函数，分配好各数据int j,p;for(j=0;j<RADIX_c;j+)fj=0;ej=0;for(p=s10.next;p!=0;p=s1p.next)j=s1p.keysi%65; /65是ascii中第一个字母A的值if(!fj) fj=p;else s1ej.next=p;ej=p;void Collect_c(slnode *s1,arrtype_c f,arrtype_c e) /一趟字母字符搜集函数，很好的串联起

23、各数据int j,t;for(j=0;!fj;j+);s10.next=fj;t=ej;while(j<RADIX_c-1)for(j=j+1;j<RADIX_c-1 && !fj;j+);if(fj)s1t.next=fj;t=ej;s1t.next=0;void Arrange(sllist *L) /顺序查找函数int p,q,i;slnode temp;p=L->s11.next; /*p指示第一个记录的当前位置*/for(i=1;i<L->length;i+)while(p<i) /*找到第i个记录，并用p指示其在的位子*/p=L-

24、>s1p.next;q=L->s1p.next; /*q指示尚未调整的表尾*/if(p!=i)temp=L->s1p;L->s1p=L->s1i;L->s1i=temp;L->s1i.next=p; /*指向被移走的记录*/p=q; /*p指向尚未调整的表尾，为下一个准备*/void radixsort(sllist *L) /链式基数排序函数int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i<L->length;i+)L->s1i.next=i+1;/0号单元仅存放指针,不存放内容L-&g

25、t;s1L->length.next=0; /*将指针改造为静态链表*/for(i=L->keynum-1;i>=2;i-) /*按最低位优先次序对个关键字进行分配和收集,先做低4位部分*/distribute(L->s1,i,fn,en); /按数字编排航班collect(L->s1,fn,en); /按数字分配航班for(i=1;i>=0;i-)Distribute_c(L->s1,i,fc,ec); /按字母编排航班Collect_c(L->s1,fc,ec); /按字母分配航班/* 对于此算法主要是注意信息长度的赋值，对于每次调用要作相应

26、的改变。 初始化航班信息*/void InputData(sllist *L)char ch,ken;int i=0,j;doL->length+;i=L->length;printf("请按照下面的格式输入航班的信息n");printf("航班号：");scanf("%s",L->s1i.keys);printf("起点站：");scanf("%s",L->s1i.others.start);printf("终点站:");scanf("%s

27、",L->s1i.others.end);printf("航班期:");scanf("%s",L->s1i.others.sche);printf("起飞时间:");scanf("%s",L->s1i.others.time1);printf("到达时间:");scanf("%s",L->s1i.others.time2);printf("机型:");scanf("%s",L->s1i.other

28、s.mode);printf("价格：");scanf("%d",&L->s1i.others.price);scanf("%c",&ken); /存储enter符号for(j=1;j<i;j+)if(strcmp(L->s1j.keys,L->s1i.keys)=0)L->length-;break;printf("请问是否再次输入航班信息？(y/n):");scanf("%c",&ch);while(ch='y'|ch=&

29、#39;Y');radixsort(L);Arrange(L);/*实现查找的各函数说明二分查找函数*/int bisearch(sllist *l,KeyType key) /在有序表l中折半查找其关键字等于key的元素，若找到，则函数值为该元素在表中的位置int low=1,mid; int high=l->length; /置区间初值while(low<=high)mid=(low+high)/2;if(strcmp(key,l->s1mid.keys)=0) return(mid); /找到待查元素else if(strcmp(key,l->s1mid.

30、keys)<0) return(mid); /未找到，则继续在前半区间进行查找else low=mid+1; /继续在后半区间进行查找return 0;void Display(sllist *L,int i) /输出查找的结果printf("航班号：");printf("%sn",L->s1i.keys);printf("起点站：");printf("%sn",L->s1i.others.start);printf("终点站:");printf("%sn"

31、,L->s1i.others.end);printf("航班期:");printf("%sn",L->s1i.others.sche);printf("起飞时间:");printf("%sn",L->s1i.others.time1);printf("到达时间:");printf("%sn",L->s1i.others.time2);printf("机型:");printf("%sn",L->s1i.oth

32、ers.mode);printf("价格：");printf("%dn",L->s1i.others.price);void SeqSearch(sllist *L,KeyType key,int i)int j,k,m=0;for(j=1;j<=L->length;j+)switch(i)case 2:k=strcmp(key,L->s1j.others.start);break;case 3:k=strcmp(key,L->s1j.others.end);break;case 4:k=strcmp(key,L->s

33、1j.others.time1);break;case 5:k=strcmp(key,L->s1j.others.time2);break;if(k=0)m=1;Display(L,j);if(m=0) printf("无此航班信息，可能是输入错误!n");/输入输出函数（包括主控菜单函数）void input_output(sllist *L)KeyType keykeylen;int i=1,k=0;do printf("*n"); printf("* 航班信息查询系统 *n"); printf("*n"); printf("* 1.航班号 *n"); printf("* 2.起点站 *n"); pri