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

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

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

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

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

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

8、時間查詢按起飛時間查詢返回查詢信息否是（3)二分法查找功能開始開始輸入航班號輸入航班號對應(yīng)序號Low=highMid=(high+low)/2Low=mid+1Num=midfight numberNummidfight number返回High=mid+1否是（4)顯示功能顯示功能是將所求單詞的所有行列信息依次顯示在屏幕上。四、詳細設(shè)計1.各函數(shù)說明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.鏈式基數(shù)排序void radixsort(sllist &l)/鏈式基數(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.航 班 號 *n);printf( * 2.起 點 站 *n);printf( * 3.終 點 站 *n);printf( * 4.起飛時間 *n);printf( * 5.到達時間 *n);printf( * 0.退出系統(tǒng) *n);printf( *n);printf( 請選擇(0-5):);scanf(%d,&i);printf(n);switch(i)case 1

12、:printf(輸入要查詢的航班號(字母要大寫):);scanf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 無此航班信息，可能是輸入錯誤！ *n);elseprintf(* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *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(輸入要查詢的航班起點站名:);scanf(%s,key);seqsearch(l,key,i);break;case 3:printf(輸入要查詢的航班終點站名:);scanf(%s,key);seqsearch(l,key,i);break;case 4:printf(輸入要查詢的航班起飛時間:);scanf(%s,key);seqsearch(l,key,i);break;case 5:printf(輸入要查詢的航班到達時間:);scanf(%

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

15、強.C程序設(shè)計.北京:清華大學(xué)出版社.1999.12.3蘇仕華.數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計.機械工業(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)/鏈式int 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(* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *n);for(j=1;j=1&i=5)printf(*n);printf( * 航班信息查詢系統(tǒng) *n);printf( *n);printf( * 1.航 班 號 *n);printf( * 2.起 點 站 *n);printf( * 3.終 點 站 *n);printf( * 4.起飛時間 *n);printf( * 5.到達時間 *n);printf( * 0.退出系統(tǒng) *n);printf( *n);printf( 請選擇(0-5):);scanf(%d,&i);printf(n);switch(i)case 1

22、:printf(輸入要查詢的航班號(字母要大寫):);scanf(%s,key);k=binsearch(l,key);printf(*n);if(k=0)printf(* 無此航班信息，可能是輸入錯誤！ *n);elseprintf(* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *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