1、數(shù)據(jù)結(jié)構(gòu)課程設計實驗報告訂票系統(tǒng)1.需求分析任務：通過此系統(tǒng)可以實現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設定）可以訂票，如果該航班已經(jīng)無票，可以提供相關可選擇航班；退票： 可退票，退票后修改相關數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設計航班信息

2、，訂票信息的存儲結(jié)構(gòu)，設計程序完成功能；2：主要設計思路：1） 算法構(gòu)造流程圖：A：主菜單：主菜單0123456789輸入航班的信息列出航班的信息按航班號查詢航班信息按城市來查詢航班訂票程序退票系統(tǒng)修改飛機航班的信息保存文件讀取文件 、下載文件退出B：各分塊模板的構(gòu)造流程圖：0.輸入航班的信息航班號起飛城市降落城市出發(fā)時間降落時間剩下的座位價格折扣1.列出航班的信息繼續(xù) y退出 n2.按航班號查詢航班信息輸入所需要查詢的航班號顯示這個航班的的信息3.按城市來查詢航班輸入起飛城市輸入降落城市顯示這個航班的信息4.訂票程序輸入號碼輸入名字輸入ID需要定的票數(shù)航班號5.退票系統(tǒng)輸入航班號輸入你ID確

3、定退票 1否定 06.修改飛機航班的信息輸入要修改的航班號重新輸入新的航班信息7.保存文件顯示保存成功3:功能函數(shù)設計：（1）：訂票系統(tǒng)主菜單函數(shù) menu_select() 本函數(shù)主要構(gòu)造系統(tǒng)的主菜單，系統(tǒng)需要實現(xiàn)很多功能，并且各個功能需要各自的函數(shù)支持，所以通過主菜單可以輕松的進入各個函數(shù)下實現(xiàn)各自的功能，故主菜單顯得尤為重要。其實就是通過鍵盤輸入選擇項，然后通過scanf接受，在通過swtich判斷進入各個選擇項。（2）：工作人員管理函數(shù) enter()&change（） 系統(tǒng)需要各個航班的詳細信息，所以需要工作人員把信息輸入系統(tǒng)里，以供乘客查詢訂票。enter（）函數(shù)的構(gòu)造就是

4、為了解決這個問題。而有可能航班線路更改或由于天氣等原因飛機的起飛時間發(fā)生了更改，故工作人員需要及時更改信息，所以需要構(gòu)造change（）函數(shù)。（3）：列出航班信息的函數(shù) list（） 乘客需要查詢各個航班的信息，所以通過系統(tǒng)要能調(diào)出上面工作人員已經(jīng)錄入好的航班信息，所以構(gòu)造本函數(shù)來實現(xiàn)這個功能。（4）乘客具體查詢函數(shù) search（） 本函數(shù)分兩個分函數(shù)：search1（）和search2（），它們分別實現(xiàn)乘客的按航班查詢和按出發(fā)及抵達城市的兩種查詢方案。（5）票務管理函數(shù) book（）&quit（） 通過book（）函數(shù)可以實現(xiàn)乘客的訂票操作，通過quit（）可以實現(xiàn)乘客的退票操作。

5、（6）文件操作函數(shù) save（）&load（）3.源程序代碼：（WIN TC下運行）#include<dos.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 20#define Q 40 /*定義數(shù)據(jù)結(jié)構(gòu)*/*乘客信息*/typedef struct char number10;/*編號*/ char id20; /*證件號*/ char name10; /*姓名*/ int count; /*訂票數(shù)*/ char flightname10;/*乘坐航

6、班號*/GUEST; /*航班信息*/typedef structchar planenumber10;/*航班號*/ char Take_off_city20;/*起飛城市*/ char Arrived_in_city20;/*抵達城市*/ char takeoff_time20;/*起飛時間*/ char Landing_time20;/*降落時間*/ int shipping; /*艙位數(shù)*/ char price5; /*票價*/ char discount5; /*折扣*/ GUEST guest20; int sit;FLY;/*菜單函數(shù)，函數(shù)返回值為整數(shù)，代表所選的菜單項*/me

