飞机票查询

实验课程名称数据结构课程设计

专业班级10级计科一班

学生姓名孙旭

学号1

指导教师冯韵

2012至2013学年第1学期第八至九周

目录

第1章概述......................................................................................3

第2章设计要求与分析..................................................................3

2.1设计要求................................................................................3

2.2设计分析................................................................................4

2.2.1定义数据类型................................................................4

2.2.2实现排序的个函数说明................................................4

第3章算法实现..............................................................................5

3.1一趟分配算法.......................................................................5

3.2一趟收集算法.......................................................................5

3.3链式基数排序算法.............................................................12

3.4二分查找的函数定义.........................................................13

第4章程序代码............................................................................14

第5章运行与测试........................................................................21

第6章实验反思............................................................................24

参考文献..........................................................................................24

第1章概述

排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要先对

数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、

时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具

有结构特点的一类关键字。因为航班号是字母数字混变的，例如CZ3869，这种记录集合是

一个适合与多关键字排序的例子。

第2章设计要求与分析

2.1设计要求

该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起

飞时间以及到达时间等信息进行查询。

对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分

查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的

顺序查找方法进行，因为他们用的较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时

间、飞机型号以及票价等，假设航班信息表如下表所示：

航班信息表

航班号起点站终点站班期起飞时间到达时间机型票价

CA1544

合肥北京

1.2.4.510

MU5341

上海广州每日

14201615M901280

CZ3869

重庆深圳

2.4.6010

MU3682

桂林南京

2.3.4.6.720502215M901380

HU1836

上海北京每日

250

CZ3528

成都厦门

1.3.4.5.715101650CRJ1060

MU4594

昆明西安

1.3.5.6160

SC7425

青岛海口

1.3.619202120DH41630

其中航班号一项的格式为：

k0k1k3k4k5k6

C3869

其中k0和k1的输入值是航空公司的别称，用两个大写字母表示，后4位为航班表号，这种

航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因

此除了票价为数值型外，均定义为字符串型即可。

2.2设计分析

2.2.1定义数据类型

根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数

据类型：

Typedefstruct{

Charstart[7];

Charend[7];

Charsche[12];

Chartime1[5];

Chartime2[5];

Charmodel[4];

Intprice;

}InfoType;

Typedefstruct{

KeyTypekeys[keylen];

InfoTypeothers;

Intnext;

}SLNode;

Typedefstruct{

SLNodes1[MaxSpace];

Intkeylen;

Intlength;

}SLList;

为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：

TypedefintArrType_n[10];

TypedefintArrType_.c[26];

2.2.2实现排序的个函数说明

（1）一趟分配函数：

VoidDistribute(SLNode*s1,intI,ArrTypef,ArrTypee);

//本算法是按关键字keys[i]建立RADIX个子集，是同一个子集中记录的keys[i]相同，

//f[0..RADIX]和e[0..RADIX]分别指向各自表中的第一个和最后一个记录

（2）一趟搜集函数：

VoidCollect(SLNode*s1,inti,ArrTypef,ArrTypee);

//本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表一次连接成一个链表

（3）链式基数排序函数：

VoidRadixSort(SLList&L);

//本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现

（4）二分查找函数：

IntBinSerach(SLListL,KeyTypekey[]);

//L为待查找的表，key[]为待查找的关键字，按二分查找的思想实现查找

（5）主控函数：

Voidmain()

{

初始化；

数据输入；

排序处理；

接受查找要求及查找关键字；

查找处理；

输出查找结果；

}

第3章算法实现

3.1一趟分配算法

VoidDistribute(SLNode*s1,intI,ArrTypef,ArrTypee)

{

Intj,p;

For(j=0;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;

Else

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

E[j]=p;

}

}

3.2一趟收集算法

VoidColect(SLNode*s1,intI,ARRTypef,ArrTypee)

