數(shù)據(jù)結(jié)構(gòu)課程設計講課講稿

1、數(shù)據(jù)結(jié)構(gòu)課程設計精品文檔濱江學院數(shù)據(jù)結(jié)構(gòu)程序設計實習報告題目_飛機訂票系統(tǒng) _專業(yè)_計算機科學與技術(shù) _年級班級 _02 計科 2 班_學號_20122308049_學生姓名 _黎曉東 _學期2014-2015(1)任課教師 _李燕 _一、設計任務與要求1.1總體目標與任務要求收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔制作一個訂票系統(tǒng)，通過此系統(tǒng)可以實現(xiàn)如下功能：1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）。2 ）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛

2、機航班情況。3 ）訂票：可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設定）。4 ）退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。5 ）修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件。根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結(jié)構(gòu)，設計程序完成功能。1.2題目選擇與目的意義選擇這個題目的原因是，訂票系統(tǒng)在現(xiàn)實生活中應用很廣泛，通過這個系統(tǒng)可以使訂票、退票等變得簡便。與傳統(tǒng)的人工用紙、筆來記錄辦理訂票、退票等相比，使用這個系統(tǒng)也會增加工作效率。這個題目做出來的系統(tǒng)還是比較實用的，所以我選擇了訂

3、票系統(tǒng)這個題目。完成此系統(tǒng)，需要綜合運用數(shù)據(jù)結(jié)構(gòu)課程中學到的幾種典型數(shù)據(jù)結(jié)構(gòu)，以及程序設計語言（ C語言），自行實現(xiàn)一個較為完整的應用系統(tǒng)的設計與開發(fā)。通過課程設計，自己通過系統(tǒng)分析、系統(tǒng)設計、編程調(diào)試，寫實驗報告等環(huán)節(jié)，進一步掌握應用系統(tǒng)設計的方法和步驟，靈活運用并深刻理解典型數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的應用。學會將知識應用于實際的方法，提高分析和解決問題的能力，增加綜合能力。1.3所選題目的主要工作收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔這個題目的主要工作是使訂票系統(tǒng)可以錄入航班情況，查詢某個航線的情況、辦理訂票、辦理退票、修改航班信息、查詢訂票信息等。二、需求分析2.1用戶需求分析用戶使用

4、此程序所要完成的工作主要為：查詢所有航線信息、查看已訂票客戶信息、查詢航線、辦理訂票業(yè)務、辦理退票業(yè)務。通過此系統(tǒng)可以方便的進行上述工作。每條航線所涉及的信息有：終點站名、航班號、飛行時間、票價、乘員定額、余票量。已訂票的客戶名單信息包括姓名、訂票量、艙位等級（1， 2 或 3）。等候替補的客戶名單信息包括姓名、所需票量。查詢航線功能可以根據(jù)旅客提出的終點站名輸出航班號、飛行時票價、乘員定額、余票量。訂票業(yè)務功能根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少于定票額，則需重新詢問客戶要求。若需要，可登記排隊候補購票。退

5、票業(yè)務功能根據(jù)客戶提供的情況（航班號、姓名）為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊候補，首收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊候補的客戶。2.2功能需求分析功能需求分析模塊圖如圖功能模塊圖：圖功能模塊圖2.3系統(tǒng)需求分析開發(fā)環(huán)境： PC機Windows XP 系統(tǒng)使用軟件：編寫實驗報告：Microsoft Office Word畫圖：億圖制 作程 序： Microsoft Visual C+6.0三、概要設計3.1各模塊的算法設計說明1瀏覽航線信息功能，調(diào)用display函數(shù)進行輸出。流程圖

6、如圖瀏覽航線信息流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖瀏覽航線信息流程圖：其中 display 函數(shù)的流程圖如圖函數(shù)流程圖：圖函數(shù)流程圖2瀏覽已訂票客戶信息功能，按順序輸出客戶信息鏈表中的信息。流程圖如圖瀏覽已訂票客戶信息功能流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖瀏覽已訂票客戶信息功能流程圖3查詢航線功能，根據(jù)客戶提出的終點站名輸出航線信息。流程圖如圖查詢航線流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖查詢航線流程圖4辦理訂票業(yè)務功能，根據(jù)客戶提出的航線信息等進行訂票。流程圖如圖辦理訂票業(yè)務功能流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖辦理

7、訂票業(yè)務功能流程圖5辦理退票業(yè)務功能，根據(jù)客戶提出的航線信息等進行退票。流程圖如圖辦理退票業(yè)務功能流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖辦理退票業(yè)務功能流程圖6主函數(shù)流程圖如圖主函數(shù)流程圖：收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖主函數(shù)流程圖3.2存儲結(jié)構(gòu)設計說明typedef struct wat_ros/*單鏈隊列存儲等候替補的客戶信息 */char name10;/*姓名 */int req_amt;/*訂票量 */收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔struct wat_ros *next;qnode,*qptr;typedef struct pqueue

