信息科學和工程學院課程設計報告課題： 航空客運訂票系統 目錄TOC\o"1-5"\h\z\o"CurrentDocument"1?課程設計內容 31.1、 課程設計目的 31.2、 課程設計題目 31.3、 課程設計內容 3\o"CurrentDocument"1.4、 實現提示 32?需求分析 43?概要設計 43.1、 系統結構圖 53.2、 算法設計 53.3、 存儲結構設計 54?詳細設計 64.1、 數據類型定義 74.2、 函數定義 84.3、函數流程圖 84.4、程序的設計思想 125?調試分析 125.1、程序測試 12、時間復雜度分析………………13、算法的改進設想………………13問題分析及課程設計的心得體會………14使用手冊 …… 158?源程序 ……??????159參考資料……………………22一、 課程設計內容1?1課程設計目的1．數據結構課程設計是綜合運用數據結構課程中學到的幾種典型數據結構，以及程序設計語言（C語言），自行實現一個較為完整的使用系統。2．通過課程設計，自己通過系統分析、系統設計、編程調試，寫實驗報告等環節，進一步掌握使用系統設計的方法和步驟，靈活運用并深刻理解典型數據結構在軟件開發中的使用。3．學會將知識使用于實際的方法，提高分析和解決問題的能力，增加綜合能力。（1）熟練掌握鏈表存儲結構及其建立過程和常用操作；（2）熟練掌握隊列的建立過程和常用操作；（3）學會自己調試程序的方法并掌握一定的技巧。1?2課程設計題目1、 每條航線所涉及的信息有：終點站名、航班號、飛機號、飛機周日（星期幾）、乘員定額、余票量、訂定票的客戶名單（包括姓名、訂票量、艙位等級1，2或3）以及等候替補的客戶名單（包括姓名和所需數量）。2、 系統能實現的操作和功能如下：1） 查詢航線：根據客戶提出的終點站名輸出如下信息：航班號、飛機號、星期幾飛行和余票額；2） 承辦訂票業務：根據客戶提出的要求（航班號、訂票數額）查詢該航班票額情況，若有余票，則為客戶辦理訂票手續，輸出座位號；若已滿員或余票量少余訂票額，則需重新詢問客戶要求。若需要，可登記排隊候補；3） 承辦退票業務：根據客戶提出的情況（日期、航班號），為客戶辦理退票手續，然后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續，否則依次詢問其它排隊候補的客戶。1.3課程設計內容航空客運訂票的業務活動包括：查詢航線、客票預訂和辦理退票等。設計個航空客運訂票系統，以使上述業務可以借助計算機來完成。1.4實現提示兩個客戶名單分別由線性表和隊列實現。為查找方便，已訂票客戶的線性表應按客戶姓名有序，并且，為了插入和刪除方便，以鏈表作為存儲結構。由于預約人數無法預計，隊列也用鏈表作為存儲結構。整個系統需匯總各條航線的情況登錄在一張線性表上，由于航線不變，可采用順序存儲結構，并按航班有序或終點站名有序。每條航線是這張表上的一個記錄，包含上述8個域，其中乘員名單域為指向成員名單鏈表的頭指針，等候替補的客戶名單域為分別指向對頭和隊尾的指針二、 需求分析本訂票系統能夠實現全部航線信息的瀏覽功能、訂票客戶信息的查詢功能、單條航線查詢功能、訂票功能和退票功能。具體分析如下：a） 全部航線信息的瀏覽功能瀏覽全部系統預設的航線信息，每條航線包含的信息有：終點站名、航班號、飛機號、飛行周日（星期幾飛行）、乘員定額和余票量。b） 訂票客戶信息的查詢功能根據輸入的航班號查詢該航線所有訂票客戶的信息，包括客戶姓名、訂票數額和艙位等級。c） 單條航線查詢功能根據客戶輸入的終點站名查看該航線上所涉及的信息。d）訂票功能根據客戶提出的要求（航班號、訂票數量）查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續，輸出座位號；若已滿員或余票額少于定票額，則詢問客戶是否愿意排隊等候，若愿意，系統則自動登記排隊候補。e）退票功能根據客戶提供的情況（航班、姓名），詢問退票張數，然后為客戶辦理退票手續。接著系統自動查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續，否則依次詢問其他排隊候補的客戶。

