数据结构课程设计航班信息的查询与检索.doc

目录
第１章 概述ﻩ2
第2章 设计要求与分析ﻩ２
2、1设计要求 2
2、2设计分析 3
２、2、1定义数据类型ﻩ3
2、2、2实现排序得个函数说明ﻩ4
第3章　算法实现ﻩ4
3、1 一趟分配算法 4
3、２　一趟收集算法ﻩ5
3、3 链式基数排序算法 5
３、4 二分查找得函数定义ﻩ6
第４章 程序代码 7
第5章 运行与测试 7
第6章 实验反思 10
参考文献ﻩ1１
第1章 概述
排序与查找就是在数据信息处理中使用频度极高得操作.为了加快查找得速度，需要先对数据记录按关键字排序。当今乘飞机旅行得人越来越多，人们需要关心了解各类航班得班次、时间、价格及机型等信息。在这个飞机航班数据得信息模型中,航班号就是关键字，而且就是具有结构特点得一类关键字。因为航班号就是字母数字混变得，例如CZ3８69,这种记录集合就是一个适合与多关键字排序得例子。
第２章 设计要求与分析
2、1设计要求
该设计要求对飞机航班信息进行排序与查找、可按航班得航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
对于本设计，可采用基数排序法对一组具有结构特点得飞机航班号进行排序，利用二分查找法对排好序得航班记录按航班号实现快速查找，按其她词关键字得查找可采用最简单得顺序查找方法进行,因为她们用得较少.
每个航班记录包括八项,分别就是:航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：
航班信息表
航班号
起点站
终点站
班期
起飞时间
到达时间
机型
票价
CＡ15４４
合肥
北京
1．2.4、5
1

60
ＭＵ５341
上海
广州
每日
1４20
161５
M90
1280
CZ３８69
重庆
深圳
２.4。6

1010
MU３682
桂林
南京
2.３．4、6、７
2０50
2215
M90
13８0
HU18３６
上海
北京
每日

1250
ＣＺ３52８
成都
厦门
１。3.４、５、7
１5１0
1650
CRＪ
1060
ＭU4５９４
昆明
西安
１.3.5、6
1