8、/*等候替補的客戶名單*/qptr front;/*等候替補客戶名單域的隊頭指針 */qptr rear;/*等候替補客戶名單域的隊尾指針 */linkqueue;上述單鏈隊列用來存儲排隊等候的客戶名單，這樣可以通過隊先進先出的特點來進行操作。先排隊的客戶可以先訂票成功。typedef struct ord_ros/*乘員名單 */char name10;/*客戶姓名 */int ord_amt;/*訂票量 */int grade;/*艙位等級 */struct ord_ros *next;linklist;上述單鏈表用來存儲乘員的信息，包括姓名、訂票量、艙位等級。struct airline

9、/*航線信息 */char ter_name10;/*抵達城市 */char air_num10;/*航班號 */char time10;/*飛機時間 */char pri7;/*票價 */int tkt_amt;/*乘員定額 */int tkt_sur;/*余票量 */linklist *order;/*乘員名單域，指向乘員名單鏈表的頭指針*/linkqueue wait;/*等候替補的客戶名單域，分別指向排隊等候名單隊頭隊尾的指針*/lineinfo;收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔這個結(jié)構(gòu)體存儲了航線信息，包括抵達城市、航班號、飛行時間、票價、乘員定額、余票量等。#defin

10、e MAXSIZE 5/*定義航線數(shù)量，可修改*/struct airline airMAXSIZE=/*初始化航線信息*/"beijing","1","1200","860",30,30,"shanghai","2","1000","770",20,20,"london","3","1330","960",10,10,"harbin",

11、"4","1700","760",50,50,"dalian","5","1400","550",40,40;通過修改全局變量MAXSIZE的數(shù)值即可更改航線數(shù)。在struct airline airMAXSIZE中可以修改、增加、刪除航線信息。航線信息內(nèi)容依次為抵達城市、航班號、飛行時間、票價、乘員定額、余票量（飛行時間1200 即 12：00）。四、詳細設計1. 查看航線信息編寫 void list()函數(shù)來查看全部航線信息。其中調(diào)用了 void di

12、splay(struct airline *info)函數(shù)，該函數(shù)的功能是打印每條航線的基本信息。這樣即可按順序打印出struct airline鏈表中存儲的全部航線信息。2. 查看已訂票客戶信息編寫 void prtlink()函數(shù)來查看已訂票客戶信息。這個函數(shù)中需要輸入要查詢的航線，通過 find() 函數(shù)來尋找這個航線然后輸出該航線乘員域的乘員信息。3. 查詢航線編寫 void search() 函數(shù)來實現(xiàn)查詢航線的功能。用戶輸入抵達城市名，該函數(shù)會在航線信息鏈表中進行查詢。如果有該城市，則會輸出此航線的信息。收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔4. . 辦理訂票業(yè)務編寫 voi

13、d order() 函數(shù)來實現(xiàn)訂票功能。首先提示用戶輸入航班號，然后調(diào)用 find() 函數(shù)來查找此航班，如果該航班存在，則會提示用戶輸入信息并調(diào)用linklist*insertlink(linklist *head,int amount,charname,int grade) 在訂票乘員名單域中添加客戶信息。如果余票不足，則會提示用戶進行排隊，如果排隊，則會調(diào)用提示用戶輸入信息并調(diào)用 linkqueueappendqueue(linkqueue q,char name,int amount)在排隊等候乘員名單域中添加客戶信息。5. 辦理退票業(yè)務編寫 void return_tkt() 函數(shù)來

14、實現(xiàn)退票功能。首先提示用戶輸入航班號，然后調(diào)用 find() 函數(shù)來查找此航班，如果該航班存在，則會提示用戶輸入信息，信息正確則會提示退票成功。此時將乘員信息中的該乘員信息刪除，然后檢查替補乘員鏈表中的信息，如果其訂票量可以得到滿足，則會將其插入到訂票客戶名單鏈表中，提示他訂票成功。6. 退出系統(tǒng)主函數(shù)中無限循環(huán)輸出菜單 for(;) ，用戶在菜單頁面下輸入 6 回車即 exit(0)，即可退出系統(tǒng)。五編碼調(diào)試運行程序主界面如圖1收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品文檔圖 1從文件中導入航班的信息 : 輸入的數(shù)據(jù)能基本能正確導入結(jié)構(gòu)體中，并在屏幕中顯示出來，但在文件中再加入一行航班信息時屏