7、nu_select() int c; printf("按任意鍵返回主菜單n");/*提示壓任意鍵繼續(xù)*/ getch(); /*讀入任意字符*/ printf(" Welcome tonn"); printf(" Tickets Booking Systemnn"); printf(" *MENU*nn"); printf(" 0. 輸入航班信息n"); printf(" 1. 列出航班的信息n"); printf(" 2. 按航班號查詢航班信息n");

8、printf(" 3. 按城市來查詢航班n"); printf(" 4. 訂票程序n"); printf(" 5. 退票系統(tǒng)n"); printf(" 6. 修改飛機航班的信息n"); printf(" 7. 保存文件n"); printf(" 8. 讀取和下載文件n"); printf(" 9. 退出n"); printf(" *nn"); do printf("n 輸入你的選擇項(09):"); /*提示輸入選項

9、*/ scanf("%d",&c); /*輸入選擇項*/ while(c<0|c>9); /*選擇項不在9之間重輸*/ return c; /*返回選擇項，主程序根據(jù)該數(shù)調(diào)用相應的函數(shù)*/*輸入函數(shù)*/int enter(FLY t) int i,k,n,m,w,j; char *s; printf("輸入航線總數(shù)(n<=40):");/*輸入航線總數(shù)*/ scanf("%d",&n); while(n>40|n<0) printf("輸入錯誤!再次輸入(0<n<=4

10、0):");/*輸入航線總數(shù)*/ scanf("%d",&n); printf(" 輸入航班的信息nn");/*提示信息*/ printf("航班號起飛城市 降落城市 出發(fā)時間 降落時間 剩下的座位 價格 折扣n"); printf("-n"); for(i=0;i<n;i+) scanf("%s",ti.planenumber);/*輸入姓名*/ scanf("%s",ti.Take_off_city);/*輸入起飛城市*/ scanf("

11、%s",ti.Arrived_in_city);/*輸入降落城市*/ scanf("%s",ti.takeoff_time);/*輸入起飛時間*/ scanf("%s",ti.Landing_time);/*輸入降落時間*/ scanf("%d",&ti.shipping);/*輸入艙位數(shù)*/ scanf("%s",ti.price);/*輸入票價*/ scanf("%s",ti.discount);/*輸入折扣*/ printf("-n"); for(i=

12、0;i<n;i+)ti.sit=0; return n; /*返回記錄條數(shù)*/*顯示記錄，參數(shù)為記錄數(shù)組和記錄條數(shù)*/void list(FLY t,int n) int i; printf("航班號起飛城市 降落城市 出發(fā)時間 降落時間 剩下的座位 價格 折扣n"); printf("-n"); for(i=0;i<n;i+) printf("%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn",ti.planenumber,ti.Take_off_city,ti.Arrived_in_city

13、,ti.takeoff_time,ti.Landing_time,ti.shipping,ti.price,ti.discount); printf(" *end*n");/*按航班號查找記錄*/void search1(FLY t,int n) char s20; /*保存待查找航班名字符串*/ int i; printf("輸入你想查找的航班名:"); scanf("%s",s); /*輸入待查找航班名*/ for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ if(strcmp(s,ti.planenumb

14、er)=0) /*記錄中的航班名和待比較的是否相等*/ break; /*相等，則返回該記錄的下標號，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號起飛城市 降落城市 出發(fā)時間 降落時間 剩下的座位 價格 折扣n"); /*顯示記錄*/ printf("-n"); printf("%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn",ti.planenumber,ti.Take_o

15、ff_city,ti.Arrived_in_city,ti.takeoff_time,ti.Landing_time,ti.shipping,ti.price,ti.discount); /*按起降城市查找記錄*/void search2(FLY t,int n) char s120; char s220; int i; printf("輸入起飛城市名稱:"); scanf("%s",s1); /*輸入起飛城市名*/ printf("輸入降落城市名稱:"); scanf("%s",s2); /*輸入降落城市名*/

16、for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ if(strcmp(s1,ti.Take_off_city)=0)&&(strcmp(s2,ti.Arrived_in_city)=0) /*記錄中的城市和待比較的是否相等*/ break; /*相等，則返回該記錄的下標號，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號起飛城市 降落城市 出發(fā)時間 降落時間 剩下的座位 價格 折扣n"); /*找到，顯示記

17、錄*/ printf("-n"); printf("%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn",ti.planenumber,ti.Take_off_city,ti.Arrived_in_city,ti.takeoff_time,ti.Landing_time,ti.shipping,ti.price,ti.discount); /*訂票*/void book(FLY t,int n) char s20,number110,name110,id120,flightname110; int i,j=0,m,k,count

