課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、 課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 教師姓名 李桂玲 本科生姓名 張玉彬 本科生學(xué)號 20111004302 本科生專業(yè) 網(wǎng)絡(luò)工程二班 所在院系 計算機學(xué)院 類別: 本科生論文 日期: 2012年12月28日 獨立工作成果聲明 本人聲明所呈交的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告，是我個人在導(dǎo)師指導(dǎo)下進行的程序編制工作及取得的成果。盡我所知，除文中已經(jīng)標明的引用內(nèi)容，和已經(jīng)標明的他人工作外，本報告未包含任何抄襲自他人的工作成果。對本報告的工作做出貢獻的個人，均已在文中以明確方式標明。本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。 報告作者簽名： 日期： 年 月 日 航空管理系統(tǒng) TOC o 1-3 t h z u HY

2、PERLINK l _Toc127921.需求分析： PAGEREF _Toc12792 1 HYPERLINK l _Toc297292.設(shè)計 PAGEREF _Toc29729 2 HYPERLINK l _Toc892.1設(shè)計思想 PAGEREF _Toc89 2 HYPERLINK l _Toc78192.2設(shè)計表示 PAGEREF _Toc7819 5 HYPERLINK l _Toc27103.調(diào)試分析： PAGEREF _Toc2710 16 HYPERLINK l _Toc12794.用戶手冊 PAGEREF _Toc1279 17 HYPERLINK l _Toc253035

