2022年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班查詢系統(tǒng)實(shí)驗(yàn)報(bào)告

1、目 錄TOC o 1-3 h u HYPERLINK l _Toc32144 一、概述 PAGEREF _Toc32144 1 HYPERLINK l _Toc13871 二、系統(tǒng)分析 PAGEREF _Toc13871 1 HYPERLINK l _Toc7774 1.航班信息的查詢與檢索 PAGEREF _Toc7774 1 HYPERLINK l _Toc24534 2.航班信息查詢與檢索數(shù)據(jù)結(jié)構(gòu)理論 PAGEREF _Toc24534 1 HYPERLINK l _Toc23760 三、概要設(shè)計(jì) PAGEREF _Toc23760 2 HYPERLINK l _Toc21361 1.系

2、統(tǒng)的功能 PAGEREF _Toc21361 2 HYPERLINK l _Toc20948 2.系統(tǒng)模塊分析及其流程圖 PAGEREF _Toc20948 3 HYPERLINK l _Toc28424 四、詳細(xì)設(shè)計(jì) PAGEREF _Toc28424 6 HYPERLINK l _Toc20675 1.各函數(shù)說(shuō)明 PAGEREF _Toc20675 6 HYPERLINK l _Toc14398 2.定義相關(guān)數(shù)據(jù)類型 PAGEREF _Toc14398 8 HYPERLINK l _Toc29112 3. 航班信息的查詢 PAGEREF _Toc29112 9 HYPERLINK l _T

3、oc29628 五、 運(yùn)行由于測(cè)試 PAGEREF _Toc29628 12 HYPERLINK l _Toc10185 六、總結(jié)與心得 PAGEREF _Toc10185 16 HYPERLINK l _Toc19719 參考文獻(xiàn) PAGEREF _Toc19719 16 HYPERLINK l _Toc2567 附錄 PAGEREF _Toc2567 16一、概述 隨著信息產(chǎn)業(yè)的飛速發(fā)展，信息化管理及查詢已經(jīng)進(jìn)入并應(yīng)用到各行各業(yè)，影響著人們的價(jià)值觀念和生活方式。因此，要提高企業(yè)信息化建設(shè)，利用先進(jìn)的辦公自動(dòng)化系統(tǒng)來(lái)實(shí)現(xiàn)企業(yè)內(nèi)部信息管理、共享及交流，從而提高企業(yè)綜合實(shí)力。 本次設(shè)計(jì)是針對(duì)航班

4、的查詢系統(tǒng)，該設(shè)計(jì)要求對(duì)飛機(jī)航班信息進(jìn)行排序和查詢?？砂春桨嗟暮桨嗵?hào)、起點(diǎn)站、終點(diǎn)站等信息進(jìn)行航班信息的查詢。二、系統(tǒng)分析1.航班信息的查詢與檢索進(jìn)入系統(tǒng)后，首先提示輸入航班的信息，包括：航班號(hào)、起點(diǎn)站、終點(diǎn)站、班期、起飛時(shí)間、到達(dá)時(shí)間、飛機(jī)型號(hào)及票價(jià)等，票價(jià)為整型，其他為字符型。當(dāng)輸入完一個(gè)信息后會(huì)提示是否繼續(xù)輸入，重復(fù)以上步驟輸入全部的信息。進(jìn)入主菜單后會(huì)給出用戶操作的界面，根據(jù)提示進(jìn)行航班信息的查詢。2.航班信息查詢與檢索數(shù)據(jù)結(jié)構(gòu)理論針對(duì)在本該類系統(tǒng)中的數(shù)據(jù)的處理情況，本系統(tǒng)采用二分查找法、基數(shù)排序法、最高位優(yōu)先法。二分查找法也稱為折半查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，

5、可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是，將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與欲查找的x作比較，如果x=an/2則找到x，算法終止。如 果xan/2，則我們只要在數(shù)組a的右 半部繼續(xù)搜索x。對(duì)航班號(hào)的排序是采用的基數(shù)排序法?；鶖?shù)排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。最高位優(yōu)先(Most Sign

6、ificant Digit first)法，簡(jiǎn)稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對(duì)各組按k2排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來(lái)，便得到一個(gè)有序序列。最低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD法：先從kd開(kāi)始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。三、概要設(shè)計(jì)1.系統(tǒng)的功能本任務(wù)要求對(duì)飛機(jī)航班信息進(jìn)行排序和查找?？砂春桨嗟暮桨嗵?hào)、起點(diǎn)站、到達(dá)站、起飛時(shí)間以及到達(dá)時(shí)間等信息進(jìn)行查詢。本設(shè)計(jì)主要是對(duì)排序以及查找等概念進(jìn)行綜