18、1; printf("輸入你想預訂的票數(shù):"); scanf("%d",&m); printf("號碼 姓名 證件號 訂的票數(shù) 航班號n"); /*提示信息*/ printf("-n"); for(k=0;k<m;k+) scanf("%s",number1); scanf("%s",name1);/*輸入訂票客戶姓名*/ scanf("%s",id1);/*輸入證件號*/ scanf("%d",&count1);

19、/*輸入訂票票數(shù)*/ scanf("%s",flightname1);/*輸入航班號*/ for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ if(strcmp(flightname1,ti.planenumber)=0) /*記錄中的航班名和待比較的是否相等*/ j=ti.sit; strcpy(ti.guestj.number,number1); strcpy(,name1); strcpy(ti.guestj.id,id1); ti.guestj.count=count1; strcpy(ti.guestj.flig

20、htname,flightname1); ti.shipping=ti.shipping-count1; ti.sit+; break; /*相等，則返回該記錄的下標號，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("對不起！沒有此航班n"); m=m+2; k+; /*退票*/void quit(FLY t,int n) char s120,s220; /*保存待查找航班名和證件號字符串*/ int i,k,j,h,l,ch; printf("請輸入你想退訂的航班號:"); scanf(&quo

21、t;%s",s1); /*輸入待查找航班名*/ printf("請輸入你的證件號:"); scanf("%s",s2); /*輸入待查找證件號*/ printf("號碼 姓名 證件號 訂的票數(shù) 航班號n"); /*顯示提示*/ printf("-n"); for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ for(j=0;j<ti.sit;j+) if(strcmp(s1,ti.guestj.flightname)=0)&&(strcmp(s2,ti.gues

22、tj.id)=0) printf("%-11s%-16s%-16s%-14d%-10sn",ti.guestj.number,,ti.guestj.id,ti.guestj.count,ti.guestj.flightname); ti.shipping=ti.shipping+ti.guestj.count; l=j; h=i; break; i=h; if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("你是否確認刪除(1/0)n&quo

23、t;); /*確認是否要刪除*/ scanf("%d",&ch); /*輸入一個整數(shù)或*/ if(ch=1) /*如果確認刪除整數(shù)為*/ for(k=l+1;k<ti.sit;k+) strcpy(ti.guestk-1.number,ti.guestk.number); /*將后一條記錄的姓名拷貝到前一條*/ strcpy(,); strcpy(ti.guestk-1.id,ti.guestk.id); ti.guestk-1.count=ti.guestk.count; strcpy(ti.gue

24、stk-1.flightname,ti.guestk.flightname); ti.sit-; printf("退票成功!n");/*提示退票成功*/ /*修改航班信息*/void channge(FLY t,int n) char s20; /*要刪除記錄的姓名*/ int i,j; printf("請輸入你要修改的航班號:"); /*提示信息*/ scanf("%s",s);/*輸入航班名*/ for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ if(strcmp(s,ti.planenumber)=0)

25、 /*記錄中的航班名和待比較的是否相等*/ break; /*相等，則返回該記錄的下標號，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號起飛城市 降落城市 出發(fā)時間 降落時間 剩下的座位 價格 折扣n"); /*找到，顯示原先記錄*/ printf("-n"); printf("%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn",ti.planenumber,ti.Take_of

26、f_city,ti.Arrived_in_city,ti.takeoff_time,ti.Landing_time,ti.shipping,ti.price,ti.discount); printf("please input the new information:n"); scanf("%s",ti.planenumber);/*輸入航班名*/ scanf("%s",ti.Take_off_city);/*輸入起始城市*/ scanf("%s",ti.Arrived_in_city);/*輸入終點城市*/ sc

