數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告——航班信息查詢系統(tǒng)(c++)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告</p><p><b>　　計算機學(xué)院</b></p><p><b>　　軟件工程</b></p><p><b>　　摘要3</b></p><p><b>　　第一章緒論4</b></p&

2、gt;<p>　　1.1課程設(shè)計選題4</p><p>　　1.1.1選題描述4</p><p>　　1.1.2選題要求4</p><p>　　第二章系統(tǒng)需求分析4</p><p>　　2.1輸入/輸出形式和輸出值4</p><p><b>　　2.2功能需求4</b>

3、</p><p><b>　　2.3數(shù)據(jù)流圖5</b></p><p>　　2.4 用戶特點5</p><p>　　2.4 假定和約束5</p><p>　　第三章概要設(shè)計5</p><p><b>　　3.1設(shè)計思想5</b></p><p&

4、gt;　　3.2基本設(shè)計概念和處理流程6</p><p>　　3.3存儲結(jié)構(gòu)設(shè)計8</p><p>　　第四章詳細(xì)設(shè)計9</p><p>　　4.1程序設(shè)計說明9</p><p>　　4.2算法設(shè)計與分析9</p><p>　　4.2.1基數(shù)排序：9</p><p>　　4.2.2

5、二分查找9</p><p>　　4.3算法實現(xiàn)10</p><p>　　4.4函數(shù)說明10</p><p><b>　　第五章測試11</b></p><p>　　5.1核心算法復(fù)雜性分析11</p><p>　　5.2測試數(shù)據(jù)及結(jié)果11</p><p>&l

6、t;b>　　第六章總結(jié)11</b></p><p><b>　　摘要</b></p><p>　　本課程設(shè)計目的在于檢驗數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計與分析兩門課程的學(xué)習(xí)成果，從而加深對所學(xué)的知識的進(jìn)一步理解與鞏固。</p><p>　　本次課程設(shè)計過程中本人主要根據(jù)課本中的理論與算法編寫程序，體現(xiàn)以課本知識的應(yīng)用為主，在學(xué)習(xí)了數(shù)據(jù)結(jié)

7、構(gòu)的基礎(chǔ)上，以能夠更加熟練的應(yīng)用所學(xué)知識，并能結(jié)合一些著名算法來實現(xiàn)對一些實際問題的應(yīng)用，從而更為深刻理解數(shù)據(jù)結(jié)構(gòu)與算法的內(nèi)涵。</p><p>　　本次課程設(shè)計利用C++語言編寫程序，實現(xiàn)對飛機航班信息進(jìn)行排序和查找。</p><p><b>　　緒論</b></p><p>　　隨著信息產(chǎn)業(yè)的飛速發(fā)展，信息化管理及查詢已經(jīng)引入并應(yīng)用到各行各

8、業(yè)，影響著人們的價值觀念與生活方式。因此，要提升企業(yè)競爭力，就要大力推進(jìn)企業(yè)信息化建設(shè)，利用先進(jìn)的辦公自動化系統(tǒng)來實現(xiàn)企業(yè)內(nèi)部信息管理、共享及交流，從而提高企業(yè)綜合實力。</p><p><b>　　1.1課程設(shè)計選題</b></p><p><b>　　1.1.1選題描述</b></p><p>　　該設(shè)計要求對飛機航班

9、信息進(jìn)行排序和查找?？砂春桨嗟暮桨嗵?、起點站、終點站、起飛時間以及到達(dá)時間等信息進(jìn)行查詢。</p><p><b>　　1.1.2選題要求</b></p><p>　?。?）每個航班記錄包括8項，分別是：航班號、起點站、終點站、航班期、起飛時間、到達(dá)時間、機型以及票價，如下給出一個航班記錄的例子： </p><p>　　航班號 起點站 終

10、點站 航班期 起飛時間 到達(dá)時間 機型 票價</p><p>　　CA1544 合肥 北京 1.2.4.5 1055 1240 M90 960</p><p>　?。?）從鍵盤輸入各記錄。</p><p>　?。?）采用基數(shù)排序方法對飛機航班號進(jìn)行排序，然后利用二分查找的方法對排好

11、序的航班記錄按航班號實現(xiàn)快速查找。</p><p>　?。?）按其它次關(guān)鍵字的查找可采用最簡單的順序查找方法進(jìn)行，因為它們用得較少。</p><p><b>　　系統(tǒng)需求分析</b></p><p>　　2.1輸入/輸出形式和輸出值</p><p>　　進(jìn)入系統(tǒng)后，首先提示輸入航班信息，包括：航班號、起點站、終點站、航班

12、期、起飛時間、到達(dá)時間、票價。除票價為整型外，其他均為字符型。每個信息以回車鍵輸入。</p><p>　　當(dāng)輸入完一個航班信息后，會提示是否繼續(xù)輸入，若要繼續(xù)輸入則重復(fù)上述步驟，否則顯示主菜單。</p><p>　　根據(jù)主菜單輸入功能序號，若用戶輸入的值超過給定范圍，則提示錯誤并要求重新輸入。</p><p><b>　　2.2功能需求</b>

