航班信息的查詢與檢索

目錄21概述21.1課程設(shè)計名稱21.2課程設(shè)計目的21.3課程設(shè)計內(nèi)容22系統(tǒng)分析22.1設(shè)計要求22.2設(shè)計分析23概要設(shè)計33.1系統(tǒng)總流程圖33.2定義數(shù)據(jù)類型33.3實現(xiàn)排序的各函數(shù)的說明44詳細設(shè)計44.1數(shù)據(jù)類型的定義44.2鏈?zhǔn)交鶖?shù)排序54.2.1一趟數(shù)字字符分配函數(shù)錯誤!未定義書簽。4.2.2一趟數(shù)字字符的收集函數(shù)錯誤!未定義書簽。4.2.3一趟字母字符分配函數(shù)錯誤!未定義書簽。4.2.4一趟字母字符收集錯誤!未定義書簽。4.2.6鏈?zhǔn)交鶖?shù)排序函數(shù)錯誤!未定義書簽。4.3重新整理靜態(tài)鏈表64.4查找算法實現(xiàn)64.4.1二分查找函數(shù)64.4.2順序查找函數(shù)74.5輸入輸出函數(shù)75運行與測試86總結(jié)與心得117參考文獻118附錄（程序源代碼）11目錄1概述1.1課程設(shè)計名稱航班信息的查詢與檢索1.2課程設(shè)計目的通過本次實驗，掌握數(shù)據(jù)結(jié)構(gòu)中的幾種排序算法和查找算法，了解靜態(tài)鏈表的運用，利用上述的算法完成航班信息的查詢與檢索。2系統(tǒng)分析2.1課程設(shè)計內(nèi)容本課程設(shè)計主要是對排序及查找等進行練習(xí)，以鏈?zhǔn)交鶖?shù)排序為主線，利用二分查找和順序查找等知識，并建立靜態(tài)鏈表，完成對航班信息的查詢與檢索。我們可以利用航班的這些信息，通過其中的任意一個信息，找出我們所需要的查找的航班的所有信息，所以，我們可以采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排序好的航班記錄按航班號實現(xiàn)快速查找，并按其他關(guān)鍵字的查找可以采用最簡單的順序查找方法進行。2.2設(shè)計要求1） 提供對航班信息的排序功能2提供對航班信息的輸入輸出記錄功能找出我們所需要的查找的航班的所有信息3）提供按關(guān)鍵字（航班號）快速查詢或順序查詢功能2.3設(shè)計分析對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進行，因為它們用得比較少。每個航班記錄包括八項，分別是：航班號，起點站，終點站，班期，起飛時間，到達時間，飛機型號以及票價等。其中航班號一項的格式為：K0k1k2k3k4k5CZ3869航班關(guān)鍵字可分為兩段，即字母和數(shù)字。其中kO和k1是航空公司的別稱，用兩個大寫字母表

