數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(圖的遍歷)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：16 大?。?5.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩15頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計(jì)報(bào)告　　題目數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 　　學(xué)生姓名 　　指導(dǎo)教師

2、 　　學(xué) 院信息科學(xué)與工程學(xué)院 　　專業(yè)班級 　　學(xué) 號 　　完成時(shí)間 2011年07月

3、 　　目錄　　第一章、需求分析2　　第二章、概要設(shè)計(jì)2　　2.1設(shè)定圖的抽象數(shù)據(jù)類型2　　2.2設(shè)定隊(duì)列的抽象數(shù)據(jù)類型3

4、　2.3本程序包含的功能模塊3　　第三章、詳細(xì)設(shè)計(jì)3　　3.1頂點(diǎn)、邊和圖的類型6　　3.2隊(duì)列類型8　　3.3主程序和其他偽碼算法9　　第四章、調(diào)試分析9

5、　　第五章、用戶手冊9　　第六章、測試結(jié)果10　　第七章、心得體會10　　附：源程序代碼11　　圖遍歷的演示　　題目:試設(shè)計(jì)一個程序,演示在連通的無向圖上訪問全部結(jié)點(diǎn)

6、的操作　　第一章、需求分析　　1、以鄰接多重表為存儲結(jié)構(gòu)；　　2、實(shí)現(xiàn)連通和非連通的無向圖的深度優(yōu)先和廣度優(yōu)先遍歷；　　3、要求利用棧實(shí)現(xiàn)無向圖的深度優(yōu)先遍歷；　　4、以用戶指定的結(jié)點(diǎn)為起點(diǎn),

7、分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和生成樹的邊集；　　5、用凹入表打印生成樹；　　6、求出從一個結(jié)點(diǎn)到另外一個結(jié)點(diǎn)，但不經(jīng)過另外一個指定結(jié)點(diǎn)的所有簡單路徑；　　6、本程序用C語言編寫，在C-Free3.5環(huán)境下通過。　　第二章、概要設(shè)計(jì)

8、　　1、設(shè)定圖的抽象數(shù)據(jù)類型:　　ADT Graph{　　數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為點(diǎn)集.　　數(shù)據(jù)關(guān)系R:　　R={VR}<

9、/p>　　VR={(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑}　　基本操作P:　　CreatGraph(&G,V,VR)　　初始條件:V是圖的頂點(diǎn)集,VR是圖中弧的集合.　　操作結(jié)

10、果:按V和VR是定義構(gòu)造圖G.　　DestroyGraph(&G)　　初始條件:圖G存在　　操作結(jié)果:銷毀圖G　　LocateVex(G,u)

11、初始條件: 圖G存在,u和G中頂點(diǎn)有相同的特征　　操作結(jié)果:若圖G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中的位置;否則返回其他信息　　GetVex(G,v)　　初始條件: 圖G存在,v是G中頂點(diǎn)　　操作結(jié)果:返回v的值　　FirstAjv

12、ex(G,v)　　初始條件: 圖G存在,v是G中頂點(diǎn)　　操作結(jié)果:返回v的第一個鄰接頂點(diǎn),若頂在圖中沒有鄰接頂點(diǎn),則返回為空　　NextAjvex(G,v,w)　　初始條件: 圖G存在,v是G中頂點(diǎn),w是v的鄰接頂點(diǎn)　　操作結(jié)果:

13、返回v的下一個鄰接頂點(diǎn),若w是v的最后一個鄰接頂點(diǎn),則返回空　　DeleteVexx(&G,v)　　初始條件: 圖G存在,v是G中頂點(diǎn)　　操作結(jié)果:刪除頂點(diǎn)v已經(jīng)其相關(guān)的弧　　DFSTraverse(G,visit())

14、　初始條件: 圖G存在,visit的頂點(diǎn)的應(yīng)用函數(shù)　　操作結(jié)果: 對圖進(jìn)行深度優(yōu)先遍歷,在遍歷過程中對每個結(jié)點(diǎn)調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗　　BFSTraverse(G,visit())　　初始條件: 圖G存在,visit的頂點(diǎn)的應(yīng)用函數(shù)　　操作

15、結(jié)果:對圖進(jìn)行廣度優(yōu)先遍歷,在遍歷過程中對每個結(jié)點(diǎn)調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗　　}ADT Graph　　2、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型：　　ADT Queue{　　數(shù)據(jù)對象:D={ai|ai屬于Elemset,i=1,2….,n,n>=0}&

16、lt;/p>　　數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai屬于D,i=1,2,…,n}　　約定ai為端為隊(duì)列頭,an為隊(duì)列尾　　基本操作:　　InitQueue(&Q)　　操作

17、結(jié)果:構(gòu)造一個空隊(duì)列Q　　DestryoQueue(&Q)　　初始條件：隊(duì)列Q已存在。　　操作結(jié)果：隊(duì)列Q被銷毀，不再存在。　　EnQueue(&Q,e)　　初始條件:隊(duì)列Q已經(jīng)存在<

18、p>　　操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素　　DeQueue(&Q,&E)　　初始條件:Q為非空隊(duì)列　　操作結(jié)果:刪除Q的隊(duì)尾元素,并用e返回其值　　QueueEmpty(Q)　　初始條件:隊(duì)列已經(jīng)存在&

19、lt;/p>　　操作結(jié)果:若隊(duì)列為空,則返回TRUE,否則返回FLASE　　}ADT Queue　　3、本程序包含四個模塊：　　主程序模塊　　void main ()