3、.測試數(shù)據(jù)及測試結(jié)果 PAGEREF _Toc25303 18 HYPERLINK l _Toc20605.1測試數(shù)據(jù) PAGEREF _Toc2060 18 HYPERLINK l _Toc108505.2測試結(jié)果 PAGEREF _Toc10850 18 HYPERLINK l _Toc253246. 參考文獻 PAGEREF _Toc25324 26 PAGE 21 航空訂票系統(tǒng)1.需求分析：試設(shè)計一個航空訂票系統(tǒng)，基本要求如下： 每條航班所涉及的信息有：航班號，航班機型，起飛機場，降落機場，日期（星期幾），起飛時間，降落時間，飛行時長，價格，乘員定額，余票量，訂定票的客戶名單(包括姓名

4、，訂票量，艙位等級（頭等艙、公務(wù)艙、經(jīng)濟倉）以及等候替補的客戶名單（包括姓名、所需數(shù)量）。采用鏈式存儲結(jié)構(gòu)。 系統(tǒng)能實現(xiàn)的操作和功能如下：航班信息管理。航空信息錄入；航班信息刪除；航班信息顯示 ； （2）查詢航線，按以下幾種方式查詢：按航班號查詢；按起點站查詢；按終點站查詢；按日期查詢；每種查詢方式中，查詢后輸出如下信息：航班號，航班機型，起飛機場，降落機場，日期（星期幾），起飛時間，降落時間，飛行時長，價格，余票量。 （3）承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求(航班號，訂票數(shù)額)查詢該航班票額情況，若有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票少于訂票額,則需重新詢問客戶要求。若需要

5、，可登記排隊候補。 （4）承辦退票業(yè)務(wù)：根據(jù)客戶提出的情況(日期，航班號)，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其它排隊候補的客戶。2.設(shè)計2.1設(shè)計思想數(shù)據(jù)結(jié)構(gòu)設(shè)計。存儲結(jié)構(gòu)設(shè)計：由題目所給定要求，該題需要用到鏈式存儲結(jié)構(gòu)來完成飛機信息的存取，而其后的waitingclient中需要的是按序訪問，所以最好是以隊列存儲等候者信息完成先入先出比較。存儲結(jié)構(gòu)如下：class flightprivate:flightNode *head;string key;class flightNodefriend

6、 class flight;public:flightNode();string flightnum; /航班號string flightmodel; /機型string start; /起點string end; /終點string date; /日期int price3; /價格int maxnum3; /三種等級艙座位數(shù)int remaining3; /余留的各等級艙座位數(shù)int firstclassMAXFIRSTCLASS;int bussinessclassMAXBUSSINESSCLASS;int economyMAXECONOMY;int departure2; int arr

7、ival2;void printout(); void printspace();void timecheck(); /飛行時長函數(shù)。 private:int flighttime2; /飛行時長flightNode *next; orderclient *head1; waitingclient *front; waitingclient *rear;class orderclientfriend class flight;string name;int level;int seat;orderclient *next;friend class flightNode;class waitin

8、gclientfriend class flight; string name; int level; waitingclient *next; friend class flightNode;邏輯結(jié)構(gòu)設(shè)計：該題所要求的是通過鏈式存儲結(jié)構(gòu)而存儲的，所以該題的邏輯結(jié)構(gòu)應(yīng)是線性結(jié)構(gòu)。算法設(shè)計。算法思想：該題是航空訂票系統(tǒng)，有航班信息，有航班中乘客的信息，其中的存入，刪除都可以通過鏈表中的指針從頭結(jié)點開始移動來遍歷，所以定義了三組結(jié)構(gòu)體，第一組的flight可視為整個航空系統(tǒng)，其中有flightNode的指針，第二組的flightNode是航班 信息，其中有orderclient和waitingcl

9、ient指針，第三組的waitingclient、orderclient分別代表等候列表與乘客列表。 在該系統(tǒng)中，可分為存入航班信息、訂票與退票三個模塊，之間由于是對內(nèi)存的改變所以所以沒有接口，存入即訪問flight遍歷flightNode結(jié)點，在最后插入新的結(jié)點，并將航班內(nèi)容存入，刪除時即刪除該結(jié)點，在航班信息輸入時，還調(diào)用了一個timecheck函數(shù)，用來計算飛行時長。訂票時，先通過訪問flightNode中的flightnum來確定所選航班，再通過訪問flightNode中對應(yīng)等級艙的余票，若大于零則進行插入操作，將內(nèi)容存orderclient中，若等于零則存入鏈式隊列waitingcl

10、ient中進行排隊操作，退票時，當(dāng)該flightNode結(jié)點存有同name的人，將其orderclient中的信息刪除，并訪問waitingclient查找最先相同等級要求的顧客并插入到該orderclient中。主函數(shù)流程圖如下：2.2設(shè)計表示函數(shù)的調(diào)用關(guān)系圖如下：詳細設(shè)計/航班信息的錄入函數(shù)。(備注：管理員密碼為123456，僅可在構(gòu)造函數(shù)中更改。）void flight:record() flightNode *t,*h; t=new flightNode; cout錄入航班信息：(航班號 航班機型 起點 終點 飛行日期 起飛時間 降落時間 座位及價格)t-flightnum; cint

11、-flightmodel; cint-start; cint-end; cint-date; cint-departure0; cint-departure1; cint-arrival0; cint-arrival1; cint-maxnum0t-price0t-maxnum1t-price1t-maxnum2t-price2; t-remaining0=t-maxnum0; t-remaining1=t-maxnum1; t-remaining2=t-maxnum2; for(int i=0;imaxnum0;i+)t-firstclassi=0; for( i=0;imaxnum1;i+

12、)t-bussinessclassi=0; for( i=0;imaxnum2;i+)t-economyi=0; t-timecheck(); h=head; while(h-next) h=h-next; t-next=h-next; h-next=t; cout信息錄入成功。endl=0) flighttime1=(arrival1-departure1); flighttime0=(arrival0-departure0); else flighttime1=(arrival1-departure1)+60; flighttime0=(arrival0-departure0)-1; if

13、(flighttime00)flighttime0=flighttime0+24;/航班訂票函數(shù)。void flight:reserve() string a; cout請輸入航班號a; flightNode *curr; curr=head-next; while(航班結(jié)點不為空) if(找到該航班) int i; cout請輸入要選艙位等級(頭等艙請輸入1，公務(wù)艙請輸入2， 經(jīng)濟艙請輸入3.i; if(i3|i1) cout無該等級艙位，請重新輸入：; goto loop; orderclient *t; t=new orderclient; cout請輸入姓名:t-name; if(該等

14、級艙余票不為0） t-level=i; cout購票成功。endl; cout航班號flightnum 姓名:name; coutlevel)/找到空位，并標志為有人，輸出座位號。 case 1:cout頭等艙; for(頭等艙找到空座); 座位號存入。 該座位號標記為1 該等級余票量減1. break; case 2:cout公務(wù)艙; for( 商務(wù)艙找到空座); 座位號存入。 該座位號標記為1 該等級余票量減1. break; case 3:couthead1; while(找到已訂票者鏈尾); a-next=t; t-next=NULL; coutseat號printspace(); /

15、航班輸出界面。 curr-printout(); /航班信息輸出。 return; else cout該艙位已滿，是否進入候補(Y/N)?q; if(q=Y|q=y) waitingclient *p; p=new waitingclient; p-name=t-name; p-level=i; if(等候隊列為空) 插入隊列第一個。 隊頭隊尾皆指向該等候者。 else 找到隊尾，并該等候者信息。 waitingclient *u; /判斷等候列表中同等級艙位的等候者。 u=curr-front; int m=0; while(u) if(u-level=i) m+; u=u-next; co

16、ut您前面等候者有m-1人endl; return; else return; else 飛機結(jié)點指針后移。 if(飛機結(jié)點為空)cout抱歉!沒有對應(yīng)的航班!endl;航空訂票信息流程圖如下：/航空退票系統(tǒng)。void flight:refund()cout請輸入航班號a;flightNode *curr;curr=head-next;while(curr)if(找到航班) cout請輸入姓名:b;orderclient *s;s=curr-head1;while(等候者存在)if(找到名字)coutq;if(q=Y|q=y)cout退票成功。next;waitingclient *m,*n;

17、m=curr-front;/從等候隊列中選顧客。 if(隊列非空) n=curr-front-next;if(curr-front-level=p-level) /隊列第一個 人就滿足購票條件。cout等候者front-name購 票成功。rear)/訪問waitingclient 可購票人。 if(n-level=p-level) /隊列末尾排除。cout等候者name購 票成功。level=p-level) /隊列末尾判斷。cout等候者rear-name 購票成功。level)/如果等待中無滿足要求者，將 座位騰出。case 1:頭等艙該座位號標記為0，頭等艙余票量 加1.break;

