圖的遍歷過程演示概要

本文格式為Word版，下載可任意編輯——圖的遍歷過程演示概要

課程設(shè)計報告設(shè)計題目設(shè)計題目：圖的遍歷航空訂票系統(tǒng)

姓名：常建明學(xué)號：131842311

：

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

目錄

一．圖的遍歷

1圖的遍歷過程演示的要求2設(shè)計思路

3詳細設(shè)計

4設(shè)計與調(diào)試分析二．航空訂票系統(tǒng)

1問題的要求2問題描述3設(shè)計思路

4主要功能函數(shù)設(shè)計5編碼實現(xiàn)6運行與測試

II/25

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

圖的遍歷圖的遍歷過程演示的要求

設(shè)計程序完成如下功能：對給定的圖結(jié)構(gòu)和起點，產(chǎn)生深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列，并給出求解過程的動態(tài)演示。

設(shè)計思路

首先由于程序中要有對圖的數(shù)據(jù)信息的創(chuàng)立，定義一個全局變量Max，表示最多建立的結(jié)點數(shù)。設(shè)計實現(xiàn)主要功能的函數(shù)有：創(chuàng)立圖的數(shù)據(jù)信息的函數(shù)CreateMGraph（）；深度優(yōu)先遍歷遞歸函數(shù)DFSM（）；廣度優(yōu)先遍歷遞歸BFSM；深度優(yōu)先遍歷DFSTraverseM（）；廣度優(yōu)先遍歷BFSTraverseM（）；然后在main()函數(shù)中使用一個switch()語句實現(xiàn)對各個子函數(shù)的調(diào)用。

抽象數(shù)據(jù)類型隊列的定義如下：ADTQueue{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,3……，n,n≥0}數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=1,2,3,……，n}約定其中a1端為隊列頭，an端為隊列尾?；静僮鳎篒nitQueue(intedges[Max][Max];intn,e;

}MGraph;/*以鄰接矩陣作為圖的存儲結(jié)構(gòu)*/

intvisited[Max];/*將visited[Max]定義為全局變量并分派最大空間*/main()