20、;　　{　　手動構(gòu)造一個圖；　　進(jìn)行深度優(yōu)先遍歷圖；　　進(jìn)行廣度優(yōu)先遍歷圖；　　}；　　手動構(gòu)造一個圖-自己輸入圖的

21、頂點(diǎn)和邊生成一個圖；　　進(jìn)行深度優(yōu)先遍歷圖-打出遍歷的結(jié)點(diǎn)序列和邊集；　　進(jìn)行廣度優(yōu)先遍歷圖-打出遍歷的結(jié)點(diǎn)序列和邊集；　　第三章、詳細(xì)設(shè)計(jì)　　頂點(diǎn),邊和圖類型<p&

22、gt;　　#define MAX_INFO 10 /* 相關(guān)信息字符串的最大長度+1 */　　#define MAX_VERTEX_NUM 20 /* 圖中頂點(diǎn)數(shù)的最大值*/　　int visited[MAX_VERTEX_NUM]; /*全局變量，訪問標(biāo)志數(shù)組 */　　t

23、ypedef char InfoType; /*相關(guān)信息類型*/　　typedef char VertexType; /* 字符類型 */　　typedef enum{unvisited,visited}VisitIf;　　typedef struct EBox

24、 /*邊結(jié)點(diǎn)類型*/ 　　{ 　　int mark; /*訪問標(biāo)記 */ 　　int ivex,jvex;

25、 /*該邊依附的兩個頂點(diǎn)位置*/　　struct EBox *ilink,*jlink; /*分別指向依附這兩個頂點(diǎn)的下一條邊 */　　}EBox; 　　typedef struct VexBox

26、 /*頂點(diǎn)結(jié)點(diǎn)類型*/ 　　{　　char data[MAX_LEN]; 　　EBox *fistedge; /*指向第一條依附該頂點(diǎn)的邊*/ 　　}VexBox;

27、 　　typedef struct　　{ 　　VexBox list[MAX_VERTEX_NUM]; 　　int vexnum,edgenum; /*無向圖當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */ &l

28、t;/p>　　}AMLGraph; 　　圖的基本操作如下：　　int LocateVex(AMLGraph G,VertexType u)；　　// 查G和u有相同特征的頂點(diǎn)，若存在則返回該頂點(diǎn)在無向圖中位置;否則返回-1。

