《航班信息的查询与检索实验报告》由会员分享,可在线阅读,更多相关《航班信息的查询与检索实验报告(13页珍藏版)》请在金锄头文库上搜索。
1、目录1概述1.1问题描述1.2基本要求2系统分析2.1功能需求分析2.2设计要求3概要设计3.1各函数说明4详纟田设计4.1数据类型定义模块4.2实现排序的各函数模块5运行与测试5.1航班信息输入5.2航班信息查询5.3退出航班信息系统6总结与心得12参考文献1概述11问题描述随着科技与经济的发展,当今乘飞机旅行的人越来越多,人们需要关心了解 各类航班的班次、时间、价格及机型等信息。在这个飞机航班数据的模型中,航 班号是关键字,而且是具有结构特点的一类关键字。通过关键字的输入,你将获 得你所需要的航班的所有信息。程序必须实现航班信息的录入和查询。程序首先 定义了一个用于储存航班信息的数据类型,
2、再由用户录入航班数据,在录入的同 时并对数据进行排序,最后执行数据查询和检索。在查询设计中,使用二分查找 法对排好序的航班数据按航班号实现快速查找,按起点站、终点站、起飞时间、 到达时间查找的则采用顺序查询方法。航班信息的查询与检索1.2基本要求1、每个航班包括8项基本要求:航班号、起始站、终点站、班期、起飞时 间、到达时间、飞机型号、票价。2、要有输入模块。3、对航班信息进行排序与查找。2系统分析2.1功能需求分析(1) 输入航班信息(2) 按不同类型查询航班信息:输入航班号,显示相应信息输入起点站,显示相应信息 输入终点站,显示相应信息 输入起飞时间,显示相应信息 输入到达时间,显示相应信
3、息2.2设计要求该设计要求对航班信息进行排序和查询。可按航班的航班号、起点站、到 达站、起飞时间以及到达时间等信息进行查询。对于本设计,可采用基数排序法 对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他关键字的查找可采用最简单的顺序查找方法进 行,因为它们用的较少。每个航班记录包括八项,分别是:航班号、起点站、终 点站、班期、起飞时间、到达时间、飞机型号以及票价等。航班号起点站终点站班期起飞时 间到达时 间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重
4、庆深圳2.4.6085510357331010MU1836桂林南京2.3.46720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH416303概要设计31各函数说明(1) 一趟数字字符分配函数void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)(2) 趟数字字符收集函数void Collect(SLNode *sl,in
5、t i,ArrType_n f,ArrType_n e)(3) 趟字母字符分配函数void Distribute_c(SLNode *sl,int i, ArrType_c f,ArrType_c e)(4) 一趟字母字符收集函数void Collect_c(SLNode *sl,int i, ArrType_c f,ArrType_c e)(5) 链式基数排序函数void RadixSort(SLList &L)(6) 按指针链重新整理静态链表void Arrange(SLList &L)/重新整理(7) 二分查找函数int BinSearch(SLList L,KeyType key)(8
6、) 顺序查找函数void SeqSearch(SLList l,KeyType key,int i)(9) 显示航班记录函数void Display(SLList L,int i)(10) 查询检索菜单控制程序searchcon(SLList L)(11) 录入航班数据函数void InputData(SLList &L)(11)主函数void main()4详细设计4.1数据类型定义模块结构体内包括六个字符数组和一个整型变量,六个字符数组中分别存放航班 信息的起点站、终点站、班期、起飞时间、到达时间、飞机型号等信息,整型变 量中存放航班的票价。然后再定义全局变量:一个结构体数组并初始化,用来
7、存 放各个航班信息。一个指向结构体变量的指针数组。typedef struet char start 6;/起点char end6;/终点char sche10;/班期char timel5;/起飞时间char time25;/到达时间char model4;/机型int price;/票价infotype;/航班记录类型typedef structkey type keyskeylen;/关键字(航班号)infotype others;int next;slnode;/静态链表结点类型typedef struetslnode slmaxspace; /静态链表,s10为头结点int keyn
8、um;/记录当前关键字字符个数int leng th;/当前表长sllis t;/静态链表类型ty pedef int arr ty pe_nradix_n; /十进制数字扌旨针数组typedef int arrtype_cradix_c; /26 个字母扌旨针数组4.2实现排序的各函数模块4.2.1 一趟分配函数模块void distribute(slnode *sl, int i,arrtype_n f,arrtype_n e) int j,p;for(j=O;jradix_n;j+)fj=ej=0;for(p=sl0.nex t; p;p=slp.nex t)j=slp.keysi%48
9、;/将数字字符转换成相对应的数值型数字if(!fj)fj=p;elseslej.nex t二p;ej=p;4.2.2 一趟搜集函数模块void collect(slnode *sl, int i,arrtype_n f,arrtype_n e) int j,t;slO.next二fj;t二ej;/slO.next 指向第一个非空子表中的一个结点while(jradix_n-l)for(j二j+l;jradix_n-l & !fj;j+)/找下一个非空子表if(fj) slt. next二fj; t二ej; slt. next=0;4.2.3链式基数排序函数模块基数排序是一种借助多关键字排序的思
10、想对单逻辑关键字进行排序的方法, 其是通过“分配”和“收集”两种操作对相应关键字进行排序。算法思路是按照 排序关键字的每一位字符进行排序。排序前,先定义一个队列数组,每个队列数 组与某个关键字位对应,某队列中只能存放与该关键字位对应的元素。首先先从 关键字的最后一位字符进行判断,根据关键字位,把这个元素放入相应的队列中 去,这就是“分配”过程。等到所有元素均被分配到相应队列中之后,在把各个 队列中的元素,按照队列数组顺序,依次重新放回原元素数组中,这就是“收集” 过程。经过“分配”和“收集”后,一次排序完成。接着再以关键字的倒数第二 位字符作为关键字位进行上述排序过程,直到按照关键字的所有位全
11、部进行排序 过后,整个序列就成为有序序列,排序完成。void radixsor t( sllis t &l)/链式 arr ty pe_n fn,en;arr ty pe_c fc,ec;for(i=0;i=2;i-) /按最低位优先次序对各关键字进行分配和收集,先做低4位数字部分dis trib ut e(l.sl,i,fn,en);collec t( l.sl,i,fn,en);for(i=1;i=0;i) /对高位的2位大写字母进行分配和收集dis trib ut e_c(l.sl,i,fc,ec);collec t_ c(l.sl,i,fc,ec);/按指针链重新整理静态链表void
12、arrange(sllis t &l)/重新整理 p=l.sl0.next;/p指向第一个记录的当前位置for(i=1;il.length;i+) /l.slli-l已按关键字有序化while(pi)p=l.slp.nex t;q=l.slp.nex t;if(p!=i) t emp=l.slp; l.slp=l.sli; l.sli =t emp; l.sli.nex t二p; p=q; 424二分查找函数模块二分查找是对有序序列进行快速查找的一种有效方法。它的基本思想是,每 次都与这个有序序列的中间元素进行比较,若找到,则输出元素信息,若没找到, 则判断这个中间元素比待查找的元素大还是小,
13、如果大,那么查找工作继续在该 有序序列的前半段进行;反之,则继续查找该有序序列的后半段。如此一直查找, 直到找到该元素或者查找到只剩下一个元素而这个元素与待查找元素不相符时, 查找结束。前一种情况找到了待查找元素,输出该元素,后一种没有找到,输出 相应提示信息。int binsearch(sllist l,keytype key) while(lowv=high)mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=O)return mid;else if(strcmp(key,l.slmid.keys)vO)high=mid-l;else low=mid+1;return 0;425主控函数模块在主函数中,依然是以while循环的方式列出该程序的操作清单。该程序的 菜单是请用户选择以什么作为查找关键字来查找航班信息。查找菜单如下:1. 航班号,2起点站,3终点站,4班期,5起飞时间,6到达时间,7机型,8. 票价,9退出。选择不同菜单项,将会提示不同信息让用户输入,然后程序根据 各自的查找方法进行查找。void main()sllist l;l.keynum=6;l.leng th=0;/输入航班记录inpu tda ta(l);/基数排序searchcon(l);5运行与测试在VC+6.0环境下编译连接生成可执行文件。编译程序无错,继