13、</p><p><b>　?。?）輸入航班信息</b></p><p>　?。?）按不同類型查詢航班信息：輸入航班號，顯示相應(yīng)信息；</p><p>　　輸入起點站，顯示相應(yīng)信息；</p><p>　　輸入終點站，顯示相應(yīng)信息；</p><p>　　輸入起飛時間，顯示相應(yīng)信息；</p>

14、;<p>　　輸入到達(dá)時間，顯示相應(yīng)信息；</p><p><b>　?。?）退出系統(tǒng)</b></p><p><b>　　2.3數(shù)據(jù)流圖</b></p><p><b>　　2.4 用戶特點</b></p><p>　　本系統(tǒng)的最終用戶是航空公司，操作人員只需具

15、備基本的計算機操作技巧即可。</p><p><b>　　2.4 假定和約束</b></p><p>　　本系統(tǒng)在開發(fā)過程中，由于技術(shù)原因可能會影響到系統(tǒng)的某方面，如有錯誤或未實現(xiàn)的功能，可以另選其他可行方案。</p><p><b>　　概要設(shè)計</b></p><p><b>　　3.

16、1設(shè)計思想</b></p><p>　　對航班信息實現(xiàn)基數(shù)排序，利用折半查找（二分查找）的方法根據(jù)航班號實現(xiàn)查詢，利用順序查找的方法對根據(jù)其他信息實現(xiàn)查詢。</p><p>　　3.2基本設(shè)計概念和處理流程</p><p><b>　　3.3存儲結(jié)構(gòu)設(shè)計</b></p><p>　　本系統(tǒng)采用鏈?zhǔn)酱鎯Φ拇鎯Y(jié)

17、構(gòu)，分別定義三個結(jié)構(gòu)體。 </p><p>　　typedef struct //定義航班信息的結(jié)構(gòu)體,靜態(tài)鏈表類型</p><p><b>　　{</b></p><p>　　char terminal[6]; //定義起點站</p><p>　　char end[6]; //定義終點站</p><

18、p>　　char flightNo[10]; //定義航班期</p><p>　　char startTime[5]; //定義起飛時間</p><p>　　char endTime[5]; //定義到達(dá)時間</p><p>　　char type[10]; //定義機型</p><p>　　int price; //定義票價</

19、p><p>　　}infotype;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　keytype keys[keylen]; //航班號，動態(tài)鏈表</p><p>　　infotype others;</p><p&

20、gt;<b>　　int next;</b></p><p><b>　　}slnode;</b></p><p>　　typedef struct//定義存儲信息的結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　slnode sl[MAX];</p&

21、gt;<p>　　int keynum; //信息數(shù)量，最大表長</p><p>　　int length; //信息長度，當(dāng)前表長</p><p>　　}sllist; //順序表類型</p><p><b>　　詳細(xì)設(shè)計</b></p><p><b>　　4.1程序設(shè)計說明</b>

22、;</p><p>　　1、利用起點站、終點站、起飛時間、到達(dá)時間為關(guān)鍵字來查詢航班信息。該查找算法使用最簡單的順序查找方法進(jìn)行。即按照航班信息的結(jié)構(gòu)體數(shù)組依次與被查找信息作比較，若找到，則輸出結(jié)果即可。若沒找到，則輸出相關(guān)提示信息。</p><p>　　2、利用航班號作為關(guān)鍵字進(jìn)行查詢</p><p>　　由于設(shè)計內(nèi)容要求使用基數(shù)排序?qū)@組航班信息進(jìn)行排序，并利用

23、二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，因此次算法設(shè)計需包括基數(shù)排序和二分查找。</p><p>　　4.2算法設(shè)計與分析</p><p>　　4.2.1基數(shù)排序：</p><p>　　基數(shù)排序是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法，其是通過“分配”和“收集”兩種操作對相應(yīng)關(guān)鍵字進(jìn)行排序。算法思路是按照排序關(guān)鍵字的每一位字符進(jìn)行排序。排序

24、前，先定義一個隊列數(shù)組，每個隊列數(shù)組與某個關(guān)鍵字位對應(yīng)，某隊列中只能存放與該關(guān)鍵字位對應(yīng)的元素。首先先從關(guān)鍵字的最后一位字符進(jìn)行判斷，根據(jù)關(guān)鍵字位，把這個元素放入相應(yīng)的隊列中去，這就是“分配”過程。等到所有元素均被分配到相應(yīng)隊列中之后，在把各個隊列中的元素，按照隊列數(shù)組順序，依次重新放回原元素數(shù)組中，這就是“收集”過程。經(jīng)過“分配”和“收集”后，一次排序完成。接著再以關(guān)鍵字的倒數(shù)第二位字符作為關(guān)鍵字位進(jìn)行上述排序過程，直到按照關(guān)鍵字的所

25、有位全部進(jìn)行排序過后，整個序列就成為有序序列，排序完成。</p><p><b>　　4.2.2二分查找</b></p><p>　　二分查找是對有序序列進(jìn)行快速查找的一種有效方法。它的基本思想是，每次都與這個有序序列的中間元素進(jìn)行比較，若找到，則輸出元素信息，若沒找到，則判斷這個中間元素比待查找的元素大還是小，如果大，那么查找工作繼續(xù)在該有序序列的前半段進(jìn)行；反之，

