(C語言版)飛機(jī)訂票系統(tǒng)

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

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

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

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

5、（6）文件操作函數(shù) save（）&load（）3.源程序代碼：（WIN TC下運(yùn)行）#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;/*編號(hào)*/ char id20; /*證件號(hào)*/ char name10; /*姓名*/ int count; /*訂票數(shù)*/ char flightname10;/*乘坐航

6、班號(hào)*/GUEST; /*航班信息*/typedef structchar planenumber10;/*航班號(hào)*/ char Take_off_city20;/*起飛城市*/ char Arrived_in_city20;/*抵達(dá)城市*/ char takeoff_time20;/*起飛時(shí)間*/ char Landing_time20;/*降落時(shí)間*/ int shipping; /*艙位數(shù)*/ char price5; /*票價(jià)*/ char discount5; /*折扣*/ GUEST guest20; int sit;FLY;/*菜單函數(shù)，函數(shù)返回值為整數(shù)，代表所選的菜單項(xiàng)*/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. 按航班號(hào)查詢航班信息n");

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

9、*/ scanf("%d",&c); /*輸入選擇項(xiàng)*/ while(c<0|c>9); /*選擇項(xiàng)不在9之間重輸*/ return c; /*返回選擇項(xiàng)，主程序根據(jù)該數(shù)調(diào)用相應(yīng)的函數(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("輸入錯(cuò)誤!再次輸入(0<n<=4

10、0):");/*輸入航線總數(shù)*/ scanf("%d",&n); printf(" 輸入航班的信息nn");/*提示信息*/ printf("航班號(hào)起飛城市 降落城市 出發(fā)時(shí)間 降落時(shí)間 剩下的座位 價(jià)格 折扣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);/*輸入起飛時(shí)間*/ scanf("%s",ti.Landing_time);/*輸入降落時(shí)間*/ scanf("%d",&ti.shipping);/*輸入艙位數(shù)*/ scanf("%s",ti.price);/*輸入票價(jià)*/ 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("航班號(hào)起飛城市 降落城市 出發(fā)時(shí)間 降落時(shí)間 剩下的座位 價(jià)格 折扣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");/*按航班號(hào)查找記錄*/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; /*相等，則返回該記錄的下標(biāo)號(hào)，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號(hào)起飛城市 降落城市 出發(fā)時(shí)間 降落時(shí)間 剩下的座位 價(jià)格 折扣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; /*相等，則返回該記錄的下標(biāo)號(hào)，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號(hào)起飛城市 降落城市 出發(fā)時(shí)間 降落時(shí)間 剩下的座位 價(jià)格 折扣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("輸入你想預(yù)訂的票數(shù):"); scanf("%d",&m); printf("號(hào)碼 姓名 證件號(hào) 訂的票數(shù) 航班號(hào)n"); /*提示信息*/ printf("-n"); for(k=0;k<m;k+) scanf("%s",number1); scanf("%s",name1);/*輸入訂票客戶姓名*/ scanf("%s",id1);/*輸入證件號(hào)*/ scanf("%d",&count1);

19、/*輸入訂票票數(shù)*/ scanf("%s",flightname1);/*輸入航班號(hào)*/ 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; /*相等，則返回該記錄的下標(biāo)號(hào)，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("對(duì)不起！沒有此航班n"); m=m+2; k+; /*退票*/void quit(FLY t,int n) char s120,s220; /*保存待查找航班名和證件號(hào)字符串*/ int i,k,j,h,l,ch; printf("請(qǐng)輸入你想退訂的航班號(hào):"); scanf(&quo

21、t;%s",s1); /*輸入待查找航班名*/ printf("請(qǐng)輸入你的證件號(hào):"); scanf("%s",s2); /*輸入待查找證件號(hào)*/ printf("號(hào)碼 姓名 證件號(hào) 訂的票數(shù) 航班號(hào)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("你是否確認(rèn)刪除(1/0)n&quo

23、t;); /*確認(rèn)是否要?jiǎng)h除*/ scanf("%d",&ch); /*輸入一個(gè)整數(shù)或*/ if(ch=1) /*如果確認(rèn)刪除整數(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; /*要?jiǎng)h除記錄的姓名*/ int i,j; printf("請(qǐng)輸入你要修改的航班號(hào):"); /*提示信息*/ scanf("%s",s);/*輸入航班名*/ for(i=0;i<n;i+)/*從第一條記錄開始，直到最后一條*/ if(strcmp(s,ti.planenumber)=0)

25、 /*記錄中的航班名和待比較的是否相等*/ break; /*相等，則返回該記錄的下標(biāo)號(hào)，程序提前結(jié)結(jié)束*/ if(i>n-1) /*如果整數(shù)i值大于n-1，說明沒找到*/ printf("沒有找到n"); else printf("航班號(hào)起飛城市 降落城市 出發(fā)時(shí)間 降落時(shí)間 剩下的座位 價(jià)格 折扣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);/*輸入終點(diǎn)城市*/ sc

27、anf("%s",ti.takeoff_time);/*輸入起飛時(shí)間*/ scanf("%s",ti.Landing_time);/*輸入降落時(shí)間*/ scanf("%d",ti.shipping);/*輸入座位號(hào)*/ scanf("%s",ti.price);/*輸入票價(jià)*/ 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"); /*將換行符號(hào)寫入文件*/ 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"); /*將換行符號(hào)寫入文件*/ fprintf(fp,"%d",ti.sit); /*將記錄數(shù)寫入文件*/ fprintf(fp,"rn"); /*將換行符號(hào)寫入文件*/ 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"); /*將換行符號(hào)寫入文件*/ fclose(fp);/*關(guān)閉文件*/ 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); /*關(guān)閉文件*/ 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ù)作開關(guān)語句的條件*/ 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)運(yùn)行時(shí)窗口截圖：（V

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

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

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

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

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

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

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

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

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

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

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

46、num,&G.arcnum); /輸入圖的頂點(diǎn)數(shù)和弧數(shù) CreateGraph(G); /生成鄰接表結(jié)構(gòu)的圖 DFSTraverse(G); /深度優(yōu)先搜索遍歷圖 BFSTraverse(G); /廣度優(yōu)先搜索遍歷圖 printf("圖遍歷完畢，繼續(xù)進(jìn)行嗎?(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); /輸入弧的起點(diǎn)和終點(diǎn) s=(ArcNode *)malloc(sizeof(ArcNode); /生成一個(gè)弧結(jié)點(diǎn) 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; /訪問標(biāo)志數(shù)組初始化 for(i=1;i<=G.vexnum;i+) if(!visitedi) DFS(G,i); /對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS printf("bb n"); void DFS(Graph G,int i) /從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度遍歷圖G int w; visitedi=True; /訪問第i個(gè)頂點(diǎn) printf("%d->",i); for(w=FirstAdjVex(G,i);w>0;w=NextAdjVex(G,i,w) if(!