三、 概要設計系統結構圖（功能模塊圖）算法設計(每個模塊的算法設計說明):(1)瀏覽航線模塊：定義voiddisplay(structairline*info),用info指向結構體structairline中的每一個成員；調用list()函數輸出全部航線信息。瀏覽訂票客戶信息模塊：定義訂票客戶信息的結構體ord_ros，根據輸入航班號調用find()函數尋找客戶信息。(3)查詢航線模塊：順著單鏈表查找，如果和航班號(航線)一致，輸出相關信息，否則，查詢不成功。(4)訂票模塊：查找乘客要訂的航班號，判斷此航班是否有空位，有則輸入乘客有關信息，訂票成功，否則失敗。(5)退票模塊：輸入要退票的乘客姓名，查找乘客資料的鏈表中是否有這位乘客，有則刪去此節點，并在空位上加1，無則退票失敗。如果此時余票額大于等于候補客戶的訂票數量，那么候補客戶訂票成功。3.3存儲結構設計：航班的信息：為了便于查找，航班情況的存儲結構采用單鏈表，每個元素表示一個航班的情況，包括終點站名、航班號、飛機號、星期幾、乘員定額和余票量，共六個數據項：終點站名航班號飛機號星期幾乘員定額余票量單鏈表如下:C語言描述如下：structairline{charter_name[10];/*終點站名*/charair_num[10];/*航班號*/charplane_num[10];/*飛機號*/charday[7];/*飛行周日(星期幾)*/inttkt_amt;/*乘員定額*/inttkt_sur;/*余票量*/linklist*order;/*乘員名單域，指向乘員名單鏈表的頭指針*/linkqueuewait;/*等候替補的客戶名單域，分別指向排隊等候名單隊頭隊尾的指針*/}lineinfo;structairline*start;（2）訂票乘客的資料：為了便于插入和刪除，同樣采用單鏈表存儲結構，每個數據元素包括姓名、訂票量和艙位等級三個數據項：乘客姓名訂票量余票量C語言描述如下：typedefstructord_ros{charname[10];/*客戶姓名*/intord_amt;/*訂票量*/intgrade;/*艙位等級*/structord_ros*next;}linklist;四、詳細設計4.1數據類型定義（1） 已訂票客戶的結點：typedefstructord_ros{charname[10];/*客戶姓名*/intord_amt;/*訂票量*/intgrade;/*艙位等級*/structord_ros*next;}linklist;（2） 候補客戶的結點：typedefstructwat_ros{charname[10];/*姓名*/intreq_amt;/*訂票量*/structwat_ros*next;}qnode,*qptr;typedefstructpqueue/*定義單鏈隊列*/{qptrfront;/*等候替補客戶名單域的頭指針*/qptrrear;/*等候替補客戶名單域的尾指針*/}linkqueue;（3） 航班結點：structairline{charter_name[10];/*終點站名*/charair_num[10];/*航班號*/charplane_num[10];/*飛機號*/charday[7];/*飛行周日(星期幾)*/inttkt_amt;/*乘員定額*/inttkt_sur;/*余票量*/linklist*order;/*乘員名單域，指向乘員名單鏈表的頭指針*/linkqueuewait;/*等候替補的客戶名單域，分別指向排隊等候名單隊頭隊尾的指針*/}lineinfo;structairline*start;函數定義(1)航線輸出函數函數名：voidlist()操作結果：輸出全部航線信息(2)航線查詢函數函數名：voidsearch()操作結果：進行航班查詢候補結點隊列函數函數名：linkqueueappendqueue(linkqueueq,charname[],intamount)操作結果：增加候補客戶名單域入隊出隊判空客戶訂票函數函數名：voidorder()操作結果：進行客戶訂票操作客戶退票函數函數名：voidreturn_tkt()操作如果：進行客戶退票操作訂票客戶查詢函數函數名：voidprtlink()操作結果：進行訂票客戶信息查詢操作主菜單控制函數函數名：intmenu_select()操作結果：a)瀏覽航線信息瀏覽已訂票客戶信息查詢航線辦理訂票業務辦理退票業務退出系統4.3函數流程圖（1）瀏覽已訂票客戶信息

