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

計(jì)算機(jī)科學(xué)與工程學(xué)院PAGEPAGE2《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告計(jì)算機(jī)科學(xué)與工程學(xué)院《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告(七)專(zhuān)業(yè)班級(jí)2017級(jí)實(shí)驗(yàn)地點(diǎn)503機(jī)房學(xué)生學(xué)號(hào)1710050108指導(dǎo)教師姚峰學(xué)生姓名劉政林實(shí)驗(yàn)時(shí)間20XX-XX-XX實(shí)驗(yàn)項(xiàng)目圖的應(yīng)用一實(shí)驗(yàn)類(lèi)別基礎(chǔ)性（）設(shè)計(jì)性（√）綜合性（）其它（）實(shí)驗(yàn)?zāi)康募耙螅?）熟練掌握?qǐng)D的基本存儲(chǔ)方法；

（2）熟練掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法。成績(jī)?cè)u(píng)定表類(lèi)別評(píng)分標(biāo)準(zhǔn)分值得分合計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律按要求完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分說(shuō)明：評(píng)閱教師：姚峰

日期：20年月日實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容：圖的兩種遍歷方法及對(duì)應(yīng)的生成樹(shù)。自己編寫(xiě)源程序，把圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷改為輸出深度優(yōu)先生成樹(shù)、廣度優(yōu)先生成樹(shù)。實(shí)驗(yàn)說(shuō)明：

（1）讀懂教師給定的程序或課本的程序；（2）輸入圖；（3）把顯示遍歷序列改為顯示深度優(yōu)先、廣度優(yōu)先生成樹(shù)。#include<stdio.h>#include<malloc.h>#defineMAXV100#defineINF1024typedefintInfotype;typedefstruct{ intno; Infotypeinfo;} Vertextype;typedefstruct{ intedges[MAXV][MAXV]; intn,e; Vertextypevexs[MAXV];}Mgraph;typedefstructAnode{ intadjvex; structAnode*nextarc; Infotypeinfo;}Arcnode;typedefintVertex;typedefstructVNode{ Vertexdata; Arcnode*firstarc;}Vnode;typedefVnodeAdjlist[MAXV];typedefstruct{ Adjlistadjlist; intn,e;}Algraph;voidMattolist(Mgraphg,Algraph*&G){ inti,j; Arcnode*p; G=(Algraph*)malloc(sizeof(Algraph)); for(i=0;i<g.n;i++) G->adjlist[i].firstarc=NULL; for(i=0;i<g.n;i++) for(j=g.n-1;j>=0;j--) if(g.edges[i][j]!=0) { p=(Arcnode*)malloc(sizeof(Arcnode)); p->adjvex=j; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; } G->n=g.n;G->e=g.e;}voidDispadj(Algraph*G){ inti; Arcnode*p; for(i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; printf("%3d:",i); while(p!=NULL) { printf("%3d",p->adjvex); p=p->nextarc;} printf("\n"); }}intvisited[MAXV];voidDFS(Algraph*G,intv){ Arcnode*p; visited[v]=1; p=G->adjlist[v].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf("<%d,%d>",v,p->adjvex); DFS(G,p->adjvex);} p=p->nextarc; }}voidBFS(Algraph*G,intv){ Arcnode*p; intqueue[MAXV],front=0,rear=0; intw,i; for(i=0;i<G->n;i++) visited[i]=0; visited[v]=1; rear=(rear+1)%MAXV; queue[rear]=v; while(front!=rear) { front=(front+1)%MAXV; w=queue[front]; p=G->adjlist[w].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf("<%d,%d>",w,p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex;} p=p->nextarc;}} printf("\n");}voidmain(){ inti,j; Mgraphg; Algraph*G; intA[MAXV][11]={{0,1,1,1,0,0,0,0,0,0,0},{1,0,0,0,1,1,0,0,0,0,0}, {1,0,0,1,0,1,1,0,0,0,0},{1,0,1,0,0,0,0,1,0,0,0},{0,1,0,0,0,0,0,0,0,0,0}, {0,1,1,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,0,1,1,1,0},{0,0,0,1,0,0,1,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,0,1,0,0,0}}; g.n=11; g.e=13; for(i=0;i<g.n;i++) for(j=0;j<g.n;j++) g.edges[i][j]=A[i][j]; G=(Algraph*)malloc(sizeof(Algraph)); Mattolist(g,G); printf("圖G的鄰接表:\n"); Dispadj(G); printf("\n"); for(i=0;i<g.n;i++) visited[i]=0;