27、anf("%s",ti.takeoff_time);/*輸入起飛時間*/ scanf("%s",ti.Landing_time);/*輸入降落時間*/ scanf("%d",ti.shipping);/*輸入座位號*/ scanf("%s",ti.price);/*輸入票價*/ scanf("%s",ti.discount);/*輸入折扣*/ /*保存資料*/void save(FLY t,int n) int i,j; FILE *fp; /*指向文件的指針*/ if(fp=fopen(&qu

28、ot;record1.txt","wb")=NULL) /*打開文件，并判斷打開是否正常*/ printf("can not open filen");/*沒打開*/ exit(1); /*退出*/ printf("n保存文件n"); /*輸出提示信息*/ fprintf(fp,"%d",n); /*將記錄數(shù)寫入文件*/ fprintf(fp,"rn"); /*將換行符號寫入文件*/ for(i=0;i<n;i+) fprintf(fp,"%s %s %s %s %s

29、%d %s %s",ti.planenumber,ti.Take_off_city,ti.Arrived_in_city,ti.takeoff_time,ti.Landing_time,ti.shipping,ti.price,ti.discount); fprintf(fp,"rn"); /*將換行符號寫入文件*/ fprintf(fp,"%d",ti.sit); /*將記錄數(shù)寫入文件*/ fprintf(fp,"rn"); /*將換行符號寫入文件*/ for(j=0;j<ti.sit;j+) fprintf(fp,

30、"%s %s %s %d %s",ti.guestj.number,,ti.guestj.id,ti.guestj.count,ti.guestj.flightname);/*格式寫入記錄*/ fprintf(fp,"rn"); /*將換行符號寫入文件*/ fclose(fp);/*關閉文件*/ printf("*恭喜！保存成功*n"); /*顯示保存成功*/*讀入函數(shù)，參數(shù)為結(jié)構(gòu)體數(shù)組*/int load(FLY t) int i,n,j; FILE *fp; /*指向文件的指針*/ if(fp=fope

31、n("record1.txt","rb")=NULL)/*打開文件*/ printf("不能打開n"); /*不能打開*/ exit(1); /*退出*/ fscanf(fp,"%d",&n); /*讀入記錄數(shù)*/ for(i=0;i<n;i+) fscanf(fp,"%s %s %s %s %s %d %s %s",ti.planenumber,ti.Take_off_city,ti.Arrived_in_city,ti.takeoff_time,ti.Landing_time,

32、&ti.shipping,ti.price,ti.discount); fscanf(fp,"%d",&ti.sit); /*讀入記錄數(shù)*/ for(j=0;j<ti.sit;j+) fscanf(fp,"%s %s %s %d %s",ti.guestj.number,,ti.guestj.id,&ti.guestj.count,ti.guestj.flightname); /*按格式讀入記錄*/ fclose(fp); /*關閉文件*/ printf("你已經(jīng)成功從文件讀取數(shù)據(jù)!nn

33、nn"); /*顯示讀取成功*/ return n; /*返回記錄數(shù)*/*主函數(shù)*/main() int i; FLY flightQ; int length; /*保存記錄長度*/ for(;)/*無限循環(huán)*/ switch(menu_select() /*調(diào)用主菜單函數(shù)，返回值整數(shù)作開關語句的條件*/ case 0:length=enter(flight);break;/*輸入記錄*/ case 1:list(flight,length);break; /*顯示全部記錄*/ case 2:search1(flight,length);break; /*查找記錄*/ case 3:

34、search2(flight,length);break; /*查找記錄*/ case 4:book(flight,length);break; /*訂票*/ case 5:quit(flight,length);break; /*退票*/ case 6:channge(flight,length);break; /*修改航班信息*/ case 7:save(flight,length);break; /*保存文件*/ case 8:length=load(flight); break; /*讀文件*/ case 9:exit(0); /*如返回值為則程序結(jié)束*/ 4.系統(tǒng)運行時窗口截圖：（V

35、C6.0下的運行結(jié)果）訂票系統(tǒng)菜單窗口0.輸入航班的信息1.列出航班的信息2.按航班號查詢航班信息3.按城市來查詢航班4.訂票程序5.退票系統(tǒng)6.修改飛機航班的信息7.保存文件8.讀取文件 、下載文件圖的遍歷過程演示一 需求分析：設計程序完成如下功能：對給定的圖的結(jié)構(gòu)和起點，產(chǎn)生深度優(yōu)先遍歷和廣度優(yōu)先遍歷，并列出求解的過程動態(tài)演示。二 主要設計思路： 設計思想：簡而言之，深度優(yōu)先，就是先遍歷它的一個鄰接點，這個鄰接點的鄰接點然后才遍歷其他的鄰接點。廣度優(yōu)先，就是先把它所有的鄰接點都遍歷完以后，再遍歷它每個鄰接點的鄰接點 。存儲結(jié)構(gòu)為圖的鄰接多重表，它是無向圖的一種鏈式存儲結(jié)構(gòu)。深度優(yōu)先遍歷：設

36、x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結(jié)束，否則繼續(xù)選擇一個尚未被訪問的頂點作為新源點，進

37、行新的搜索過程。 廣度優(yōu)先遍歷：設x和y是兩個相繼要被訪問的未訪問過的頂點。它們的鄰接點分別記為x1，x2，xs和y1，y2，yt。 為確保先訪問的頂點其鄰接點亦先被訪問，在搜索過程中使用隊列來保存已訪問過的頂點。當訪問x和y時，這兩個頂點相繼入隊。此后，當x和y相繼出隊時，我們分別從x和y出發(fā)搜索其鄰接點x1，x2，xs和y1，y2，yt，對其中未訪者進行訪問并將其入隊。這種方法是將每個已訪問的頂點入隊，故保證了每個頂點至多只有一次入隊。A. 圖的算法構(gòu)造思想：1CreateALGraph()初始條件:V是圖的頂點集,VR是圖中弧的集合.操作結(jié)果:按V和VR是定義構(gòu)造圖G.2. Destro

38、yGraph(&G)初始條件:圖G存在操作結(jié)果:銷毀圖G3LocateVex(G,u)初始條件: 圖G存在,u和G中頂點有相同的特征操作結(jié)果:若圖G中存在頂點u,則返回該頂點在圖中的位置;否則返回其他信息4. GetVex(G,v)初始條件: 圖G存在,v是G中頂點操作結(jié)果:返回v的值5. FirstAjvex(G,v)初始條件: 圖G存在,v是G中頂點操作結(jié)果:返回v的第一個鄰接頂點,若頂在圖中沒有鄰接頂點,則返回為空6. NextAjvex(G,v,w)初始條件: 圖G存在,v是G中頂點,w是v的鄰接頂點操作結(jié)果:返回v的下一個鄰接頂點,若w是v的最后一個鄰接頂點,則返回空7. D

39、eleteVexx(&G,v)初始條件: 圖G存在,v是G中頂點操作結(jié)果:刪除頂點v已經(jīng)其相關的弧8. DFStraverse(ALGraph)初始條件: 圖G存在,visit的頂點的應用函數(shù)操作結(jié)果: 對圖進行深度優(yōu)先遍歷,在遍歷過程中對每個結(jié)點調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗9. BFStraverse(ALGraph)初始條件: 圖G存在,visit的頂點的應用函數(shù)操作結(jié)果: 對圖進行廣度優(yōu)先遍歷,在遍歷過程中對每個結(jié)點調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗附圖的結(jié)構(gòu)體構(gòu)造：ALGraph數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為點集

40、.數(shù)據(jù)關系R:R=VRVR=(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑B隊列的算法構(gòu)造：1. Init_SeqQueue()操作結(jié)果:構(gòu)造一個空隊列Q2. DestryoQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：隊列Q被銷毀，不再存在。3. In_SeqQueue()初始條件:隊列Q已經(jīng)存在操作結(jié)果:插入元素e為Q的新的隊尾元素4. Out_SeqQueue()初始條件:Q為非空隊列操作結(jié)果:刪除Q的隊尾元素,并用e返回其值5. Empty_SeqQueue()初始條件:隊列已經(jīng)存在操作結(jié)果:若隊列為空,則返回TRUE,否則返回FLASEC本程序包含的模

41、板：1.程序模塊 Main()取得頂點數(shù)和弧數(shù)；生成鄰接表結(jié)構(gòu)的圖；深度遍歷圖；廣度遍歷圖；2造鄰接表結(jié)構(gòu)的圖；3度優(yōu)先遍歷圖；4度優(yōu)先遍歷圖；5列的基本操作模塊；6數(shù)聲明模塊；三.源程序代碼：(VC+6.0下運行)#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VERTEX_NUM 50 /圖的最大頂點數(shù) #define MAXQSIZE 200 /隊列的最大容量 enum BOOL False,True; /定義枚舉變量typedef struct ArcNod

42、e /圖的鄰接表存儲int adjvex; /該弧所指向的頂點的位置 struct ArcNode *nextarc; /指向下一條弧的指針 ArcNode; /弧結(jié)點 typedef struct ArcNode* AdjListMAX_VERTEX_NUM; /指向第一條依附該頂點的弧的指針 int vexnum,arcnum; /圖的當前頂點和弧數(shù) Graph; typedef struct /隊列結(jié)構(gòu) int elemMAXQSIZE; /數(shù)據(jù)域 int front; /隊頭指針 int rear; /隊尾指針 SqQueue; BOOL visitedMAX_VERTEX_NUM;

43、/全局變量訪問標志數(shù)組 void CreateGraph(Graph &); /生成圖的鄰接表 void DFSTraverse(Graph); /深度優(yōu)先搜索遍歷圖 void DFS(Graph,int); void BFSTraverse(Graph); /廣度優(yōu)先搜索遍歷圖 void Initial(SqQueue &); /初始化一個隊列 BOOL QueueEmpty(SqQueue); /判斷隊列是否空 BOOL EnQueue(SqQueue &,int); /將一個元素入隊列 BOOL DeQueue(SqQueue &,int &);

44、/將一個元素出隊列 int FirstAdjVex(Graph,int); /求圖中某一頂點的第一個鄰接頂點 int NextAdjVex(Graph,int,int); /求某一頂點的下一個鄰接頂點 int main() Graph G; /采用鄰接表結(jié)構(gòu)的圖 char j='y' printf("題目:編制一個“圖遍歷的演示”的程序.n"); /-程序解說- printf("n本程序?qū)⒀菔旧梢粋€圖，并對它進行遍歷.n"); printf("輸入圖的頂點數(shù)和弧數(shù):n格式：頂點數(shù)，弧數(shù)；例如:5,4n"); prin

45、tf("接著輸入各邊(弧尾，弧頭):n例如:5,3n 3,1n 1,2n 2,4n"); printf("程序會生成一個圖，并對它進行深度和廣度遍歷.n"); printf("深度遍歷:1->2->4->3->5n廣度遍歷:1->2->3->4->5n"); /- while(j!='N'&&j!='n') printf("n請輸入頂點數(shù)和弧數(shù)："); scanf("%d,%d",&G.vex

46、num,&G.arcnum); /輸入圖的頂點數(shù)和弧數(shù) CreateGraph(G); /生成鄰接表結(jié)構(gòu)的圖 DFSTraverse(G); /深度優(yōu)先搜索遍歷圖 BFSTraverse(G); /廣度優(yōu)先搜索遍歷圖 printf("圖遍歷完畢，繼續(xù)進行嗎?(Y/N)"); scanf(" %c",&j); void CreateGraph(Graph &G) /構(gòu)造鄰接表結(jié)構(gòu)的圖G int i; int start,end; ArcNode *s; for(i=1;i<=G.vexnum;i+) G.AdjListi=NU

47、LL; /初始化指針數(shù)組 for(i=1;i<=G.arcnum;i+) scanf("%d,%d",&start,&end); /輸入弧的起點和終點 s=(ArcNode *)malloc(sizeof(ArcNode); /生成一個弧結(jié)點 s->nextarc=G.AdjListstart; /插入到鄰接表中 s->adjvex=end; G.AdjListstart=s; s=(ArcNode *)malloc(sizeof(ArcNode); s->nextarc=G.AdjListend; s->adjvex=star

48、t; G.AdjListend=s; void DFSTraverse(Graph G) /深度優(yōu)先遍歷圖G int i; printf("深度優(yōu)先遍歷:"); for(i=1;i<=G.vexnum;i+) visitedi=False; /訪問標志數(shù)組初始化 for(i=1;i<=G.vexnum;i+) if(!visitedi) DFS(G,i); /對尚未訪問的頂點調(diào)用DFS printf("bb n"); void DFS(Graph G,int i) /從第i個頂點出發(fā)遞歸地深度遍歷圖G int w; visitedi=True; /訪問第i個頂點 printf("%d->",i); for(w=FirstAdjVex(G,i);w>0;w=NextAdjVex(G,i,w) if(!