目    录

 

一、概述...................................................... 1

二、系统分析.................................................. 1

1.航班信息的查询与检索...................................... 1

2.航班信息查询与检索数据结构理论............................ 1

三、概要设计.................................................. 2

1.系统的功能................................................ 2

2.系统模块分析及其流程图.................................... 3

四、详细设计.................................................. 6

1.各函数说明................................................ 6

2.定义相关数据类型.......................................... 8

3. 航班信息的查询........................................... 9

五、 运行由于测试............................................ 12

六、总结与心得............................................... 16

参考文献..................................................... 16

附录......................................................... 16

 

一、概述

    随着信息产业的飞速发展，信息化管理及查询已经进入并应用到各行各业，影响着人们的价值观念和生活方式。因此，要提高企业信息化建设，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，从而提高企业综合实力。

    本次设计是针对航班的查询系统，该设计要求对飞机航班信息进行排序和查询。可按航班的航班号、起点站、终点站等信息进行航班信息的查询。

二、系统分析

1.航班信息的查询与检索

进入系统后，首先提示输入航班的信息，包括：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价等，票价为整型，其他为字符型。

当输入完一个信息后会提示是否继续输入，重复以上步骤输入全部的信息。

进入主菜单后会给出用户操作的界面，根据提示进行航班信息的查询。

2.航班信息查询与检索数据结构理论

针对在本该类系统中的数据的处理情况，本系统采用二分查找法、基数排序法、最高位优先法。

二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

对航班号的排序是采用的基数排序法。基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

三、概要设计

1.系统的功能

本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综合练习。以链式基数排序为主线，用到二分查找和顺序查找等知识，还有建立静态链表等相关概念。

2.系统模块分析及其流程图

（1）航班排序

对输入系统内的航班首先要进行排序，我们采用的基数排序，从低位到高位依次对关键字进行分配和收集，分两段实现其算法流程图。

                         

    （2)时间查找

根据航班的起飞时间（到达时间）查找航班的信息。

（3)二分法查找功能

（4)显示功能

显示功能是将所求单词的所有行列信息依次显示在屏幕上。

四、详细设计

1.各函数说明

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;

}

2.定义相关数据类型

根据设计要求我们知道所用的记录中只有航班信息，因此要定义相关的数据类型，其源程序如下：

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个字母指针

3. 航班信息的查询

    航班信息的查询，可以根据不同的用户需求采用按航班号、起点站、终点站、起飞时间、到达时间来进行查询，其源代码如下。

void searchcon(sllist l)

{

keytype key[keylen];

int i=1,k;

while(i>=1&&i<=5)

{

printf("\n ********************\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):");

scanf("%d",&i);

printf("\n");

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\n\n 再 见\n\n\n");

}

}

}

五、运行由于测试

六、总结与心得

在本次试验中，遇到了很多的问题。首先，按照书上的代码输入后，有很多错误，发现里面的代码有顺序不对的，有没有定义的等问题，经过修改解决了这些问题。其次，就是在输入时遇到了输入不当得问题，修改输入方法后得到了修改。最后，便是对几个算法的理解不是很透彻，对算法的具体实现了解不深。

针对以上问题，对各个算法解读了还几次，对算法的理解有了一定的理解，对整个系统运行有了全面的了解。

参考文献

[1]严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.2007.

[2]谭浩强.C程序设计.北京:清华大学出版社.1999.12.

[3]苏仕华.数据结构 课程设计.机械工业出版社

附录

#include <stdio.h>

#include <string.h>

#define maxspace 100

#define keylen 7

#define radix_n 10

#define radix_c 26

typedef 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];

int keynum;

int length;

}sllist;

typedef int arrtype_n[radix_n];

typedef int arrtype_c[radix_c];

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;

else

sl[e[j]].next=p;

e[j]=p;

}

}

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];

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]=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;

}

}

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;

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);

}

}

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;

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):");

scanf("%d",&i);

printf("\n");

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\n\n 再 见\n\n\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()

{

sllist l;

l.keynum=6;

l.length=0;

inputdata(l);

searchcon(l);

}