29、　　VertexType& GetVex(AMLGraph G,int v)；　　//以v返回鄰接多重表中序號為i的頂點(diǎn)。　　int FirstAdjVex(AMLGraph G,VertexType v)；　　//返回v的第一個鄰接頂點(diǎn)的序號。若頂點(diǎn)在G中沒有鄰接頂點(diǎn),則返回-1。

30、　　int NextAdjVex(AMLGraph G,VertexType v,VertexType w)；　　//返回v的(相對于w的)下一個鄰接頂點(diǎn)的序號若w是v的最后一個鄰接點(diǎn),則返回-1。　　void CreateGraph(AMLGraph &G)；

31、　//采用鄰接多重表存儲結(jié)構(gòu),構(gòu)造無向圖G。　　Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)；　　//在G中刪除邊<v,w>。　　Status DeleteVex(AMLGraph &G,VertexType v)；&l

32、t;/p>　　//在G中刪除頂點(diǎn)v及其相關(guān)的邊。　　void DestroyGraph(AMLGraph &G)；　　//銷毀一個圖　　void Display(AMLGraph G)；　　//輸出

33、無向圖的鄰接多重表G。　　void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType))；　　//從start頂點(diǎn)起,（利用棧非遞歸）深度優(yōu)先遍歷圖G。　　void BFSTraverse(AMLGraph G,VertexType st

34、art,int(*Visit)(VertexType))；　　//從start頂點(diǎn)起,廣度優(yōu)先遍歷圖G。void MarkUnvizited(AMLGraph G)；//置邊的訪問標(biāo)記為未被訪問。其中部分操作的算法如下： void CreateGraph(AMLGraph *p) /*創(chuàng)建無向圖 */<p&g

35、t;　　{ 　　int i,j,k; 　　EBox *q; 　　printf("\n\t\t\t請輸入圖的結(jié)點(diǎn)個數(shù)和邊的個數(shù):"); 　　/*輸入圖的結(jié)點(diǎn)數(shù)和邊數(shù)*/&l

36、t;/p>　　scanf("%d,%d",&p->vexnum,&p->edgenum); 　　for(i=1;i<=p->vexnum;i++) 　　{ printf("\n\t\t\t請輸入結(jié)點(diǎn)%d的名稱:",i);/*輸入頂點(diǎn)數(shù)據(jù)信

37、息*/　　scanf("%s",p->list[i].data); 　　p->list[i].fistedge=NULL; /*初始化指針*/ 　　} <p&g

38、t;　　for(k=0;k<p->edgenum;k++) /*輸入各邊并構(gòu)造多重鏈表*/ 　　{ printf("\n\t\t\t請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):");　　scanf("%d,%d",&i,&j);

39、　q=(EBox *)malloc(sizeof(EBox));　　q->mark=0; /*對邊結(jié)點(diǎn)賦值*/　　q->ivex=i;　　q->ilink=p->list[i].fistedge;&l

40、t;p>　　q->jvex=j;　　q->jlink=p->list[j].fistedge;　　p->list[i].fistedge=p->list[j].fistedge=q; /*完成邊在鏈頭的插入*/　　}

41、　　printf("\n");　　}　　void DFS(AMLGraph *p, int v) 　　{ /*對第v個頂點(diǎn)的深度優(yōu)先遍歷 */

42、　　int w; 　　EBox *q; 　　visited[v]=1; /*標(biāo)記已訪問結(jié)點(diǎn) */　　printf("%s ",p->list[v].data);&l

43、t;/p>　　for(q=p->list[v].fistedge;q!=NULL;) 　　{if(q->ivex==v)　　{w=q->jvex; q=q->jlink;} 　　else &

44、lt;p>　　{w=q->ivex; q=q->ilink;} 　　if(!visited[w]) DFS(p,w); /*對尚未訪問的點(diǎn)調(diào)用DFS*/　　} 　　}