６0
ＳC7425
青岛
海口
1.３.6
1９2０
2120
ＤH4
1630
其中航班号一项得格式为：
　 　　 k0 　 　k1 　 k3 　ｋ４　 　 k5　 　 k6
C　　
Z
３
　 ８
６ 　　
　 　 ９
其中k0与k1得输入值就是航空公司得别称，用两个大写字母表示,后4位为航班表号，这种航班号关键字可分成两段，即字母与数字。其余七项输入内容因为不涉及本设计得核心,因此除了票价为数值型外,均定义为字符串型即可。
2、2设计分析
2。2.１定义数据类型
根据设计要求，我们知道设计中所用到得数据记录只有航班信息,因此要定义行管得数据类型：
Typｅdef stｒucｔ{
　 Cｈar staｒt［7］；
　 Cｈar end［7]；
Chａr　sche［1２］;
Char　time１［5］;
Chａr tｉme2[5]；
Cｈａｒ ｍoｄeｌ［4］;
Int prｉcｅ；
}InfｏTｙpe;
Tｙｐedef　ｓtruct{
　KeyＴype kｅys［keyleｎ］；
InfoType oｔhers；
Inｔ nexｔ;
}ＳLNｏde;
Ｔypｅdef sｔruｃt｛
SLNoｄe s1[MaxSｐace］；
Int ｋｅｙleｎ；
　 Int ｌengtｈ；
｝SLList;
为了进行基数排列,需要定义在分配与手机操作使用到得指针数组:
Ｔypeｄeｆ ｉnｔ ArｒType_n[10］;
Tyｐedef iｎt　ＡrrＴypｅ_、ｃ［26];
2.2。2实现排序得个函数说明
(1）一趟分配函数：
Ｖoｉd Diｓtribuｔｅ(SLNode ＊s1，iｎt I，ArｒＴyｐe ｆ,AｒrType e)；
//本算法就是按关键字ｋeys［i］建立RAＤIX个子集，就是同一个子集中记录得keｙs［i］相同,//ｆ［0、、RADIX]与e[0、、RADIX］分别指向各自表中得第一个与最后一个记录
(2)一趟搜集函数:
Void Collｅｃt（ＳLNｏde ＊s1，inｔ i,ＡrrTyｐe ｆ，ArｒTypｅ ｅ);
//本算法就是按关键字kｅys［ｉ］从小到大将[0、、RAＤIX］所指得各子表一次连接成一个链表
(3)链式基数排序函数：
Void　RａdｉxSｏrｔ（SＬLiｓt ＆L)；
//本算法就是按关键字从低位到高位依次对各关键字进行分配与收集，分两端实现
(4)二分查找函数：
Int BinSerach（SLList L,KeyTypｅ　key［］);
//L为待查找得表,key［］为待查找得关键字,按二分查找得思想实现查找
(５)主控函数：
Ｖoiｄ main(）
｛
初始化;
　数据输入；
排序处理;
接受查找要求及查找关键字；
查找处理;
　　输出查找结果；
｝
第3章 算法实现
３、1 一趟分配算法
Void Dｉsｔriｂｕte（ＳＬＮoｄe *ｓ1，ｉｎｔ　I,ＡrrＴype　f,ＡrrTyｐｅ e)
｛
Inｔ　j,p；
For(j=０;ｊ＜RADIX；j+＋)
｛／/分子表初始化为空表
　F［j］＝０；
　E［j]=０；
}
Foｒ（ｐ=s１［0］、neｘt；p；p=s1［p］、next)
{
　 　　J=ｓ1[ｐ］、ｋeｙs[i]％48；
If(!f[j])
F[j］＝p；
Else
　Ｓ1[ｅ［j]］、ｎeｘｔ=p；
E[j]＝p;
｝
}
3、2　一趟收集算法
Ｖoid Ｃoleｃt(ＳLＮodｅ ＊s1,inｔ I,ARＲＴypｅ f,ＡｒrType　e)
{
Int j，t；
For（j=0;!ｆ［ｊ］；j++);
Ｓ1［０］、next=ｆ［ｊ]；t=e［j］；
Whｉle（j<RSDIＸ-１)
｛
　 Ｆor(j=j+1;j〈ＲADＩX-1＆&!f［j];j＋+）;
　If（f[j］）｛s１[t]、ｎeｘt=f［j］；t=e[j]；｝
｝
Ｓ１［t]、ｎexｔ=0；
｝
／/主函数程序
＃inｃｌude<stdio、h〉
＃ｉnclude＜stｒiｎg、h〉
#definｅ MaxＳpａcｅ 100
＃ｄｅfiｎe　ｋeylen 6
＃dｅfinｅ　RAＤIX_ｎ　10
＃defｉnｅ RＡＤＩＸ_c 26
#defiｎe SHOW_MSＧ_ERＲOＲ　”\n错误信息：航班号须由2位大写字母与4位数字组成。\n输入数据错误，程序终止执行！\n"
ｔypedef chａｒ ＫeyType;
typedef struct　｛
char ｓtart[6];
cｈar end［6］；
ｃhar sche［６］；
chaｒ　ｔｉｍｅ1［6］;
ﻩcｈaｒ　tiｍe２［6］；
ｃhar　modｅl［３]；
ﻩｉnt prｉｃe；ﻩ
}ＩｎfｏTｙpe；
tyｐedeｆ struct ｛
ﻩＫeｙＴype keｙs［keyleｎ］；
ﻩInfoType　others；
int next；
}SLNoｄｅ;ﻩ
typedeｆ ｓtｒuｃt　{
ﻩSLＮｏｄｅ ｓｌ［MaxSｐacｅ]；
ﻩinｔ ｋeynum;
ﻩinｔ length；ﻩ
}SLList；ﻩ ﻩﻩﻩ
typeｄef int ＡrrTｙpe＿ｎ［RAＤIＸ＿n］;
typedｅｆ　int AｒrTyｐe_c[RAＤIＸ＿c]；
KeｙTyｐｅ keｙ［keylen］，kl［4]；
void　Dｉstriｂuｔe（SLＮode　＊ｓl, int　ｉ,　ArrＴype_n ＆f， AｒｒTｙｐe＿n　&e）；
voｉｄ　Ｃollecｔ（ＳＬNode　＊sｌ, int i， ＡｒrＴｙpe＿n f， ArrTyｐe＿ｎ e）;
voiｄ Diｓｔributｅ_c(ＳLNoｄe ＊sl， int i, ArｒType_c　＆f， ＡrｒＴｙｐe_c ＆e）；
voｉd Collect＿c（SＬNｏdｅ *sl, ｉnt i, ArrTｙpe_c f， ArｒTypｅ_c ｅ）;
ｖoiｄ RａdiｘSｏrt（SＬＬｉst &Ｌ);
void Arraｎge（SＬLisｔ ＆L)；
int ＢｉnSearch（SLＬiｓｔ L， KeｙTｙｐe key［])；
voｉd　SeｑSearch(ＳLLｉsｔ L, KｅyType ｋey［］,iｎｔ i);
voiｄ ＤisｐｌayStyle（int　ｉ， chaｒ ＊ｓ);
vｏid　Dｉspｌay(SLＬist L，　ｉnt　i）;
void　searchｃon（SLList Ｌ）;
voｉｄ Prompｔ( ）；
ｂool IｎputData（SＬList &L）；
boｏl Ｃheck＿HａngBａnＨaｏ(ｃhar ＊ＨaｎgBanHａo）；
ｖoid Distribute(SLNｏde　*sl, ｉnt i， ArrＴypｅ_n &f,　ArｒTypｅ_n ＆e)
｛
ﻩｉnt j，p；
ｆor（j=０;ｊ〈ＲADIＸ_n;ｊ＋+)
ﻩｆ［ｊ］＝０;
for（p=sl［０］、ｎext; p； p=sｌ[p]、ｎeｘt）
｛
ﻩ ｊ＝sl［ｐ]、ｋeｙｓ［i］％48；
ﻩ if（!f［ｊ]) ﻩ
ﻩﻩf［j］=p;ﻩ ﻩ
ﻩｅlseﻩ
ﻩﻩsl[e［ｊ］］、next=p；
ﻩﻩｅ［j］=p;ﻩﻩﻩ
ﻩ}
}
vｏid Coｌlｅcｔ（SLNoｄｅ　*sｌ， ArrTyｐe_n f, ArrType＿n e）
｛　
iｎｔ j，t;
　　 for(j＝０;！ｆ[ｊ];j++)；
ｓｌ[０]、ｎext=ｆ［ｊ］；
t=e［ｊ］;
ﻩwhilｅ（ｊ〈RADIX_ｎ－1）
ﻩ｛
ﻩ for（j=j+1；ｊ<RADIＸ_n－1 &＆　!f[j]；j+＋）;
ﻩ if(f［j]）
ﻩ｛
ﻩｓl[ｔ］、next＝f［j];t＝ｅ［j]；ﻩ
ﻩﻩ}
｝
sl［t］、nｅxｔ=0；
}
vｏid Ｄｉstribute_ｃ（SLNode ＊ｓl， inｔ i， ArrＴype_c　&f， AｒrType_c ＆ｅ）
｛　　
int j,p；
ﻩｆor(j=0;j<ＲＡDＩX＿ｃ；j+＋）
f[j]＝0;
foｒ（ｐ=sl[0］、nexｔ;　p！=0;　ｐ=ｓl[ｐ]、next）
｛
ﻩj=sl[p］、keyｓ［ｉ］%6５；
ﻩif（！f［j］）ﻩ ﻩ
ﻩ ｆ［ｊ]=p;ﻩﻩ
ﻩelse
ｓl[e［ｊ］］、neｘt＝p；ﻩ
e[j]＝p; ﻩﻩ
ﻩ}
}
vｏid Coｌlect_c(ＳLNｏdｅ ＊sl, ArrＴype_c f， ArrTｙｐe_c ｅ）
{
ﻩint ｊ,ｔ;
ﻩfｏr(j=0；！ｆ[j］； ｊ++）;
sl［0]、nexｔ=f[j]；t=e［j］;
ﻩwｈile(j〈RADIＸ_c－1)
｛
for（j=j+１;ｊ<RAＤIX_c—1　&＆ !ｆ[j］;ｊ+＋);
if（ｆ［ｊ］)
｛
ﻩｓl［t］、ｎext=f[j];t=e［j]；
ﻩﻩ｝
｝
sl［t］、neｘt=0；
｝
voiｄ RａdixSorｔ(SLLiｓt ＆L)
{ 　
int i；
　 ArrＴｙpe_ｎ fn，en；
　 ＡrrTｙｐe_ｃ　fc，ｅc;
　 for(i＝0； i<L、lengｔh；i＋+）
ﻩ Ｌ、ｓｌ［i］、ｎext=i＋1;
ﻩＬ、ｓl［L、length]、ｎext=0；
ｆoｒ（i=Ｌ、kｅｙnum—１；i>=２；i—－)
{
ﻩ Distribuｔe（L、sｌ，ｉ，fｎ，ｅn);
ﻩCｏlｌｅct(L、sl，fn,ｅn）;
}
ﻩfor（i=１;i>=0；i--）
ﻩ｛
ﻩ Ｄisｔrｉｂutｅ＿c（L、sｌ,ｉ，ｆｃ，ｅc）;
ﻩ Cｏllect_ｃ(Ｌ、sｌ，fc,eｃ）；
ﻩ｝
｝
void Arｒaｎgｅ（SLList ＆Ｌ）
｛　　
iｎｔ　ｐ,q，i；
SLＮｏｄe　temp；
ﻩp＝Ｌ、sl［0]、nｅxｔ；
for(i＝１；ｉ〈L、lenｇth;i++)
｛
ﻩ whｉｌe（p〈i)
p＝L、sl［ｐ]、ｎeｘt;
q=L、sl[ｐ］、next；
if（p！＝i）
ﻩﻩ{
ﻩﻩﻩｔemｐ=L、sl[p］;L、ｓl［p］=L、ｓｌ[i］;L、ｓl［i]=teｍｐ;
ﻩ L、sl［i］、ｎext＝p；
ﻩ ｝
ﻩ p＝q;
ﻩ}
｝
ｉnｔ ＢinＳearch(SＬLｉst L， KeyTyｐe key［］)
｛　 int lｏw,higｈ,mｉｄ;
low=1； hｉｇｈ=L、lengｔh;
ﻩ　ｗhilｅ(ｌow<=high)｛
ﻩﻩ ｍiｄ=(low+high)/2;
ﻩ　iｆ(sｔrcmｐ（ｋeｙ,L、ｓl[mid］、keyｓ)=＝0）
ﻩ ﻩ reｔurn ｍid；
ﻩ　else if（ｓｔrｃmp(ｋeｙ，L、sl［ｍｉd]、keys)<0)
ﻩ hiｇh=mid-1；
ﻩ ｅlｓｅ lｏw=mｉｄ+１;
ﻩ }
ﻩ ｒｅtｕｒn 0;
}
void SeqSｅａrcｈ(SLLisｔ Ｌ， KeyTｙｐe　ｋey［]，int i)
｛ ｉnｔ j,k，m=０;
ｆｏr(j=1；j＜=L、ｌｅngth;j++)
　　 ｛
switch（i）｛
　caｓe　2:k=sｔrcmp（kｅy,L、sl［j］、ｏｔhers、sｔart)；ｂreak；
　 caｓe 3：k＝ｓtrcmp（key，L、ｓｌ[j］、otｈeｒs、ｅnd)； 　brｅaｋ;
ﻩ case ４：k＝ｓtrcｍｐ（kｅｙ,L、sｌ[ｊ］、othｅrs、timｅ1）;ｂreaｋ；
　 　 cａse　5：k=stｒｃmp（kｅｙ,L、sｌ［j]、othｅrs、time2）;brｅak；
　}
ﻩ if（ｋ=＝0）
ﻩ　 ｛
ﻩ 　 ｍ=1；
ﻩ 　　 Displａy（L,j)；
　 ｝
　　　｝
ｉf（m=＝０)
ﻩ ｐriｎtf（＂很抱歉,无此航班信息。\n")；
}
ｖoid　Diｓplay(SLList L， int i）
｛
ｐｒinｔf("航班号　 起点站 终点站　　航班期 起飞时间　 到达时间　 机型 　票价\ｎ”)；
DisplaｙＳtｙle(６， L、sl［i]、ｋeys)；DisplaySｔyle(7, L、sｌ[i]、otheｒｓ、ｓｔart）；
ﻩDisｐlaｙStyle(7， L、ｓl[i］、others、ｅnｄ）;DisplayStyle（7, Ｌ、sl［i]、othｅrs、sche）；
ﻩＤisplayＳtylｅ(9， Ｌ、ｓｌ［i]、others、ｔime1）；DisplａyＳtylｅ(9,　L、sl［i]、ｏｔｈers、time2）;
DiｓplayＳtylｅ（５， L、sl［i]、ｏtheｒs、model）；prinｔf（"%６ｄ\ｎ"，Ｌ、sl［i］、oｔhｅrs、prｉｃe）;
ﻩprinｔf（”\ｎ”）；
｝
voｉｄ DｉｓplayStyｌe(iｎt　ｉ， char *ｓ）
{
iｎt　j；
i -= stｒｌen(s)；
for（j=０; j＜i； ++j）
ｐriｎｔｆ(” ＂)；
ﻩpｒiｎtf（"%s，”, s）；
｝
ｖoｉd sｅaｒchｃon（ＳLList　L)
｛
ﻩinｔ i=1，k；
ﻩwhile(i〉＝１ ＆＆ ｉ＜=５）｛
priｎtｆ(”＼n请选择命令代号（0－———５)： ”）；
ﻩscanf("％d”， &i);
ｓwitch(i）{
ﻩcase　１： ｐriｎtf（”输入要查询得航班号（字母要大写): "）；
ﻩ 　　ｓcanf("　%ｓ”, key）;ｋ=BiｎSｅarｃｈ(L， key);
ﻩﻩ ｉf(k)
ﻩﻩ ﻩDｉsplay（L，ｋ);
ﻩﻩﻩﻩelse
ﻩﻩﻩﻩ printf(”很抱歉,无此航班信息。＼n＂)；
ﻩ ｂｒeak;
ｃａｓe 2： ｐrintf（”输入要查询得航班起点站名: ＂)；
ﻩ ﻩ 　 scanｆ(” %ｓ”, key)； SｅqSearch（Ｌ， key， i)；
break；
ﻩﻩcaｓe　3： pｒintf（”输入要查询得航班终点站名： ");
scaｎf（＂%s"， keｙ）； SeｑSearch（Ｌ，　ｋｅy, i）；
ﻩbreaｋ；
ﻩ case 4： ｐrintf（＂输入要查询得航班起飞时间： ＂）;
ﻩ 　 ｓcanf（"％ｓ"， ｋl）; SeｑSearch(L， kl, i)；
ﻩ ﻩbreak;
ﻩ ｃase ５:　printf("输入要查询得航班到达时间: ＂）;
ﻩ 　 scanf(＂%s"， kl）; SeqSeａrcｈ(L，　kl， ｉ);
ﻩ bｒeａｋ;
ﻩｃａse 0：　prinｔf(＂再见!\n”);
retｕrn;
}
Prompt（　);
}
}
void　Ｐrompt（　)
{
ﻩprinｔf(＂*＊＊＊*＊*＊＊＊*＊＊＊＊＊*＊＊＊**＊＊*＊*＊＊＊＊**＊＊＊*＊*＊＊＊＊*＊*＊＊＊＊*\n"）;
ﻩpｒintf（”　　　　 ＊ 　 航班信息查询与检索系统　 　 　＊\n”)；ﻩ
ｐriｎtf（”*＊*＊**＊＊＊＊*＊**＊**＊＊＊＊**＊＊＊*＊*＊*＊＊＊*＊＊*＊*＊**＊*＊＊＊＊＊＊＼n"）;
ﻩｐrｉntf（”　 * 　 1、按航班号查询 　 　 ＊\n")；
ﻩpｒintf（＂ 　 *　　 　 　　　 　2、按起点站查询　 　 　 　　　 *\ｎ”）；
ﻩｐｒｉntf(" 　* 　 3、按终点站查询　 　 　 　 　 ＊\n＂);
ﻩprｉntf(” ＊ 　 　 ４、按起飞时间查询 　 　　　　 　＊\n”);
printf（＂ 　 * 　 　 5、按到达时间查询 　　 　 　 ＊＼n＂）;
ﻩprintf(” 　* 　　 ０、退出系统　 　 　 　*\n＂）；
ﻩｐrintｆ(”*＊*＊**＊*＊*＊＊**＊*＊****＊＊＊**＊**＊*＊＊＊＊＊＊＊**＊＊＊**＊*＊＊**\n"）;
｝
bool　InputDatａ（SLLisｔ　&L）
｛
inｔ　i＝+＋L、length；
ﻩ char yn=’y';
ﻩ ｐriｎtf（＂\ｎ请依次录入航班信息数据（航班号由2位大写字母与4位数字组成）:"）;
ﻩ　do
{
ﻩ priｎｔf（”＼n航班号　 起点站 终点站 　航班期 起飞时间 到达时间　 机型 　票价＼n");
ﻩ sｃanf(”％ｓ％s％ｓ％s%s%ｓ％s%ｄ”,　L、sl[i］、keys， L、ｓl[i］、otｈｅrs、starｔ,
L、sl[ｉ]、ｏtｈerｓ、ｅnd, L、sｌ［ｉ］、oｔhｅrｓ、ｓche, L、sｌ［ｉ]、oｔhｅrs、timｅ1，
ﻩﻩ L、ｓl[i]、otheｒs、tｉme2, L、sl[i]、otｈｅrs、mｏdｅｌ, &L、sｌ[ｉ]、oｔherｓ、ｐriｃe);
ﻩ ffluｓh(ｓtdin）;
ﻩﻩ ｉf（！Chｅck_HangＢanＨaｏ（L、sl[i］、kｅys))
ﻩﻩﻩ　rｅturn fａlｓe；
++ｉ;
ﻩ pｒｉｎtf(＂继续输入吗？ y/ｎ："）；
ﻩ　scanf("%c",ｙn）；
ﻩ　}
ﻩ　whｉle(yn=='y’ ｜｜ yn==＇Ｙ'）；
printf（”\n")；
L、length　= i-１;
RaｄixSoｒt（L)；
ﻩ Ａrranｇｅ(L);
ﻩ　retｕrn ｔｒue；
｝
bｏｏｌ Cheｃk＿HaｎｇBanHaｏ（cｈaｒ　＊HangBaｎHａo）
{
ﻩｉf (sｔｒlen（HangＢaｎHａo) !=　6)
ﻩﻩretｕrn ｆａlｓｅ；
ﻩelse if （HaｎｇBａｎHao［0]〈’A’ ｜｜ HanｇBａnHao［0]>'Z’
ﻩﻩ |｜ ＨangBａnＨａo[1］〈＇A＇ ｜｜ HａｎｇＢａnHao[１]〉＇Z’)
retuｒn fａlse;ﻩ
ﻩfor（int ｉ=2；　i<=5; i++）
{
ﻩｉf （HaｎgＢanHao［i]〈’0' |｜ ＨangBanHao[i］>'9’）
ﻩ return　falsｅ；
ﻩ}
returｎ true;
}
inｔ maｉn（　）
{
ﻩSＬList L；
ﻩL、kｅynum=6;L、lｅngth＝０;ﻩ
ﻩPrompt（ ）;
ﻩif（!InpｕtＤata（L））ﻩ
ﻩ｛
printf(SHＯW＿ＭＳG_ＥＲROR)；
return 1;
ﻩ｝
ﻩseaｒcｈｃon（L)；
ﻩreｔurn　0;
}
3、3 链式基数排序算法
Void RaｄixSorｔ（SLＬisｔ &L)
｛
ArrType＿n fｎ，en;
ＡrrTyｐｅ＿c　fｃ,en；
For(ｉ=０；ｋ<L、lengｔh；i++)
L、ｓ１[i］、nexｔ=i+１;
L、ｓ1[Ｌ、ｌseｎgtｈ]、ｎext=0；
Ｆor(i＝L、kｅynｕｍ—1；i〉＝2；i-—）
｛／/需分为两段完成，因为自负得那个分关键字要单独做
　 Diｓtrｉbute_ｎ(L、s1,i，fn,en);
　 　Ｃolleｃt_n（L、s１，i,fn，en）;
}
Fｏr(i=１;i>=0;i－—)
｛
　　 　Distribｕte＿ｃ（Ｌ、s１，ｉ，fc,ec）；
Colleｃt＿c(L、s１,i,fｃ，ec);
｝
｝／/RaｄｉxSｏrｔ
／/按指针链整理链表
Ｖoid Aｒrangｅ（SLLisｔ　&Ｌ）
{ﻫ p=L、s1［０］、next;
For(i=1；i〈L、length;ｉ＋+)
｛
While(ｐ<ｉ)p＝L、s１[p]、next;
　 //找到第i个记录,并用p指示其在L中得当前位置
　 Ｑ=Ｌ、s1［p]、nｅxt;
　 　If（ｐ!=ｉ)
｛
　Temp=L、s1［p];L、ｓ1[p］=L、s１[ｉ］;L、ｓ1[ｉ]=teｍp；
　　　 　 L、s1[i］、nｅxｔ=p；
}
　 P=q;
　 }
｝//ＡＡrｒaｎge
3、4　二分查找得函数定义
Int　BinSearch（SＬＬｉst Ｌ，KeysＴype ｋey[])
｛
While（lｏw＜=high)｛
Mid＝（ｌow+ｈｉgh)/2；
　 Ｉf(sｔrcmｐ（kｅy,L、s1［mｉｄ]、ｋeys）=＝０)
Rｅｔurn ｍｉd；
Else　loｗ=ｍiｄ+１;
｝
Ｒeturｎ　０;
｝//BiｎSearch
第4章 程序代码
＃incluｄe〈stdiｏ、h＞
＃ｉｎcludｅ<sｔring、ｈ>
/* 宏定义 */
#define MaxSpace 1０0
＃defｉｎe keyleｎ　６
＃ｄｅfine RADIX＿ｎ １0
＃define RADIX_c 26
＃ｄeｆine SＨOW_MＳＧ_ERROＲ "\n错误信息:航班号须由2位大写字母与4位数字组成。＼n输入数据错误，程序终止执行！\ｎ"
typｅdｅf chａr KｅyTｙpe;
/＊ 航班记录数据结构描述 ＊/
tｙpeｄeｆ　strucｔ {
ﻩchar　staｒｔ［6］;　 　 　 　 　 　　 　　 /／起点
char ｅnd[6]; 　 　 　 　 　　 　 　 　 　 　／/终点
char sche[6]; 　 　 　 　 　 　 　 　 　　　//班期
char ｔｉme1[6］；ﻩ 　 　 　 　 　 　　 　　 　　　 　 　 　 　//起飞时间
ﻩcｈaｒ　ｔime２［6]；ﻩ 　 　 　 　　　 　 　 　　 　　 　　 　/／到达时间
ﻩchaｒ　mｏdel[3］；ﻩ 　 　 　 　 　 　 　　 　 　 　 　　 //机型
int ｐrice;ﻩ 　 　 　　 　 　 　 　 　　 　　 　 　　 　 　 　　 //票价
}ＩnfｏTypｅ; ﻩﻩ
/＊　静态链表结点类型 */
tyｐｅｄｅf ｓｔｒuct ｛
KeｙTyｐｅ keys［keyleｎ];ﻩ　 　　 　 　 　 //关键字(航班号)
IｎｆoTypｅ oｔhers；
ﻩint nexｔ;
｝ＳLNode；
／＊ 静态链表类型 */ ﻩﻩﻩ
typedef ｓｔrｕｃt ｛
ﻩSLNoｄｅ ｓl［ＭaxＳpaｃe]；ﻩ 　 　　 　 　　　 　 　　 　 ／/静态链表
ﻩint ｋeynｕm； 　 　　 　 　 　 　　/／关键字字符数
int ｌeｎgth; ﻩﻩ 　　 　 　 　 　 　 　 　 　　 //表长
｝SLList； ﻩﻩ ﻩ
tｙｐeｄef int ArrＴypｅ_n[RADIX＿n］;　 　 　 　　 　 　 　 　 /／数字字符
typeｄef iｎｔ ArrＴype_ｃ［ＲADIX_c］； 　 　 　 　 　 　　　／/字母字符
KeyType　ｋｅｙ[keylｅn]，kl[4］；
/＊ 功能函数声明　*/
vｏｉd Ｄistｒibute（SLＮｏｄe *sｌ, iｎｔ i, AｒｒTypｅ＿n　&f， ＡrrＴｙpｅ_n ＆ｅ）;
ｖｏiｄ Ｃolleｃt(ＳLNode *ｓl，　ｉnt i,　ArrTyｐe_n　f， ArｒTｙｐｅ_n　e);
ｖｏid Distribuｔe_c(SLＮode ＊sl, int i， AｒrType＿c &f，　AｒrType_c &ｅ）;
void Ｃollect_c（SLＮode *sｌ， inｔ ｉ， ArｒTyｐe＿ｃ f,　ArｒＴype_c　ｅ）;
ｖoid ＲadｉxSｏrｔ（SＬList ＆Ｌ)；
vｏid Ａrrange(SLList &L）；
int　BｉｎＳeａrcｈ（ＳLList L, ＫeyTｙｐe kｅy［]）;
voiｄ ＳｅqSearch(SＬLiｓt L,　KeyTypｅ keｙ［]，int i）；
vｏｉd DｉｓplayＳｔyｌｅ（ｉnｔ i, chａr *s）；
vｏid　Display（SLList L， inｔ　ｉ)；
void ｓeａrｃｈｃon(SLLiｓｔ L）；
void Proｍpt（ );
ｂool InｐutDａta（SＬＬiｓt ＆Ｌ)；
bｏol　Check＿ＨangBanＨao(char *ＨａngBanHaｏ）；
/＊ 1、 数字字符分配函数 */
vｏｉｄ Dｉsｔrｉbute(SLNode ＊sl, inｔ ｉ, ArｒTｙｐe＿n ＆f， ArrTyｐe_n ＆e）
｛
int j，ｐ;
　 　 fｏr(ｊ＝0;ｊ〈RADIX_ｎ;j＋＋）
ﻩf［j]=0;
ｆｏr(p=sl［0］、ｎexｔ； p;　p=sl[p］、next）
{
j=sｌ［p］、ｋeys［i］％4８; 　 　 　 　 　　 　/／将数字字符映射为十进制数字
if（！f[j])ﻩﻩﻩ
f［j］=p；
ﻩｅlse ﻩ ﻩ 　　　 　 　　　 　　 ／/将p指向得结点插入到第j个子表中
ﻩ sl[e[j]]、next=p;
ﻩe[j]=p；ﻩ ﻩ
ﻩ}
｝
/＊　2、 数字字符收集函数 *／
vｏid Cｏllect（SLNode ＊sl, ＡrｒTyｐe_n　f， ＡrｒType_n ｅ)
{
inｔ j，t；
　　 ｆor(ｊ=0;！f［j］;ｊ＋+); ﻩ　 　 　　 　　 　 　 　 　 　 ／/找第一个非空子表
ﻩsl［０]、nexｔ=ｆ[ｊ]；ﻩ 　 　 　／/将sl[0]、ｎeｘt指向第一个非空子表得第一个结点
ﻩｔ=e［ｊ］；
ﻩｗhｉle（j＜ＲADIＸ_ｎ-1)
｛
ﻩﻩfor(j=j＋1；j<ＲAＤＩX_ｎ-1 &＆ ！ｆ［j];j++); 　 　 　 ﻩ／/找下一个非空子表
if(f［j］）
ﻩ｛
ｓl［t]、nｅxt＝f［j］；t=e［j］; ﻩﻩ 　 　 　 ／／链接到主链表
ﻩ ｝
ﻩ｝
ﻩｓl[t］、nｅxt=0；
｝
/＊ 3、 字母字符分配函数 ＊/
voｉd Ｄisｔributｅ_c(SLNode ＊sｌ， int ｉ，　ArrTｙpｅ_c ＆f, ArrType_ｃ　＆e）
{
iｎt　j,p；
fｏr(j=0；ｊ<RADIX＿ｃ;j＋＋)
ﻩﻩｆ[ｊ］=0；
ﻩfoｒ(p=sl[0］、neｘｔ;　p!=0； p=ｓｌ［p］、nｅｘt）
｛
ｊ=sｌ[p］、ｋeｙs[i]%6５; 　 　　 /／将字母字符映射为字母集中得相应序号
ﻩif(！f［j］） ﻩﻩ
ﻩ ﻩｆ［j］=p；ﻩ
ﻩ elｓe 　 　 /／将ｐ指向得结点插入到第ｊ个子表中
ﻩ ｓl［e［ｊ]］、next=p;
ﻩ e［j］=p；ﻩ
｝
｝
/* 4、 字母字符收集函数 ＊/
void Coｌlecｔ＿ｃ（SLNode *sｌ,　ＡrrType_ｃ f, ＡrｒTypｅ_c　ｅ)
{
ｉnｔ　j，t;
ﻩfoｒ（j=0;!f［j］；　ｊ++)；ﻩ 　　 　　 　　　 　 　　 　　　 　 　 //找第一个非空子表
sl［0]、next=ｆ［j］；ｔ=e[j];ﻩ　　 　 　/／将sl[０］、nｅxt指向第一个非空子表得第一个结点
ﻩwhilｅ(j<ＲAＤIX＿ｃ-1）
{
foｒ(j=j＋1;ｊ＜RADIX_c-１ &＆ !f［ｊ];j++)；ﻩ　 　　 　 　 //找下一个非空子表
ﻩｉf(f［ｊ]）
ﻩ｛
ﻩsl[t]、nｅxt＝f［ｊ];t=e［ｊ］； ﻩﻩ 　 　　　　 //链接到主链表
ﻩ｝
}
sl［t]、nｅxt=0；
}
/* ５、 链式基数排序函数 ＊/
vｏid RａdiｘSort(ＳLLｉｓt &L)
{　
int　i；
　 AｒｒType＿n fｎ，en；
　 AｒｒＴyｐe_c　fc，ec；
ｆｏr（i=０;　i〈Ｌ、lengｔｈ;i++) 　 　　 　 　 　 //将线性表改造为静态链表
ﻩL、sｌ[ｉ]、nｅxt=i+１；
ﻩＬ、sl[L、lｅngth］、nexｔ=0； ﻩ 　 　 　 　 　 　 　 //＂0"表示空指针
ﻩ 　 　 　　 　　 　 　 　 //按最低位优先依次对各关键字进行分配与收集
fｏr(i=L、ｋeｙnum—1;i〉=２；i--） 　 　 　 　 　 //对低四位数字部分进行分配与收集
{
ﻩDiｓｔribute(L、sl，i,fn，ｅn);
ﻩﻩＣｏｌlecｔ（L、sｌ，fn,ｅｎ）；
ﻩ}
for(i＝1;ｉ>=0；i－－）ﻩﻩ 　 　 　 //对高位得2位字母进行分配与收集
{
ﻩＤiｓｔｒibute＿c（L、sl,i,fｃ，ｅc);
Collect_c（L、ｓl,ｆc，ec）；
ﻩ｝
｝
／＊ ６、 按指针链整理线性表 */
void Ａrrａnge(ＳLLｉst &L)
｛
ｉnt ｐ，ｑ，i；
SLNｏｄｅ tｅmp；
p=Ｌ、sl[0］、nｅxt; 　　 　 　 　　 　　 　 　/／p指向第一个结点
for（i=1；i〈L、length;ｉ++）
{
ﻩwｈile(p<ｉ） ／/查找第ｉ个结点，并用p指向此结点
ﻩﻩp=L、sl[p］、nｅxｔ；
ﻩ q=L、sl［p］、neｘt；
ﻩif（p！＝i)ﻩ 　 　　　 　/／若第i个结点不在当前位置，交换结点数据
ﻩ {
ﻩ temp＝L、sl［p］；Ｌ、sl［p]=L、ｓl[i］;L、sl[ｉ]＝ｔemp；
ﻩ L、sｌ[i］、next＝p;
ﻩ }
ﻩﻩp=q； ﻩﻩ 　　 　 　 　 　/／p指向下一个未调整结点
ﻩ｝
}
/*