航班信息的查询与检索

《航班信息的查询与检索》由会员分享，可在线阅读，更多相关《航班信息的查询与检索（38页珍藏版）》请在装配图网上搜索。

1、航班信息的查询与检索航班信息的查询与检索目录41概述41.1课程设计名称41.2课程设计目的41.3课程设计内容42系统分析42.1设计要求42.2设计分析53概要设计53.1系统总流程图53.2定义数据类型63.3实现排序的各函数的说明错误!未定义书签。4详细设计错误!未定义书签。4.1数据类型的定义错误!未定义书签。4.2链式基数排序104.2.1 一趟数字字符分配函数错误!未定义书签。4.2.2 一趟数字字符的收集函数错误!未定义书签。4.2.3 一趟字母字符分配函数错误!未定义书签。4.2.4 一趟字母字符收集错误!未定义书签。4.2.6链式基数排序函数错误!未定义书签。4.3重新整理

2、静态链表114.4查找算法实现124.4.1二分查找函数124.4.2顺序查找函数134.5输入输出函数145运行与测试176总结与心得207参考文献218附录（程序源代码）21目录1概述1.1课程设计名称航班信息的查询与检索1.2课程设计目的通过本次实验，掌握数据结构中的几种排序算法和 查找算法，了解静态链表的运用，利用上述的算法 完成航班信息的查询与检索。2系统分析2.1课程设计内容u本课程设计主要是对排序及查找等进行练习， 以链式基数排序为主线，利用二分查找和顺序查找 等知识，并建立静态链表，完成对航班信息的查询 与检索。我们可以利用航班的这些信息，通过其中 的任意一个信息，找出我们所需

3、要的查找的航班的 所有信息，所以，我们可以采用基数排序法对一组 具有结构特点的飞机航班号进行排序，利用二分查 找法对排序好的航班记录按航班号实现快速查找， 并按其他关键字的查找可以采用最简单的顺序查 找方法进行。2.2设计要求1）提供对航班信息的排序功能心、r f2提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息3）提供按关键字（航班号）快速查询或顺序查询 功能2.3设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序， 利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查 找可采用最简单的顺序查找方法进行，因为它们用得比较少。每个

4、航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间， 到达时间，飞机型号以及票价等。其中航班号一项的格式为：K0 k1 k2 k3 k4 k5CZ3航班关键字可分为两段，即字母和数字。其中k0 和k1是航空公司的别称，用两个大写字母表示， 后4位为航班编号。3概要设计3.1系统总流程图航班信息的查询与检索系统3.2定义数据类型根据设计要求，设计中所用到的数据记录只有 航班信息，因此要定义相关的数据类型： typedef struct charstart7;起点char终点char/班期char起飞时间char到达时间char机型intend7;sche12;time15;time

5、25;model4;price;/票价InfoType;/航班记录类型typedef structKeyType关键字InfoType others;int next;slnode;/表结点typedef structSLNode/静态链表，s10为头结点int关键字长int/当前表长keyskeylen;slMaxSpace;keylen;length;SLList;/静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedefintArrType_n10;/十进制数字指针数组typedefintArrType_c26;/26个字母指针数组3.3实现排序的各函数的说

6、明1) 一趟分配函数：void Distribute(SLNode *sl,int i,ArrType f,ArrType e);本算法是按关键字keyi建立RADIX个子表，使 同一个子表中记录的keysi相同，f0.RADIX和e0.RADIX分别指向各子表中的第一个和最后一个记录2) 一趟搜集函数：void Collect(SLNode *sl,int i,AirType f,ArrType e)；本算法是按关键字keysi从小到大将0.RADIX所指的各子表依次链接成一个链表3) 链式基数排序函数： void RadixSort(SLList &L);本算法是按关键字从低位到高位依次对

7、各关键 字进行分配和收集，分两段实现4) 二分查找函数:int BinSearch(SLList L,Key Type key);L为待查找的表，key为待查找的关键字，按二分查找的思想实现查找5) 主控函数void main()初始化； 数据输入;排序处理；接受查找要求及查找关键字；查找处理；输出查找结果；4详细设计4.1数据类型的定义根据设计要求我们知道所用的记录中只有航班信息因此要定义相关的数据类型其源程序如下typedef structchar start6;/起点char end6; 终点char sche10;/班期char timel5;/ 起飞时间char time!5;/到达