26、則繼續(xù)查找該有序序列的后半段。如此一直查找，直到找到該元素或者查找到只剩下一個元素而這個元素與待查找元素不相符時，查找結(jié)束。前一種情況找到了待查找元素，輸出該元素，后一種沒有找到，輸出相應(yīng)提示信息。</p><p><b>　　4.3算法實現(xiàn)</b></p><p><b>　　1、順序查找</b></p><p>　　對

27、于根據(jù)起點站、終點站、航班期、起飛時間、到達(dá)時間來進(jìn)行航班查找的函數(shù)，只需將這個查找關(guān)鍵字與結(jié)構(gòu)體數(shù)組中相應(yīng)的鍵值進(jìn)行比較，因為每個關(guān)鍵字查找不一定是唯一的，所以如果想要查找到所有的相關(guān)信息，則必須將結(jié)構(gòu)體查找到底。當(dāng)找到相應(yīng)航班信息時，只要將其輸出即可。</p><p><b>　　2、基數(shù)排序</b></p><p>　　最高位優(yōu)先(Most Significan

28、t Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。</p><p><b>　　3、二分查找</b></p><p>　　設(shè)置標(biāo)志位left，right，mid。其中l(wèi)eft表示查找

29、序列的左端第一個元素下標(biāo)，right表示查找序列的右端第一個元素下標(biāo)。mid等于（left+right）/2。函數(shù)使用while循環(huán)，循環(huán)條件是left<=right。在循環(huán)體內(nèi)，首先判斷待查找信息的航班號是否與以mid為下標(biāo)的數(shù)組內(nèi)指針?biāo)赶虻慕Y(jié)構(gòu)體變量一致，若一致，則輸出該航班信息，若比該結(jié)構(gòu)體變量小，則令rihgt=mid-1，繼續(xù)進(jìn)入下一輪循環(huán)，若比較大，則令left=mid+1，繼續(xù)循環(huán)。這樣查找到最后，若找到，則會輸出

30、相應(yīng)航班信息，若沒有找到，需要輸出提示信息。</p><p><b>　　4、主函數(shù)</b></p><p>　　在主函數(shù)中，依然是以while循環(huán)的方式列出該程序的操作清單。該程序的菜單是請用戶選擇以什么作為查找關(guān)鍵字來查找航班信息。查找菜單如下：1.航班號，2.起點站，3.終點站，4.起飛時間，5.到達(dá)時間，0.退出。選擇不同菜單項，將會提示不同信息讓用戶輸入，然

31、后程序根據(jù)各自的查找方法進(jìn)行查找。</p><p><b>　　4.4函數(shù)說明</b></p><p>　?。?）一趟數(shù)字字符分配函數(shù)</p><p>　　void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)</p><p>　　（2）一趟數(shù)字字符收集函數(shù)&l

32、t;/p><p>　　void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)</p><p>　?。?）一趟字母字符分配函數(shù)</p><p>　　void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)</p><p>　?。?）一

33、趟字母字符收集函數(shù)</p><p>　　void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)</p><p>　?。?）鏈?zhǔn)交鶖?shù)排序函數(shù)</p><p>　　void radixsort(sllist &l)</p><p>　?。?）按指針鏈重新整理靜態(tài)鏈表</p&g

34、t;<p>　　void arrange(sllist &l)</p><p><b>　?。?）二分查找函數(shù)</b></p><p>　　int binsearch(sllist l,keytype key[])</p><p><b>　?。?）順序查找函數(shù)</b></p><

35、p>　　void seqsearch(sllist l,keytype key[],int i)</p><p><b>　?。?）查詢檢索菜單</b></p><p>　　void searchcon(sllist l)</p><p>　　（10）錄入航班數(shù)據(jù)函數(shù)</p><p>　　void inputdat

36、a(sllist &l)</p><p><b>　　（11）主函數(shù)</b></p><p>　　void main()</p><p><b>　　測試</b></p><p>　　5.1核心算法復(fù)雜性分析</p><p>　?。?）基數(shù)排序復(fù)雜性分析</p&

37、gt;<p>　　設(shè)待排序列為n個記錄，d個關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時間復(fù)雜度為O(d(n+radix))，其中，一趟分配時間復(fù)雜度為O(n)，一趟收集時間復(fù)雜度為O(n)，共進(jìn)行d趟分配和收集。 空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜態(tài)鏈表的n個指針。</p><p>　?。?）折半查找復(fù)雜性分析</p><p>　　

38、問題規(guī)模為n，其算法復(fù)雜度為o（log（n））</p><p>　　5.2測試數(shù)據(jù)及結(jié)果</p><p><b>　　略</b></p><p><b>　　總結(jié)</b></p><p>　　本設(shè)計的重點和難點在于對航班數(shù)據(jù)的排序和查找，以鏈?zhǔn)交鶖?shù)排序為主，用到了二分查找和順序查找、建立靜態(tài)鏈表等知