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

數(shù)據(jù)結(jié)構(gòu)圖實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)圖實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)圖實(shí)驗(yàn)報(bào)告xxx公司數(shù)據(jù)結(jié)構(gòu)圖實(shí)驗(yàn)報(bào)告文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握?qǐng)D的相關(guān)概念，包括圖，有向圖，無(wú)向圖，完全圖，子圖，連通圖，度，入度，出度，簡(jiǎn)單回路和環(huán)等定義。（2）重點(diǎn)掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)，包括鄰接矩陣和鄰接表等。（3）重點(diǎn)掌握?qǐng)D的基本運(yùn)算，包括創(chuàng)建圖，輸出圖，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等。（4）掌握?qǐng)D的其他運(yùn)算，包括最小生成樹(shù)，最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑等算法。（5）靈活運(yùn)用圖這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問(wèn)題。二、實(shí)驗(yàn)內(nèi)容和方法(1)實(shí)驗(yàn)內(nèi)容：1、編寫(xiě)一個(gè)程序，實(shí)現(xiàn)不帶權(quán)圖和帶權(quán)圖的鄰接矩陣與鄰接表的相互轉(zhuǎn)換算法、輸出鄰接矩陣與鄰接表的算法，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)如下功能：①建立如圖1所示的有向圖G的鄰接矩陣，并輸出；②由有向圖G的鄰接矩陣產(chǎn)生鄰接表，并輸出；③再由②的鄰接表產(chǎn)生對(duì)應(yīng)的鄰接矩陣，并輸出。11569758453015243圖12、編寫(xiě)一個(gè)程序，實(shí)現(xiàn)圖的遍歷運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)程序完成如下功能：①輸出圖1所示的有向圖G從頂點(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列（遞歸算法）；②輸出圖1所示的有向圖G從頂點(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列（非遞歸算法）；③輸出圖1所示的有向圖G從頂點(diǎn)0開(kāi)始的廣度優(yōu)先遍歷序列。3、設(shè)計(jì)一個(gè)程序,采用鄰接表存儲(chǔ)圖，并輸出圖（a）中從指定頂點(diǎn)1出發(fā)的所有深度優(yōu)先遍歷序列。(2)實(shí)驗(yàn)方法：1、綜合運(yùn)用課本所學(xué)的知識(shí)，用不同的算法實(shí)現(xiàn)在不同的程序功能。2、結(jié)合指導(dǎo)老師的指導(dǎo)，解決程序中的問(wèn)題，正確解決實(shí)際中存在的異常情況，逐步改善功能。3、根據(jù)實(shí)驗(yàn)內(nèi)容，編譯程序。三、實(shí)驗(yàn)環(huán)境：Windows7，VisualC++三、實(shí)驗(yàn)過(guò)程描述文件中定義了圖的鄰接矩陣表示類型和鄰接表表示類型，該頭文件在以下三個(gè)實(shí)驗(yàn)中都會(huì)使用到。其代碼如下：#ifndefGRAPH_H_INCLUDED#ifndefGRAPH_H_INCLUDED#defineGRAPH_H_INCLUDEDtypedefintInfoType;#defineMAXV100//最大頂點(diǎn)個(gè)數(shù)#defineINF32767//INF表示無(wú)限大//以下定義鄰接矩陣類型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;#endif//GRAPH_H_INCLUDEDVertexTypevexs[MAXV];VertexTypevexs[MAXV];}MGraph;//以下定義鄰接表類型typedefstructANode{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefintVertex;typedefstructVNode{Vertexdata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;#endif//GRAPH_H_INCLUDED實(shí)驗(yàn)①源程序。一、輸入如下所示程序；//文件名：//文件名：#include<>#include<>#include""externvoidMatToList1(MGraph,ALGraph*&);externvoidListToMat1(ALGraph*,MGraph&);externvoidDispMat1(MGraph);externvoidDispAdj1(ALGraph*);intmain()intmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][6]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};=6;=10;for(i=0;i<;i++)for(j=0;j<;j++)[i][j]=A[i][j];printf("有向圖G的鄰接矩陣：\n");DispMat1(g);G=(ALGraph*)malloc(sizeof(ALGraph));printf("圖G的鄰接矩陣轉(zhuǎn)換成鄰接表：\n");MatToList1(g,G);DispAdj1(G);printf("圖G的鄰接表轉(zhuǎn)換成鄰接矩陣：\n");ListToMat1(G,g1);DispMat1(g1);return0;}//文件名：//文件名：#include<>#include<>#include""http://不帶權(quán)圖的算法voidMatToList(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<;i++)for(j=;j>=0;j--)if[i][j]!=0)if[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->e=;}voidListToMat(ALGraph*G,MGraph&g){inti,j;ArcNode*p;for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)[i][j]=0;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){[i][p->adjvex]=1;p=p->nextarc;}}=G->n;=G->e;}voidDispMat(MGraphg){inti,j;for(i=0;i<;i++){for(j=0;j<;j++)printf("%3d",[i][j]);printf("\n");}}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");}}irstarc=NULL;for(i=0;i<;i++)for(j=;j>=0;j--)if[i][j]!=0&&[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=;G->e=;}voidListToMat1(ALGraph*G,MGraph&g){inti,j;ArcNode*p;for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)if(i==j)[i][j]=0;else[i][j]=INF;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){[i][p->adjvex]=p->info;p=p->nextarc;}}=G->n;=G->e;}voidDispMat1(MGraphg){inti,j;for(i=0;i<;i++){for(j=0;j<;j++)if[i][j]==INF)printf("%3s","∞");elseprintf("%3d",[i][j]);printf("\n");}}voidDispAdj1(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(%d)",p->adjvex,p->info);p=p->nextarc;}printf("\n");}}voidDispAdj1(ALGraph*G)voidDispAdj1(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(%d)",p->adjvex,p->info);p=p->nextarc;}printf("\n");}}二、編譯并鏈接程序；三、運(yùn)行程序，結(jié)果如下圖：實(shí)驗(yàn)eq\o\ac(○,2)源程序一、輸入如下所示程序；//文件名：//文件名：#include<>#include<>#include""externvoidMatToList1(MGraph,ALGraph*&);externvoidDispAdj1(ALGraph*G);externvoidDFS(ALGraph*G,intv);externvoidDFS1(ALGraph*G,intv);externvoidDFS2(ALGraph*G,intv);externvoidBFS(ALGraph*G,intv);intmain(){inti,j;MGraphg;ALGraph*G;intA[MAXV][6]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};=6;=10;for(i=0;i<;i++)for(j=0;j<;j++)[i][j]=A[i][j];G=(ALGraph*)malloc(sizeof(ALGraph));MatToList1(g,G);printf("圖G的鄰接表：\n");DispAdj1(G);printf("從頂點(diǎn)0開(kāi)始的DFS（遞歸算法）：\n");DFS(G,0);printf("\n");printf("從頂點(diǎn)0開(kāi)始的DFS（非遞歸算法）：\n");DFS1(G,0);printf("\n");printf("從頂點(diǎn)0開(kāi)始的BFS：\n");BFS(G,0);printf("\n");returne0；}irstarirstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}voidDFS1(ALGraph*G,intv)irstarc;while(top>-1){p=St[top];top--;while(p!=NULL){w=p->adjvex;if(visited[w]==0){printf("%3d",w);visited[w]=1;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intvisited[MAXV];intw,i;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);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("%3d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidMatToList1(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<;i++)for(j=;j>=0;j--)if[i][j]!=0&&[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=;G->e=;}voidDispAdj1(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(%d)",p->adjvex,p->info);p=p->nextarc;}printf("\n");}}top++;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intvisited[MAXV];intw,i;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);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("%3d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidMatToList1(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<;i++)for(j=;j>=0;j--)if[i][j]!=0&&[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=;G->e=;}voidDispAdj1(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(%d)",p->adjvex,p->info);p=p->nextarc;}printf("\n");}}voidMatToList1(MGraphg,ALGraph*&G)voidMatToList1(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<;i++)for(j=;j>=0;j--)if[i][j]!=0&&[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=;G->e=;}voidDispAdj1(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(%d)",p->adjvex,p->info);p=p->nextarc;}printf("\n");}}二、對(duì)程序進(jìn)行編譯鏈接；三、運(yùn)行該程序，結(jié)果如圖實(shí)驗(yàn)③源程序。一、輸入如下所示程序；#include<>#include<>#include<>#include""externvoidMatToList(MGraph,ALGraph*&);externvoidDispAdj(ALGraph*);intvisited[MAXV];voidDFSALL(ALGraph*G,intv,intpath[],intd){ArcNode*p;visited[v]=1;path[d]=v;d++;if(d==G->n){for(intk=0;k<d;k++)printf("%2d",path[k]);printf("\n");}p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFSALL(G,p->adjvex,path,d);p=p->nextarc;}visited[v]=0;}intmain(){intpath[MAXV],i,j,v=1;MGraphg;ALGraph*G;=5;=8;intA[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};for(i=0;i<;i++)for(j=0;j<;j++)[i][j]=A[i][j];MatToList(g,G);for(i=0;i<;i++)visited[i]=0;printf("圖G的鄰接表：\n");DispAdj(G);printf("從頂點(diǎn)%d出發(fā)的所有深度優(yōu)先序列：\n",v);DFSALL(G,v,path,0);printf("\n");return0;}voidMatToList(MGraphg,ALGraph*&G){inti,j;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<;i++)for(j=;j>=0;j--)if[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->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");}}if(visited[p->adjvex]==0)if(visited[p->adjvex]==0)DFSALL(G,p->adjvex,path,d);p=p->nextarc;}visited[v]=0;}intmain(){intpath[MAXV],i,j,v=1;MGraphg;ALGraph*G;=5;=8;intA[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};for(i=0;i<;i++)for(j=0;j<;j++)[i][j]=A[i][j];MatToList(g,G);for(i=0;i<;i+