示，后4位為航班編號。3概要設(shè)計3.1系統(tǒng)總流程圖航班信息的查詢與檢索系統(tǒng)航班信息的查詢與檢索系統(tǒng)按航班號查詢按起飛時間查詢按到達時間查詢按起點站查詢按終點站查詢按航班號查詢按起飛時間查詢按到達時間查詢按起點站查詢按終點站查詢//起點//起點//終點IIk、八、、//班期//起飛時間//到達時間//機型//票價//航班記錄類型//關(guān)鍵字//表結(jié)點〃靜態(tài)鏈表，s1[0]為頭結(jié)點//關(guān)鍵字長//當(dāng)前表長3.2定義數(shù)據(jù)類型根據(jù)設(shè)計要求，設(shè)計中所用到的數(shù)據(jù)記錄只有航班信息，因此要定義相關(guān)的數(shù)據(jù)類型typedefstruct{charstart[7];charend[7];charsche[12];chartime1[5];chartime2[5];charmodel[4];intprice;}InfoType;typedefstruct{KeyTypekeys[keylen];InfoTypeothers;intnext;}slnode;typedefstruct{SLNodesl[MaxSpace];intkeylen;intlength;}SLList; 〃靜態(tài)鏈表類型為了進行基數(shù)排序，需要定義在分配和收集操作時用到的指針數(shù)組：typedefintArrType_n[10]; 〃十進制數(shù)字指針數(shù)組typedefintArrType_c[26]; 〃26個字母指針數(shù)組3.3實現(xiàn)排序的各函數(shù)的說明一趟分配函數(shù)：voidDistribute(SLNode*s1,inti,ArrTypef,ArrTypee);〃本算法是按關(guān)鍵字key[i]建立RADIX個子表，使同一個子表中記錄的keys[i]〃相同，f[0..RADIX]和e[0..RADIX]分別指向各子表中的第一個和最后一個記錄一趟搜集函數(shù)：voidCollect(SLNode*s1,inti,ArrTypef,ArrTypee);〃本算法是按關(guān)鍵字keys[i]從小到大將[0..RADIX]所指的各子表依次成一個鏈表鏈?zhǔn)交鶖?shù)排序函數(shù)：voidRadixSort(SLList&L);〃本算法是按關(guān)鍵字從低位到高位依次對各關(guān)鍵字進行分配和收集，分兩段實現(xiàn)二分查找函數(shù)：intBinSearch(SLListL,KeyTypekey[]);//L為待查找的表，key□為待查找的關(guān)鍵字，按二分查找的思想實現(xiàn)查找主控函數(shù)voidmain(){初始化；數(shù)據(jù)輸入；排序處理；接受查找要求及查找關(guān)鍵字；查找處理；輸出查找結(jié)果；}4詳細設(shè)計4.1數(shù)據(jù)類型的定義根據(jù)設(shè)計要求我們知道所用的記錄中只有航班信息因此要定義相關(guān)的數(shù)據(jù)類型其源程序如下typedefstruct{charstart[6];〃起點charend[6];〃終點charsche[10];〃班期chartime1[5];〃起飛時間chartime2[5];〃到達時間charmodel[4];〃機型intprice; 〃票價}infotype; 〃航班記錄類型typedefstruct{keytypekeys[keylen];〃關(guān)鍵字航班號

infotypeothers;intnext;}slnode;〃靜態(tài)鏈表類型typedefstruct{slnodesl[maxspace];〃靜態(tài)鏈表sl[0]為頭結(jié)點intkeynum;intlength;}sllist;〃記錄當(dāng)前關(guān)鍵字字符個數(shù)〃當(dāng)前表長〃靜態(tài)鏈表類型typedefintarrtype_n[radix_n];〃十進制數(shù)字指針typedefintarrtype_c[radix_c];//26個字母指針4.2鏈?zhǔn)交鶖?shù)排序

4.3重新整理靜態(tài)鏈表重新整理靜態(tài)鏈表，P指示第一個記錄的當(dāng)前位置，L.sl[l..i-1]已按關(guān)鍵字有序排列，第一個記錄在L中的當(dāng)前位置應(yīng)不小于i,使用while循環(huán)，找到第i個記錄，并用p指示其在L中的當(dāng)前位置，而q指示尚未調(diào)整的表尾，若if(p!=i)則p指向被移走的記錄，使得以后可由while循環(huán)找回，當(dāng)p=q時，p指向尚未調(diào)整的表尾，為找到第i+個記錄做準(zhǔn)備4.4查找算法實現(xiàn)4.4.1二分查找函數(shù)輸入航班號對應(yīng)序列號4.4.2順序查找函數(shù)voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;for(j=1;j<L.length;j++){switch(i){case2:k=strcmp(key,L.s1[j].others.start);break;case3:k=strcmp(key,L.s1[j].others.end);break;case4:k=strcmp(key,L.s1[j].others.time1);break;case5:k=strcmp(key,L.s1[j].others.time2);break;}if(k==0){m=1;Display(L,j);}}if(m==0)printf(”無此航班信息，可能是輸入錯誤！\n");}4.5輸入輸出函數(shù)serachcon(SLListL){inti=1,k,k1;while(i>=1&&i<=5){printf("*****************************\n");printf("*航班信息查詢系統(tǒng)*\n");printf("*1航班號*\n");printf("*2起點站*\n");printf("*3終點站*\n");printf("*4起飛時間*\n");printf("*5到達時間*\n");printf("*0退出系統(tǒng)*\n");*J「11 \ff\-**%1--1-f11 \-**%11?printf("請選擇0-5：\n");scanf("%d",&i);switch(i){case1:printf("輸入要查的航班號(字母要大寫)：”);scanf("%s",key);k=BinSearch(L,key);Display(L,k);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",k1);SeqSearch(L,k1,i);break;case5:printf(”輸入要查詢的航班到達時間：");scanf("%s",k1);SeqSearch(L,k1,i);

