航班信息的查詢與及檢索

1、實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)綜合設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目 航班信息的查詢與檢索課程設(shè)計(jì)名稱航班信息的查詢與檢索資料課程設(shè)計(jì)目的通過(guò)本次實(shí)驗(yàn)，掌握數(shù)據(jù)結(jié)構(gòu)中的幾種排序算法和查找算 法，了解靜態(tài)鏈表的運(yùn)用，利用上述的算法完成航班信息的 查詢與檢索。2系統(tǒng)分析課程設(shè)計(jì)內(nèi)容本課程設(shè)計(jì)主要是對(duì)排序及查找等進(jìn)行練習(xí)，以鏈?zhǔn)交?數(shù)排序?yàn)橹骶€，利用二分查找和順序查找等知識(shí)，并建立靜 態(tài)鏈表，完成對(duì)航班信息的查詢與檢索。我們可以利用航班 的這些信息，通過(guò)其中的任意一個(gè)信息，我由我們所需要的 查找的航班的所有信息，所以，我們可以采用基數(shù)排序法對(duì) 一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)航班號(hào)進(jìn)行排序，利用二分查找法 對(duì)排序好的航班記錄按航班

2、號(hào)實(shí)現(xiàn)快速查找，并按其他關(guān)鍵 字的查找可以采用最簡(jiǎn)單的順序查找方法進(jìn)行。設(shè)計(jì)要求1）提供對(duì)航班信息的排序功能2 提供對(duì)航班信息的輸入輸出記錄功能找出我們所需要 的查找的航班的所有信息3）提供按關(guān)鍵字（航班號(hào)）快速查詢或順序查詢功能資料2.3設(shè)計(jì)分析對(duì)于本設(shè)計(jì)，可采用基數(shù)排序法對(duì)一組具有結(jié)構(gòu)特點(diǎn)的 飛機(jī)航班號(hào)進(jìn)行排序，利用二分查找法對(duì)排好序的航班記錄 按航班號(hào)實(shí)現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡(jiǎn) 單的順序查找方法進(jìn)行，因?yàn)樗鼈冇玫帽容^少。每個(gè)航班記錄包括八項(xiàng)，分別是：航班號(hào)，起點(diǎn)站，終 點(diǎn)站，班期，起飛時(shí)間，到達(dá)時(shí)間，飛機(jī)型號(hào)以及票價(jià)等。 其中航班號(hào)一項(xiàng)的格式為：K0 k1 k2 k3

3、k4 k5CZ3869航班關(guān)鍵字可分為兩段，即字母和數(shù)字。其中 k0和k1是航 空公司的別稱，用兩個(gè)大寫(xiě)字母表示，后 4位為航班編號(hào).3概要設(shè)計(jì)系統(tǒng)總流程圖航班信息的查詢與檢索系統(tǒng)資料按 航 班 號(hào) 查 詢按 起 飛 時(shí) 問(wèn) 查 詢按 到 達(dá) 時(shí) 問(wèn) 查 詢按 起 點(diǎn) 站 查 詢按 終 點(diǎn) 站 查 詢定義數(shù)據(jù)類型根據(jù)設(shè)計(jì)要求，設(shè)計(jì)中所用到的數(shù)據(jù)記錄只有航班信息，因此要定義相關(guān)的數(shù)據(jù)類型：typedef struct char start7;起點(diǎn)char end7;終點(diǎn)char sche12;/ 班期char time15;起飛時(shí)問(wèn)資料char time25;char model4;int pr

4、ice;InfoType;記錄類型typedef structKeyType keyskeylen;InfoType others;int next;slnode;點(diǎn)typedef structSLNode slMaxSpace;鏈表，s10為頭結(jié)點(diǎn)int keylen;int length;長(zhǎng)SLList;鏈表類型/到達(dá)時(shí)機(jī)型票價(jià)航班關(guān)鍵字表結(jié)靜態(tài)/關(guān)鍵字長(zhǎng)/當(dāng)前表靜態(tài)為了進(jìn)行基數(shù)排序，需要定義在分配和收集操作時(shí)用到的指針數(shù)組：資料/十進(jìn)制數(shù)typedef int ArrType_n10;字指針數(shù)組typedef int ArrType_c26;/26 個(gè)字母指針數(shù)組實(shí)現(xiàn)排序的各函數(shù)的說(shuō)明一

