數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班信息查詢與檢索系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：航班信息查詢與檢索專業(yè)：班級(jí)：學(xué)號(hào)：姓名：任課老師：2010年12月26日目錄一、設(shè)計(jì)題目.1二、設(shè)計(jì)要求.2三、概要設(shè)計(jì).21.設(shè)計(jì)思路22.流程圖2四、詳細(xì)設(shè)計(jì).3 1.定義數(shù)據(jù)類型.3 2.算法實(shí)現(xiàn).3五、測(cè)試數(shù)據(jù).6 1.錄入航班信息6 2.航班信息查詢7六、收獲與體會(huì).8一、設(shè)計(jì)題目 設(shè)計(jì)一個(gè)航班信息查詢與檢索系統(tǒng)?？砂春桨嗟暮桨嗵?hào)、起點(diǎn)站、終點(diǎn)站、起飛時(shí)間以及到達(dá)時(shí)間等信息進(jìn)行查詢。二、設(shè)計(jì)要求1、每個(gè)航班記錄包括八項(xiàng)：航班號(hào)、起始站、終點(diǎn)站、班期、起飛時(shí)間、到達(dá)時(shí)間、飛機(jī)型號(hào)、票價(jià)。如下表所示：航班信息表航班號(hào) 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)機(jī) 到達(dá)時(shí)間

2、 機(jī)型 票價(jià) ca1544 合肥 北京 1.2.5 1055 1240 733 9602、要有輸入模塊。3、對(duì)航班信息進(jìn)行排序與查找。三、概要設(shè)計(jì)1、設(shè)計(jì)思路根據(jù)題目所要求，程序必須實(shí)現(xiàn)航班信息的錄入和查詢。程序首先定義了一個(gè)用于儲(chǔ)存航班信息的數(shù)據(jù)類型，再由用戶錄入航班數(shù)據(jù)，在錄入的同時(shí)并對(duì)數(shù)據(jù)進(jìn)行排序，最后執(zhí)行數(shù)據(jù)查詢和檢索。在查詢?cè)O(shè)計(jì)中，使用二分查找法對(duì)排好序的航班數(shù)據(jù)按航班號(hào)實(shí)現(xiàn)快速查找，按起點(diǎn)站、終點(diǎn)站、起飛時(shí)間、到達(dá)時(shí)間查找的則采用順序查詢方法。2、流程圖定義數(shù)據(jù)類型 輸出查找結(jié)果接受查找條件、查找關(guān)鍵字?jǐn)?shù)據(jù)輸入、排序四、詳細(xì)設(shè)計(jì) 1 . 定義數(shù)據(jù)類型 根據(jù)設(shè)計(jì)要求，設(shè)計(jì)中所用到的數(shù)

3、據(jù)記錄只有航班信息，因此要定義相關(guān)的數(shù)據(jù)類型：typedef struct char start6; /起點(diǎn)站char end6; /終點(diǎn)站char sche10; /航班期char time15; /起飛時(shí)間char time25; /到達(dá)時(shí)間char model4; /機(jī)型int price; /票價(jià)infotype; /航班記錄類型typedef structkeytype keyskeylen; /關(guān)鍵字infotype others;int next;slnode; /表結(jié)點(diǎn)typedef structslnode slmaxspace; /靜態(tài)鏈表，s10為頭結(jié)點(diǎn)int keynu

4、m; /關(guān)鍵字長int length; /當(dāng)前表長sllist; /靜態(tài)鏈表類型為了進(jìn)行基數(shù)排序，需要定義在分配和收集操作時(shí)用到的指針數(shù)組：typedef int arrtype_n10; /十進(jìn)制數(shù)字指針數(shù)組typedef int arrtype_c26; /26個(gè)字母指針數(shù)組2 . 算法實(shí)現(xiàn) （1）一趟分配算法 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ù)字

5、字符轉(zhuǎn)化為對(duì)應(yīng)的數(shù)值型數(shù)字if(!fj)fj=p;elseslej.next=p;ej=p; /將p指向的結(jié)點(diǎn)插入到第j個(gè)結(jié)點(diǎn)（2）一趟收集算法void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,t;for(j=0;!fj;j+); /找第一個(gè)非空子表sl0.next=fj;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;（3）鏈?zhǔn)交鶖?shù)排序算法 void radixs