45、　　void DFSTraverse(AMLGraph *p,int n) 　　{ /*深度優(yōu)先遍歷 */　　int v;　　printf("\n

46、\t\t\t");　　for(v=1;v<=p->vexnum;v++) 　　visited[v]=0; *訪問標(biāo)志數(shù)組初始化*/ 　　DFS(p,n); /*對起

47、始頂點(diǎn)調(diào)用DFS*/ 　　for(v=1;v<=p->vexnum;v++) 　　if(!visited[v]) DFS(p,v); /*對尚未訪問的頂點(diǎn)調(diào)用DFS*/　　printf("\n");

48、　　} 　　2、隊(duì)列類型　　typedef int QelemType；　　typedef struct QNode{　　QElemType data;</p&

49、gt;　　struct QNode *next;　　}QNode,*QueuePtr;　　typedef struct{　　QueuePtr front;　　QueuePtr rear; /* 隊(duì)頭、隊(duì)尾指針 */<p&

50、gt;　　}LinkQueue;　　隊(duì)列的基本操作如下：Status InitQueue(LinkQueue &Q)；//構(gòu)造一個空隊(duì)列Q。Status DestroyQueue(LinkQueue &Q)；//銷毀隊(duì)列Q(無論空否均可)。Status QueueEmpty(LinkQueue Q)；//若Q為空隊(duì)列,則返回1,否則返回-1。Status EnQue

51、ue(LinkQueue &Q,QElemType e)；//插入元素e為Q的新的隊(duì)尾元素。Status DeQueue(LinkQueue &Q,QElemType &e)；//若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回1,否則返回-1。　　其中部分操作的算法如下：　　void BFS(AMLGraph *p,in

52、t v) 　　{ /*對第v個頂點(diǎn)進(jìn)行廣度優(yōu)先遍歷*/ 　　int u,w; 　　EBox *x; 　　typedef struct queue

53、;　　{ 　　int m; 　　struct queue *next; 　　}Q; /*輔助隊(duì)列Q*/ <p&g

54、t;　　Q *head,*tail,*q; 　　head=tail=(Q *)malloc(sizeof(Q)); 　　tail->next=NULL; 　　visited[v]=1; /*標(biāo)記已訪問結(jié)點(diǎn) */&l

55、t;p>　　printf("%s ",p->list[v].data);　　tail->m=v; /*v入隊(duì)列 */ 　　tail->next=(Q *)malloc(sizeof(Q)); 　　ta

56、il=tail->next; 　　tail->next=NULL; 　　while(head!=tail)　　{ 　　q=head; 　　head=head->

57、;next; 　　u=q->m; /*對頭元素出隊(duì)并置為u*/ 　　free(q); 　　for(x=p->list[u].fistedge;x!=NULL;) 　　{ if(x->

58、;ivex==u) {w=x->jvex;x=x->ilink;}　　else {w=x->ivex;x=x->jlink;} 　　if(!visited[w])　　{ 　　visited[w]=

59、1; 　　printf("%s ",p->list[w].data);　　tail->m=w; /*w入隊(duì)列*/　　tail=tail->next=(Q *)malloc(sizeof(Q)); </p&

60、gt;　　tail->next=NULL; 　　} /*if*/　　} /*for */　　} /*while*/　　} /*BFS*/</

61、p>　　void BFSTraverse(AMLGraph *p,int n) 　　{ printf("\n\t\t\t"); /*廣度優(yōu)先遍歷*/　　int v;

62、　　for(v=1;v<=p->vexnum;v++) 　　visited[v]=0; /*訪問標(biāo)志數(shù)組初始化*/ 　　BFS(p,n); /*對起始頂點(diǎn)調(diào)用BFS*/

63、for(v=1;v<=p->vexnum;v++) 　　if(!visited[v]) BFS(p,v);　　printf("\n"); /*對未訪問頂點(diǎn)調(diào)用BFS*/　　}

