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

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

2、gt;<p>　　1.1課程設(shè)計(jì)選題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 用戶特點(diǎn)5</p><p>　　2.4 假定和約束5</p><p>　　第三章概要設(shè)計(jì)5</p><p><b>　　3.1設(shè)計(jì)思想5</b></p><p&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、gt;<b>　　int next;</b></p><p><b>　　}slnode;</b></p><p>　　typedef struct//定義存儲(chǔ)信息的結(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è)計(jì)</b></p><p><b>　　4.1程序設(shè)計(jì)說明</b>

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

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

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

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

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

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

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

29、序列的左端第一個(gè)元素下標(biāo)，right表示查找序列的右端第一個(gè)元素下標(biāo)。mid等于（left+right）/2。函數(shù)使用while循環(huán)，循環(huán)條件是left<=right。在循環(huán)體內(nèi)，首先判斷待查找信息的航班號(hào)是否與以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)。這樣查找到最后，若找到，則會(huì)輸出

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

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>　　（9）查詢檢索菜單</b></p><p>　　void searchcon(sllist l)</p><p>　?。?0）錄入航班數(shù)據(jù)函數(shù)</p><p>　　void inputdat

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

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

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