3）辦理訂票業務5）辦理退票業務4.4程序的設計思想訂票客戶由線性表實現，鏈表作為其存儲結構；為了插入和刪除方便，候補客戶由隊列實現，隊列也用鏈表做為存儲結構。增刪操作只需修改指針，這樣系統運行效率有了很大提高。五?調試分析5.1程序測試(1)主菜單 歡迎使用航空客運訂票系統 信票業業線晉票票統舫已㈱'乩系貫翥理理出瀏瀏查辦番息信票業業線晉票票統舫已㈱'乩系貫翥理理出瀏瀏查辦番息II..息客務務請選擇幷按回車鍵結束:踐點站名beijingshanghailondon航班號1飛磯號B8571S1O02踐點站名beijingshanghailondon航班號1飛磯號B8571S1O02L1O03請違擇并按回車鍵結豆汩飛行周日 乘員定額SUN 3MONFBI余票量3I戶:2票級

量羋

數—位=1的盤=1?!

5-1-SII.班ts票弓號航入座座的請選擇井按回車鍵結束冷，牛訂票成功?祝您旅誅愉快!瀏覽已訂票客戶信息

士―… 請選擇并按回車鍵結束止遠艷入砸班號注畧&姓茗訂票數額艙位等級牛 2 1查詢航班請選擇并按回車鍵結束汴霸鐺■點站名喘矚飛機號飛亍周日beijing 1 請選擇并按回車鍵結束汴霸鐺■點站名喘矚飛機號飛亍周日beijing 1 B8571SUN乘員定額3余票量1辦理退票業務請選攔井按回三鍵結束瀉:牛戶請選攔井按回三鍵結束瀉:牛戶客2

票:

退量

12數

:1名??票

號姓需

棗香

人IA訂人

