1、數據結構課程設計實驗報告C語言版課題：飛機訂票系統和圖的遍歷的動態演示姓名：學號：班級：指導教師：-1 -數據結構課程設計實驗報告訂票系統1需求分析任務：通過此系統可以實現如下功能：錄入：可以錄入航班情況（數據可以存儲在一個數據文件中，數據結 構、具體數據自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間， 起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；退票：可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及

2、航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數據文件要求：根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序 完成功能；2:主要設計思路：1） 算法構造流程圖:A :主菜單：主菜單0123456789輸列出按航按訂票退票修改保存讀取退出入航班班號城程序系統飛機文件文航的信查詢市航班件、班息航班來的信下載的信息查息文件信詢息航班B:各分塊模板的構造流程圖:0.輸入航班的信息航班號起飛城市降落城市出發時間降落時間剩下的座位價格折扣1列出航班的信息繼續 y退出n2按航班號查詢航班信息輸入所需要查詢的航班號顯示這個航班的的信息3按城市來查詢航班輸入起飛城市輸入降落城市顯示

3、這個航班的信息4訂票程序輸入號碼輸入名字輸入ID需要定的票航班號數5退票系統輸入航班號輸入你ID確定退票1否定 06. 修改飛機航班的信息輸入要修改的航班號重新輸入新的航班信息7保存文件顯示保存成功3:功能函數設計：(1) :訂票系統主菜單函數menu_select(本函數主要構造系統的主菜單，系統需要實現很多功能，并且 各個功能需要各自的函數支持，所以通過主菜單可以輕松的進入各個 函數下實現各自的功能，故主菜單顯得尤為重要。其實就是通過鍵盤 輸入選擇項，然后通過scanf接受，在通過swtich判斷進入各個選擇 項。(2) :工作人員管理函數 enter()&change ()系統需

4、要各個航班的詳細信息，所以需要工作人員把信息輸入 系統里，以供乘客查詢訂票。enter ()函數的構造就是為了解決這 個問題。而有可能航班線路更改或由于天氣等原因飛機的起飛時間發 生了更改，故工作人員需要及時更改信息，所以需要構造 change() 函數。(3) ：列出航班信息的函數list()乘客需要查詢各個航班的信息，所以通過系統要能調出上面工 作人員已經錄入好的航班信息，所以構造本函數來實現這個功能。(4) 乘客具體查詢函數 search ()本函數分兩個分函數：search1 ()和search2(),它們分別實 現乘客的按航班查詢和按出發及抵達城市的兩種查詢方案。(5) 票務管理函數

5、 book () &quit ()通過book ()函數可以實現乘客的訂票操作，通過 quit ()可以實現乘客的退票操作。(6)文件操作函數 save ()&load ()3源程序代碼：(WIN TC下運行)#include <dos.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 20 #define Q 40 /*定義數據結構*/*乘客信息*/typedef structchar number10;/*編號 */char id20;/*證

6、件號*/char name10;/*姓名 */int count;/*訂票數*/char flightname10; /* 乘坐航班號 */GUEST;/*航班信息*/typedef struct/*航班號*/*起飛城市*/*抵達城市*/*起飛時間*/*降落時間*/*艙位數*/*票價*/*折扣*/char planenumber10;char Take_off_city20;char Arrived_in_city20;char takeoff_time20;char Landing_time20;int shipping;char price5;char discount5;GUEST gu

7、est20;int sit;FLY;/*菜單函數，函數返回值為整數，代表所選的菜單項*/menu_select()int c;-7 -數據結構課程設計實驗報告printf( "按任意鍵返回主菜單n" ); /*提示壓任意鍵繼續*/getch(); /*讀入任意字符*/-# -數據結構課程設計實驗報告-# -數據結構課程設計實驗報告printf(Welcome tonn")；printf(Tickets Booking Systemnn"printf(*MENU*nn"printf(0.printf(1.printf("2.printf

8、("3.printf("4.printf("5.printf("6.printf("7.printf("8.printf("9.);) 輸入航班信息n");列出航班的信息n");按航班號查詢航班信息n"); 按城市來查詢航班n");訂票程序n");退票系統n");修改飛機航班的信息n");保存文件n");讀取和下載文件n");退出n");printf(*nn");-# -數據結構課程設計實驗報告doprintf( &