5、趟分配函數(shù)：void Distribute(SLNode *s1,int i,ArrType f,ArrType e);本算法是按關(guān)鍵字 keyi建立RADIX個(gè)子表，使同一個(gè)子表中記錄的keysi相同，f0.RADIX和e0.RADIX分別指向各子表中的第一個(gè)和最后一個(gè)記錄一趟搜集函數(shù)：void Collect(SLNode *s1,int i,ArrType f,ArrType e);本算法是按關(guān)鍵字keysi從小到大將0.RADIX所指的各子表依次鏈接成一個(gè)鏈表3)鏈?zhǔn)交鶖?shù)排序函數(shù)：void RadixSort(SLList &L);/本算法是按關(guān)鍵字從低位到高位依次對(duì)各關(guān)鍵字進(jìn)行分配和

6、收集，分兩段實(shí)現(xiàn)4)二分查找函數(shù)：int BinSearch(SLList L,KeyType key);/L為待查找的表，key口為待查找的關(guān)鍵字，按二分查找的資料思想實(shí)現(xiàn)查找5)主控函數(shù)void main()(初始化；數(shù)據(jù)輸入；排序處理；接受查找要求及查找關(guān)鍵字；查找處理；輸由查找結(jié)果；)4詳細(xì)設(shè)數(shù)據(jù)類型的定義根據(jù)設(shè)計(jì)要求我們知道所用的記錄中只有航班信息因此要定義相關(guān)的數(shù)據(jù)類型其源程序如下typedef struct(char start6;/ 起點(diǎn)char end6;/ 終點(diǎn)char sche10;/ 班期char time15;/ 起飛時(shí)間資料char time25;/ 到達(dá)時(shí)間cha

7、r model4;/ 機(jī)型int price; / 票價(jià)infotype;/航班記錄類型typedef struct keytype keyskeylen;/ 關(guān)鍵宇 航班號(hào)infotype others;int next;slnode;/靜態(tài)鏈表類型typedef struct slnode slmaxspace; 靜態(tài)鏈表sl0為頭結(jié)點(diǎn)int keynum;/記錄當(dāng)前關(guān)鍵字字符個(gè)數(shù)int length;/當(dāng)前表長(zhǎng)sllist;/靜態(tài)鏈表類型typedef int arrtype_nradix_n;/ 十進(jìn)制數(shù)字指針typedef int arrtype_cradix_c;/26 個(gè)字母指針

8、鏈?zhǔn)交鶖?shù)排序資料輸入數(shù)據(jù)、基數(shù)、長(zhǎng)度改造為靜態(tài)鏈表對(duì)關(guān)鍵字分配和收集將數(shù)據(jù)分為兩段每段進(jìn)行串式基數(shù)排序iL.length資料L.sli.next=i+1按指針整理鏈表重新整理靜態(tài)鏈表重新整理靜態(tài)鏈表，P指示第一個(gè)記錄的當(dāng)前位置，L.s11.i-1 已按關(guān)鍵字有序排列，第一個(gè)記錄在L中的當(dāng)前位置應(yīng)不小于i,使用while循環(huán)，找到第i個(gè)記錄，并用p指示其在 L中的當(dāng)前位置，而q指示尚未調(diào)整的表尾，若if(p!=i)則p指向被移走的記錄，使得以后可由while循環(huán)找回，當(dāng)p=q時(shí)，p指向尚未調(diào)整的表尾，為找到第i+個(gè)記錄做準(zhǔn)備資料4.4查找算法實(shí)現(xiàn)4.4.1二分查找函數(shù)開(kāi)始輸入航班輸入航班號(hào)對(duì)應(yīng)序

9、列號(hào)資料low=mid+1Mid=(low+high)/24.4.2順序查找函數(shù)void SeqSearch(SLList L,KeyType key,int i) int j,k,m=0;for(j=1;j=1 & i=5) printf(”*n);printf(*航班信息查詢系統(tǒng)*n);printf(*1航班號(hào)*n);printf(*2起點(diǎn)站*n);printf(*3終點(diǎn)站*n);資料printf(*4起飛時(shí)間*n);printf(*5到達(dá)時(shí)間*n);printf(*0退由系統(tǒng)*n);printf(*n);printf( 請(qǐng)選擇 0-5 : n );scanf(%d,&i);switch(

10、i) printf(輸入要查的航班號(hào)(字母要大寫(xiě))：);scanf(%s,key);k=BinSearch(L,key);Display(L,k);break; TOC o 1-5 h z printf(輸入要查詢的航班起點(diǎn)站名：);scanf(%s,key);SeqSearch(L,key,i);break;printf(輸入要查詢的航班終點(diǎn)站點(diǎn)：);scanf(%s,key); SeqSearch(L,key,i);break;printf(輸入要查詢的航班起飛時(shí)間：);scanf(%s,k1); SeqSearch(L,k1,i);break;printf(輸入要查詢的航班到達(dá)時(shí)間：);