7、合練習(xí)。以鏈?zhǔn)交鶖?shù)排序?yàn)橹骶€，用到二分查找和順序查找等知識(shí)，還有建立靜態(tài)鏈表等相關(guān)概念。航班信息查詢系統(tǒng)航班信息查詢系統(tǒng)按航班號(hào)查詢退出系統(tǒng)輸入航班信息按起點(diǎn)站查詢按終點(diǎn)站查詢按到達(dá)時(shí)間查詢按起飛時(shí)間查詢2.系統(tǒng)模塊分析及其流程圖（1）航班排序?qū)斎胂到y(tǒng)內(nèi)的航班首先要進(jìn)行排序，我們采用的基數(shù)排序，從低位到高位依次對(duì)關(guān)鍵字進(jìn)行分配和收集，分兩段實(shí)現(xiàn)其算法流程圖。NN每段進(jìn)行串式基數(shù)排序Y開(kāi)始輸入數(shù)據(jù)數(shù)組，基數(shù)n,長(zhǎng)度Max分配收集操作輪數(shù)nT=0將數(shù)據(jù)分成P段每段n/p個(gè)nT+=1nT=Max結(jié)束 （2)時(shí)間查找根據(jù)航班的起飛時(shí)間（到達(dá)時(shí)間）查找航班的信息。開(kāi)始開(kāi)始輸入查詢時(shí)間Time=1按抵達(dá)

8、時(shí)間查詢按起飛時(shí)間查詢返回查詢信息否是（3)二分法查找功能開(kāi)始開(kāi)始輸入航班號(hào)輸入航班號(hào)對(duì)應(yīng)序號(hào)Low=highMid=(high+low)/2Low=mid+1Num=midfight numberNummidfight number返回High=mid+1否是（4)顯示功能顯示功能是將所求單詞的所有行列信息依次顯示在屏幕上。四、詳細(xì)設(shè)計(jì)1.各函數(shù)說(shuō)明1.一趟分配函數(shù)void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)/一趟字母分配字符函數(shù)int j,p;for(j=0;jradix_c;j+)fj=ej=0;for(p=sl0

9、.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;2.一趟收集函數(shù)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;3.鏈?zhǔn)交鶖?shù)排序void radixsort(sllist &l)/鏈?zhǔn)交鶖?shù)排序函數(shù)int i

10、;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-)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);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

11、)=0)return mid;else if(strcmp(key,l.slmid.keys)=1&i=5)printf(n *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

12、:printf(輸入要查詢的航班號(hào)(字母要大寫(xiě)):);scanf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 無(wú)此航班信息，可能是輸入錯(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.ti

13、me2,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);seqsearch(l,key,i);break;case 4:printf(輸入要查詢的航班起飛時(shí)間:);scanf(%s,key);seqsearch(l,key,i);break;case 5:printf(輸入要查詢的航班到達(dá)時(shí)間:);scanf(%

14、s,key);seqsearch(l,key,i);break;case 0:printf(nnn 再 見(jiàn)nnn);運(yùn)行由于測(cè)試六、總結(jié)與心得在本次試驗(yàn)中，遇到了很多的問(wèn)題。首先，按照書(shū)上的代碼輸入后，有很多錯(cuò)誤，發(fā)現(xiàn)里面的代碼有順序不對(duì)的，有沒(méi)有定義的等問(wèn)題，經(jīng)過(guò)修改解決了這些問(wèn)題。其次，就是在輸入時(shí)遇到了輸入不當(dāng)?shù)脝?wèn)題，修改輸入方法后得到了修改。最后，便是對(duì)幾個(gè)算法的理解不是很透徹，對(duì)算法的具體實(shí)現(xiàn)了解不深。針對(duì)以上問(wèn)題，對(duì)各個(gè)算法解讀了還幾次，對(duì)算法的理解有了一定的理解，對(duì)整個(gè)系統(tǒng)運(yùn)行有了全面的了解。參考文獻(xiàn)1嚴(yán)蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）. 北京:清華大學(xué)出版社.2007.2譚浩

15、強(qiáng).C程序設(shè)計(jì).北京:清華大學(xué)出版社.1999.12.3蘇仕華.數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì).機(jī)械工業(yè)出版社附錄#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;i

16、nfotype others;int next;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;el

17、seslej.next=p;ej=p;void 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.

18、next;p;p=slp.next)j=slp.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)/鏈?zhǔn)絠nt i;arrtype_n fn,en;arrtyp

19、e_c fc,ec;for(i=0;i=2;i-)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;

20、l.sli.next=p;p=q;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;elselow=mid+1;return 0;void seqsearch(sllist l,keytype key,int i)int j,k,m=0;printf(*n);print

21、f(* 航班號(hào) 起點(diǎn)站 終點(diǎn)站 航班期 起飛時(shí)間 到達(dá)時(shí)間 機(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

22、:printf(輸入要查詢的航班號(hào)(字母要大寫(xiě)):);scanf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 無(wú)此航班信息，可能是輸入錯(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);prin