《航班信息的查询与检索》由会员分享，可在线阅读，更多相关《航班信息的查询与检索（23页珍藏版）》请在金锄头文库上搜索。
1、计科系实验报告实验课程名称专业班级学生姓名学号10410901025指导教师冯韵2012 至2013学年第丄学期第 八 至九周目录第 1 章 概述 3第 2 章 设计要求与分析 32.1 设计要求 32.2 设计分析 42.2.1 定义数据类型 42.2.2 实现排序的个函数说明 4第 3 章 算法实现 53.1 一趟分配算法 53.2 一趟收集算法 53.3 链式基数排序算法 123.4 二分查找的函数定义 13第 4 章 程序代码 14第 5 章 运行与测试 21第 6 章 实验反思 24参考文献 24第 1 章 概述排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要
2、先对 数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、 时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具 有结构特点的一类关键字。因为航班号是字母数字混变的，例如CZ3869，这种记录集合是 一个适合与多关键字排序的例子。第 2 章 设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起 飞时间以及到达时间等信息进行查询。对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分 查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的
3、顺序查找方法进行，因为他们用的较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时 间、飞机型号以及票价等，假设航班信息表如下表所示：k0 k1 k3 k4k5 k6航班信息表航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.346.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650
4、CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为：C3869其中 k0 和 k1 的输入值是航空公司的别称，用两个大写字母表示，后 4 位为航班表号，这种 航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因 此除了票价为数值型外，均定义为字符串型即可。2.2设计分析 2.2.1 定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef structChar start7;Char end7;Char
5、sche12;Char time15;Char time25;Char model4;Int price;InfoType;Typedef structKeyType keyskeylen;InfoType others;Int next;SLNode;Typedef structSLNode s1MaxSpace;Int keylen;Int length;SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n10;Typedef int ArrType_.c26;2.2.2 实现排序的个函数说明（1）一趟分配函数：Void Di
6、stribute（SLNode *s1,int I,ArrType f,ArrType e）;/本算法是按关键字keysi建立RADIX个子集，是同一个子集中记录的keysi相同, fO.RADIX和eO.RADIX分别指向各自表中的第一个和最后一个记录（2）一趟搜集函数：Void Collect（SLNode *sl,int i,ArrType f,ArrType e）;本算法是按关键字keysi从小到大将0.RADIX 所指的各子表一次连接成一个链表（3）链式基数排序函数：Void RadixSort（SLList &L）; /本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两
7、端实现（4）二分查找函数：Int BinSerach(SLList L,KeyType key);/L为待查找的表，key为待查找的关键字，按二分查找的思想实现查找(5) 主控函数：Void main()初始化；数据输入；排序处理；接受查找要求及查找关键字；查找处理； 输出查找结果；第3 章 算法实现3.1 一趟分配算法Void Distribute(SLNode *s1,int I,ArrType f,ArrType e) Int j,p;For(j=0;jRADIX;j+) /分子表初始化为空表Fj=0;Ej=0; For(p=s10.next;p;p=s1p.next)J=s1p.key
8、si%48;If(!fj)Fj=p;ElseS1ej.next=p;Ej=p;3.2 一趟收集算法Void Colect(SLNode *s1,int I,ARRType f,ArrType e) Int j,t;For(j=0;!fj;j+);S10.next=fj;t=ej;While(jRSDIX-1) For(j=j+1;jRADIX-1&!fj;j+); If(fj)s1t.next=fj;t=ej;S1t.next=0;/主函数程序#include#include#define MaxSpace 100#define keylen 6#define RADIX_n 10#defin
9、e RADIX_c 26#define SHOW_MSG_ERROR n错误信息：航班号须由2位大写字母和4位数字组成。n 输入数据错误，程序终止执行！ ntypedef char KeyType;typedef struct char start6;char end6;char sche6;char time16;char time26;char model3;int price;InfoType;typedef struct KeyType keyskeylen;InfoType others;int next;SLNode;typedef struct SLNode slMaxSpace
10、;int keynum;int length;SLList;typedef int ArrType_nRADIX_n;typedef int ArrType_cRADIX_c;KeyType keykeylen,kl4;void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e);void Collect(SLNode *sl, int i, ArrType_n f, ArrType_n e);void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e);void
11、 Collect_c(SLNode *sl, int i, ArrType_c f, ArrType_c e); void RadixSort(SLList &L);void Arrange(SLList &L);int BinSearch(SLList L, KeyType key);void SeqSearch(SLList L, KeyType key,int i);void DisplayStyle(int i, char *s);void Display(SLList L, int i);void searchcon(SLList L);void Prompt( );bool Inp
12、utData(SLList &L);bool Check_HangBanHao(char *HangBanHao);void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e) int j,p; for(j=0;jRADIX_n;j+)fj=0;for(p=sl0.next; p; p=slp.next) j=slp.keysi%48; if(!fj)fj=p;elseslej.next=p;ej=p;void Collect(SLNode *sl, ArrType_n f, ArrType_n e)int j,t; for(j=
13、0;!fj;j+);sl0.next=fj;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;void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e)int j,p;for(j=0;jRADIX_c;j+)fj=0;for(p=sl0.next; p!=0; p=slp.next) j=slp.keysi%65; if(!fj) fj=p;else slej.next=p;ej=p;void Collect_c(SLNode *sl, ArrType_c f, 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_