64、　　3、主程序和其他偽碼算法 void main (){顯示菜單；輸入功能選擇鍵；switch(flag){case 1:手動構(gòu)造一個圖；case 2:進(jìn)行深度優(yōu)先遍歷圖；case 3:進(jìn)行廣度優(yōu)先遍歷圖； case 4:退出程序；}算法代碼　　main() /*主函數(shù) */ &l

65、t;/p>　　{ int x,n; 　　AMLGraph graph,*p; 　　p=&graph;　　system("color 1f");　　printf(&qu

66、ot;\t\t\t****** 圖的深度和廣度優(yōu)先遍歷 *******\n");　　printf("\t\t\t* *\n");　　printf("\t\t\t****** ********\n"

67、);　　printf("\n");　　while(1)　　{ printf("\n");　　printf("\t\t\t ~~~~~~~~ 功能菜單

68、 ~~~~~~~ \n");　　printf("\n");　　printf("\t\t\t*********************************************\n");　　printf("\t\t\t*

69、 1.創(chuàng)建圖 *\n");　　printf("\t\t\t* *\n");　　printf("\t\t\t* 2.深度優(yōu)先遍歷圖 *\n&q

70、uot;);　　printf("\t\t\t* *\n");　　printf("\t\t\t* 3.廣度優(yōu)先遍歷圖 *\n");　　prin

71、tf("\t\t\t* *\n");　　printf("\t\t\t* 4.退出系統(tǒng) *\n");　　printf("\t\t\t*

72、 *\n");　　printf("\t\t\t*********************************************\n");　　printf("\n\t\t\t請輸入選擇的功能編號（1-4）："); &l

73、t;p>　　scanf("%d",&n);　　if(n<0 || n>4)　　{　　printf("\n\n\t\t\t你輸入的功能號錯誤，請重新輸入，按Enter鍵繼續(xù)??！");<

74、;p>　　getchar();　　getchar();　　continue;　　}　　switch(n)<

75、;b>　　{　　case 1: system("color 3f");　　CreateGraph(p);break;　　case 2: { system("color 79");　　printf(&

76、quot;\n\t\t\t請輸入起始遍歷結(jié)點(diǎn):");　　scanf("%d",&x); 　　printf("\n\t\t\t深度優(yōu)先遍歷結(jié)果為:"); 　　printf("\n");　　DF

77、STraverse(p,x);　　printf("\n");　　} break;　　case 3: { system("color 2E");　　printf("\n\t\t\t請

78、輸入起始遍歷結(jié)點(diǎn):");　　scanf("%d",&x); 　　printf("\n\t\t\t廣度優(yōu)先遍歷結(jié)果為:"); 　　printf("\n");　　BFSTraverse(p,x);&

79、lt;/p>　　printf("\n"); 　　} break;　　case 4: printf("\n\n\t\t\t謝謝你的使用！\n\n\n");　　exit(0);</b

80、>　　}/*switch */ 　　} /*while */　　} /*main */　　第四章、調(diào)試分析1、本程序以鄰接多重表為存儲結(jié)構(gòu)。這個程序涉及到圖的生成和圖的深度以及廣度遍歷,文件的保存和讀取，還有棧和隊(duì)列的操

81、作，另外還有森林的生成和打印，路徑的尋找。2、本程序不僅可以進(jìn)行連通無向圖的遍歷，還可以進(jìn)行非連通圖的遍歷。為了方便顯示和理解，現(xiàn)在暫且用一個大寫字母表示一個頂點(diǎn)。邊還可以附加信息，但為了方便操作，暫且不輸入信息。已經(jīng)先把圖的相關(guān)信息保存在了文本文檔里，所以要測試時(shí)直接從文件導(dǎo)入，可以減少用手輸入的麻煩，同時(shí)也可以減少輸入的錯誤。3、由于構(gòu)造圖時(shí)，后輸入的邊是插在先輸入的邊的前面。所以在輸入邊時(shí)，可以按字母從大到小的順序輸入。那么顯

82、示圖的時(shí)候就可以按字母從小到大的順序顯示。4、程序定義了一個二倍頂點(diǎn)長的數(shù)組存放輸入的邊，以便程序可以把它保存到文件里。故耗費(fèi)了一定的內(nèi)存空間。第五章、用戶手冊1、本程序的運(yùn)行環(huán)境DOS操作系統(tǒng)，GTraverse.exe2、進(jìn)入演示程序后即顯示一個有功能選擇的界面，如下：3、選擇操作1：程序就提示分別輸入無向圖的頂點(diǎn)數(shù)，邊數(shù)，邊的信息，頂點(diǎn)和邊的值：輸入完成后</p

83、>　　5、選擇操作3：系統(tǒng)提示輸入遍歷圖的起始點(diǎn)，程序運(yùn)行后，首先顯示廣度優(yōu)先遍歷的訪問結(jié)點(diǎn)序列。　　6、選擇操作4：退出程序。　　第六章、測試結(jié)果1、數(shù)據(jù)可以任意輸入,但是頂點(diǎn)數(shù)不要太多，不然占用太多內(nèi)存，會導(dǎo)致死機(jī)。2、遍歷一個連通的無向圖，如遍歷以下這個連通無向圖：　　1)

84、選擇操作1，分別進(jìn)行以下操作:　　請輸入圖的結(jié)點(diǎn)個數(shù)和邊的個數(shù):4,5　　請輸入結(jié)點(diǎn)1的名稱:A 　　請輸入結(jié)點(diǎn)2的名稱:B　　請輸入結(jié)點(diǎn)3的名稱:C　　請輸入結(jié)點(diǎn)4的名稱:D　　請輸入互

85、相有關(guān)聯(lián)的兩個結(jié)點(diǎn):1,2　　請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):1,3　　請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):1,4　　請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):2,4　　請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):3,4　　2) 選擇操作2，輸出圖的信息如下：</p