9、quot;n輸入你的選擇項(09):" ); /*提示輸入選項*/scanf("%d"，&c);/* 輸入選擇項 */ while (c<0|c>9);/*選擇項不在 9之間重輸*/return c; /*返回選擇項，主程序根據該數調用相應的函數*/*輸入函數*/int enter(FLY t)int i,k,n,m,w,j;char *s;printf( "輸入航線總數(n<=40):" );/*輸入航線總數*/scanf("%d",&n);while (n>40|n<0)pr

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

11、_off_city);/* 輸入起飛城市 */scanf( "%s" ,ti.Arrived_in_city);/* 輸入降落城市 */scanf("%s",ti.takeoff_time);/*輸入起飛時間*/scanf("%s",ti.Landing_time);/*輸入降落時間*/scanf("%d", &ti.shipping);/*輸入艙位數*/scanf("%s",ti.price);/* 輸入票價 */scanf("%s",ti.discount);/*

12、輸入折扣*/);printf( "n"for (i=0;i<n;i+)ti.sit=0;return n; /*返回記錄條數*/*顯示記錄，參數為記錄數組和記錄條數*/void list(FLY t, int n)int i;printf("航班號起飛城市降落城市出發時間 降落時間 剩下的座位 價格 折扣n");printf(n");-9 -數據結構課程設計實驗報告for (i=0;i<n;i+) printf( "%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn" ,ti.plane

13、number,ti.Take_off_city,ti.Arrived_in_city,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);/*輸入待查找航班名*/f

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

15、7d%-7s%-7sn"，圳.planenumber,ti.Take_off_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

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

17、下的座位價格折扣n");示記錄*/printf(n");printf( "%-12s%-12s%-10s%-12s%-10s%-7d%-7s%-7sn" ,ti.planenumber,ti.Take_off_city,ti.Ar rived_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

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

19、ount1); /* 輸入訂票票數 */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.

20、flightname,flightname1);ti.shipping=ti.shipping-count1;ti.sit+;break ;/*相等，則返回該記錄的下標號，程序提前結結束*/if (i>n-1)/*如果整數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( "%s&qu

21、ot;,s1);/*輸入待查找航班名 */printf("請輸入你的證件號:");scanf( "%s",s2);/*輸入待查找證件號*/printf( "號碼 姓名證件號訂的票數航班號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.guestj.id)=0)pr

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

23、/scanf( "%d"，&ch); /* 輸入一個整數或 */if (ch=1)/*如果確認刪除整數為*/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.guestk-1.flightname,ti

24、.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)/*記錄中的航班名和待比較的是否相等*/b

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

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

