目录第1章概述 (1)第2章设计要求与分析 (2)2.1设计要求 (2)2.2设计分析 (2)2.2.1定义数据类型 (2)2.2.2实现排序的个函数说明 (3)第3章算法实现 (4)3.1 一趟分配算法 (4)3.2 一趟收集算法 (4)3.3 链式基数排序算法 (11)3.4 二分查找的函数定义 (12)第4章程序代码 (12)第5章运行与测试 (20)第6章实验反思 (23)参考文献 (23)第1章概述排序和查找是在数据信息处理中使用频度极高的操作。

为了加快查找的速度，需要先对数据记录按关键字排序。

当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。

在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。

因为航班号是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。

第2章设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：其中k0和k14位为航班表号，这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。

2.2设计分析2.2.1定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef struct{Char start[7];Char end[7];Char sche[12];Char time1[5];Char time2[5];Char model[4];Int price;}InfoType;Typedef struct{KeyType keys[keylen];InfoType others;Int next;}SLNode;Typedef struct{SLNode s1[MaxSpace];Int keylen;Int length;}SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n[10];Typedef int ArrType_.c[26];2.2.2实现排序的个函数说明（1）一趟分配函数：Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);//本算法是按关键字keys[i]建立RADIX个子集，是同一个子集中记录的keys[i]相同，//f[0..RADIX]和e[0..RADIX]分别指向各自表中的第一个和最后一个记录（2）一趟搜集函数：Void Collect(SLNode *s1,int i,ArrType f,ArrType e);//本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表一次连接成一个链表（3）链式基数排序函数：Void RadixSort(SLList &L);//本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现（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;j<RADIX;j++){//分子表初始化为空表F[j]=0;E[j]=0;}For(p=s1[0].next;p;p=s1[p].next){J=s1[p].keys[i]%48;If(!f[j])F[j]=p;ElseS1[e[j]].next=p;E[j]=p;}}3.2 一趟收集算法Void Colect(SLNode *s1,int I,ARRType f,ArrType e) {Int j,t;For(j=0;!f[j];j++);S1[0].next=f[j];t=e[j];While(j<RSDIX-1){For(j=j+1;j<RADIX-1&&!f[j];j++);If(f[j]){s1[t].next=f[j];t=e[j];}}S1[t].next=0;}//主函数程序#include<stdio.h>#include<string.h>#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR "\n错误信息：航班号须由2位大写字母和4位数字组成。

\n 输入数据错误，程序终止执行！\n"typedef char KeyType;typedef struct {char start[6];char end[6];char sche[6];char time1[6];char time2[6];char model[3];int price;}InfoType;typedef struct {KeyType keys[keylen];InfoType others;int next;}SLNode;typedef struct {SLNode sl[MaxSpace];int keynum;int length;}SLList;typedef int ArrType_n[RADIX_n];typedef int ArrType_c[RADIX_c];KeyType key[keylen],kl[4];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 &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 &f, ArrType_n &e) {int j,p;for(j=0;j<RADIX_n;j++)f[j]=0;for(p=sl[0].next; p; p=sl[p].next){j=sl[p].keys[i]%48;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}void Collect(SLNode *sl, ArrType_n f, ArrType_n e){int j,t;for(j=0;!f[j];j++);sl[0].next=f[j];t=e[j];while(j<RADIX_n-1){for(j=j+1;j<RADIX_n-1 && !f[j];j++);if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) {int j,p;for(j=0;j<RADIX_c;j++)f[j]=0;for(p=sl[0].next; p!=0; p=sl[p].next){j=sl[p].keys[i]%65;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e) {int j,t;for(j=0;!f[j]; j++);sl[0].next=f[j];t=e[j];while(j<RADIX_c-1){for(j=j+1;j<RADIX_c-1 && !f[j];j++);if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}void RadixSort(SLList &L){int i;ArrType_n fn,en;ArrType_c fc,ec;for(i=0; i<L.length;i++)L.sl[i].next=i+1;L.sl[L.length].next=0;for(i=L.keynum-1;i>=2;i--){Distribute(L.sl,i,fn,en);Collect(L.sl,fn,en);}for(i=1;i>=0;i--){Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,fc,ec);}}void Arrange(SLList &L){int p,q,i;SLNode temp;p=L.sl[0].next;for(i=1;i<L.length;i++){while(p<i)p=L.sl[p].next;q=L.sl[p].next;if(p!=i){temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp;L.sl[i].next=p;}p=q;}}int BinSearch(SLList L, KeyType key[]){ int low,high,mid;low=1; high=L.length;while(low<=high){mid=(low+high)/2;if(strcmp(key,L.sl[mid].keys)==0)return mid;else if(strcmp(key,L.sl[mid].keys)<0)high=mid-1;else low=mid+1;}return 0;}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.sl[j].others.start);break;case 3:k=strcmp(key,L.sl[j].others.end); break;case 4:k=strcmp(key,L.sl[j].others.time1);break;case 5:k=strcmp(key,L.sl[j].others.time2);break;}if(k==0){m=1;Display(L,j);}}if(m==0)printf("很抱歉，无此航班信息。