1、數據結構實驗報告航空訂票系統課程設計報告 姓名：常建明 學號：131842311 設計題目 ： 圖的遍歷 設計題目 ：航空訂票系統目 錄1 圖的遍歷 1 圖的遍歷過程演示的要求 2 設計思路 3 詳細設計 4 設計與調試分析 2 航空訂票系統 1 問題的要求 2 問題描述 3 設計思路 4 主要功能函數設計 5 編碼實現 6 運行與測試 圖的遍歷圖的遍歷過程演示的要求設計程序完成如下功能：對給定的圖結構和起點，產生深度優先遍歷和廣度優先遍歷序列，并給出求解過程的動態演示。 設計思路首先由于程序中要有對圖的數據信息的創建，定義一個全局變量Max，表示最多建立的結點數。設計實現主要功能的函數有：創

2、建圖的數據信息的函數CreateMGraph（）；深度優先遍歷遞歸函數DFSM（）；廣度優先遍歷遞歸BFSM；深度優先遍歷DFSTraverseM（）；廣度優先遍歷BFSTraverseM（）；然后在main()函數中使用一個switch()語句實現對各個子函數的調用。抽象數據類型隊列的定義如下：ADT Queue 數據對象：D=ai| ai ElemSet,i=1,2,3，n,n0數據關系：R1=<ai-1,ai>| ai-1,ai D,i=1,2,3,，n 約定其中a1端為隊列頭，an端為隊列尾?；静僮鳎篒nitQueue(&Q) 操作結果：構造一個空隊列Q。Dest

3、royQueue(&Q) 初始條件：隊列Q已存在。 操作結果：隊列Q被銷毀，不再存在。ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結果：將Q清為空隊列。QueueEmpty(Q) 初始條件：隊列Q已存在。 操作結果：若Q為空隊列，則返回TRUE，否則FALSE。QueueLength(Q) 初始條件：隊列Q已存在。操作結果：返回Q的元素個數，即隊列的長度。GetHead(Q,&e) 初始條件：Q為非空隊列。 操作結果：用e返回Q的對頭元素。EnQueue(&Q,e) 初始條件：隊列Q已存在。 操作結果：插入元素e為Q的新的隊尾元素。DeQueue