饉番輸321!t-t-AE-!功號號號退亜B蚩陛功的的7)再次瀏覽航線信息終點站名beijingshanghailorndon航班號12終點站名beijingshanghailorndon航班號12請二飛機號B8571S1302L丄S03擇并按回玄鍵結束疽飛行周日 乘貝定額SUN 3MON 2FBI 1余票量Q115.2時間復雜度分析瀏覽遍歷整張航線線性表的時間復雜度：0(1)；線性表的插入和刪除操作的時間復雜度：O(n)；查詢為線性表的查找，時間復雜度：O(n)；訂票為線性表的查找，時間復雜度：O(n)；退票是查找兩張線性表，時間復雜度為：O(n*e)，其中n為航班總數，e為對應航班已訂票人數。5.3算法的改進設想在算法效率上，由于此課程設計所用的是線性表的建立、查找、插入、刪除、和隊列的建立、插入、刪除，所涉及的是查找和排序問題，所以在建立插入時按照客戶姓名進行有序，查找時采用分塊查找，因此對訂票客戶信息的存儲應采用指針數組存儲。在函數重組，把處理不同問題相同算法思想(如線性表的插入、刪除、查找等等)寫在一個函數中，其它函數要用到這種操作時只需調用這些函數，這樣會減少整個程序的代碼量，方便理解、閱讀和使用。六．問題分析及課程設計的心得體會總體體會：看著簡單，做著難，我自己眼高收低，心太急，不過敢想敢寫感嘗試，努力付出還真有蠻多收獲。(1)學和做：做了這次課程設計，我覺得課程設計這種形式真的是我們需要的，可以讓我們學到很多，包括書上的、書外的。理論永遠不等于實際。我在調試時出現了很多的問題，下面列舉幾個:程序中定義了一個字符串"new",但在C-Free中“new"不是以未定義的形式存在，所以把“new”改寫成“NEW”就可以了；C-Free中“getchar”表示讀取下一個字符的含義，而“getch”不表示，出現“getch”時系統會報錯；在編寫退票模塊的代碼時，設計先輸入退票數然后進行退票，調試時發現艙位等級的輸出出現了混亂，后來經仔細分析才知道，原來“grade=pl->grade;”放在了if()大循環的后面，而在f循環里pl已經釋放，所以把“grade=p1->grade;”放在第一個“free(p1);”之前就可以了。真正會了這些算法，理論和實際永遠差那么一點，不去做是體會不出來的。坐在電腦前才真正知道自己會不會，眼高手低是要不得的。(2)C和算法描述:在學數據結構的時候總是分不清算法和C語言的區別，總覺得算法就是程序了，通過這兩周的課程設計總算是把它們之間的關系搞透徹了。其實算法是解決問題的步驟；程序是算法的代碼實現；算法要依靠程序來完成功能；程序需要算法作為靈魂。兩者是相互聯系密不可分的。(3)小收獲:摸索著做完課程設計，增強了自己的自學能力，這應該是最有用的吧，語言會過時，學習的能力卻不會過時。構造結構體;定義清晰明確的各種變量；主函數、子函數的聲明及定義。另外:對函數調用，參數傳遞很有體會。(4)遇到的問題和感受:這次課程設計面臨的大問題就是——選擇的余地太大，頭腦不好受。連續幾天的思考，我都不能決定攻克哪個，好幾個都是考慮了一部分又放棄了，以至前功盡棄。這使我認識到認定干一件事就必須將它干到底，以使自己的思想連續。我也開始考慮當事情有重疊時，如何去應對，雖然最后的抉擇不一定是對的。我也在這段時間內好好地看了一遍書，對書中的算法思想有一個更深的了解，雖然在使用中顯得不是很自如，可我通過這次課設體驗到可視化編程的樂趣。這也給我以后編程莫大的激勵，因為我認為所謂算法通過老師的傳授每個人都會一點點，而課外的東西則是通過自己的學習獲得的。寫程序是一種樂趣，特別是當我看到程序運行成功時，我會感到無比的喜悅。而數據結構是任何程序的基礎，沒有數據結構的支持，就沒有程序的存在，至少說不會存在有價值的程序。有了數據結構的知識，再加上程序設計技術，這對以后的深入學習應該會有很大的幫助七?用戶使用手冊說明書本程序可以運行在c-free最新5.0版本完美運行1瀏覽航線信息按數字1即可查詢2瀏覽已訂票客戶的信息要輸入你訂票客戶的航班號根據提出的航班號課查詢是否有訂票客戶的信息。如果沒有則會輸出“該航線沒有客戶信息”如果有訂票客戶。則會顯示改客戶訂票信息3查詢航線首先輸入終點站名，如果沒有該終點站，則會輸出“對不起。該航線未找到！”如果有改終點站，則會輸出該航線的信息4辦理訂票業務首先輸入航班號，如果沒有該航班號。則會輸出“對不起，該航線未找到！"如果有該航班，則按照輸入順序。輸入訂票數量，訂票客戶，艙位等級。系統會給出你的座位號如果你訂票數量大于總數，則會輸出“對不起。您輸入的票的數量已經超過成員定額！”如果你訂票的數量大于剩余票數，那么系統會提示你是否需要排隊。如果你需要，則輸入排隊的客戶信息5辦理退票業務先輸入航班號，如果你輸入的航班號不存在，那么系統會輸出“對不起。該航線未找到！”如果你輸入的航班號存在，那么系統會讓你輸入你退票客戶的名字。如果有該客戶，那么退票成功。如果沒有該客戶。那么系統會輸出“對不起。你沒有定過票”6查詢剩余票數并排序系統會按航線剩余票數的多少進行排序0退出系統系統退出八．源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE3/*定義航線量的最大值*/typedefstructwat_ros{charname[10];/*姓名*/intreq_amt;/*訂票量*/structwat_ros*next;}qnode,*qptr;typedefstructpqueue/*定義單鏈隊列*/{qptrfront;/*等候替補客戶名單域的頭指針*/qptrrear;/*等候替補客戶名單域的尾指針*/}linkqueue;typedefstructord_ros{charname[10];/*客戶姓名*/intord_amt;/*訂票量*/intgrade;/*艙位等級*/structord_ros*next;}linklist;structairline{charter_name[10];/*終點站名*/charair_num[10];/*航班號*/charplane_num[10];/*飛機號*/charday[7];/*飛行周日(星期幾)*/inttkt_amt;/*乘員定額*/inttkt_sur;/*余票量*/linklist*order;/*乘員名單域，指向乘員名單鏈表的頭指針*/linkqueuewait;/*等候替補的客戶名單域，分別指向排隊等候名單隊頭隊尾的指針*/}lineinfo;structairline*start;voiddisplay(structairline*info)/*打印每條航線的基本信息*/{printf("%8s\t%3s\t%s\t%4s\t\t%3d\t%10d\n",info->ter_name,info->air_num,info->plane_num,info->day,info->tkt_amt,info->tkt_sur);}voidlist()/*打印全部航線信息*/{structairline*info;inti=0;info=start;printf("終點站名\t航班號\t飛機號\t飛行周日\t乘員定額\t余票量\n");while(i<MAXSIZE){display(info);info++;i++;}printf("\n\n");voidsearch()/*根據客戶提出的終點站名輸出航線信息*/{structairline*info,*find();charname[10];inti=0;info=start;printf(“請輸入終點站名:")；scanf("%s",name);while(i<MAXSIZE){if(!strcmp(name,info->ter_name))break；info++；i++；}if(i>=MAXSIZE)printf("對不起，該航線未找到!\n");else{printf("終點站名\t航班號\t飛機號\t飛行周日\t乘員定額\t余票量\n");display(info);}}structairline*find()/*根據系統提出的航班號查詢并以指針形式返回*/{structairline*info;charnumber[10];inti=0;info=start;printf("請輸入航班號:")；scanf("%s",number);while(i<MAXSIZE){if(!strcmp(number,info->air_num))returninfo;info++;i++;}printf("對不起，該航線末找到!\n");returnNULL;}voidprtlink()/*打印訂票乘員名單域的客戶名單信息*/{linklist*p;structairline*info;info=find();p=info->order;if(p!=NULL){printf(“客戶姓名訂票數額艙位等級\n");while(p){printf("%s\t\t%d\t%d\n",p->name,p->ord_amt,p->grade);p=p->next;}}elseprintf("該航線沒有客戶信息!!\n");}linklist*insertlink(linklist*head,intamount,charname[],intgrade)/*增加訂票乘員名單域的客戶信息*/{linklist*p1,*NEW;p1=head;NEW=(linklist*)malloc(sizeof(linklist));if(!NEW){printf("\nOutofmemory!!\n");returnNULL;}strcpy(NEW->name,name);NEW->ord_amt=amount;NEW->grade=grade;NEW->next=NULL;if(head==NULL)/*若原無訂票客戶信息*/{head=NEW;NEW->next=NULL;}elsehead=NEW;NEW->next=p1;returnhead;}linkqueueappendqueue(linkqueueq,charname[],intamount)/*增加排隊等候的客戶名單域*/{qptrNEW;NEW=(qptr)malloc(sizeof(qnode));strcpy(NEW->name,name);NEW->req_amt=amount;NEW->next=NULL;if(q.front==NULL)/*若原排隊等候客戶名單域為空*/q.front=NEW;elseq.rear->next=NEW;q.rear=NEW;returnq;voidorder()/*辦理訂票業務*/{structairline*info;intamount,grade;charname[10];info=start;if(!(info=find()))return;/*根據客戶提供的航班號進行查詢，如為空，退出該模塊*/printf("請輸入您訂票的數量:")；scanf("%d",&amount);if(amount>info->tkt_amt)/*若客戶訂票額超過乘員定票總額，退出*/{ printf("\n對不起，您輸入訂票的數量已經超過乘員定額!")；return;}if(amountv=info->tkt_sur)/*若客戶訂票額末超過余票量，訂票成功并等記信息*/{inti；printf("請輸入您的姓名(訂票客戶)：")；scanf("%s",name)；printf("請輸入％s票的艙位等級:",name);scanf("%d",&grade)；info->order=insertlink(info->order,amount,name,grade);/*在訂票乘員名單域中添加客戶信息*/for(i=0;ivamount;i++)/*依次輸出該訂票客戶的座位號*/printf("%s的座位號是:％d\n",name,info->tkt_amt-info->tkt_sur+i+l);info->tkt_sur-=amount;/*該航線的余票量應減掉該客戶的訂票量*/printf("\n訂票成功，祝您旅途愉快！\n");}else /*若滿員或余票額少于訂票額，詢問客戶是否需要進行排隊等候*/{charr;printf("\n已經沒有更多的票，您需要排隊等候嗎?(需要請按'Y',若不需要請按'N')");fflush(stdin);scanf("%c",&r);if(r=='Y'||r=='y'){printf("\n請輸入您的姓名(排隊訂票客戶)：")；scanf("%s",name);info->wait=appendqueue(info->wait,name,amount);/*在排隊等候乘員名單域中添加客戶信息*/printf("\n注冊成功!\n");}elseprintf("\n歡迎您下次再次訂購！\n");}}voidreturn_tkt()/*退票模塊*/{structairline*info;qnode*t,*back,*f,*r;intgrade,num;linklist*p1,*p2,*head;charcusname[10];if(!(info=find()))return;/*調用查詢函數，根據客戶提供的航線進行搜索*/head=info->order;p1=head;printf("請輸入你的姓名(退票客戶)：")；scanf("%s",cusname);while(p1!=NULL){/*根據客戶提供的姓名到訂票客戶名單域進行查詢*/if(!strcmp(cusname,p1->name))break;p2=p1;p1=p1->next;}if(pl==NULL){printf("對不起，你沒有訂過票!\n");return;}/*若未找到，退出本模塊*/else{/*若信息查詢成功，刪除訂票客戶名單域中的信息*/printf("您的訂票量為：％d\n",p1->ord_amt);printf("請輸入您的退票數量：")；scanf("%d",&num);if(p1==head){grade=p1->grade;if(p1->ord_amt==num){head=p1->next;free(p1);}else{if(p1->ord_amt>num)head->ord_amt-=num;}}else{if(p1->ord_amt==num){p2->next=p1->next;free(p1);}else{if(p1->ord_amt>num)p1->ord_amt-=num;}}info->tkt_sur+=num;printf("\n成功退票！\n");}info->order=head;/*重新將航線名單域指向訂票單鏈表的頭指針*/f=(info->wait).front;/*f指向排隊等候名單隊列的頭結點*/r=(info->wait).rear;/*r指向排隊等候名單隊列的尾結點*/t=f;/*t為當前滿點條件的排隊候補名單域*/while(t){if(info->tkt_sur>=info->wait.front->req_amt){/*若滿足條件者為頭結點*/inti;info->wait.front=t->next;printf("%s訂票成功！\n",t->name);for(i=0;ivt->req_amt;i++)/*輸出座位號*/printf("%s的座位號是:％d\n",t->name,(info->tkt_sur)-i);info->tkt_sur-=t->req_amt;info->order=insertlink(info->order,t->req_amt,t->name,grade);/*插入至U訂票客戶名單鏈表中*/free(t);b