淮北师范大学综合设计报告航班信息的查询与检索（排序应用）课程数据结构学院计算机科学与技术专业网络工程年级 2014级学号 20141204060姓名覃小玲任课教师乙从才2015年12月2 3日一、设计目的与内容通过本次实验，掌握数据结构中的几种排序算法和查找算法，了解静态链表的运用，利用上述的算法完成航班信息的查询与检索。
二、设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。
每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。
其中航班号一项的格式为：K0 k1 k2 k3 k4 k5航班关键字可分为两段，即字母和数字。
其中k0和k1是航空公司的别称，用两个大写字母表示，后4位为航班编号。
（1）系统总流程图（2）定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：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 sl[MaxSpace]; //静态链表，s1[0]为头结点int keylen; //关键字长int length; //当前表长}SLList; //静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedef int ArrType_n[10]; //十进制数字指针数组typedef int ArrType_c[26]; //26个字母指针数组（3）实现排序的各函数的说明1)一趟分配函数：void Distribute(SLNode *s1,int i,ArrType f,ArrType e);//本算法是按关键字key[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 BinSearch(SLList L,KeyType key[]);//L为待查找的表，key[]为待查找的关键字，按二分查找的思想实现查找5）主控函数void main(){初始化；数据输入；排序处理；接受查找要求及查找关键字；查找处理；输出查找结果；}三、主要功能模块流程图（1）根据设计要求我们知道所用的记录中只有航班信息 因此要定义相关的数据类型 其源程序如下typedef struct{char start[6];//起点char end[6]; //终点char sche[10];//班期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 sl[maxspace];//静态链表sl[0]为头结点int keynum; //记录当前关键字字符个数int length; //当前表长}sllist; //静态链表类型typedef int arrtype_n[radix_n];//十进制数字指针typedef int arrtype_c[radix_c];//26个字母指针(2) 链式基数排序是(3)重新整理静态链表重新整理静态链表，P指示第一个记录的当前位置，L.s1[1..i-1]已按关键字有序排列，第一个记录在L中的当前位置应不小于i，使用while循环，找到第i个记录，并用p指示其在L 中的当前位置，而q指示尚未调整的表尾，若if(p!=i) 则p指向被移走的记录，使得以后可由while循环找回，当p=q时，p指向尚未调整的表尾，为找到第i+个记录做准备(4) 查找算法实现1:二分查找函数2: 顺序查找函数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.s1[j].others.start);break;case 3:k=strcmp(key,L.s1[j].others.end);break;case 4:k=strcmp(key,L.s1[j].others.time1);break;case 5:k=strcmp(key,L.s1[j].others.time2);break;}if(k==0){ m=1;Display(L,j);}}if(m==0)printf("无此航班信息，可能是输入错误！\n"); }四、系统测试航班信息输入如图：按航班号查询：输入航班号错误则显示如下图：按航班起点站查询：按起飞时间查询：显示查询主菜单，退出查询系统：五：总结通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。
而对于有序序列的查找算法，二分查找是一种效率比较高的方法。
这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。
在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。
本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查找有了一个很好的掌握。
其查找过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
在实验过程中，程序中许多定义需要我们有一个很仔细的了解，比如上述的对字符长度的定义，这需要对所定义的对象给一个合理的字符长度，在输入的过程中才不会出现因输入的字符长度过长而不能识别。
本次实验中用到了静态链表，定义静态链表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。
通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。
六、源程序及系统文件使用说明#include <stdio.h>#include <string.h>#define MaxSpace 100#define keylen 7#define RADIX_n 10#define RADIX_c 26typedef char KeyType;typedef struct{char start[6]; //起点char end[6]; //终点char sche[10]; //班期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 sl[MaxSpace]; //静态链表，s1[0]为头结点int keynum; //记录当前关键字字符个数int length; //当前表长}SLList; //静态链表类型typedef int ArrType_n[RADIX_n]; //十进制数字指针数组typedef int ArrType_c[RADIX_c]; //26个字母指针数组// 一趟数字字符分配函数void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e){int j,p;for(j=0;j<RADIX_n;j++){ //各子表置为空表f[j]=e[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; //将p指向的结点插入到第j个子表中}}// 一趟数字字符的收集函数void Collect(SLNode *sl,int i,ArrType_n f,ArrType_n e){int j,t;for(j=0;!f[j];j++) //找第一个非空子表sl[0].next=f[j]; //s1[0].next指向第一个非空子表中的一个结点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; //t指向最后一个非空子表中的最后一个结点}// 一趟字母字符分配函数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]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%65; //将字母字符转换成在字母集中相应的序号（0-25）if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}// 一趟字母字符收集void Collect_c(SLNode *sl,int i,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; //0号单元仅存放指针，不存储内容L.sl[L.length].next=0; //将普通的线性表改造为静态链表for(i=L.keynum-1;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=L.sl[0].next; //p指向第一个记录的当前位置for(i=1;i<L.length;i++) //l.s1[1…i-1]已按关键字有序化{while(p<i)p=L.sl[p].next; //找到第i个记录，并用p指向其在L中当前位置q=L.sl[p].next; //q指向尚未调整的表尾if(p!=i){temp=L.sl[p]; L.sl[p]=L.sl[i]; L.sl[i]=temp; L.sl[i].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(key,L.sl[mid].keys)==0)return mid;else if(strcmp(key,L.sl[mid].keys)<0)high=mid-1;elselow=mid+1;}return 0;}// 顺序查找函数void SeqSearch(SLList L,KeyType key[],int i){int j,k,m=0;printf("*************************************************************\n"); printf("* 航班号起点站终点站航班期起飞时间到达时间机型票价*\n");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;printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",L.sl[j].keys,L.sl[j].others.start,L.sl [j].others.end,L.sl[j].others.sche,L.sl[j].others.time1,L.sl[j].others.time2,L.sl[j].others.model,L.sl[j].others.price);}}if(m==0)printf("* 无此航班信息，可能是输入错误！*\n");printf("*************************************************************\n"); }// 查询检索菜单控制程序void searchcon(SLList L){KeyType key[keylen];int i=1,k;while(i>=1&&i<=5){printf(" ********************\n");printf(" * 航班信息查询系统*\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);printf("*************************************************************\n");if(k==0)printf(" 无此航班信息，可能是输入错误！\n");else{printf("* 航班号起点站终点站航班期起飞时间到达时间机型票价*\n"); printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",L.sl[k].keys,L.sl[k].others.start,L.sl [k].others.end,L.sl[k].others.sche,L.sl[k].others.time1,L.sl[k].others.time2,L.sl[k].others.model,L.sl[k].others.price);}printf("*************************************************************\n"); 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(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.sl[i].keys,L.sl[i].others.start,L.sl[i].others.end,L.sl [i].others.sche,L.sl[i].others.time1,L.sl[i].others.time2,L.sl[i].others.model,&L.sl [i].others.price);++i; getchar();RadixSort(L);Arrange(L);printf("继续输入吗?y/n:");scanf("%c",&yn);}L.length=i-1;}void main(){// int i,k;SLList L;// KeyType key[keylen];L.keynum=6; L.length=0; //输入航班记录InputData(L); //基数排序RadixSort(L);Arrange(L);searchcon(L);return ;}。