86、>　　請輸入起始遍歷結(jié)點(diǎn):1　　深度優(yōu)先遍歷結(jié)果為:A B D C　　3) 選擇操作3，輸出圖的信息如下：　　請輸入起始遍歷結(jié)點(diǎn):1　　廣度優(yōu)先遍歷結(jié)果為:A B C D　　第七章、心得體會這道題的完

87、成，花了一個星期時(shí)間，因?yàn)槲乙粋€多學(xué)期沒接觸C語言和數(shù)據(jù)結(jié)構(gòu)首先我把基本功能完成后來逐步地增加了許多功能。把本來只能遍歷連通圖的功能上，改進(jìn)為可以遍歷非連通圖。通過這道設(shè)計(jì)題,使我更深刻的理解數(shù)據(jù)結(jié)構(gòu)及其重要作用,對數(shù)據(jù)結(jié)構(gòu)有了一個新的認(rèn)識,深刻的認(rèn)識到數(shù)據(jù)結(jié)構(gòu)對于我們學(xué)習(xí)計(jì)算機(jī)的重要性和其深遠(yuǎn)但是意義.同時(shí),通過這次課程設(shè)計(jì),也加強(qiáng)我的動手能力和思維能力,可以將自己所學(xué)的知識用于實(shí)踐,這不僅對自己是一次鍛煉機(jī)會,而且讓自己有一種成就感

88、和自豪感，覺得自己終于可以做出一點(diǎn)有用的東西了。不過,我覺得自己編寫程序的一些思路算法和水平還非常有限。所以以后自己還得在C語言和其他語言上下苦功夫。　　附：源程序　　#include <stdio.h> 　　#include <stdlib.h>

89、; 　　#define MAX_VERTEX_NUM 30 /*無向圖最大頂點(diǎn)數(shù)*/ 　　#define MAX_LEN 20 /*數(shù)據(jù)最大長度 */　　int visited[MAX_VERTEX_N