4、(&Q,&e) 初始條件：隊列Q已存在。 操作結果：刪除Q的對頭元素，并用e返回其值。QueueTraverse(Q,visit() 初始條件：Q已存在且非空。 操作結果：從對頭到對尾，依次對Q的每個數據元素調用函數visit()。一旦visit()失敗，則操作失敗。詳細設計 #include<stdio.h>/*頭文件*/#include<stdlib.h>#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct c

5、har vexsMax; int edgesMaxMax; int n,e;MGraph;/*以鄰接矩陣作為圖的存儲結構*/int visitedMax;/*將visitedMax定義為全局變量并分配最大空間*/ main() MGraph *G,a; char ch1; int i,j,ch2; G=&a;ch1='y'/*設置控制語句標志*/ while(ch1='y'|ch1='Y') /*菜單欄*/ printf("n");printf("tt+圖的遍歷過程演示+n"); printf(&q

6、uot;tt+ 選擇菜單 +n"); printf("tt+n"); printf("tt+ 創建圖的數據請按:1 +n"); printf("tt+ 深度優先搜索請按:2 +n"); printf("tt+ 廣度優先搜索請按:3 +n"); printf("tt+ 退出搜索請按:0 +n"); printf("tt+n"); printf("ntt請選擇菜單號（0-3）："); scanf("%d",&ch2); g

7、etchar(); switch(ch2) case 1: CreateMGraph(G);/*選1創建一個新的圖矩陣*/ break; case 2: DFSTraverseM(G);/*選2進入深度優先搜索*/ break; case 3: BFSTraverseM(G);/*選3進入廣度優先搜索*/ break; case 0:/*選0結束搜索，退出程序*/ ch1='n' break; default: system("cls"); printf("ntt輸入有誤！n"); break; if(ch2=1|ch2=2|ch2=3)

8、 printf("nntt ");/*控制格式*/ typedef struct int front; int rear; int count; int dataQueueSize;CirQueue;/*定義隊列的數據結構*/void InitQueue(CirQueue *Q) Q->front=Q->rear=0; Q->count=0; int QueueEmpty(CirQueue *Q) return Q->count=QueueSize;/*返回隊列的最大長度*/ int QueueFull(CirQueue *Q) return Q-&

9、gt;count=QueueSize;/*返回隊列的最大長度*/void EnQueue(CirQueue *Q,int x) if(QueueFull(Q)/*隊列滿則出錯*/ Error("Queue overflow"); else Q->count+;/*否則count+，將x進隊*/ Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp;/*定義整型的變量*/ if(QueueEmpty(Q)/*若為真則出錯*/ Error

10、("Queue underflow"); else/*為假則count-，將隊員出隊*/ temp=Q->dataQ->front;/*用temp返回其值*/ Q->count-; Q->front=(Q->front+1)%QueueSize; return temp;/*返回出隊元素值*/ void CreateMGraph(MGraph *G) int i,j,k;/*定義整型變量*/ char ch1,ch2;/*定義字符型變量*/ printf("n請輸入頂點數，邊數（格式：3，4）:"); scanf("

11、;%d,%d",&(G->n),&(G->e);/*輸入圖的頂點數和邊數*/ for(i=0;i<G->n;i+) getchar(); printf("n請輸入第%d個頂點序號",i+1); scanf("%c",&(G->vexsi);/*輸入頂點的序號*/ for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) G->edgesij=0;/*初始化矩陣*/ for(k=0;k<G->e;k+) getchar(); prin

12、tf("n請輸入第%d條邊的頂點序號（格式：i，j）:",k+1); scanf("%c,%c",&ch1,&ch2);/*輸入邊的頂點序號*/ for(i=0;ch1!=G->vexsi;i+); for(j=0;ch2!=G->vexsj;j+); G->edgesij=1;/*有邊則賦值為1*/ void DFSM(MGraph *G,int i) int j; printf("%c ",G->vexsi); visitedi=TRUE;/*標記visitedi*/ /*依次優先搜索訪問v

13、isitedi的每個鄰接點*/for(j=0;j<G->n;j+) /*若visitedi的一個有效鄰接點visitedj未被訪問過，則從visitedj出發進行遞歸調*/ if(G->edgesij=1&&!visitedj) DFSM(G,j);void DFSTraverseM(MGraph *G) int i; printf("n 深度優先遍歷序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*訪問標志數組初始化*/ for(i=0;i<G->n;i+) if(!visited

14、i)/*對尚未訪問的頂點調用DFSM*/ DFSM(G,i); void BFSM(MGraph *G,int k) int i,j; CirQueue Q;/*定義一個隊列Q，初始化隊列為空*/ InitQueue(&Q); printf("%c ",G->vexsk);/*訪問初始點，并將其標記已訪問過*/ visitedk=TRUE; EnQueue(&Q,k);/*將以訪問過的初始點序號k入隊*/ while(!QueueEmpty(&Q)/*隊列非空進行循環處理*/ i=DeQueue(&Q);/*將隊首元素出隊*/ for(

15、j=0;j<G->n;j+)/*依次搜索vexsk的每一個可能的鄰接點*/ if(G->edgesij=1 &&! visitedj) visitedj=TRUE;/*標記vexsj已訪問過*/ EnQueue(&Q,j);/*頂點序號j入隊*/ void BFSTraverseM(MGraph *G) int i; printf("n 廣度優先遍歷序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*訪問標志數組初始化*/ for(i=0;i<G->n;i+) if(!visi

16、tedi)/*對尚未訪問的頂點調用BFSM*/ BFSM(G,i); 7）各個模塊之間的調用關系如下：廣度優先遍歷圖修改圖的信息深度優先遍歷圖進入菜單選擇用戶登錄圖信息的錄入 退出程序設計與調試分析從上面的算法和調用關系可以看出，這個程序的基本樣子已經非常的清楚，但是真正的程序中還要考慮各種限制條件。在調試過程中，程序中出現了許多的錯誤，有錯誤的調用、一些變量沒有定義、等等。不斷的對程序進行調試以得到最好的結果，程序中特別要注意的是類的對象作為作為參數時要注意如何去調用它，使程序有一個令人滿意的結果，具體的調試是在上機過程中進行的，在編寫程序的過程中主要有如下錯誤：1、在編寫程序的過程出現了一

17、些函數名、變量的大小寫不統一的錯誤，導致程序在運行的過程中出現函數名、變量沒有被定義等問題；2、在編寫程序的過程中數組的大小寫沒有被確定；3、在編寫程序的過程中一些變量沒有被定義，導致程序出錯；4、數組visitedMax應定義為全局變量，若不是則會出錯；5、函數的返回類型要確定，是void還是其他類型要十分注意；6、在編程的過程中，函數里一些控制語句的嵌套使用，括號要引起注意，這次的課程設計就有一些括號漏了或者多打了，導致括號不配套；創建數據就是把最開始要輸入的數據輸入到系統里。界面如下：按照深度優先搜索來遍歷圖。界面如下：按照廣度優先搜索來遍歷圖。界面如下：重新創建另一個圖的數據。界面如下

18、：完成任務后，退出的界面如下： 航空訂票系統問題的要求 設計航班信息，訂票信息的存儲結構，設計程序完成如下功能：錄入：可以錄入航班情況(數據可以存儲在一個數據文件中，數據結構、具體數據自定)查詢：可以查詢某個航線的情況(如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉)；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：(訂票情況可以存在一個數據文件中，結構自己設定)可以訂票，如果該航班已經無票，可以提供相關可選擇航班；退票： 可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數據文件問

19、題描述航空訂票的業務活動一般包括查詢航線信息、客票預訂、辦理退票等。每條航線所涉及的信息由：終點站名、航班號、飛機號、成員數額、余票量、已訂票的客戶名單。設計思路主要有三個方面的內容，查詢航線信息、訂票和退票業務。程序的基本功能有：(1) 查詢航線。根據旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票數。(2) 承辦訂票業務。根據客戶提出的要求查詢該航班票額情況，若有余票，為客戶辦理訂票手續，輸出座位號。若無票，則須重新詢問客戶要求。若需要，可登記排隊等候。（3） 退票業務。根據客戶提供的情況，為客戶辦理退票手續，然后查詢該航班是否有人排隊等候，首先詢問排在

20、第一的客戶，若所退票額能瞞住他的要求，則為他辦理退票手續，否則依次詢問其他排隊候補的客戶。主要功能函數設計（1）總航線信息預覽：通過調用display()預覽已經建立的全部航線的相關信息（航班號、飛機號 、終點站 、飛行日期 、 定額 、余票數 、排隊等候人數），預覽完返回主菜單。（2）查詢單條航線信息：根據乘客提出的終點站名或航班號調用Search()函數來查詢并輸出此條航線的相關信息（航班號、飛機號 、終點站 、飛行日期 、 定額 、余票數 、已訂票乘客名單、排隊等候乘客名單）。 并且查詢完后詢問乘客是否訂票，是就調用訂票Book()函數來為乘客進行訂票，否就返回主菜單。（3）辦理訂票業務

21、：客戶先輸入的終點站名、訂票數、姓名信息再來調用訂票Book()函數，Book()函數根據客戶提供的終點站名查詢到該航線信息，若客戶訂票額末超過余票量，訂票成功并登記信息，在訂票乘員名單鏈表中添加乘客的信息； 如果暫時余票數不足是，詢問客戶是否要排隊等侯，如果是，則在排隊等候的隊列中增加該乘客的訂票信息。（4）辦理退票業務：調用tuipiao()查詢函數，根據客戶提供的航線進行搜索根據客戶提供的姓名到訂票客戶名單域進行查詢。退票成功后，重新將航線名單域指向訂票單鏈表的頭指針。根據隊列中從出的客戶信息判斷是否滿足要求，如果滿足，則將該客戶的信息插入到乘客信息鏈表中。（5）錄入航班信息：調用Cre

22、atPlane（）函數，根據輸入的航班的相關的信息（航班號、飛機號 、終點站 、飛行日期 、 定額 、余票數），將此航班加入到原來的航班組中。（6）退出系統編碼實現#include<stdio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXSIZE100typedef struct Cust/已訂票乘客信息char Name15;/乘客姓名 char number10;/乘客所乘飛機航班號 char end15;/乘客終點typedef struct waitN

23、ode/排隊等候客戶信息 char name15;/乘客姓名int ticket;/乘客的訂票數struct waitNode *next;waitNode,*waitlink;typedef structwaitlink front;waitlink rear;waitQueue;typedef struct Plane/航班信息char number10;/航班號int planenum;/飛機號char end15;/終點站char date10;/飛行日期int dinge;/成員定額 int tick;/剩余票數 int k;/排隊等候的人數Customer *first;/鏈接已訂

24、票客戶waitQueue Q;/鏈接候補客戶PlaneLink;int Search(PlaneLink *p,int N) int i=0,Q; cout<<"=n" cout<<" 1.按終點站名查詢n"cout<<" 2.按航班號查詢 n"cout<<"_n"cout<<">>>>>>n"cout<<" 請選擇查詢方式 (1/2)：" cin>>Q;i

25、f(Q=1)char end10;cout<<" 請您輸入要查詢的航班的終點站名: " /按站點名查詢航班信息 cin>>end; while(i<N) if(strcmp(pi.end,end)=0) /先查看是否存在到該站點的航班 cout<<"n*您所查詢的航班信息如下*n" cout<<"_n" cout<<" 航班號 飛機號 終點站 飛行日期 余票數n" cout<<" "<<pi.number&

26、lt;<setw(7)<<pi.planenum<<setw(12)<<pi.end<<setw(10)<<pi.date<<setw(10)<<pi.tick<<endl; cout<<"n=n" break; i+;else if(Q=2) char num10; cout<<" 請您輸入要查詢的航班的航班號: " /按站點名查詢航班信息 cin>>num; while(i<N) if(strcmp(pi.n

27、umber,num)=0) /查看是否存在該航班號的航班 cout<<"n*您所查詢的航班信息如下：*n" cout<<"_n" cout<<" 航班號 終點 飛行日期 余票數n" cout<<" "<<pi.number<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(12)<<pi.tick<<endl; cout<<&

28、quot;n=n" break; i+; display_s(p, i, N); /調用display_s()函數輸出該航班的已訂票乘客和排隊等候乘客的名單信息if(i<N) /如果存在該航班，詢問客戶是否要預定 該航班的 機票int j; cout<<" 是否需要預定 該航班的票(1/0):" cin>>j; if(j=1) char name10; int ticket; cout<<" 請輸入訂票數目、姓名：" cin>>ticket>>name; Book(p,pi.en

29、d,ticket, name, N); else cout<<" 很抱歉，沒有您查詢的航班信息!n" return 0;int Book(PlaneLink *p,char end,int ticket,char name,int N) int i; for(i=0;i<N;i+)if(strcmp(pi.end,end)=0) /先找出是否存在要訂票的航班 if(pi.tick>=ticket) /查看 余票數是否 >= 訂票客戶 訂票數pi.tick-=ticket;Customer *t=(Customer *)malloc(sizeof

30、(Customer);t->ticket=ticket;strcpy(t->Name,name);strcpy(t->number,pi.number); strcpy(t->end,pi.end);t->next=pi.first; pi.first=t; / 此使用的是頭插法將訂票乘客的信息放入到 鏈表中 cout<<" 您訂票成功!n"cout<<" 您的航班信息如下:n"cout<<"_n"cout<<" 航班號 飛機號 終點站 飛行日期

31、定額n"cout<<"_n"cout<<" "<<setw(9)<<pi.number<<setw(6)<<pi.planenum<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(10)<<pi.dinge<<endl;cout<<"=nn"break;else if(pi.dinge<ticket) /訂票數超出航

32、班的定額時，不能訂票，也不能無法排隊等候了 cout<<" 您預訂的票數超過了航班定額，無法為您訂票!n" break; else / 余票數不足時，詢問乘客是否排隊等候char z;cout<<" 該航班剩余票數為："<<pi.tick<<endl;cout<<" 很抱歉，剩余的票數不夠!n" cout<<" 您是否需要排隊等候 (Y(y)/N(n): " cin>>z; if(z='Y'|z='y'

33、;) Queue(p,end,ticket , name, N,i); /調用入隊列函數，將乘客信息插入排隊等候的人后面break;if(i>=N) cout<<" 很抱歉，沒有您所需要的航班!n" return 0;int display_s(PlaneLink *p,int i,int N) /輸出已定票及排隊乘客的名單信息if(pi.first!=NULL) /pi.first!=NULL說明已訂票鏈表不為空， 輸出 已訂票乘客的名單信息cout<<"*該航班的已訂票乘客名單如下：*n" cout<<&qu

34、ot;_n"cout<<" 姓名 訂票量n"Customer *t=pi.first;while(t) cout<<setw(10)<<t->Name<<" "<<setw(7)<<t->ticket<<endl; t=t->next;if(i<N&&pi.Q.front!=NULL) /pi.Q.front!=NULL，輸出正在排隊等候乘客的名單信息 cout<<"*該航班等候訂票的乘客名單如下:

35、*n"cout<<" 姓名 訂票量n"waitlink S=pi.Q.front; while(S!=NULL)cout<<setw(10)<<S->name<<" "<<setw(7)<<S->ticket<<endl;S=S->next; cout<<"=n" return 0;int Queue(PlaneLink *p,char end,int ticket,char name,int N ,int i)

36、 /入隊函數，將等候排隊的乘客放入原來的隊列中system("cls");system("color 2e");waitlink q=(waitlink)malloc(sizeof(waitNode); /將要的入隊的結點，存儲將要入隊乘客的信息strcpy(q->name,name);q->ticket=ticket;q->next=NULL; if(pi.Q.front=NULL) pi.Q.front=pi.Q.rear=q; pi.k+; /pi.k用來記錄排隊人數elsepi.Q.rear->next=q;pi.Q.re

37、ar=q; pi.k+; cout<<"已為您登記，請耐心等候！n"return 0;int tuipiao(PlaneLink *p,int N) int i; Customer *R,*S;char number10,Name15;cout<<">>>>>>n"cout<<" 請輸入您的航班號與姓名:"cin>>number>>Name;for(i=0;i<N;i+) if(strcmp(pi.number,number)=0&a

38、mp;&pi.first!=NULL)if(strcmp(pi.first->Name,Name)=0)pi.tick=pi.tick+pi.first->ticket;pi.first=pi.first->next;cout<<" 您已成功退票!nn"else R=pi.first; S=pi.first->next;while(S!=NULL)if(strcmp(S->Name,Name)=0)pi.tick=pi.tick+S->ticket;R->next=S->next;cout<<&

39、quot; 您已經成功退票!nn" break;R=R->next; S=S->next;if(S=NULL) cout<<" 很抱歉,在該航班上沒有找到您的姓名，請核實信息!nn"if(pi.Q.front!=NULL)waitlink Q=pi.Q.front , q; while(Q!=NULL)if(pi.tick>=Q->ticket)if(Q=pi.Q.front)cout<<" 正在為等候的乘客 "<<Q->name<<"辦理訂票!n"

40、;Book(p,pi.end,Q->ticket,Q->name,N);if(pi.Q.front=pi.Q.rear)pi.Q.front=pi.Q.rear=NULL;Q=Q->next;else pi.Q.front=pi.Q.front->next; Q=Q->next;elsecout<<" 正在為等候的乘客 "<<Q->name<<"辦理訂票!n"Book(p,pi.end,Q->ticket,Q->name,N);q->next=Q->next;

41、 Q=Q->next;else q=Q; Q=Q->next; break; if(strcmp(pi.number,number)=0&&pi.first=NULL)cout<<" 很抱歉，該航班目前沒有已訂票的乘客，無法為你退票，請核實信息!nn" break;if(i>=N) cout<<" 很抱歉，沒有該航班信息,無法為你退票，請核實信息!nn"return 0;void CreatPlane(PlaneLink *p,int n,int N) int i,j;for(i=N;i<N

42、+n;i+)pi.first=NULL; / 帶頭結點的單鏈表為空時的條件pi.Q.front=pi.Q.rear=NULL; /隊列為空時的條件cout<<">>>>>>n" cout<<" 請輸入航班號: " cin>>pi.number;cout<<" 輸入終點站名: " cin>>pi.end;for( j=0;j<N;j+)if(strcmp(pi.number,pj.number)=0) /查看該航班號是否已經存在cout

43、<<" 已經存在該航班號!n " break; if(strcmp(pi.end,pj.end)=0) / 查看是否存在到改站點的航班cout<<" 已經有到該站點的航班!n " break;if(j=N)cout<<" 飛機號、飛行日期、成員定額：n" cin>>pi.planenum>>pi.date>>pi.dinge; pi.tick=pi.dinge; pi.k=0;cout<<" 錄入完成!n"int display(PlaneLink *p,int N) /N為當前的航班數 cout<<&