{

Intj,t;

For(j=0;!f[j];j++);

S1[0].next=f[j];t=e[j];

While(j

{

For(j=j+1;j

If(f[j]){s1[t].next=f[j];t=e[j];}

}

S1[t].next=0;

}

//主函数程序

#include

#include

#defineMaxSpace100

#definekeylen6

#defineRADIX_n10

#defineRADIX_c26

#defineSHOW_MSG_ERROR"n错误信息：航班号须由2位大写字母和4位数字组成。n

输入数据错误，程序终止执行！n"

typedefcharKeyType;

typedefstruct{

charstart[6];

charend[6];

charsche[6];

chartime1[6];

chartime2[6];

charmodel[3];

intprice;

}InfoType;

typedefstruct{

KeyTypekeys[keylen];

InfoTypeothers;

intnext;

}SLNode;

typedefstruct{

SLNodesl[MaxSpace];

intkeynum;

intlength;

}SLList;

typedefintArrType_n[RADIX_n];

typedefintArrType_c[RADIX_c];

KeyTypekey[keylen],kl[4];

voidDistribute(SLNode*sl,inti,ArrType_n&f,ArrType_n&e);

voidCollect(SLNode*sl,inti,ArrType_nf,ArrType_ne);

voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e);

voidCollect_c(SLNode*sl,inti,ArrType_cf,ArrType_ce);

voidRadixSort(SLList&L);

voidArrange(SLList&L);

intBinSearch(SLListL,KeyTypekey[]);

voidSeqSearch(SLListL,KeyTypekey[],inti);

voidDisplayStyle(inti,char*s);

voidDisplay(SLListL,inti);

voidsearchcon(SLListL);

voidPrompt();

boolInputData(SLList&L);

boolCheck_HangBanHao(char*HangBanHao);

voidDistribute(SLNode*sl,inti,ArrType_n&f,ArrType_n&e)

{

intj,p;

for(j=0;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;

else

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

e[j]=p;

}

}

voidCollect(SLNode*sl,ArrType_nf,ArrType_ne)

{

intj,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];

t=e[j];

while(j

{

for(j=j+1;j

if(f[j])

{

sl[t].next=f[j];t=e[j];

}

}

sl[t].next=0;

}

voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e)

{

intj,p;

for(j=0;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;

else

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

e[j]=p;

}

}

voidCollect_c(SLNode*sl,ArrType_cf,ArrType_ce)

{

intj,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];t=e[j];

while(j

{

for(j=j+1;j

if(f[j])

{

sl[t].next=f[j];t=e[j];

}

}

sl[t].next=0;

}

voidRadixSort(SLList&L)

{

inti;

ArrType_nfn,en;

ArrType_cfc,ec;

for(i=0;i<;i++)

[i].next=i+1;

[].next=0;

for(i=-1;i>=2;i--)

{

Distribute(,i,fn,en);

Collect(,fn,en);

}

for(i=1;i>=0;i--)

{

Distribute_c(,i,fc,ec);

Collect_c(,fc,ec);

}

}

voidArrange(SLList&L)

{

intp,q,i;

SLNodetemp;

p=[0].next;

for(i=1;i<;i++)

{

while(p

p=[p].next;

q=[p].next;

if(p!=i)

{

temp=[p];[p]=[i];[i]=temp;

[i].next=p;

}

p=q;

}

}

intBinSearch(SLListL,KeyTypekey[])

{intlow,high,mid;

low=1;high=;

while(low<=high){

mid=(low+high)/2;

if(strcmp(key,[mid].keys)==0)

returnmid;

elseif(strcmp(key,[mid].keys)<0)

high=mid-1;

elselow=mid+1;

}

return0;

}

voidSeqSearch(SLListL,KeyTypekey[],inti)

{intj,k,m=0;

for(j=1;j<=;j++)

{

switch(i){

case2:k=strcmp(key,[j].);break;

case3:k=strcmp(key,[j].);break;

case4:k=strcmp(key,[j].1);break;

case5:k=strcmp(key,[j].2);break;

}

if(k==0)

{

m=1;

Display(L,j);

}

}

if(m==0)

printf("很抱歉，无此航班信息。n");

}

voidDisplay(SLListL,inti)

{

printf("航班号起点站终点站航班期起飞时间到达时间机型票价n");

DisplayStyle(6,[i].keys);DisplayStyle(7,[i].);

DisplayStyle(7,[i].);DisplayStyle(7,[i].);

DisplayStyle(9,[i].1);DisplayStyle(9,[i].2);

DisplayStyle(5,[i].);printf("%6dn",[i].);

printf("n");

}

voidDisplayStyle(inti,char*s)

{

intj;

i-=strlen(s);

for(j=0;j

printf("");

printf("%s,",s);

}

voidsearchcon(SLListL)

{

inti=1,k;

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

printf("n请选择命令代号(0----5):");

scanf("%d",&i);

switch(i){

case1:printf("输入要查询的航班号(字母要大写):");

scanf("%s",key);k=BinSearch(L,key);

if(k)

Display(L,k);

else

printf("很抱歉，无此航班信息。n");

break;

case2:printf("输入要查询的航班起点站名:");

scanf("%s",key);SeqSearch(L,key,i);

break;

case3:printf("输入要查询的航班终点站名:");

scanf("%s",key);SeqSearch(L,key,i);

break;

case4:printf("输入要查询的航班起飞时间:");

scanf("%s",kl);SeqSearch(L,kl,i);

break;

case5:printf("输入要查询的航班到达时间:");

scanf("%s",kl);SeqSearch(L,kl,i);

break;

case0:printf("再见!n");

return;

}

Prompt();

}

}

voidPrompt()

{

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

}

boolInputData(SLList&L)

{

inti=++;

charyn='y';

printf("n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:");

do

{

printf("n航班号起点站终点站航班期起飞时间到达时间机型票价

n");

scanf("%s%s%s%s%s%s%s%d",[i].keys,[i].,

[i].,[i].,[i].1,

[i].2,[i].,&[i].);

fflush(stdin);

if(!Check_HangBanHao([i].keys))

returnfalse;

++i;

printf("继续输入吗?y/n:");

scanf("%c",yn);

}

while(yn=='y'||yn=='Y');

printf("n");

=i-1;

RadixSort(L);

Arrange(L);

returntrue;

}

boolCheck_HangBanHao(char*HangBanHao)

{

if(strlen(HangBanHao)!=6)

returnfalse;

elseif(HangBanHao[0]<'A'||HangBanHao[0]>'Z'

||HangBanHao[1]<'A'||HangBanHao[1]>'Z')

returnfalse;

for(inti=2;i<=5;i++)

{

if(HangBanHao[i]<'0'||HangBanHao[i]>'9')

returnfalse;

}

returntrue;

}

intmain()

{

SLListL;

=6;=0;

Prompt();

if(!InputData(L))

{

printf(SHOW_MSG_ERROR);

return1;

}

searchcon(L);

return0;

}

3.3链式基数排序算法

VoidRadixSort(SLList&L)

{

ArrType_nfn,en;

ArrType_cfc,en;

For(i=0;k<;i++)

L.s1[i].next=i+1;

L.s1[h].next=0;

For(i=-1;i>=2;i--)

{//需分为两段完成，因为自负的那个分关键字要单独做

Distribute_n(L.s1,i,fn,en);

Collect_n(L.s1,i,fn,en);

}

For(i=1;i>=0;i--)

{

Distribute_c(L.s1,i,fc,ec);

Collect_c(L.s1,i,fc,ec);

}

}//RadixSort

//按指针链整理链表

VoidArrange(SLList&L)

{

p=L.s1[0].next;

For(i=1;i<;i++)

{

While(p

//找到第i个记录，并用p指示其在L中的当前位置

Q=L.s1[p].next;

If(p!=i)

{

Temp=L.s1[p];L.s1[p]=L.s1[i];L.s1[i]=temp;

L.s1[i].next=p;

}

P=q;

}

}//AArrange

3.4二分查找的函数定义

IntBinSearch(SLListL,KeysTypekey[])

{

While(low<=high){

Mid=(low+high)/2;

If(strcmp(key,L.s1[mid].keys)==0)

Returnmid;

Elselow=mid+1;

}

Return0;

}//BinSearch

第4章程序代码

#include

#include

/*宏定义*/

#defineMaxSpace100

#definekeylen6

#defineRADIX_n10

#defineRADIX_c26

#defineSHOW_MSG_ERROR"n错误信息：航班号须由2位大写字母和4位数字组成。n

输入数据错误，程序终止执行！n"

typedefcharKeyType;

/*航班记录数据结构描述*/

typedefstruct{

charstart[6];//起点

charend[6];//终点

charsche[6];//班期

chartime1[6];//起飞时间

chartime2[6];//到达时间

charmodel[3];//机型

intprice;//票价

}InfoType;

/*静态链表结点类型*/

typedefstruct{

KeyTypekeys[keylen];//关键字（航班号）

InfoTypeothers;

intnext;

}SLNode;

/*静态链表类型*/

typedefstruct{

SLNodesl[MaxSpace];//静态链表

intkeynum;//关键字字符数

intlength;//表长

}SLList;

typedefintArrType_n[RADIX_n];//数字字符

typedefintArrType_c[RADIX_c];//字母字符

KeyTypekey[keylen],kl[4];

/*功能函数声明*/

voidDistribute(SLNode*sl,inti,ArrType_n&f,ArrType_n&e);

voidCollect(SLNode*sl,inti,ArrType_nf,ArrType_ne);

voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e);

voidCollect_c(SLNode*sl,inti,ArrType_cf,ArrType_ce);

voidRadixSort(SLList&L);

voidArrange(SLList&L);

intBinSearch(SLListL,KeyTypekey[]);

voidSeqSearch(SLListL,KeyTypekey[],inti);

voidDisplayStyle(inti,char*s);

voidDisplay(SLListL,inti);

voidsearchcon(SLListL);

voidPrompt();

boolInputData(SLList&L);

boolCheck_HangBanHao(char*HangBanHao);

/*1.数字字符分配函数*/

voidDistribute(SLNode*sl,inti,ArrType_n&f,ArrType_n&e)

{

intj,p;

for(j=0;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;

else//将p指向的结点插入到第j个子表中

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

e[j]=p;

}

}

/*2.数字字符收集函数*/

voidCollect(SLNode*sl,ArrType_nf,ArrType_ne)

{

intj,t;

for(j=0;!f[j];j++);//找第一个非空子表

sl[0].next=f[j];//将sl[0].next指向第一个非空子表的第一个结点

t=e[j];

while(j

{

for(j=j+1;j

if(f[j])

{

sl[t].next=f[j];t=e[j];//链接到主链表

}

}

sl[t].next=0;

}

/*3.字母字符分配函数*/

voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e)

{

intj,p;

for(j=0;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;

else//将p指向的结点插入到第j个子表中

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

e[j]=p;

}

}

/*4.字母字符收集函数*/

voidCollect_c(SLNode*sl,ArrType_cf,ArrType_ce)

{

intj,t;

for(j=0;!f[j];j++);//找第一个非空子表

sl[0].next=f[j];t=e[j];//将sl[0].next指向第一个非空子表的第一个结点

while(j

{

for(j=j+1;j

if(f[j])

{

sl[t].next=f[j];t=e[j];//链接到主链表

}

}

sl[t].next=0;

}

/*5.链式基数排序函数*/

voidRadixSort(SLList&L)

{

inti;

ArrType_nfn,en;

ArrType_cfc,ec;

for(i=0;i<;i++)//将线性表改造为静态链表

[i].next=i+1;

[].next=0;//"0"表示空指针

//按最低位优先依次对各关键字进行分配和收集

for(i=-1;i>=2;i--)//对低四位数字部分进行分配和收集

{

Distribute(,i,fn,en);

Collect(,fn,en);

}

for(i=1;i>=0;i--)//对高位的2位字母进行分配和收集

{

Distribute_c(,i,fc,ec);

Collect_c(,fc,ec);

}

}

/*6.按指针链整理线性表*/

voidArrange(SLList&L)

{

intp,q,i;

SLNodetemp;

p=[0].next;//p指向第一个结点

for(i=1;i<;i++)

{

while(p

p=[p].next;

q=[p].next;

if(p!=i)//若第i个结点不在当前位置，交换结点数据

{

temp=[p];[p]=[i];[i]=temp;

[i].next=p;

}

p=q;//p指向下一个未调整结点

}

}

/*7.二分查找函数*/

intBinSearch(SLListL,KeyTypekey[])

{intlow,high,mid;

low=1;high=;

while(low<=high){

mid=(low+high)/2;

if(strcmp(key,[mid].keys)==0)

returnmid;

elseif(strcmp(key,[mid].keys)<0)

high=mid-1;

elselow=mid+1;

}

return0;

}

/*8.顺序查找函数*/

voidSeqSearch(SLListL,KeyTypekey[],inti)

{intj,k,m=0;

for(j=1;j<=;j++)

{

switch(i){

case2:k=strcmp(key,[j].);break;

case3:k=strcmp(key,[j].);break;

case4:k=strcmp(key,[j].1);break;

case5:k=strcmp(key,[j].2);break;

}

if(k==0)

{

m=1;

Display(L,j);

}

}

if(m==0)

printf("很抱歉，无此航班信息。n");

}

/*9.打印班次信息函数*/

voidDisplay(SLListL,inti)

{

printf("航班号起点站终点站航班期起飞时间到达时间机型票价n");

DisplayStyle(6,[i].keys);DisplayStyle(7,[i].);

DisplayStyle(7,[i].);DisplayStyle(7,[i].);

DisplayStyle(9,[i].1);DisplayStyle(9,[i].2);

DisplayStyle(5,[i].);printf("%6dn",[i].);

printf("n");

}

/*10.调整对齐格式函数*/

voidDisplayStyle(inti,char*s)

{

intj;

i-=strlen(s);

for(j=0;j

printf("");

printf("%s,",s);

}

/*11.交互界面函数*/

voidsearchcon(SLListL)

{

inti=1,k;

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

printf("n请选择命令代号(0----5):");

scanf("%d",&i);

switch(i){

case1:printf("输入要查询的航班号(字母要大写):");

scanf("%s",key);k=BinSearch(L,key);

if(k)

Display(L,k);

else

printf("很抱歉，无此航班信息。n");

break;

case2:printf("输入要查询的航班起点站名:");

scanf("%s",key);SeqSearch(L,key,i);

break;

case3:printf("输入要查询的航班终点站名:");

scanf("%s",key);SeqSearch(L,key,i);

break;

case4:printf("输入要查询的航班起飞时间:");

scanf("%s",kl);SeqSearch(L,kl,i);

break;

case5:printf("输入要查询的航班到达时间:");

scanf("%s",kl);SeqSearch(L,kl,i);

break;

case0:printf("再见！n");

return;

}

Prompt();//循环显示主菜单

}

}

/*12.显示主菜单*/

voidPrompt()

{

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

}

/*13.输入航班记录函数*/

boolInputData(SLList&L)

{

inti=++;

charyn='y';

printf("n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:");

do

{

printf("n航班号起点站终点站航班期起飞时间到达时间机型票价

n");

scanf("%s%s%s%s%s%s%s%d",[i].keys,[i].,

[i].,[i].,[i].1,

[i].2,[i].,&[i].);

fflush(stdin);//清空输入缓冲区

if(!Check_HangBanHao([i].keys))

returnfalse;

++i;

printf("继续输入吗?y/n:");

scanf("%c",&yn);

}

while(yn=='y'||yn=='Y');

printf("n");

=i-1;

RadixSort(L);

Arrange(L);

return(true);

}

/*14.航班号输入效验*/

boolCheck_HangBanHao(char*HangBanHao)

{

//必须为6位

if(strlen(HangBanHao)!=6)

returnfalse;

//1-2位须为大写字母

elseif(HangBanHao[0]<'A'||HangBanHao[0]>'Z'

||HangBanHao[1]<'A'||HangBanHao[1]>'Z')

returnfalse;

//3-6位须为数字

for(inti=2;i<=5;i++)

{

if(HangBanHao[i]<'0'||HangBanHao[i]>'9')

returnfalse;

}

returntrue;

}

/*15.主函数*/

intmain()

{

SLListL;

=6;=0;//初始化

Prompt();//显示界面

if(!InputData(L))//信息录入，并作输入效验

{

printf(SHOW_MSG_ERROR);

return1;

}

searchcon(L);//执行相关查询

return0;

}

第5章运行与测试

按要求依次输入要查询的信息：

（1）先输入航班信息

例如：

CA1544

合肥北京

1.2.4.510

（2）输入选择要怎样查询

输入1，查询航班号

输入2，查询起点站

输入3，查询终点站

输入4，查询起飞时间

输入5，查询到达时间

输入0，退出系

第6章实验反思

本设计的重点和难点是在于对航班数据的排序和查找，以链式基数排序为主线，用到

了二分查找和顺序查找等知识，还有建立静态链表等。通过这次课程设计，使我对C语言

编程有了新的认识。以前编程只是注重如何编写函数能够完成所需要的功能，只是凭单纯的

意识和简单的语句来堆砌出一段程序。但现在编程感觉完全不同了。在编写一个程序之前，

自己能够综合考虑各种因素，选取自己需要的数据结构，在编写每一个函数之前，可以仔细

斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自

己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体

会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一

种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。

参考文献

《数据结构课程设计》苏仕华等编著

《数据结构（C语言版）》严蔚敏吴伟民编著