11、scanf(%s,k1); SeqSearch(L,k1,i);break;資料case 0: printf(再 見(jiàn)！ n);return 0;)void InputData(SLList &L) int i=+L.length;char yn=y;while(yn=y | yn=Y) printf(航班號(hào) 起點(diǎn)站 終點(diǎn)站 航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)n);scanf(%s%s%s%s%s%s%s%d,L.s1i.keys,L.s1i.others.start,L.s1i.others.end,L.s1i.others.sche,L.s1i.others.time1,L.s1i.others

12、.time2,L.s1i.others.model,&L.s1i.others.price);+i;printf(繼續(xù)輸入嗎？y/n: n);scanf(%c,&yn);)L.length=i-1;)資料5運(yùn)行與測(cè)試航班信息輸入如圖:點(diǎn)反至占需點(diǎn)海宇占朗虎壽席瞿 A:整A0馨國(guó)An起廣年-斕 號(hào)叫悔蠢罵外s智23詢苕粵！3粵加輸 T第“虢建如i ”靠i富曲技 物魅需簫CZ需疆施黑母泄冊(cè)就維n n n n n髭解箱狷:品由點(diǎn)義串占我北IV3K翼深7釐超南到血出站 真E點(diǎn)劇 瞽展北 站鬻按航班號(hào)查詢:航土如期迎飛時(shí)間 .2.4.5 J.酶后甯f助相飛時(shí)間 1 42iH艇明期 售R起飛時(shí)M 36&S

13、蟹營(yíng)期起飛時(shí)間l；1Wkl航珈期1 .3.5包飛時(shí)間 i2oe航期期1 .S起飛時(shí)間1占WH航珈期 1 -1 T旦飛時(shí)閩1時(shí)時(shí)就如期2 .1起飛時(shí)間L23G到達(dá)時(shí)間 1240手中古時(shí)間IfclS到達(dá)時(shí)間到達(dá)時(shí)間 13311到達(dá)盟同 1512至中土?xí)r間 W到達(dá)時(shí)間XW1時(shí)到達(dá)時(shí)間 2013機(jī)型挈布 7339G電機(jī)型察價(jià)H9H P約機(jī)型累傷 7331010帆型早價(jià) bH 1 mu機(jī)型要價(jià) 877-10Q機(jī)型平價(jià)%HX 1WMW鞏型票價(jià)H771231機(jī)型享僑 744 XQ2S輸入航班號(hào)錯(cuò)誤則顯示如下圖:亡二 .Vi nd.Mr.KyE：t.cHi3Vbeb-ng：MB , exe-航班信息查詢系統(tǒng)-