6、ort(sllist &l)int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-) /按最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配和收集distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i=0;i-)distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void arrange(sllist &l) /按指針鏈表整理靜態(tài)鏈表int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i+)while(

7、pi)p=l.slp.next;q=l.slp.next;if(p!=i)temp=l.slp;l.slp=l.sli;l.sli=temp; /交換記錄l.sli.next=p;p=q;（4）二分查找函數(shù)定義int binsearch(sllist l,keytype 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;elsel

8、ow=mid+1;return 0;五、測(cè)試數(shù)據(jù)1、錄入航班信息編譯后運(yùn)行，顯示：航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)錄入：mu4594昆明西安 1.3.5.6 1015 1140 3281160顯示：繼續(xù)輸入嗎?y/n:錄入：y顯示：航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)錄入：sc7425青島海口 1.3.6 1920 2120 dh41630顯示：繼續(xù)輸入嗎?y/n:錄入：n2、航班信息查詢錄入航班信息后，屏幕顯示：* 航班信息查詢系統(tǒng) * 1.航 班 號(hào) * 2.起 點(diǎn) 站 * 3.終 點(diǎn) 站 * 4.起飛時(shí)間 * 5.到達(dá)時(shí)間 * 0.退出系統(tǒng) *請(qǐng)選擇(0-5)

9、:錄入：1顯示：輸入要查詢的航班號(hào)(字母要大寫):錄入：mu4594顯示：航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)mu4594-昆明 -西安 -1.3.5.6 -1015 -1140 -328 -1160錄入：2顯示：輸入要查詢的航班起點(diǎn)站名:錄入：青島顯示：航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)sc7425-青島-?？?-1.3.6 -1920 -2120 -dh4-1630錄入：2顯示：輸入要查詢的航班起點(diǎn)站名:錄入：廣州顯示：* 無此航班信息，可能是輸入錯(cuò)誤！ *六、收獲與體會(huì)本設(shè)計(jì)的重點(diǎn)和難點(diǎn)是在于對(duì)航班數(shù)據(jù)的排序和查找，以鏈?zhǔn)交鶖?shù)排序?yàn)橹骶€，用到了二分查找和順序查找

10、等知識(shí)，還有建立靜態(tài)鏈表等。通過這次課程設(shè)計(jì)，使我對(duì)c語言編程有了新的認(rèn)識(shí)。以前編程只是注重如何編寫函數(shù)能夠完成所需要的功能，只是憑單純的意識(shí)和簡單的語句來堆砌出一段程序。但現(xiàn)在編程感覺完全不同了。在編寫一個(gè)程序之前，自己能夠綜合考慮各種因素，選取自己需要的數(shù)據(jù)結(jié)構(gòu)，在編寫每一個(gè)函數(shù)之前，可以仔細(xì)斟酌比對(duì)，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質(zhì)量。另外，我還體會(huì)到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解這樣定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程

11、序的關(guān)鍵。附錄源程序清單：#include stdafx.h#include #include #define maxspace 100#define keylen 7#define radix_n 10#define radix_c 26typedef char keytype;typedef struct char start6;char end6;char sche10;char time15;char time25;char model4;int price;infotype;typedef structkeytype keyskeylen;infotype others;int ne

12、xt;slnode;typedef structslnode slmaxspace;int keynum;int length;sllist;typedef int arrtype_nradix_n;typedef int arrtype_cradix_c;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;if(!fj)fj=p;elseslej.next=p;ej=p;vo

13、id collect(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jradix_n-1)for(j=j+1;jradix_n-1&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)int j,p;for(j=0;jradix_c;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=s

14、lp.keysi%65;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=ej; slt.next=0;void radixsort(sllist &l)int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-

15、)distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i=0;i-)distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void arrange(sllist &l) int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i+)while(pi)p=l.slp.next;q=l.slp.next;if(p!=i)temp=l.slp;l.slp=l.sli;l.sli=temp;l.sli.next=p;p=q;int binsearc

16、h(sllist l,keytype 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;elselow=mid+1;return 0;void seqsearch(sllist l,keytype key,int i)int j,k,m=0;printf(*n);printf(* 航班號(hào) 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)間 到達(dá)時(shí)間

17、 機(jī)型 票價(jià) *n);for(j=1;j=1&i=5)printf(*n);printf( * 航班信息查詢系統(tǒng) *n);printf( *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):);scanf(%d,&i);printf(n);switch(i)case 1:printf(輸入要查詢的航班號(hào)(字母要大寫):);sc

18、anf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 無此航班信息，可能是輸入錯(cuò)誤！ *n);elseprintf(* 航班號(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.slk.others.model,l.slk.others.price);printf(*n);break;case 2:printf(輸入要查詢的航班起點(diǎn)站名:);scanf(%s,key);seqsearch(l,key,i);break;case 3:printf(輸入要查詢的航班終點(diǎn)站名:);scanf(%s,key);s