break;case0:printf("再見！\n");return0;}}}voidInputData(SLList&L){inti=++L.length;charyn='y';while(yn=='y'IIyn=='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.timel,L.s1[i].others.time2,L.s1[i].others.model,&L.s1[i].others.price);++i;printf("繼續(xù)輸入嗎？y/n:\n");scanf("%c",&yn);}L.length=i-1;}5運行與測試航班信息輸入如圖ILHP:S.V± s.%.s.yet. SJ)eihn bm.pseo*起飛時間到達旳間嘰刑票價51B55 1246 733966起飛時間到達時間機型芋價14^0 1615 H￥B12BB起飛時間到達時間機型幕價0055 1B35 7331B1B起飛時間到達日寸間機型票價130? ±330 528±00起飛時間到達旳間機型票價1200 1512 8??4BEI起飛時間到達旳間機型票倚1520 2012 SB2100B起飛時間到達日寸間機型票價1306 2033 877±230起飛時間到達時司機型票價123@ 2@13 7441@2@n"^■m~>月w理MfMf其班2.wn普班日航班期丄.3■占航班期±_5航班期1=3.4航班期2=4站站〔實斗州占和H.r-y'-■占衍—1-lcluZI占幾占《IU川占幾占"點肥旺點海歹點莽點陽即點海站g點京旺點欝己'I-1.-匕oTn&H己「-口nd,DLkH己4「口丿"—%走上A-Tk^AJNLA、衣上，幣一Aj寸h、才14-匚\號44輸號41轡！P“輸號22輸號239“輸號53輸號23輸J'lI煒藩沙怨煎:IH紋J'li爼掰沁注Jill"韁J'll畀落II承庇狀惟.1JLIU崔亢愆M崔.yL-lm崔二幾童H崔.IJL'X崔McM士-■知cM±l.田WPEZHX±_-按航班號查詢:-!□!x|Hj-!□!x|HjlnlxlCN卜航班號起點站終點姑航班期起飛時間到達時間機空克仆**MU5341上;每 .1：卜航班號起點站終點姑航班期起飛時間到達時間機空克仆**MU5341上;每 .1：1,|,|嗎日 1420 1615 lltiti*輸入航班號錯誤則顯示如下圖:*C:\.T±ndjove\syet?b32VDehn@：\.bb.aza*航班信息査詢系統(tǒng)*I二骯期忙息色詢系軌X^BC"3BC"3Bi^BC"3BC"3BC"3Bt!lBtB3BC"3BC"3BtB3|C"3BC"3BC"3BC"3Bfr3BC"3BtB3BC"3BtTOC\o"1-5"\h\zX 1 妙:靈 Xm H_iEH 占站 m芒站 *4-ti E吋間 *—列達II寸冋 ***************卅********請覽扌平5-9》：輸人妾査向的航班號■:字勺^A^^MU5341〕話站碩嚟豐w鋼-----123450in覽捋-5-恥=輸幾旻魚向的航班號■:寧?^AH＞：MU5431兒此航班恬思.nJ能是輸人鉗ix!按航班起點站查詢:管戸站終石辰班朗起飛時間到達時'可機型票價管戸站終石辰班朗起飛時間到達時'可機型票價*LB航班信息查詢系統(tǒng)*JOOCKJOOOCJCJOOOCKJOOOCKJCC:\TiQdoTE\EysteB321Deb-u航班信息查詢系統(tǒng)*JOOCKJOOOCJCJOOOCKJOOOCKJC耳耳JOCKXK耳耳>O<K>OCKK>O<KK*航班信息直詢貝統(tǒng)*XXJ(M：KXKKKJOCXKKKJCKKX1?肌班2?起點TOC\o"1-5"\h\z3.4.5.0.XXJCJOO<XJOO<XXXJOOO<XXK請選擇<0-5>：輸入要查詢的航玖［起點站名;南匡按起飛時間查詢:顯示查詢主菜單，退出查詢系統(tǒng):EB :\Tind9VEYsyEteB32YDebng\BB.exen_石站間間統(tǒng)Is123450請選擇<0-5>：0再見Pressanykeytocontinue總結(jié)與心得通過本實驗，我了解了基數(shù)排序是作為一種內(nèi)部排序方法，當(dāng)關(guān)鍵字位數(shù)較少而排序序列較長時，該排序算法有一定的優(yōu)越性。而對于有序序列的查找算法，二分查找是一種效率比較高的方法。在本實驗中，對這兩種算法的應(yīng)用，我加深了對他們的理解，掌握了他們的實現(xiàn)方法。在本次實驗過程中，輸入錯誤還是存在的問題，但能很快的通過編譯解決，一些編譯不能發(fā)現(xiàn)的問題，在組建過程中也能發(fā)現(xiàn)并解決。這次實驗的過程中遇到了很多問題，定義的過程中存在定義不清楚的問題，還有一些模糊定義和重定義的問題出現(xiàn)。在程序的定義過程中，存在著函數(shù)的調(diào)用失敗的問題，在調(diào)用過程中不能正常調(diào)用，通過把調(diào)用的函數(shù)直接用在程序中，不通過調(diào)用的方法，使得程序正常運行。本次實驗的問題只要通過調(diào)試和對整個程序的理解，便可以解決所有的發(fā)現(xiàn)的問題本次實驗利用二分查找法很快的完成了對航班信息的查找，使我們對二分查找有了一個很好的掌握。其查找過程是先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。在實驗過程中，程序中許多定義需要我們有一個很仔細的了解，比如上述的對字符長度的定義，這需要對所定義的對象給一個合理的字符長度，在輸入的過程中才不會出現(xiàn)因輸入的字符長度過長而不能識別。本次實驗中用到了靜態(tài)鏈表，定義靜態(tài)鏈表的過程中，需要有一個很熟悉的了解，知道靜態(tài)鏈表是如何定義以及如何實現(xiàn)。通過這次實驗，使得對于查找以及檢索有了一個很好的掌握，讓我們在以后的程序設(shè)計過程中對于類似的函數(shù)定義有一個很清晰的過程以及了解。參考文獻1）X孝凱，魏榮《數(shù)據(jù)結(jié)構(gòu)》，機械工程2） 譚浩強《程序設(shè)計》，大學(xué)3） 楊路明《C語言程序設(shè)計教程》，郵電大學(xué).4） 耿國華《數(shù)據(jù)結(jié)構(gòu)-C語言描述》，高等教育附錄（程序源代碼）#include<stdio.h>#include<string.h>#defineMaxSpace100#definekeylen7#defineRADIX_n10#defineRADIX_c26typedefcharKeyType;typedefstruct{charstart[6]; //起點charend[6]; //終點charsche[10]; //班期chartime1[5]; //起飛時間chartime2[5]; //到達時間charmodel[4]; //機型intprice; //票價}InfoType; //航班記錄類型typedefstruct{KeyTypekeys[keylen];InfoTypeothers;intnext;}SLNode;typedefstruct{SLNodesl[MaxSpace];intkeynum;intlength;}SLList;//關(guān)鍵字（航班號）//靜態(tài)鏈表結(jié)點類型〃靜態(tài)鏈表，s1[0]為頭結(jié)點//記錄當(dāng)前關(guān)鍵字字符個數(shù)//當(dāng)前表長//靜態(tài)鏈表類型typedefintArrType_n[RADIX_n];//十進制數(shù)字指針數(shù)組typedefintArrType_c[RADIX_c];//26個字母指針數(shù)組//一趟數(shù)字字符分配函數(shù)voidDistribute(SLNode*sl,inti,ArrType_nf,ArrType_ne){intj,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; //將數(shù)字字符轉(zhuǎn)換成相對應(yīng)的數(shù)值型數(shù)字if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p; 〃將p指向的結(jié)點插入到第j個子表中}}//一趟數(shù)字字符的收集函數(shù)voidCollect(SLNode*sl,inti,ArrType_nf,ArrType_ne){intj,t;for(j=0;!f[j];j++) //找第一個非空子表sl[0].next=f[j]; 〃sl[0].next指向第一個非空子表中的一個結(jié)點t=e[j];while(j<RADIX_n-l){for(j=j+l;j<RADIX_n-l&&!f[j];j++) //找下一個非空子表if(f[j]){sl[t].next=f[j];t=e[j];} //兩個非空子表}sl[t].next=0; 〃t指向最后一個非空子表中的最后一個結(jié)點}//一趟字母字符分配函數(shù)voidDistribute_c(SLNode*sl,inti,ArrType_cf,ArrType_ce)intj,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; //將字母字符轉(zhuǎn)換成在字母集中相應(yīng)的序號(0-25)if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}//一趟字母字符收集voidCollect_c(SLNode*sl,inti,ArrType_cf,ArrType_ce){intj,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;}//鏈?zhǔn)交鶖?shù)排序函數(shù)voidRadixSort(SLList&L)〃鏈?zhǔn)絳inti;ArrType_nfn,en;ArrType_cfc,ec;for(i=0;i<L.length;i++)L.sl[i].next=i+1; //0號單元僅存放指針，不存儲內(nèi)容L.sl[L.length].next=0; //將普通的線性表改造為靜態(tài)鏈表for(i=L.keynum-1;i>=2;i--){//按最低位優(yōu)先次序?qū)Ω麝P(guān)鍵字進行分配和收集，先做低4位數(shù)字部分Distribute(L.sl,i,fn,en);Collect(L.sl,i,fn,en);}for(i=1;i>=0;i--){//對高位的2位大寫字母進行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,i,fc,ec);}//按指針鏈重新整理靜態(tài)鏈表voidArrange(SLList&L)//重新整理{intp,q,i;SLNodetemp;p=L.sl[0].next;//p指向第一個記錄的當(dāng)前位置for(i=l;ivL.length;i++)〃l.sl[l???i-l]已按關(guān)鍵字有序化{while(p<i)p=L.sl[p].next; 〃找到第i個記錄，并用p指向其在L中當(dāng)前位置q=L.sl[p].next; 〃q指向尚未調(diào)整的表尾if(p!=i){temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp;L.sl[i].next=p;}//交換記錄p=q; 〃p指向尚未調(diào)整的表尾，為找第i+1個記錄做準(zhǔn)備}}//二分查找函數(shù)intBinSearch(SLListL,KeyTypekey[]){intlow,high,mid;low=l;high=L.length;while(low<=high){mid=(low+high)/2;if(strcmp(key,L.sl[mid].keys)==0)returnmid;elseif(strcmp(key,L.sl[mid].keys)<0)high=mid-l;elselow=mid+l;}return0;}//順序查找函數(shù)voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;「printf("*航班號起點站終點站航班期起飛時間到達時間機型票價*\n");for(j=l;j<=L.length;j++){switch(i){case2:k=strcmp(key,L.sl[j].others.start);break;case3:k=strcmp(key,L.sl[j].others.end);break;case4:k=strcmp(key,L.sl[j].others.timel);break;case5: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");「//查詢檢索菜單控制程序voidsearchcon(SLListL){KeyTypekey[keylen];inti=1,k;while(i>=1&&i<=5){printf("printf("*航班信息查詢系統(tǒng)*\n"）;printf("printf("printf("printf("printf("printf("printf("printf("printf("*航班信息查詢系統(tǒng)*\n"）;printf("printf("printf("printf("printf("printf("printf("********************\n");*1.航班號*\n");*2.起點站*\n");*3.終點站*\n");*4.起飛時間*\n");*5.到達時間*\n");*0.退出系統(tǒng)*\n");printf("printf("請選擇(0-5):printf("printf("請選擇(0-5):\n");scanf("%d",&i);switch(i){case1:printf("輸入要查詢的航班號(字母要大寫):");scanf("%s",key);k=BinSearch(L,key);「if（k==0）printf（"無此航