航班信息查询系统分析
航班信息查询系统
当今乘飞机的人越来越多，人们需要关心了解各类航班的班次、时间、价格、机型等信息，设计一个航班信息查询系统，可供人们查询航班信息，该查询系统可按一个或者多个条件查询，航班信息表的部分内容如下：
航班号
起点站
终点站
起飞时间
机型
票价
CA1544
合肥
北京
10:55
733
960
MU5341
上海
重庆
14:20
M90
1280
CZ3869
广州
南京
08:55
733
1010
MU3682
深圳
桂林
20:50
M90
1060
HUI1863
昆明
西安
10:15
738
1250
一、需求分析（余子轩、包灵美）
制作一个航班信息查询系统，能够完整显示航班信息 可以通过航班号、机型、起点站、到达站、起飞时间中的一个或多个条件查询并显示航班动态。
要求进入查询系统后，可以按要求选择需要更新的操作，并按提速输入要更新的航班数据，更新操作完成后返回初始界面。在选择查询时，能显示输入查询条件的界面并提示输入信息（航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价），若输入的信息符合要求则显示相对应的航班信息，否则显示“没有相关航班”并返回输入界面。如果主要想实现查询功能，就可以采用顺序的存储结构；想实现更新操作，采用链式存储结构；相比之下，这次主要想实现的功能是查询功能，因此采用顺序存储结构。考虑到此航班信息查询系统查询功能用到的比较多而更新操作使用的比较少，为了使操作简便，程序利用效率高，使用顺序表来存储航班信息。本系统采用二分查法、基数排序法、最高位优先法。
二分查法也称为折半查法：将n个元素分成个数大致相同的两半，取a[n/2]与欲查的x作比较，如果x=a[n/2]则到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继
续搜索x。
基数排序法：其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
最高位优先法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
需要注意到的是：在整个航班信息查询系统当中，需要对所要查询的信息进行一定的判断，看是否存在乘客所要查询的航班信息，以及在进行关键字查询时出现错误输入等。
二、 概要设计（黄飞）
1.系统的功能：
本任务要求对飞机航班信息进行排序和查。可按航班的航班号、起点站、到达站、起飞时间、飞机型号及票价等信息进行查询。本设计主要是对航班信息存储、排序以及查等概念
进行综合练习。以链式基数排序为主线，用到二分查和顺序查等知识，还有建立静态链表等相关概念，本系统使用dos界面实现。
2.系统模块分析：
（1）航班排序 对输入系统内的航班首先要进行排序，我们采用的按航班号排序，从低位到高位依次对关键字进行分配和收集，分两段实现其算法。
输入信息：MU5341 上海 重庆 14:20 M90 1280
                  CZ3869 广州 南京 08:55 733 1010
排序之后：CZ3869 广州 南京 08:55 733 1010
MU5341 上海 重庆 14:20 M90 1280
（2)    按航班号查航班的信息。
输入航班号： MU5341
  显示： MU5341 上海 重庆 14:20 M90 12
（3)    按航班起始站查航班的信息。
输入起始站：广州
显示：CZ3869 广州 南京 08:55 733 1010
（4)    按航班终点站查航班的信息。
输入起始站：南京
显示：CZ3869 广州 南京 08:55 733 1010
（5)根据航班的起飞时间查航班的信息。
输入起飞时间：08:55
显示：CZ3869 广州 南京 08:55 733 1010
（6)根据航班的机型查航班的信息。
输入飞机机型：733
显示：CZ3869 广州 南京 08:55 733 1010
（7)根据航班的票价查航班的信息。
输入飞机票价：1010
显示：CZ3869 广州 南京 08:55 733 1010
三、详细分析（包灵美、陈足萍）
根据题目所述，程序必须实现对航班信息的录入和查询，应该首先定义一个用于存储航班信息数据类型，再由管理员录入航班数据，将数据进行整理后，实现通过按照关键字搜索项目，有下面几种情况：
按航班号查询
按起飞时间查询
按到机型查询
按出发地查询
按目的地查询
退出系统
系统功能图：（包灵美）
定义数据类型
//tydedef  struct{
//char start[6];      //起点站
//char end6];      //终点站
//char Stime[5];    //起飞时间
//char model[4];  //机型
//int price;      //票价
}infotype;      //航班记录类型
tydedef  struct{
keytype keys[keylen];  //关键字
infotype others;
int next;
}slnode;          //表结点
typedef struct{
  slnode sl[maxspace];
  int keynum;    // 关键字长
int length;      //当前表长
}sllist;          //静态链表类型
typedef  int arrtype_n[10];    //十进制数字指针组
typedef  int arrtype_c[26];      //26个字母指针数组
各函数说明
1.一趟分配函数
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;
if(!f[j])
f[j]=p;
else
sl[e[j]].next=p;
e[j]=p;
}
}
2.一趟收集函数
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;
}
3.链式基数排序
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,i,fn,en);
}
for(i=1;i>=0;i--)
{
distribute_c(l.sl,i,fc,ec);
collect_c(l.sl,i,fc,ec);
}
}
4.二分法查函数
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;
}