《数据结构课程设计航班信息的查询与检索》由会员分享，可在线阅读，更多相关《数据结构课程设计航班信息的查询与检索（23页珍藏版）》请在金锄头文库上搜索。
1、目录第1章 概述2第2章 设计要求与分析22.1设计要求22.2设计分析32.2.1定义数据类型32.2.2实现排序的个函数说明4第3章 算法实现43.1 一趟分配算法43.2 一趟收集算法53.3 链式基数排序算法53.4 二分查找的函数定义6第4章 程序代码7第5章 运行与测试7第6章 实验反思10参考文献11第1章 概述排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要先对数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。因为航班号
2、是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。第2章 设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：航班信息表航班号起点站终点站班期起飞时间到达时间机型票价
3、CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为： k0 k1 k3 k4 k5 k6C Z 3 8 6 9其中k0和k1的输入值是航空
4、公司的别称，用两个大写字母表示，后4位为航班表号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。2.2设计分析2.2.1定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef struct Char start7; Char end7;Char sche12;Char time15;Char time25;Char model4;Int price;InfoType;Typedef struct KeyType keyskeylen;InfoType oth
5、ers;Int next;SLNode;Typedef struct SLNode s1MaxSpace; Int keylen; Int length;SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n10;Typedef int ArrType_.c26;2.2.2实现排序的个函数说明（1）一趟分配函数：Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);/本算法是按关键字keysi建立RADIX个子集，是同一个子集中记录的keysi相同，/f0.RADIX和e0.RA
6、DIX分别指向各自表中的第一个和最后一个记录（2）一趟搜集函数：Void Collect(SLNode *s1,int i,ArrType f,ArrType e);/本算法是按关键字keysi从小到大将0.RADIX所指的各子表一次连接成一个链表（3）链式基数排序函数：Void RadixSort(SLList &L);/本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现（4）二分查找函数：Int BinSerach(SLList L,KeyType key);/L为待查找的表，key为待查找的关键字，按二分查找的思想实现查找（5）主控函数：Void main() 初始化；
7、 数据输入； 排序处理； 接受查找要求及查找关键字； 查找处理； 输出查找结果；第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.keysi%48;If(!fj) Fj=p;Else S1ej.next=p;Ej=p;3.2 一趟收集算法Void Colect(SLNode *s1,int I,ARRType f,ArrType e)Int
8、 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#define RADIX_c 26#define SHOW_MSG_ERROR n错误信息：航班号须由2位大写字母和4位数字组成。n输入数据错误，程序终止执行！ntypedef char KeyType;typed
9、ef 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;int keynum;int length;SLList;typedef int ArrType_nRADIX_n; typedef int ArrType_cRADIX_c;KeyType keykeyl
10、en,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 Collect_c(SLNode *sl, int i, ArrType_c f, ArrType_c e);void RadixSort(SLList &L);void Arrange(SLList &
11、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 InputData(SLList &L);bool Check_HangBanHao(char *HangBanHao);void Distribute(SLNode *sl, int i, ArrType_n &
12、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=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.nex
13、t=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;elseslej.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+