8、时间char model4;机型int price; 票价 infotype;航班记录类型typedef struct (keytype keyskeylen;关键字 航班号infotype others;int next;slnode;/静态链表类型typedef struct slnode slmaxspace;/静 态链表sl0为头结点int keynum;int length;sllist;记录当前关键字字符个数/当前表长/静态链表类型typedef int arrtype_nradix_n ;/十进制数字指针 typedef int arrtype_cradix_c;/26 个字母指

9、针4.2链式基数排序开输入数据、基数、长度输入数据、基数、长度改造为对关键字对关键字将数据每段进行串i按指针结4.3重新整理静态链表重新整理静态链表，P指示第一个记录的当前位录在L中的当前位置应不小于i,使用while循环，找到第i个记录，并用p指示其在L中的当前位置,而q指示尚未调整的表若if(p!=i)则p指向被移走的记录，使得以后可由while循环找回，当p=q时，p指向尚未调整的表尾，为找到第i+个记录做准备4.4查找算法实现4.4.1二分查找函数是是4.4.2顺序查找函数void SeqSearch(SLList L,KeyType key,int i) int j,k,m=0;fo

10、r(j=1;j=1 & ilowssysteHi32Debug：BB. exe-Ini x*航班信息查询系统*it*请选择8-5：i.te班4.国飞时回 S到达时何 札浪出系统输入要查询的航班起点站名:上海*航班号起点站终点站航班期起飞时间到达时间机型票价* 上海 广Z 二海雨宁1.3.5* MU5341* MMB9234201615M90 280 乂12001512877400 *曰.心、5萨豆站终*肮班飞息查询案统*航班信息查询系统*按起飞时间查询:XM JI MMX XMJC 芦 MXMMMJCXMK请选择0-5 ：输入要查询的航以起点站名;南旨i-M班2起点3 - SW .04.起飞肘

11、 s.到达庄 .携出案XXKNXXJCXX M强XXXKXMMXN 请选择0-5 ：显示查询主菜单，退出查询系统:PM C - TindovEEysteB32DebiigBB. exe*航班信息查询系统*n 一也站间间获 普点飞达出12 3 4 5 0XMX 知 XNXXJCXXMXMXNXXMX请选择0-5 ：见ss any key to continue6总结与心得liiJ通过本实验，我了解了基数排序是作为一种内 部排序方法，当关键字位数较少而排序序列较长 时，该排序算法有一定的优越性。而对于有序序列 的查找算法，二分查找是一种效率比较高的方法。 在本实验中，对这两种算法的应用，我加深了对

12、他 们的理解，掌握了他们的实现方法。liiJ在本次实验过程中，输入错误还是存在的问题， 但能很快的通过编译解决，一些编译不能发现的问 题，在组建过程中也能发现并解决。这次实验的过 程中遇到了很多问题，定义的过程中存在定义不清 楚的问题，还有一些模糊定义和重定义的问题出 现。在程序的定义过程中，存在着函数的调用失败 的问题，在调用过程中不能正常调用，通过把调用 的函数直接用在程序中，不通过调用的方法，使得 程序正常运行。本次实验的问题只要通过调试和对 整个程序的理解，便可以解决所有的发现的问题本次实验利用二分查找法很快的完成了对航班信息的查找,使我们对二分查找有了一个很好的 掌握。其查找过程是先

13、确定待查记录所在的范围 （区间），然后逐步缩小范围直到找到或找不到该记录为止。在实验过程中，程序中许多定义需要我们有一 个很仔细的了解，比如上述的对字符长度的定义， 这需要对所定义的对象给一个合理的字符长度，在 输入的过程中才不会出现因输入的字符长度过长 而不能识别。本次实验中用到了静态链表，定义静 态链表的过程中，需要有一个很熟悉的了解，知道 静态链表是如何定义以及如何实现。通过这次实 验，使得对于查找以及检索有了一个很好的掌握， 让我们在以后的程序设计过程中对于类似的函数 定义有一个很清晰的过程以及了解。7参考文献1）徐孝凯，魏荣数据结构，机械工程出版社2）谭浩强程序设计，北京大学出版社3

14、）杨路明C语言程序设计教程，北京邮电大学出版社.4）耿国华数据结构-C语言描述，高等教育出版社8附录（程序源代码）#include #include #define MaxSpace 100#define keylen 7#define RADIX_n 10#define RADIX_c 26 typedef char KeyType;typedef structchar start6;char end6;char sche10;char time15;char time25;char model4;int price;InfoType;起点终点/班期起飞时间/倒达时间/机型/票价/航班记录类

15、型typedef structKeyType keyskeylen;InfoType others;int next;SLNode;typedef structSLNode slMaxSpace;结点/关键字（航班号）/静态链表结点类型/静态链表，s10为头int keynum;记录当前关键字字符个数int length;当前表长SLList;静态链表类型typedef int ArrType_nRADIX_n; 十进制数字指针数组typedef int ArrType_cRADIX_c; 26 个字母指针数组/ 一趟数字字符分配函数void Distribute(SLNode *sl,int

16、 i,ArrType_nf,ArrType_n e)int j,p;for(j=0;jRADIX_n;j+)/各子表置为空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;将数字字符转换成相对应的数值型数字if(!fj)fj=p;elseslej.next=p;ej=p;/将p指向的结点插入到第j个子表中/ 一趟数字字符的收集函数void Collect(SLNode *sl,int i,ArrType_n f,ArrType_n e)int j,t;for(j=0;!fj;j+)/找第一个非空子表sl0.next=fj;s10.next

17、指向第一个非空子表中的一个结点t=ej;while(jRADIX_n-1)for(j=j+1;jRADIX_n-1&!fj;j+)找下一个非空子表if(fj)slt.next=fj; t=ej; 链接两个非空子表slt.next=0;t指向最后一个非空子表中的最后一个结点/ 一趟字母字符分配函数void Distribute_c(SLNode *sl,int i,ArrType_c f,ArrType_c e) int j,p;for(j=0;jRADIX_c;j+) /各子表置为空表fj=ej=0；for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;/将字母

18、字符转换成在字母集中相应的序号(0-25)if(!fj)fj=p;elseslej.next=p;ej=p;/ 一趟字母字符收集void Collect_c(SLNode *sl,int i,ArrType_cf,ArrType_c e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jRADIX_c-1) for(j=j+1;jRADIX_c-1&!fj;j+); if(fj)slt.next=fj;t=ej;slt.next=0;链式基数排序函数void RadixSort(SLList &L)链式 int i;ArrType_n fn,en;

19、ArrType_c fc,ec;for(i=0;i=2;i-)按最低位优先次序对各关键字进行分配和收集，先做低4位数字部分Distribute(L.sl,i,fn,en);Collect(L.sl,i,fn,en);for(i=1;i=0;i-) 对高位的2位大写字母进行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,i,fc,ec);/按指针链重新整理静态链表void Arrange(SLList &L) 重新整理int p,q,i;SLNode temp;/p指向第一个记录的当p=L.sl0.next;前位置for(i=1;iL.length;

20、i+) /l.s11 i-1已按关键字有序化while(pi)p=L.slp.next;找到第i个记录，并用p指向其在L中当前位置/q指向尚未调整的表尾q=L.slp.next;if(p!=i)L.slp=L.sli; L.sli=temp;/交换记录temp=L.slp;L.sli.next=p; p=q;p指向尚未调整的表尾，为找第i+1个记录做准备/二分查找函数int BinSearch(SLList L,KeyType key) int low,high,mid;low=1;high=L.length;while(low=high)mid=(low+high)/2;if(strcmp(

21、key,L.slmid.keys)=0) return mid;else if(strcmp(key,L.slmid.keys)0) high=mid-1;else low=mid+1;return 0;/顺序查找函数 void SeqSearch(SLList L,KeyType key,int i) int j,k,m=0;_ A nzetprintf（*业业业业业业业业业业业业业业业业业业业业业业业业业._n ）;printf（n*航班号 起点站 终点站 航班期 起飞时 间到达时间机型票价*n）;for(j=1;j=1&i=5)printf( *n);printf( *航班信息查询系统*

22、n);printf( *n); printf( *1.航班号*n);printf( *2.起 点站*n);printf( *3.终点站*n);printf( *4.起飞时间*n);printf( *5.到达时间*n);printf( *0.退出系统*n);printf( *n);printf(请选择(0-5): n);scanf(%d”,&i);switch(i)case 1:printf(输入要查询的航班号(字母要大写):，scanf(%s”,key);k=BinSearch(L,key);_ A nzetprintii*业业业业业业业业业业业业业业业业业业业业业业业业业_ *m );if(

23、k=0)printf（无此航班信息，可能是输入错误！ n）;else printf（*航班号 起点站 终点站 航班期 起飞时 间到达时间机型票价*n）;printf(* %8s%7s%6s%11s%9s%7s%5s%4d *n”,L.slk.keys,L.slk.others.start,L.slk.others.end,L.slk.others.sche,L.slk.others.ti me1,L.slk.others.time2,L.slk.others.model,L.slk.others.price); _ A Z t f eft* afa at* aftA afa eft* afa

24、at* aftA afa eft* afa at* aftA afa eft* afa at* aftA afa eft* afaprintf(*业业业业业业业业业业业业业业业业业业业业业业业业一 _*七 );break;case 2:printf（输入要查询的航班起点站名:）;scanf(%s”,key);SeqSearch(L,key,i);break;case 3:printf(输入要查询的航班终点站名:);scanf(%s,key);SeqSearch(L,key,i);break;case 4:printf(输入要查询的航班起飞时间:);scanf(%s,key);SeqSearch

25、(L,key,i);break;case 5:printf(输入要查询的航班到达时间:);scanf(%s”,key);SeqSearch(L,key,i);break;case 0:printf(再见 n);/输入航班记录函数void InputData(SLList &L)int i=+L.length;char yn=y;while(yn=y|yn=Y)printf(航班号 起点站 终点站 航班期 起飞时间 到达时间机型票价n);scanf(%s%s%s%s%s%s%s%d”,L.sli.keys,L.sli.others.start,L.sli.others.end,L.sli.oth

26、ers.sche,L.sli.others.time1,L.sli.others.ti me2,L.sli.others.model,&L.sli.others.price);+i; getchar();RadixSort(L);Arrange(L);printf(继续输入吗? y/n:);scanf(%c”,&yn); L.length=i-1; void main() II int i,k;SLList L;II KeyType keykeylen;L.keynum=6; L.length=0;I/输入航班记录InputData(L);基数排序RadixSort(L); Arrange(L);searchcon(L); return ;