14、|D| x|一 7K ”甘立：星統(tǒng)鬻品翁1 2 3453請(qǐng)選擇G-C：前人要查詢的航班號(hào)字母要大與力間京雙無(wú)此航班信息-可能是輸入相反!資料點(diǎn) 站 查 詢航班總總查詢系統(tǒng)i 口星站一班點(diǎn)點(diǎn)航遠(yuǎn)終遠(yuǎn)量一 _12 2 4 5 0二mixmn、三尸寫(xiě) t E,32，D 紀(jì)bn告exe越fee*(， 衽* I統(tǒng)i森h(huán)超站圖統(tǒng) 瞿汝灌第 w M 1 2 3 4 5 0 * * *請(qǐng)選擇9-5）：）入要查詢的航班起點(diǎn)站名;南昌資料M-KN-at* * * * H.34站圄統(tǒng) 飛達(dá)出。冬桓FM，* M 12 3 4 5 0 MT * MMw * 曇分 * *清-先擇日13 00期需 W W 器期起飛程到達(dá)慨

15、嚶產(chǎn) *顯示查詢主菜單，退由查詢系統(tǒng)：6總結(jié)與心得通過(guò)本實(shí)驗(yàn)，我了解了基數(shù)排序是作為一種內(nèi)部排序方 法，當(dāng)關(guān)鍵字位數(shù)較少而排序序列較長(zhǎng)時(shí)，該排序算法有一 定的優(yōu)越性。而對(duì)于有序序列的查找算法，二分查找是一種 效率比較高的方法。在本實(shí)驗(yàn)中，對(duì)這兩種算法的應(yīng)用，我 加深了對(duì)他們的理解，掌握了他們的實(shí)現(xiàn)方法。在本次實(shí)驗(yàn)過(guò)程中，輸入錯(cuò)誤還是存在的問(wèn)題，但能很 快的通過(guò)編譯解決，一些編譯不能發(fā)現(xiàn)的問(wèn)題，在組建過(guò)程 中也能發(fā)現(xiàn)并解決。這次實(shí)驗(yàn)的過(guò)程中遇到了很多問(wèn)題，定 義的過(guò)程中存在定義不清楚的問(wèn)題，還有一些模糊定義和重 定義的問(wèn)題由現(xiàn)。在程序的定義過(guò)程中，存在著函數(shù)的調(diào)用 失敗的問(wèn)題，在調(diào)用過(guò)程中不能正

16、常調(diào)用，通過(guò)把調(diào)用的函 數(shù)直接用在程序中，不通過(guò)調(diào)用的方法，使得程序正常運(yùn)行資料本次實(shí)驗(yàn)的問(wèn)題只要通過(guò)調(diào)試和對(duì)整個(gè)程序的理解，便可以解決所有的發(fā)現(xiàn)的問(wèn)題本次實(shí)驗(yàn)利用二分查找法很快的完成了對(duì)航班信息的 查找，使我們對(duì)二分查找有了一個(gè)很好的掌握。具查找過(guò)程 是先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。在實(shí)驗(yàn)過(guò)程中，程序中許多定義需要我們有一個(gè)很仔細(xì) 的了解，比如上述的對(duì)字符長(zhǎng)度的定義，這需要對(duì)所定義的 對(duì)象給一個(gè)合理的字符長(zhǎng)度，在輸入的過(guò)程中才不會(huì)由現(xiàn)因 輸入的字符長(zhǎng)度過(guò)長(zhǎng)而不能識(shí)別。本次實(shí)驗(yàn)中用到了靜態(tài)鏈 表，定義靜態(tài)鏈表的過(guò)程中，需要有一個(gè)很熟悉的了解，知

17、道靜態(tài)鏈表是如何定義以及如何實(shí)現(xiàn)。通過(guò)這次實(shí)驗(yàn)，使得 對(duì)于查找以及檢索有了一個(gè)很好的掌握，讓我們?cè)谝院蟮某?序設(shè)計(jì)過(guò)程中對(duì)于類似的函數(shù)定義有一個(gè)很清晰的過(guò)程以 及了解。8附錄（程序源代碼）#include #include #define MaxSpace 100#define keylen 7資料#define RADIX_n 10#define RADIX_c 26typedef char KeyType;typedef structchar start6; / 起點(diǎn)char end6;/ 終點(diǎn)char sche10;班期char time15;/ 起飛時(shí)間char time25;/ 到達(dá)

18、時(shí)間char model4;/ 機(jī)型int price;票價(jià)InfoType;/航班記錄類型typedef structKeyType keyskeylen; 關(guān)鍵字（航班號(hào)）InfoType others;int next;SLNode;/靜態(tài)鏈表結(jié)點(diǎn)類型typedef structSLNode slMaxSpace; 靜態(tài)鏈表，s10為頭結(jié)點(diǎn)資料int keynum;/記錄當(dāng)前關(guān)鍵字字符個(gè)數(shù)int length;/當(dāng)前表長(zhǎng)SLList;/靜態(tài)鏈表類型typedef int ArrType_nRADIX_n;/ 十進(jìn)制數(shù)字指針數(shù)組typedef int ArrType_cRADIX_c; /

