數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)報(bào)告課程名：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）實(shí)驗(yàn)名：圖的遍歷姓 名： 班 級(jí)： 學(xué) 號(hào)： 時(shí) 間：2014.11.15一 實(shí)驗(yàn)?zāi)康呐c要求1. 掌握?qǐng)D的遍歷的方法2. 利用 C 語(yǔ)言實(shí)現(xiàn)圖的遍歷二 實(shí)驗(yàn)內(nèi)容 將一個(gè)圖存儲(chǔ)起來(lái) 對(duì)該圖分別進(jìn)行先深和先廣遍歷三 實(shí)驗(yàn)結(jié)果與分析程序：#include <stdlib.h>#include <stdio.h>#define INFINITY 32767#define MAX_VEX 20 /最大頂點(diǎn)個(gè)數(shù)#define QUEUE_SIZE (MAX_VEX+1) /隊(duì)列長(zhǎng)度/using namespace std

2、;bool *visited; /訪問(wèn)標(biāo)志數(shù)組,避免同一頂點(diǎn)多次訪問(wèn)/*圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)*/typedef struct char *vexs; /頂點(diǎn)向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)Graph;/*隊(duì)列類(lèi)*/class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_

3、SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear;/*圖G中查找元素c的位置*/int Locate(Graph G,char c) for(int i=0;i<G.vexnum;i+) if(G.vexsi=c) return i; return -1;/*創(chuàng)建無(wú)向網(wǎng)*/void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf("

4、輸入頂點(diǎn)數(shù)和弧數(shù):"); scanf("%d%d",&G.vexnum,&G.arcnum); temp=getchar(); /接收回車(chē) G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點(diǎn)數(shù)目 printf("輸入%d個(gè)頂點(diǎn).n",G.vexnum); for(i=0;i<G.vexnum;i+) /初始化頂點(diǎn) printf("輸入頂點(diǎn)%d:",i); scanf("%c",&G.vexsi); temp=getchar()

5、; /接收回車(chē) for(i=0;i<G.vexnum;i+) /初始化鄰接矩陣 for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; printf("輸入%d條弧.n",G.arcnum); for(i=0;i<G.arcnum;i+) /初始化弧 printf("輸入弧%d:",i); scanf("%c %c %d",&a,&b,&w); /輸入一條邊依附的頂點(diǎn)和權(quán)值 temp=getchar(); /接收回車(chē) s1=Locate(G,a); s2=Locat

6、e(G,b); G.arcss1s2=G.arcss2s1=w; /*圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn)*/int FirstVex(Graph G,int k) if(k>=0 && k<G.vexnum) /k合理 for(int i=0;i<G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1;/*圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)*/int NextVex(Graph G,int i,int j) if(i>=0 && i<G.vexnum &&

7、j>=0 && j<G.vexnum) /i,j合理 for(int k=j+1;k<G.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1;/*深度優(yōu)先遍歷*/void DFS(Graph G,int k) int i; if(k=-1) /第一次執(zhí)行DFS時(shí),k為-1 for(i=0;i<G.vexnum;i+) if(!visitedi) DFS(G,i); /對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS else visitedk=true; printf("%c ",G.vexsk);

8、/訪問(wèn)第k個(gè)頂點(diǎn) for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /對(duì)k的尚未訪問(wèn)的鄰接頂點(diǎn)i遞歸調(diào)用DFS /*廣度優(yōu)先遍歷*/void BFS(Graph G) int k; Queue Q; /輔助隊(duì)列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visitedi) /i尚未訪問(wèn) visitedi=true; printf("%c ",G.vexsi); Q.EnQueue(i); /i入列 while(Q.front!=Q

9、.rear) Q.DeQueue(k); /隊(duì)頭元素出列并置為k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w) if(!visitedw) /w為k的尚未訪問(wèn)的鄰接頂點(diǎn) visitedw=true; printf("%c ",G.vexsw); Q.EnQueue(w); /*主函數(shù)*/void main() int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf("n廣度優(yōu)先遍歷: "); for(i=0;i<