15、幕上不會顯示，但在查詢時能輸出該航線的信息，表明文件正確導入結(jié)構(gòu)體中，但沒有輸出到屏幕上，將 for(j = 0;j<i-1;j+) 中的 i-1 改成 i ，并且文件中輸入數(shù)據(jù)時不要輸入多余的空格就可以正確顯示出來；如圖2圖 2查詢終點站為武漢的航班信息如圖3圖 3查詢終點站為廣州的航班信息如圖4圖 4訂票模塊：訂票時各航線數(shù)據(jù)除第一行外都能夠正確顯示，并提示訂票。經(jīng)過調(diào)試發(fā)現(xiàn)是從文件導入數(shù)據(jù)時第一行數(shù)據(jù)沒有正確初始化；改進之后就可以全部顯示； 此中第一條航班信息北京即為邊界數(shù)據(jù)。選擇訂票有航線：北京，姓名：王，訂票數(shù)： 7，顯示訂票成功，如圖 5收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精

16、品文檔圖 5在此基礎(chǔ)上選擇訂票，姓名：張；訂票數(shù)： 4，顯示余票不足，選擇預約如圖 6圖 6退票模塊：進入退票功能時，輸入航班后提示輸入訂票客戶姓名但不管輸入任何訂票客戶的信息都提示沒有該客戶的信息，則說明退票函數(shù)的功能沒有正確執(zhí)行。錯誤的原因：刪除訂票客戶節(jié)點的函數(shù) lianbiaoDelete70219 的參數(shù)沒有傳遞對，剛開始傳遞的是該航線單鏈表的頭指針，根據(jù)函數(shù)功能應該傳遞的是這項刪除節(jié)點的前一個節(jié)點的指針，改正之后能夠正確執(zhí)行函數(shù)功能；在以上客戶訂票基礎(chǔ)上執(zhí)行退票，航線：北京，姓名：王。退票成功并且是首位預約客戶訂票成功，如圖7圖 7六設計體會收集于網(wǎng)絡，如有侵權(quán)請聯(lián)系管理員刪除精品

17、文檔1. 由于是首次進行稍微復雜的程序設計，所以在需求分析階段需花費一定的時間以便深刻的了解該階段到底要實現(xiàn)什么功能，才能為后幾個階段做好準備；比如需求分析時寫入了較多的專業(yè)術(shù)語既是一種錯誤的做法，此階段需要的是可供非專業(yè)人員讀懂的設計要求，所以過多的專業(yè)術(shù)語將導致需求分析失去了其作用；2. 概要設計時及要求大腦中有一個大概的輪廓知道如何設計各種數(shù)據(jù)類型并進行存儲以及個數(shù)據(jù)類型之間的關(guān)系，需要知道主功能模塊與個數(shù)據(jù)類型基本操作之間的調(diào)用關(guān)系；3. 詳細設計時實現(xiàn)實現(xiàn)個函數(shù)功能做主要的階段，由于以往不良的編程習慣導致剛開始設計程序時是直接上手敲代碼，致使函數(shù)功能的實現(xiàn)中出現(xiàn)了大量的錯誤，后來在張

18、有華老師的要求下重頭開始先用漢字將算法描述一遍，然后再有類 c 語言寫出算法，這樣不僅讓函數(shù)功能的實現(xiàn)更加清晰，而且使得程序在編譯時錯誤大大減少；4. 編碼調(diào)試階段由于函數(shù)中任然存在各種問題，如指針、引用的使用，函數(shù)參數(shù)的傳遞，實參、虛參之間的關(guān)系，在老師和同學的幫助下終于將問題一一擊破；5. 測試結(jié)果及所采用的測試相關(guān)數(shù)據(jù)已經(jīng)在編碼調(diào)試階段給出了一些分析，錄入航班信息的功能時間復雜度為 O(n) 、空間復雜度為 O(l) ，查詢功能的時間復雜度為 O(n) ，空間復雜度O(n) ，訂票功能的時間復雜度為 O(n), 時間復雜度 O(l), 退票功能的時間復雜度為 O(n*n) ；6. 算法改進，此程序中預約客戶使用隊列的存儲存在一個缺陷。即隊列是采用的尾進頭出的存儲結(jié)構(gòu)，也就是說大部分的預約客戶（隊頭元素除外）不能夠?qū)崿F(xiàn)取消預約的情況，顯然在實際情況中不大合情理。改進思路可以采用鏈表的形式存儲，但需要對鏈表進行一定的限制，如必須在鏈表尾部插入新的預約客戶信息。另一個需要改進的地方是航空客運訂票系統(tǒng)應該分