19、26 個(gè)字母指針數(shù)組/ 一趟數(shù)字字符分配函數(shù)void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)int j,p;for(j=0;jRADIX_n;j+)/各子表置為空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;將數(shù)字字符轉(zhuǎn)換成相對(duì)應(yīng)的數(shù)值型數(shù)字if(!fj)fj=p;elseslej.next=p;ej=p;將p指向的結(jié)點(diǎn)插入到第j個(gè)子表中資料)/ 一趟數(shù)字字符的收集函數(shù)void Collect(SLNode *sl,int i,ArrType_n f,ArrType_n

20、e)(int j,t;for(j=0;!fj;j+)/我第一個(gè)非空子表sl0.next=fj; /s10.next指向第一個(gè)非空子表中的一個(gè)結(jié)點(diǎn)t=ej;while(jRADIX_n-1)(for(j=j+1;jRADIX_n-1&!fj;j+)/ 找下一個(gè)非空子表if(fj)(slt.next=fj; t=ej; / 鏈接兩個(gè)非空子表)slt.next=0;/t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn)/ 一趟字母字符分配函數(shù)void Distribute_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)資料(int j,p;for(j=0;jRADIX_c;

21、j+) /各子表置為空表fj=ej=0;)for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;將字母字符轉(zhuǎn)換成在字母集中相應(yīng)的序號(hào)(0-25 )if(!fj)fj=p;elseslej.next=p;ej=p;)/ 一趟字母字符收集void Collect_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)int j,t;for(j=0;!fj;j+);資料sl0.next=fj;t=ej;while(jRADIX_c-1)(for(j=j+1;jRADIX_c-1&!fj;j+);if(fj)(slt.next=fj;t=

22、ej;slt.next=0;/鏈?zhǔn)交鶖?shù)排序函數(shù)void RadixSort(SLList &L)/ 鏈?zhǔn)?int i;ArrType_n fn,en;ArrType_c fc,ec;for(i=0;i=2;i-) /按最低位優(yōu)先次序?qū)Ω麝P(guān)鍵字進(jìn)行分配和收集，先做低4位數(shù)字部分Distribute(L.sl,i,fn,en);Collect(L.sl,i,fn,en);for(i=1;i=0;i-) /對(duì)高位的2位大寫(xiě)字母進(jìn)行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,i,fc,ec);/按指針鏈重新整理靜態(tài)鏈表void Arrange(SLLi

23、st &L)/ 重新整理int p,q,i;SLNode temp;p=L.sl0.next;/p指向第一個(gè)記錄的當(dāng)前位置for(i=1;iL.length;i+)/l.s11 - i-1已按關(guān)鍵字有序化資料while(pi)p=L.slp.next;找到第i個(gè)記錄，并用p指向其在L中當(dāng)前位置q=L.slp.next;/q指向尚未調(diào)整的表尾if(p!=i)(temp=L.slp; L.slp=L.sli; L.sli=temp; L.sli.next=p; /交換記錄p=q; /p指向尚未調(diào)整的表尾，為我第 i+1個(gè)記錄做準(zhǔn)備/二分查找函數(shù)int BinSearch(SLList L,KeyT

24、ype key)(int low,high,mid;low=1;high=L.length;while(low=high)(mid=(low+high)/2;資料if(strcmp(key,L.slmid.keys)=0) return mid;else if(strcmp(key,L.slmid.keys)0) high=mid-1;else low=mid+1;return 0;/順序查找函數(shù)void SeqSearch(SLList L,KeyType key,int i) int j,k,m=0;printf(”*n);到達(dá)時(shí)printf(*航班號(hào) 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)間 間

25、機(jī)型票價(jià)*n);for(j=1;j=1&i=5)(printf(*n);printf（ *航班信息查詢系統(tǒng)*n）;printf( *,*n“)；printf( *1.航班號(hào)*nprintf( *2.起點(diǎn)站*nprintf( *3.終點(diǎn)站*nprintf( *4.起飛時(shí)間*nprintf( *5.到達(dá)時(shí)間*nprintf( *0.退由系統(tǒng)*nprintf( *,*n“)；printf(請(qǐng)選擇(0-5): n);scanf(%d,&i);switch(i) (（字母要大寫(xiě)）：）;case 1:printf(輸入要查詢的航班號(hào) scanf(%s,key);資料k=BinSearch(L,key);printf(”*n）;if（k=0）printf（無(wú)此航班信息，可能是輸入錯(cuò)誤！n）;else (printf(*航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)*n);printf(*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*n,L.slk.keys,L.slk.others.start,L.slk.others.end,L.slk.others.sche,L.slk.others.time1,L.slk.others.time2,L.sl k.others.model,