90、UM]; /*全局變量，訪問標(biāo)志數(shù)組 */ 　　typedef struct EBox /*邊結(jié)點(diǎn)類型*/ 　　{ 　　int mark;

91、 /*訪問標(biāo)記 */ 　　int ivex,jvex; /*該邊依附的兩個頂點(diǎn)位置*/　　struct EBox *ilink,*jlink; /*分別指向依附這兩個頂點(diǎn)的下一條邊 */

92、　　}EBox; 　　typedef struct VexBox /*頂點(diǎn)結(jié)點(diǎn)類型*/ 　　{　　char data[MAX_LEN]; </p

93、>　　EBox *fistedge; /*指向第一條依附該頂點(diǎn)的邊*/ 　　}VexBox; 　　typedef struct　　{ <p&g

94、t;　　VexBox list[MAX_VERTEX_NUM]; 　　int vexnum,edgenum; /*無向圖當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */ 　　}AMLGraph; 　　void CreateGraph(AMLGraph *p)

95、 /*創(chuàng)建無向圖 */　　{ 　　int i,j,k; 　　EBox *q; 　　printf("\n\t\t\t請輸入圖的結(jié)點(diǎn)個數(shù)和邊的個數(shù):&qu

96、ot;); /*輸入圖的結(jié)點(diǎn)數(shù)和邊數(shù)*/　　scanf("%d,%d",&p->vexnum,&p->edgenum); 　　for(i=1;i<=p->vexnum;i++) 　　{ printf("\n\t\t\t請輸入結(jié)點(diǎn)

97、%d的名稱:",i); /*輸入頂點(diǎn)數(shù)據(jù)信息*/　　scanf("%s",p->list[i].data); 　　p->list[i].fistedge=NULL; /*初始化指針*/

98、} 　　for(k=0;k<p->edgenum;k++) /*輸入各邊并構(gòu)造多重鏈表*/ 　　{ printf("\n\t\t\t請輸入互相有關(guān)聯(lián)的兩個結(jié)點(diǎn):");　　scanf("%d,%d&quo

99、t;,&i,&j);　　q=(EBox *)malloc(sizeof(EBox));　　q->mark=0; /*對邊結(jié)點(diǎn)賦值*/　　q->ivex=i;　　q->

100、;ilink=p->list[i].fistedge;　　q->jvex=j;　　q->jlink=p->list[j].fistedge;　　p->list[i].fistedge=p->list[j].fistedge=q; /*完成邊在鏈頭的插入*/</

101、p>　　}　　printf("\n");　　}　　void DFS(AMLGraph *p, int v) 　　{

102、 /*對第v個頂點(diǎn)的深度優(yōu)先遍歷 */　　int w; 　　EBox *q; 　　visited[v]=1; /*標(biāo)記已訪問結(jié)點(diǎn) */

103、　　printf("%s ",p->list[v].data);　　for(q=p->list[v].fistedge;q!=NULL;) 　　{if(q->ivex==v)　　{w=q->jvex; q=q->jlink;} <

104、;/p>　　else 　　{w=q->ivex; q=q->ilink;} 　　if(!visited[w]) DFS(p,w); /*對尚未訪問的點(diǎn)調(diào)用DFS*/　　} </

105、b>　　}　　void DFSTraverse(AMLGraph *p,int n) 　　{ /*深度優(yōu)先遍歷 */<b&g

106、t;　　int v;　　printf("\n\t\t\t");　　for(v=1;v<=p->vexnum;v++) 　　visited[v]=0; /*訪問標(biāo)志數(shù)組初始化*/

107、　　DFS(p,n); /*對起始頂點(diǎn)調(diào)用DFS*/ 　　for(v=1;v<=p->vexnum;v++) 　　if(!visited[v]) DFS(p,v); /*對尚未訪問的頂點(diǎn)調(diào)用DFS*/

108、　　printf("\n"); 　　} 　　void BFS(AMLGraph *p,int v) 　　{ /

109、*對第v個頂點(diǎn)進(jìn)行廣度優(yōu)先遍歷*/ 　　int u,w; 　　EBox *x; 　　typedef struct queue　　{ 　　int m; &

110、lt;/b>　　struct queue *next; 　　}Q; /*輔助隊(duì)列Q*/ 　　Q *head,*tail,*q; 　　head=tail=(Q *)mallo

111、c(sizeof(Q)); 　　tail->next=NULL; 　　visited[v]=1; /*標(biāo)記已訪問結(jié)點(diǎn) */　　printf("%s ",p->list[v].data);<

112、p>　　tail->m=v; /*v入隊(duì)列 */ 　　tail->next=(Q *)malloc(sizeof(Q)); 　　tail=tail->next; 　　tail->next=NULL; <

113、;/p>　　while(head!=tail)　　{ 　　q=head; 　　head=head->next; 　　u=q->m;

114、 /*對頭元素出隊(duì)并置為u*/ 　　free(q); 　　for(x=p->list[u].fistedge;x!=NULL;) 　　{ if(x->ivex==u) {w=x->jvex;x=x->ilink;}<p&g

115、t;　　else {w=x->ivex;x=x->jlink;} 　　if(!visited[w])　　{ 　　visited[w]=1; 　　printf("%s ",p->l

116、ist[w].data);　　tail->m=w; /*w入隊(duì)列*/　　tail=tail->next=(Q *)malloc(sizeof(Q)); 　　tail->next=NULL;

117、;　　} /*if*/　　} /*for */　　} /*while*/　　} /*BFS*/　　void BFSTraverse(AMLGraph *p,int n) &l

118、t;/p>　　{ printf("\n\t\t\t"); /*廣度優(yōu)先遍歷*/　　int v;　　for(v=1;v<=p->vexnum;v++) <p&

119、gt;　　visited[v]=0; /*訪問標(biāo)志數(shù)組初始化*/ 　　BFS(p,n); /*對起始頂點(diǎn)調(diào)用BFS*/ 　　for(v=1;v<=p->vexnum;v++) <

120、p>　　if(!visited[v]) BFS(p,v);　　printf("\n"); /*對未訪問頂點(diǎn)調(diào)用BFS*/　　}　　main()

121、 /*主函數(shù) */ 　　{ int x,n; 　　AMLGraph graph,*p; 　　p=&graph;　　system("color 1f");<p&

122、gt;　　printf("\t\t\t****** 圖的深度和廣度優(yōu)先遍歷 *******\n");　　printf("\t\t\t* *\n");　　printf("\t\t\t****** **

123、******\n");　　printf("\n");　　while(1)　　{ printf("\n");　　printf("\t\t\t ~~~~~~~~

124、功能菜單 ~~~~~~~ \n");　　printf("\n");　　printf("\t\t\t*********************************************\n");　　printf("\t\t\

125、t* 1.創(chuàng)建圖 *\n");　　printf("\t\t\t* *\n");　　printf("\t\t\t* 2.深度優(yōu)先遍歷圖

126、 *\n");　　printf("\t\t\t* *\n");　　printf("\t\t\t* 3.廣度優(yōu)先遍歷圖 *\n");&

127、lt;p>　　printf("\t\t\t* *\n");　　printf("\t\t\t* 4.退出系統(tǒng) *\n");　　printf("\t\t\t*

128、 *\n");　　printf("\t\t\t*********************************************\n");　　printf("\n\t\t\t請輸入選擇的功能編號（1-4）：");

129、　　scanf("%d",&n);　　if(n<0 || n>4)　　{　　printf("\n\n\t\t\t你輸入的功能號錯誤，請重新輸入，按Enter鍵繼續(xù)??！");&

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(圖的遍歷)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(圖的遍歷)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載