{

MGraph*G,a;charch1;inti,j,ch2;G=

ch1='y';/*設(shè)置控制語句標志*/

while(ch1=='y'||ch1=='Y'){/*菜單欄*/printf(\

printf(\圖的遍歷過程演示++++++++++++++\\n\

printf(\選擇菜單+\\n\

IV/25

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

printf(\printf(\創(chuàng)立圖的數(shù)據(jù)請按:1+\\n\printf(\深度優(yōu)先探尋請按:2+\\n\printf(\廣度優(yōu)先探尋請按:3+\\n\printf(\退出探尋請按:0+\\n\printf(\printf(\請選擇菜單號（0-3）：\scanf(\getchar();switch(ch2){

case1:CreateMGraph(G);/*選1創(chuàng)立一個新的圖矩陣*/break;case2:DFSTraverseM(G);/*選2進入深度優(yōu)先探尋*/break;case3:BFSTraverseM(G);/*選3進入廣度優(yōu)先探尋*/break;

case0:/*選0終止探尋，退出程序*/ch1='n';break;default:system(\printf(\輸入有誤！\\n\break;}

if(ch2==1||ch2==2||ch2==3)

printf(\控制格式*/}}

typedefstruct{

intfront;

V/25

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

4、數(shù)組visited[Max]應(yīng)定義為全局變量，若不是則會出錯；5、函數(shù)的返回類型要確定，是void還是其他類型要十分注意；

6、在編程的過程中，函數(shù)里一些控制語句的嵌套使用，括號要引起注意，這次的課程設(shè)計就有一些括號漏了或者多打了，導(dǎo)致括號不配套；創(chuàng)立數(shù)據(jù)就是把最開始要輸入的數(shù)據(jù)輸入到系統(tǒng)里。界面如下：

依照深度優(yōu)先探尋來遍歷圖。界面如下：

依照廣度優(yōu)先探尋來遍歷圖。界面如下：

XI/25

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

重新創(chuàng)立另一個圖的數(shù)據(jù)。界面如下：

完成任務(wù)后，退出的界面如下：

航空訂票系統(tǒng)

問題的要求

設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成如下功能：

錄入：可以錄入航班狀況(數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定)

查詢：可以查詢某個航線的狀況(如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉)；可以輸入起飛抵達城市，查詢飛機航班狀況；

訂票：(訂票狀況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定)可以訂票，假使該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；

退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班狀況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件

問題描述航空訂票的業(yè)務(wù)活動一般包括查詢航線信息、客票預(yù)訂、辦理退票等。每條航線所涉及的信息由：

終點站名、航班號、飛機號、成員數(shù)額、余票量、已訂票的客戶名單。

XII/25

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

設(shè)計思路

主要有三個方面的內(nèi)容，查詢航線信息、訂票和退票業(yè)務(wù)。程序的基本功能有：

(1)查詢航線。根據(jù)旅客提出的終點站名輸出以下信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票數(shù)。

(2)承辦訂票業(yè)務(wù)。根據(jù)客戶提出的要求查詢該航班票額狀況，若有余票，為客戶辦理訂票手續(xù)，輸出座位號。若無票，則須重新詢問客戶要求。若需要，可登記排隊等候。

（3）退票業(yè)務(wù)。根據(jù)客戶提供的狀況，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊等候，首先詢問排在第一的客戶，若所退票額能瞞住他的要求，則為他辦理退票手續(xù)，否則依次詢問其他排隊候補的客戶。

主要功能函數(shù)設(shè)計

（1）總航線信息預(yù)覽：通過調(diào)用display()預(yù)覽已經(jīng)建立的全部航線的相關(guān)信息（航班號、飛機號、終點站、飛行日期、定額、余票數(shù)、排隊等候人數(shù)），預(yù)覽完返回主菜單。

（2）查詢單條航線信息：根據(jù)乘客提出的終點站名或航班號調(diào)用Search()函數(shù)來查詢并輸出此條航線的相關(guān)信息（航班號、飛機號、終點站、飛行日期、定額、余票數(shù)、已訂票乘客名單、排隊等候乘客名單）。并且查詢完后詢問乘客是否訂票，是就調(diào)用訂票Book()函數(shù)來為乘客進行訂票，否就返回主菜單。（3）辦理訂票業(yè)務(wù)：客戶先輸入的終點站名、訂票數(shù)、姓名信息再來調(diào)用訂票Book()函數(shù)，Book()函數(shù)根據(jù)客戶提供的終點站名查詢到該航線信息，若客戶訂票額末超過余票量，訂票成功并登記信息，在訂票乘員名單鏈表中添加乘客的信息；假使暫時余票數(shù)不足是，詢問客戶是否要排隊等侯，假使是，則在排隊等候的隊列中增加該乘客的訂票信息。

（4）辦理退票業(yè)務(wù)：調(diào)用tuipiao()查詢函數(shù)，根據(jù)客戶提供的航線進行探尋根據(jù)客戶提供的姓名到訂票客戶名單域進行查詢。退票成功后，重新將航線名單域指向訂票單鏈表的頭指針。根據(jù)隊列中從出的客戶信息判斷是否滿足要求，假使?jié)M足，則將該客戶的信息插入到乘客信息鏈表中。

（5）錄入航班信息：調(diào)用CreatPlane（）函數(shù)，根據(jù)輸入的航班的相關(guān)的信息（航班號、飛機號、終點站、飛行日期、定額、余票數(shù)），將此航班參與到原來的航班組中。

（6）退出系統(tǒng)

編碼實現(xiàn)

#include#include#include#include#defineMAXSIZE100

typedefstructCust{

XIII/25

//已訂票乘客信息

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

charName[15];//乘客姓名

charnumber[10];//乘客所乘飛機航班號charend[15];

//乘客終點

typedefstructwaitNode//排隊等候客戶信息{

charname[15];

intticket;

//乘客姓名

//乘客的訂票數(shù)

structwaitNode*next;

}waitNode,*waitlink;typedefstruct{

waitlinkfront;waitlinkrear;

}waitQueue;typedefstructPlane

{

charnumber[10];intplanenum;charend[15];chardate[10];intdinge;

//航班號

//航班信息

//飛機號//終點站//飛行日期

//成員定額

inttick;

intk;

//剩余票數(shù)

//排隊等候的人數(shù)//鏈接已訂票客戶

Customer*first;waitQueueQ;

//鏈接候補客戶

}PlaneLink;

intSearch(PlaneLink*p,intN){

inti=0,Q;

cout>Q;if(Q==1){

charend[10];

cout>end;

while(i>num;

while(i數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

}

cout>j;if(j==1){

charname[10];intticket;

cout>ticket>>name;

Book(p,p[i].end,ticket,name,N);

}}

else{cout=ticket)//查看余票數(shù)是否>=訂票客戶訂票數(shù)

{

p[i].tick-=ticket;

Customer*t=(Customer*)malloc(sizeof(Customer));t->ticket=ticket;strcpy(t->Name,name);

strcpy(t->number,p[i].number);strcpy(t->end,p[i].end);

t->next=p[i].first;p[i].first=t;//此使用的是頭插法將訂票乘客的信息放入到鏈表中

cout>z;

if(z=='Y'||z=='y'){

Queue(p,end,ticket,name,N,i);}//調(diào)用入隊列函數(shù)，將乘客信

息插入排隊等候的人后面

}

XVII/25

break;

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

}

}

}

if(i>=N){coutNamenext;}

while(S!=NULL)

{

coutnamenext;

}

cout>number>>Name;

XIX/25

system(\system(\

waitlinkq=(waitlink)malloc(sizeof(waitNode));//將要的入隊的結(jié)點，存儲將要入隊乘客的信息strcpy(q->name,name);q->ticket=ticket;q->next=NULL;if(p[i].Q.front==NULL){}else{}

coutnext=q;p[i].Q.rear=q;p[i].k++;p[i].Q.front=p[i].Q.rear=q;

p[i].k++;//p[i].k用來記錄排隊人數(shù)

數(shù)據(jù)結(jié)構(gòu)試驗報告————航空訂票系統(tǒng)

for(i=0;inext;coutnext;

}

if(p[i].Q.front!=NULL){

waitlinkQ=p[i].Q.front,q;while(Q!=NULL){

if(p[i].tick>=Q->ticket){

XX/25

while(S!=NULL){}

if(S==NULL)coutName,Name)==0){}

R=R->next;S=S->next;

p[i].tick=p[i].tick+S->ticket;R->next=