27、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( "record1.txt"*

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

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

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

31、1.txt" ,"rb" )=NULL)/* 打開文件 */printf("不能打開n" );/*不能打開*/exit(1);/* 退出 */fscanf(fp,"%d",&n);/* 讀入記錄數 */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，& ti.sh

32、ipping,ti.price,ti.discount);fscanf(fp, "%d",&ti.sit);/* 讀入記錄數 */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( "你已經成功從文件讀取數據！!nnnn&quo

33、t;); /*顯示讀取成功*/-17 -數據結構課程設計實驗報告return n; /*返回記錄數*/*主函數*/ main() int i;FLY flightQ;*/int length; /*保存記錄長度for (;) /*無限循環*/switch (menu_select()/*調用主菜單函數，返回值整數作開關語句的條件*/case O:length=enter(flight);break; /*輸入記錄*/case 1:list(flight,length);case 2:search1(flight,length);break ; /*顯示全部記錄*/break ; /*查找記錄*

34、/-19 -數據結構課程設計實驗報告-# -數據結構課程設計實驗報告case 7:save(flight,length);息tt惠 班班 信 息的件 息信詢詢 班文 信的査查 航載 霍系飛文朿 入出航城sf存r二 翦篥訂退修保讀退case3:search2(flight,length);break ;/*查找記錄*/case4:book(flight,length);break;/*訂票*/case5:quit(flight,length);break;/*退票*/case6:channge(flight,length);break ;/*修改航班信息*/break ;/*保存文件*/case

35、 8:length=load(flight);break;/* 讀文件 */case 9:exit(0);/*如返回值為則程序結束*/4系統運行時窗口截圖：(VC6.0下的運行結果)訂票系統菜單窗口*C: Docu>.ent s and Sett ingsAd>iinist rat or®Debugbookt icket. exeMe looms toTickets Booking System耳耳 X 疋 鴻X Jf MEME 弭:JcHENLI 耳黑弭:KKJCiKXCHM-# -數據結構課程設計實驗報告-# -數據結構課程設計實驗報告輸入你的選擇項0-9 ：-# -

36、數據結構課程設計實驗報告-# -數據結構課程設計實驗報告0.輸入航班的信息輸入你的選擇項0：«輸入航妾總藪n-«：2輸入航班的信息札班號起飛城市降落城市出發時間降落吋間剩下的座位價格折扣123 上癟 合膽 10： OR Id. 40 500 R00 Q.8124 南京 d匕京 8 : 50 9： 50 500 1300 0.7512 . 怙任意鍵返回主菜單b班車埶翳擇蠶蒜'1列出航班的信息出發時門降落時間豈下的座位逆折扣1123合魁 訥LOf 10 Sflfl BRR (L0124南京北京 趴 509； 50500130B0.75桂任意鍵返回主菜單QQPinyin

37、半：2按航班號查詢航班信息I輻V你旳選拝項0：2暑箝:橫鵲'汽蠡齡出發時間降落時間剩下的座位價格折扣123上穆合月巴10： 0010： 405008000.8按任意鍵返回圭菜單3按城市來查詢航班<0海肥落 項左口障 e£«s :芒一亍、>"出發時間降落iq間剎下的座位123上悔合肥IB： B010； 40500B000.8義任意鍵返回主菜單4訂票程序胃碼 姓名證件號訂的票數航班號01關宏新2 124險任意鍵返回主菜單5退票系統織入你的選擇項H9：5請觸入捺想退訂爾航班號七4請輸入你的證件號= 342423

38、198908122191勰 捱名證件號訂的票數航班號01關宏新3424231989081221912124你是否確認刪退票成功? t按任意鍵返回主菜單6.修改飛機航班的信息航班號起飛城市f出發時間降落時間剰下的座隹價格折扣上悔合肥 10S 00please input the new information:125 上篙 合月巴 9： 40 IB： 05 450 750 0.910； 40500B000.87保存文件輸入你的選擇項0：7 k存文童卿*恭旨！保存成功* 帳任盍犍返回主菜單8讀取文件、下載文件你己纟牟項 0*"?：8 讀取數據忖圖的遍歷過程演示一. 需求分析：設計程序完成

39、如下功能：對給定的圖的結構和起點，產生深度優先遍 歷和廣度優先遍歷，并列出求解的過程動態演示。二. 主要設計思路：設計思想：簡而言之，深度優先，就是先遍歷它的一個鄰接點，這 個鄰接點的鄰接點然后才遍歷其他的鄰接點。 廣度優先，就是先 把它所有的鄰接點都遍歷完以后，再遍歷它每個鄰接點的鄰接點。存儲結構為圖的鄰接多重表，它是無向圖的一種鏈式存儲結構。深度優先遍歷：設x是當前被訪問頂點，在對X做過訪問標記后，選 擇一條從x出發的未檢測過的邊(x , y)。若發現頂點y已訪問過，則 重新選擇另一條從x出發的未檢測過的邊，否則沿邊(x , y)到達未曾 訪問過的y,對y訪問并將其標記為已訪問過；然后從

40、y開始搜索， 直到搜索完從y出發的所有路徑，即訪問完所有從y出發可達的頂點 之后，才回溯到頂點x，并且再選擇一條從x出發的未檢測過的邊。 上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源 點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑 相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通 圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新源 點，進行新的搜索過程。廣度優先遍歷：設x和y是兩個相繼要被訪問的未訪問過的頂點。-23 -數據結構課程設計實驗報告它們的鄰接點分別記為x1, x2，xs和y1 , y2，yt。為確保先訪問的頂點其鄰接點亦先被訪問

41、，在搜索過程中使用隊列來保存已訪問過的頂點。當訪問x和y時，這兩個頂點相繼入隊。此后, 當x和y相繼出隊時，我們分別從x和y出發搜索其鄰接點x1, x2，, xs和y1, y2，yt，對其中未訪者進行訪問并將其入隊。這種方 法是將每個已訪問的頂點入隊，故保證了每個頂點至多只有一次入 隊。A. 圖的算法構造思想：1. CreateALGraph()初始條件:V是圖的頂點集,VR是圖中弧的集合.操作結果：按V和VR是定義構造圖G.2. DestroyGraph(&G)初始條件：圖G存在操作結果:銷毀圖G3. LocateVex(G,u)初始條件：圖G存在,u和G中頂點有相同的特征操作結果:

42、若圖G中存在頂點u,則返回該頂點在圖中的位置否則返回其他信息4. GetVex(G,v)初始條件：圖G存在,v是G中頂點操作結果:返回v的值5. FirstAjvex(G,v) 初始條件：圖G存在,v是G中頂點操作結果:返回v的第一個鄰接頂點，若頂在圖中沒有鄰 接頂點，則返回為空6. NextAjvex(G,v,w)初始條件：圖G存在,v是G中頂點,w是v的鄰接頂點操作結果:返回v的下一個鄰接頂點，若w是v的最后一個 鄰接頂點，則返回空7. DeleteVexx(&G,v)初始條件：圖G存在,v是G中頂點操作結果：刪除頂點v已經其相關的弧8. DFStraverse(ALGraph)初

43、始條件：圖G存在,visit的頂點的應用函數操作結果：對圖進行深度優先遍歷，在遍歷過程中對每個 結點調用visit 函數一次，一旦visit 失敗, 則操作失敗9. BFStraverse(ALGraph)初始條件：圖G存在,visit的頂點的應用函數操作結果：對圖進行廣度優先遍歷，在遍歷過程中對每個結點調用visit 函數一次，一旦visit 失敗, 則操作失敗附圖的結構體構造：ALGraph數據對象V:V是具有相同特性的數據元素的集合，稱為點集.數據關系RR=VRVR二(v,w)|v,w 屬于V,(v,w)表示v和w之間存在的路B. 隊列的算法構造：1.1 ni t_SeqQueue()操

44、作結果：構造一個空隊列Q2. DestryoQueue(&Q)初始條件：隊列Q已存在。操作結果：隊列Q被銷毀，不再存在。3. In_SeqQueue()初始條件：隊列Q已經存在操作結果:插入元素e為Q的新的隊尾元素4. Out_SeqQueue()初始條件:Q為非空隊列操作結果：刪除Q的隊尾元素，并用e返回其值5. Empty_SeqQueue()初始條件：隊列已經存在操作結果：若隊列為空，則返回TRUE否則返回FLASEC. 本程序包含的模板:1. 程序模塊Mai n()取得頂點數和弧數；生成鄰接表結構的圖；深度遍歷圖；廣度遍歷圖；2. 造鄰接表結構的圖；3. 度優先遍歷圖；4. 度

45、優先遍歷圖；5. 列的基本操作模塊；6. 數聲明模塊；三源程序代碼：(VC+6.0下運行)#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_VERTEX_NUM 50 圖的最大頂點數#define MAXQSIZE 200 /隊列的最大容量enumBOOL False,True; / 定義枚舉變量typedef struct ArcNode / 圖的鄰接表存儲int adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc; / 指向下一條弧的

46、指針ArcNode; / 弧結點typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一條依附該頂點的弧的指針 int vexnum,arcnum; /圖的當前頂點和弧數Graph;typedef struct / 隊列結構int elemMAXQSIZE; / 數據域int front; /隊頭指針int rear; /隊尾指針SqQueue;BOOL visitedMAX_VERTEX_NUM; /全局變量訪問標志數組void CreateGraph(Graph &);/ 生成圖的鄰接表voidDFSTraverse(Graph);/深

47、度優先搜索遍歷圖voidDFS(Graph, int );voidBFSTraverse(Graph);/廣度優先搜索遍歷圖voidlnitial(SqQueue &);/初始化一個隊列BOOL QueueEmpty(SqQueue); / 判斷隊列是否空BOOL EnQueue(SqQueue &jnt );/ 將一個元素入隊列BOOL DeQueue(SqQueue &int &);/ 將一個元素出隊列int FirstAdjVex(Graph, int ); /求圖中某一頂點的第一個鄰接頂點int NextAdjVex(Graph, int , int )

48、; /求某一頂點的下一個鄰接頂點int main()Graph G; /采用鄰接表結構的圖char j= 'y'printf("題目：編制一個“圖遍歷的演示”的程序 .n");/ 程序解說printf( "n本程序將演示生成一個圖，并對它進行遍歷.n");printf("輸入圖的頂點數和弧數：n格式：頂點數，弧數；例如:5,4n"););printf("接著輸入各邊(弧尾，弧頭):n例如:5,3n3,1n1,2n2,4n"printf("程序會生成一個圖，并對它進行深度和廣度遍歷.n&qu

49、ot;);printf("深度遍歷：1->2->4->3->5n廣度遍歷：1->2->3->4->5n");/while (j!= 'N' &&j!= 'n')printf( "n請輸入頂點數和弧數：”)；scanf( "%d,%d",&G.vexnum,&G.arcnum); / 輸入圖的頂點數和弧數CreateGraph(G); /生成鄰接表結構的圖DFSTraverse(G); /深度優先搜索遍歷圖BFSTraverse(G);

50、 /廣度優先搜索遍歷圖printf("圖遍歷完畢，繼續進行嗎 ？(Y/N)");scanf( " %c" ,&j);void CreateGraph(Graph &G)/構造鄰接表結構的圖Gint i;int start,end;ArcNode *s;for (i=1;i<=G.vexnum;i+) G.AdjListi=NULL;/ 初始化指針數組for (i=1;i<=G.arcnum;i+)scanf( "%d,%d",&start,&end);/ 輸入弧的起點和終點s=(ArcNod

51、e *)malloc( sizeof (ArcNode); / 生成一個弧結點 s->nextarc=G.AdjListstart;/ 插入到鄰接表中s->adjvex=end;G.AdjListstart=s;s=(ArcNode *)malloc( sizeof (ArcNode);s->nextarc=G.AdjListend;s->adjvex=start;G.AdjListend=s;void DFSTraverse(Graph G)/深度優先遍歷圖Gint i;printf("深度優先遍歷:");for (i=1;i<=G.vexnum;i+) visitedi=False;/ 訪問標志數組初始化for (i=1;i<=G.vexnum;i+)if (!visitedi) DFS(G,i);/對尚未訪問的頂點調用DFSprintf( "bb n");void DFS(Graph G, in