18、case 2:商務(wù)艙該座位號標記為0，商務(wù)余票量 加1.break;case 3:經(jīng)濟艙該座位號標記為0，經(jīng)濟艙余票量 加1.break;s-next=p-next;free(p); 信息輸入。輸出更改后航班信息。return; else 等候者指針后移。if(s-next=NULL)cout查無此人endl;return; else 飛機結(jié)點指針后移。if(curr=NULL)cout查無此航班endl;航空退票信息流程圖如下：3.調(diào)試分析：主要問題：該程序設(shè)計之中，第一個問題就是代碼太長，編寫量大，第二個就是指針的關(guān)系，有時由于代碼太長判斷條件太多而遺漏指針的后移或初始化等。解決方法：首先

19、，對這個系統(tǒng)先進行框架分析，留下大概的設(shè)計步驟，再在頭文件中首先聲明函數(shù)體，再一步步定義，而指針問題，則根據(jù)循環(huán)中的來判斷指針循環(huán)的范圍并小心檢查，多調(diào)試，而由于編程中復(fù)合語句會有后移的區(qū)分，所以檢查時在兩等行的大括號下分析處理。設(shè)計編碼回顧分析：這題是一次不小的考驗，由于使用C+的數(shù)據(jù)結(jié)構(gòu)，起初在定義各個類的指針交互上有些模糊，不過現(xiàn)在已經(jīng)學(xué)習(xí)到了很多，受益匪淺。在編碼過程中，我深刻的體會到一個程序的編寫需要一個清晰的思路，否則就是在原地打轉(zhuǎn)，此次在訂票和退票操作上耗時較大，需要判斷的條件較多，很容易出現(xiàn)指針未后移的問題，不過，在花費了許多時間之后得到的產(chǎn)物還是比較滿意的，有不小的成就感，并

20、且鞏固了一些相關(guān)的專業(yè)知識。算法的時間、空間復(fù)雜度分析：在該系統(tǒng)中，一共存在著4種函數(shù)類型，第一個是添加飛機信息，由于其中包含的第一個是查詢位子是否為空，和define的座位最大數(shù)有關(guān)，為常數(shù)，其次是飛機結(jié)點指針的后移，所以時間復(fù)雜度是O(n)，空間復(fù)雜度因僅與飛機結(jié)點大小有關(guān)所以是O(1),第二個是查詢，時間復(fù)雜僅與飛機結(jié)點數(shù)有關(guān)，所以為O（1），無空間利用，所以空間復(fù)雜度為O(1),第三個是訂票，主要時間耗在找飛機結(jié)點上與其中的訂單者指針的后移，所以時間復(fù)雜度為O（n*m），空間復(fù)雜度為O(m).第四個是退票，時間復(fù)雜度在飛機結(jié)點后移與訂單者后移，所以為O(n*m),空間復(fù)雜度為O（1）。

21、4.用戶手冊備注:(航空訂票.cpp，flight detail.cpp，flight detail.h三個文件應(yīng)放在一起，特別是頭文件flight detail.h不能丟，在VC上運行時應(yīng)先打開主函數(shù)文件航空訂票.cpp，然后再打開flight detail.cpp文件方能正確運行，然后進入系統(tǒng)進行功能測試及錯誤檢測)進入該飛機訂票系統(tǒng)后，主菜單上會出現(xiàn)兩種身份的選擇，鍵盤輸入1是以管理員身份進入，進入前需要擁有管理員密碼，輸入錯誤則返回主菜單，進入后，可以鍵入1來添加航班信息，輸入2來刪除航班信息，輸入3來查看現(xiàn)有航班信息，輸入4返回主菜單，輸入5則退出該系統(tǒng)，而在主菜單中輸入2則是以顧客身份登錄系統(tǒng)，擁有的主要功能有，輸入1返回上級主菜單，輸入2是按航班號查詢，輸入3是按航線起點查詢，輸入4是按航線終點查詢，輸入5是按照航線日期查詢，輸入6是訂票，7是退票，而8則是所有航班的信息顯示，9則是退出該航空訂票系統(tǒng)。在整個系統(tǒng)中，如果輸入的功能選項不存在，都會返回該層界面進行重新輸入。5.測試數(shù)據(jù)及測試結(jié)果5.1測試數(shù)據(jù)航班號 航班機型 起點 終點 日期