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

目录第章 概述2第2章 设计要求与分析2、1设计要求22、2设计分析3、2、1定义数据类型32、2、2实现排序得个函数说明4第3章算法实现43、1 一趟分配算法43、一趟收集算法53、3 链式基数排序算法5、4 二分查找得函数定义6第章 程序代码7第5章 运行与测试7第6章 实验反思10参考文献1第1章 概述排序与查找就是在数据信息处理中使用频度极高得操作.为了加快查找得速度，需要先对数据记录按关键字排序。当今乘飞机旅行得人越来越多，人们需要关心了解各类航班得班次、时间、价格及机型等信息。在这个飞机航班数据得信息模型中,航班号就是关键字，而且就是具有结构特点得一类关键字。因为航班号就是字母数字混变得，例如CZ369,这种记录集合就是一个适合与多关键字排序得例子。第章 设计要求与分析2、1设计要求该设计要求对飞机航班信息进行排序与查找、可按航班得航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用基数排序法对一组具有结构特点得飞机航班号进行排序，利用二分查找法对排好序得航班记录按航班号实现快速查找，按其她词关键字得查找可采用最简单得顺序查找方法进行,因为她们用得较少.每个航班记录包括八项,分别就是:航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：航班信息表航班号起点站终点站班期起飞时间到达时间机型票价C15合肥北京12.4、5160341上海广州每日120161M901280CZ69重庆深圳.4。61010MU682桂林南京2.4、6、2502215M90130HU18上海北京每日125052成都厦门。3.、7501650CR1060U4昆明西安.3.5、610C7425青岛海口1.6122120H41630其中航班号一项得格式为： k0 k1 k3 k5 k6C Z 其中k0与k1得输入值就是航空公司得别称，用两个大写字母表示,后4位为航班表号，这种航班号关键字可分成两段，即字母与数字。其余七项输入内容因为不涉及本设计得核心,因此除了票价为数值型外,均定义为字符串型即可。2、2设计分析2。2.定义数据类型根据设计要求，我们知道设计中所用到得数据记录只有航班信息,因此要定义行管得数据类型：Typdef stuc Car stat7； Car end7；Chrsche1;Chartime5;Chr tme25；C oe4;Int prc；InfTpe;Tedeftruct Keyype kyskeyle；InfoType ohers；In nex;LNde;ypdef srut SLNoe s1MaxSace； Int le； Int engt；SLList;为了进行基数排列,需要定义在分配与手机操作使用到得指针数组:ypee n ArType_n10;Tyedef itrryp_、26;2.2。2实现排序得个函数说明(1）一趟分配函数：od Ditribu(SLNode s1，it I，Arye ,ArType e)；/本算法就是按关键字eysi建立RAIX个子集，就是同一个子集中记录得kesi相同,/0、RADIX与e0、RADIX分别指向各自表中得第一个与最后一个记录(2)一趟搜集函数:Void Collt（LNde s1，in i,rrTye ，ArTyp );/本算法就是按关键字kys从小到大将0、RAIX所指得各子表一次连接成一个链表(3)链式基数排序函数：VoidRdxSr（SLit L)；/本算法就是按关键字从低位到高位依次对各关键字进行分配与收集，分两端实现(4)二分查找函数：Int BinSerach（SLList L,KeyTypkey);/L为待查找得表,key为待查找得关键字,按二分查找得思想实现查找()主控函数：oi main(） 初始化; 数据输入； 排序处理; 接受查找要求及查找关键字； 查找处理; 输出查找结果；第3章 算法实现、1 一趟分配算法Void Dsrite（oe *1，I,rrypef,rrTy e)Inj,p；For(j=;RADIX；j+)/分子表初始化为空表 Fj； Ej=；Fo（=s0、net；p；p=s1p、next) J=1、esi48；If(!fj) Fjp；Else 1j、e=p；Ejp;3、2一趟收集算法oid olet(Lod s1,in I,ARyp f,rTypee)Int j，t；For（j=0;!；j+);1、next=；t=ej；Whle（jRSDI-) or(j=j+1;jADX-1&!fj;j+）; If（fj）st、et=fj；t=ej；t、ex=0；/主函数程序inudestdio、hncludestig、h#defin Maxpc 100fieeylen 6dfinRAIX_10defn R_c 26#defie SHOW_MS_ERO”n错误信息：航班号须由2位大写字母与4位数字组成。n输入数据错误，程序终止执行！nypedef ch eyType;typedef structchar tart6;car end6；har sche；cha16;catie6；harmodl；nt pre；fTpe；tyede struct eype keskeyle；InfoTypeothers；int next；SLNo;typede tutSL MaxSac；in eynum;in length；SLList；typeef int rrTpeRAIn; typedint ArTye_cRAIc；KeTy kekeylen，kl4；voidDstriue（SLodel, int,Arrype_n f， ATen&e）；voollec（Nodes, int i， rpen f， ArrTye e）;voi Diribut_c(LNoe sl， int i, ArType_cf， re_c e）；vod Collectc（SNd *sl, nt i, ArrTpe_c f， ArTyp_c ）;oi RdiSrt（Sst &);void Arrage（SLis L)；int nSearch（SLi L， KeTe key)；vodSeSearch(LLs L, KyType ey,i i);voi isayStyle（int， cha );vidDspay(SList L，nti）;voidsearchon（SLList ）;vo Promp( ）；ool IputData（SList &L）；bol heckHngBna(har agBanHo）；oid Distribute(SLNde*sl, nt i， Arryp_n &f,ArTyp_n e)nt j，p； or（j=;ADI_n;+);for（p=sl、ext; p； p=sp、et）sl、ei48； if（!f)fj=p;lsesle、next=p；j=p;vid Colc（SLNo*s， ArrTye_n f, ArrTypen e） i j，t; for(j;！;j+)；、ext=；t=e;whil（RADIX_1）for（j=j+1；RADI_n1 &!fj；j+）;if(fj）l、nextfj;tj；slt、nx=0；vid stribute_（SLNode l， in i， Arrype_c&f， ArType_c ）int j,p；or(j=0;jDX；j+）fj0;fo（=sl0、nex;p！=0;=l、next）j=slp、key%6；if（！fj）=p;elsele、netp；ejp;vid Colect_c(LNd sl, Arrype_c f， ArrTe_c ） int ,;fr(j=0；！j； +）;sl0、nex=fj；t=ej;wile(jRADI_c1)for（j=j+;RAIX_c1& !j;+);if（) lt、ext=fj;t=ej；slt、net=0；voi RdixSor(SLLit L) int i； Arrpe_ fn，en； rrTe_fc，c; for(i0； i=；i)Distribue（L、s，f，n);Clct(L、sl，fn,n）;for（i=;i=0；i-）isrutc（L、s,，c）;Cllect_(、s，fc,e）；void Arag（SLList ） i,q，i； SLetemp；p、sl0、nx；for(i；L、lenth;i+)whe（pi)pL、sl、et;q=L、sl、next；if（p！i）em=L、slp;L、lp=L、i;L、li=te;L、sli、extp；pq;n inearch(SLst L， KeyTye key) int lw,hig,m; low=1； h=L、lengh;hil(ow=high) i=(low+high)/2;i(srcm（e,L、lmid、key)=0） reurn id；else if（rmp(e，L、sld、keys)Z| angBno1A HnHaoZ)retun flse;for（int =2；i9）returnfals；retur true;in man（）SList L；L、kynum=6;L、lngth;Prompt（ ）;if（!Inptata（L）printf(SHWG_ROR)；return 1;seacon（L)；reurn0;3、3 链式基数排序算法Void RaixSor（SLis &L)ArrTypen f，en;rrTycf,en；For(=；=0;i) Distribte（、s，fc,ec）；Colletc(L、s,i,f，ec);/RaxSr/按指针链整理链表oid Arang（SLLis&） p=L、s1、next;For(i=1；iL、length;+) While()pL、sp、next; /找到第i个记录,并用p指示其在L中得当前位置 =、s1p、nxt; If（!=) Temp=L、s1p;L、1p=L、s;L、1=tep； L、s1i、nx=p； P=q; /rage3、4二分查找得函数定义IntBinSearch（Sst ，Keysype ey) While（lw=high) Mid（ow+gh)/2； f(srcm（ky,L、s1m、eys）=) Rurn d； Elselo=i+;etur;/BiSearch第4章 程序代码incluestdi、hclud/* 宏定义 */#define MaxSpace 10defe keylefine RADIX 0define RADIX_c 26eine SOW_M_ERRO n错误信息:航班号须由2位大写字母与4位数字组成。n输入数据错误，程序终止执行！typdf chr KyTpe;/ 航班记录数据结构描述 /tpeestruc charsta6; /起点char nd6; /终点char sche6; /班期char me16； /起飞时间caime6； /到达时间chamdel3； /机型int rice; /票价nfTyp;/静态链表结点类型 */tyf uct KeTy keyskeyle; /关键字(航班号)IoTyp ohers；int nex;LNode； 静态链表类型 */typedef rt SLNo laxpae； /静态链表int eynm； /关键字字符数int egth; /表长SLList；teef int Arryp_nRADIXn; /数字字符typeef i Arrype_ADIX_c； /字母字符KeyTypekeyln，kl4；/ 功能函数声明*/vd istibute（SLe *s, i i, ATypn&f， rrp_n ）;i ollet(LNode *l，nt i,ArrTye_nf， ArT_ne);id Distribue_c(SLode sl, int i， ArTypec &f，ArType_c &）;void ollect_c（SLode *s， in ， ArTye f,Arype_c）;oid adxSr（SList )；vid rrange(SLList &L）；intBerc（LList L, eyTe ky）;voi qSearch(SLit L,KeyTyp ke，int i）；vd Dplayy（n i, chr *s）；vidDisplay（SLList L， in)；void eron(SLLi L）；void Propt（ );ool InutDta（Sit )；bolCheckangBanao(char *ngBanHa）；/ 1、 数字字符分配函数 */v Dsrbute(SLNode sl, in , ArTen f， ArrTye_n e）int j，; fr(0;RADIX_;j）fj=0;r(p=sl0、ex； p;p=slp、next）j=sp、eysi4; /将数字字符映射为十进制数字if（！fj)fj=p；lse /将p指向得结点插入到第j个子表中slej、next=p;ej=p；/2、 数字字符收集函数 *vid Cllect（SLNode sl, rTye_nf， rType_n ) in j，t； or(=0;！fj;+); /找第一个非空子表sl、nex=； /将sl0、et指向第一个非空子表得第一个结点=e；hle（jADI_-1)for(j=j1；jAX_-1 & ！j;j+); /找下一个非空子表if(fj）lt、nxtfj；t=ej; 链接到主链表lt、nxt=0；/ 3、 字母字符分配函数 /vod isribut_c(SLNode s， int ，ArrTp_c f, ArrType_e） itj,p；fr(j=0；RADIX;j)=0；fo(p=sl0、ne;p!=0； p=p、nt）=sp、esi%6; /将字母字符映射为字母集中得相应序号if(！fj）j=p；ele /将指向得结点插入到第个子表中le、next=p;ej=p；/* 4、 字母字符收集函数 /void Colec（SLNode *s,rrType_ f, rTyp_c) nj，t;fo（j=0;!fj；+)； /找第一个非空子表sl0、next=j；=ej; /将sl、nxt指向第一个非空子表得第一个结点whil(j=0；i） /对高位得2位字母进行分配与收集iibutec（L、sl,i,f，c);Collect_c（L、l,c，ec）； 、 按指针链整理线性表 */void rrnge(LLst &L) nt ，i； SLN tmp；p=、sl0、nxt; /p指向第一个结点for（i=1；iL、length;+）wile(p） /查找第个结点，并用p指向此结点p=L、slp、nx；q=L、slp、net；if（p！i) /若第i个结点不在当前位置，交换结点数据tempL、slp；、slp=L、li;L、slemp；L、si、nextp;p=q； /p指向下一个未调整结点/*