數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-圖的基本操作.doc

浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目名稱 實(shí)驗(yàn)十三/十四 圖的基本操作 學(xué)生姓名 專業(yè)班級 學(xué)號 實(shí)驗(yàn)成績 指導(dǎo)老師（簽名 ） 日期 2014/06/09 一. 實(shí)驗(yàn)?zāi)康暮鸵?、掌握圖的主要存儲結(jié)構(gòu)。2、學(xué)會對幾種常見的圖的存儲結(jié)構(gòu)進(jìn)行基本操作。二. 實(shí)驗(yàn)內(nèi)容1、 圖的鄰接矩陣定義及實(shí)現(xiàn)：建立頭文件test13_AdjM.h，在該文件中定義圖的鄰接矩陣存儲結(jié)構(gòu)，并編寫圖的初始化、建立圖、輸出圖、輸出圖的每個(gè)頂點(diǎn)的度等基本操作實(shí)現(xiàn)函數(shù)。同時(shí)建立一個(gè)驗(yàn)證操作實(shí)現(xiàn)的主函數(shù)文件test13.cpp（以下圖為例），編譯并調(diào)試程序，直到正確運(yùn)行。01246532、圖的鄰接表的定義及實(shí)現(xiàn)：建立頭文件test13_AdjL.h，在該文件中定義圖的鄰接表存儲結(jié)構(gòu)，并編寫圖的初始化、建立圖、輸出圖、輸出圖的每個(gè)頂點(diǎn)的度等基本操作實(shí)現(xiàn)函數(shù)。同時(shí)在主函數(shù)文件test13.cpp中調(diào)用這些函數(shù)進(jìn)行驗(yàn)證（以下圖為例）。0011223343、填寫實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告文件取名為report13.doc。4、上傳實(shí)驗(yàn)報(bào)告文件report13.doc到BB。注: 下載p256_GraphMatrix.cpp(鄰接矩陣)和p258_GraphAdjoin.cpp(鄰接表)源程序，讀懂程序完成空缺部分代碼。三. 函數(shù)的功能說明及算法思路 （包括每個(gè)函數(shù)的功能說明，及一些重要函數(shù)的算法實(shí)現(xiàn)思路）四. 實(shí)驗(yàn)結(jié)果與分析（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）5. 心得體會程序比較難寫，但是可以通過之前的一些程序來找到一些規(guī)律（記錄實(shí)驗(yàn)感受、上機(jī)過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）【附錄-源程序】256:/p-255 圖的存儲結(jié)構(gòu)以 數(shù)組鄰接矩陣 表示, 構(gòu)造圖的算法。#include #include #include #include typedef char VertexType; /頂點(diǎn)的名稱為字符const int MaxVertexNum=10; /圖的最大頂點(diǎn)數(shù)const int MaxEdgeNum=100; /邊數(shù)的最大值typedef int WeightType; /權(quán)值的類型const WeightType MaxValue=32767; /權(quán)值的無窮大表示typedef VertexType VexlistMaxVertexNum; /頂點(diǎn)信息，定點(diǎn)名稱typedef WeightType AdjMatrixMaxVertexNumMaxVertexNum; /鄰接矩陣typedef enumDG,DN,AG,AN GraphKind; /有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct Vexlist vexs; / 頂點(diǎn)數(shù)據(jù)元素AdjMatrix arcs; / 二維數(shù)組作鄰接矩陣int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;void CreateGraph(MGraph &G, GraphKind kd)/ 采用數(shù)組鄰接矩陣表示法，構(gòu)造圖G/構(gòu)造有向網(wǎng)G int i,j,k,q;char v, w;G.kind=kd; /圖的種類printf(輸入要構(gòu)造的圖的頂點(diǎn)數(shù)和弧數(shù)：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/過濾回車 printf(依次輸入圖的頂點(diǎn)名稱ABCD.等等：n); for (i=0; iG.vexnum; i+) scanf(%c,&G.vexsi);/構(gòu)造頂點(diǎn)數(shù)據(jù)getchar();/過濾回車 for (i=0; iG.vexnum; i+) /鄰接矩陣初始化for (j=0; j頭頂點(diǎn)名，權(quán)值 輸入數(shù)據(jù):如A-B,23 n);elseprintf(按照： 尾頂點(diǎn)名-頭頂點(diǎn)名輸入數(shù)據(jù):A-Bn); for (k=0; k%c,%d,&v,&w,&q); /輸入弧的兩個(gè)定點(diǎn)及該弧的權(quán)重elsescanf(%c-%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.vexsi=v) break;/查找出v在vexs中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.vexsj=w) break;/查找出v在vexs中的位置j if(j=G.vexnum) cerr頭頂點(diǎn)名，權(quán)值 輸入數(shù)據(jù):如A-B,23a-b,5a-c,8c-b,7a-d,4d-c,3輸出鄰接矩陣 | 5 | 8 | 4 | | | | | | 7 | | | | | 3 | |Press any key to continue*/void PrintMGraph(MGraph &G)int i,j;switch(G.kind) case DG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %2.d | ,G.arcsij); printf(n); break; case DN: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij!=MaxValue) printf( %2.d | ,G.arcsij); else printf( | ); printf(n); break; case AG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %2.d | ,G.arcsij); printf(n); break; case AN: /*完成構(gòu)造無向網(wǎng)* /* 請模仿編寫無向網(wǎng)*/ for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij!=MaxValue) printf( %2.d | ,G.arcsij); else printf( | ); printf(n); break; /*完成函數(shù)*void countdig(MGraph G) /請完成計(jì)算圖的入度或初度if(G.kind=DG|G.kind=DN)/計(jì)算有向圖或網(wǎng)的各個(gè)頂點(diǎn)的入度與出度int outD,inD;int i,j;for(i=0;iG.vexnum;i+)outD=inD=0;for(j=0;jG.vexnum;j+)if(G.arcsij!=0&G.arcsij!=MaxValue)outD+;for(j=0;jG.vexnum;j+)if(G.arcsji!=0&G.arcsji!=MaxValue)inD+;printf(%c：出度是%d,入度是%dn,G.vexsi,outD,inD);else/ 計(jì)算無向圖或網(wǎng)的度int i,j;int Du;for(i=0;iG.vexnum;i+)Du=0;for(j=0;jG.vexnum;j+)if(G.arcsij!=0&G.arcsij!=MaxValue)Du+;printf(%c的度是%dn,G.vexs,Du);/*參照p265設(shè)計(jì)深度有限搜索*void DFSMatrix(MGraph G,int i,int n,bool*visited) coutG.vexsi ; visitedi=true; for(int j=0;jn;j+) if(G.arcsij!=0&G.arcsij!=MaxValue& !visitedj) DFSMatrix(G,j,n,visited);/*參照p268設(shè)計(jì)廣度有限搜索*void BFSMatrix(MGraph G,int i, int n , bool*visited) const int MaxSize=30; int qMaxSize=0; int front=0,rear=0; coutG.vexsi ; visitedi=true; q+rear=i; while(front!=rear) front=(front+1)%MaxSize; int k=qfront; for(int j=0;jn;j+) if(G.arcsij!=0&G.arcsij!=MaxValue& !visitedj) coutG.vexsj ; visitedj=true; rear=(rear+1)%MaxSize; qrear=j; void main()MGraph G; int k;printf(請選擇圖的種類：0:有向圖,1:有向網(wǎng),2:無向圖,3:無向網(wǎng). 請選擇：);scanf(%d,&k);switch(k) /DG,DN,AG,ANcase 0: printf(構(gòu)造有向圖n);CreateGraph(G,DG); / 采用數(shù)組鄰接矩陣表示法，構(gòu)造有向圖break;case 1:printf(構(gòu)造有向網(wǎng)n);CreateGraph(G,DN); / 采用數(shù)組鄰接矩陣表示法，構(gòu)造有向網(wǎng)AGGbreak;case 2:printf(構(gòu)造無向圖n);CreateGraph(G,AG); / 采用數(shù)組鄰接矩陣表示法，構(gòu)造無向圖AGGbreak;case 3:printf(構(gòu)造無向網(wǎng)n);CreateGraph(G,AN); / 采用數(shù)組鄰接矩陣表示法，構(gòu)造無向網(wǎng)AGGbreak;PrintMGraph(G); /打印圖的鄰接矩陣bool*visited=new boolG.vexnum;int i;cout按圖的鄰接矩陣得到的深度優(yōu)先遍歷序列endl;for(i=0;iG.vexnum;i+) visitedi=false;DFSMatrix(G,0,G.vexnum,visited);cout按圖的鄰接矩陣得到的廣度優(yōu)先遍歷序列endl;for(i=0;iG.vexnum;i+) visitedi=false;BFSMatrix(G,0,G.vexnum,visited);cout度：頭頂點(diǎn)名 輸入數(shù)據(jù):如A-Ba-ba-ca-dc-bd-c*/ #include #include #include #include typedef char VertexType; /頂點(diǎn)的名稱為字符const int MaxVertexNum =10; /圖的最大頂點(diǎn)數(shù)const int MaxEdgeNum =100; /邊數(shù)的最大值typedef int WeightType; /權(quán)值的類型const WeightType MaxValue =32767; /權(quán)值的無窮大表示typedef VertexType Vexlist MaxVertexNum; /頂點(diǎn)信息，定點(diǎn)名稱 /鄰接矩陣typedef enum DG,DN,AG,AN GraphKind; /有向圖,有向網(wǎng),無向圖,無向網(wǎng)struct EdgeNode /鏈表邊結(jié)點(diǎn)，表示弧int adjvex; /存放與頭結(jié)點(diǎn)頂點(diǎn)有關(guān)的另一個(gè)頂點(diǎn)在鄰接表(數(shù)組)中的下標(biāo)。 EdgeNode *next; /指向鏈表下一個(gè)結(jié)點(diǎn)WeightType info; / 權(quán)重值，或?yàn)樵摶∠嚓P(guān)信息;typedef struct VNode /鄰接表，表示頂點(diǎn) VertexType data; / 頂點(diǎn)數(shù)據(jù)，頂點(diǎn)名稱 EdgeNode *firstarc; / 指向邊結(jié)點(diǎn)鏈表第一個(gè)結(jié)點(diǎn) VNode, AdjListMaxVertexNum;typedef struct AdjList vertices;int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 ALGraph;void CreateGraph_DG(ALGraph &G)/構(gòu)造有向圖G EdgeNode *p; int i,j,k;char v,w; G.kind=DG; /圖的種類printf(輸入要構(gòu)造的有向圖的頂點(diǎn)數(shù)和弧數(shù)：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/過濾回車 printf(依次輸入圖的頂點(diǎn)名稱ABCD.等等：n); for (i=0; i頭頂點(diǎn)名 輸入數(shù)據(jù):如A-B n);for (k=0; k%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾頂點(diǎn)號p-info =MaxValue; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesi.firstarc; /插入鏈表G.verticesi.firstarc=p; /void CreateGraph_DN(ALGraph &G)/構(gòu)造有向網(wǎng)G EdgeNode *p; int i,j,k;char v,w; WeightType q;G.kind=DN; /圖的種類printf(輸入要構(gòu)造的有向網(wǎng)的頂點(diǎn)數(shù)和弧數(shù)：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/過濾回車 printf(依次輸入圖的頂點(diǎn)名稱ABCD.等等：n); for (i=0; i頭頂點(diǎn)名,權(quán)值 輸入數(shù)據(jù):如A-B,8 n);for (k=0; k%c,%d,&v,&w,&q);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾頂點(diǎn)號p-info =q; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesi.firstarc; /插入鏈表G.verticesi.firstarc=p; void CreateGraph_AG(ALGraph &G)/構(gòu)造無向圖G EdgeNode *p; int i,j,k;char v,w; G.kind=AG; /圖的種類printf(輸入要構(gòu)造的有向圖的頂點(diǎn)數(shù)和弧數(shù)：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/過濾回車 printf(依次輸入圖的頂點(diǎn)名稱ABCD.等等：n); for (i=0; i頭頂點(diǎn)名 輸入數(shù)據(jù):如A-B n);for (k=0; k%c,&v,&w);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾頂點(diǎn)號p-info =MaxValue; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesi.firstarc; /插入鏈表G.verticesi.firstarc=p; /無向圖和網(wǎng)的邊結(jié)點(diǎn)依附于i,j兩個(gè)頂點(diǎn),兩方均應(yīng)添加邊 p=(EdgeNode *)malloc(sizeof(EdgeNode);/申請弧結(jié)點(diǎn)p-adjvex=i; /置入弧尾頂點(diǎn)號p-info =MaxValue; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesj.firstarc; /插入鏈表G.verticesj.firstarc=p; /void CreateGraph_AN(ALGraph &G)/構(gòu)造無向網(wǎng)GEdgeNode *p; int i,j,k;char v,w; WeightType q;G.kind=AN; /圖的種類printf(輸入要構(gòu)造的無向網(wǎng)的頂點(diǎn)數(shù)和弧數(shù)：n);scanf(%d,%d,&G.vexnum,&G.arcnum);getchar();/過濾回車 printf(依次輸入圖的頂點(diǎn)名稱ABCD.等等：n); for (i=0; iG.vexnum; i+) scanf(%c,&G.verticesi.data);/構(gòu)造頂點(diǎn)數(shù)據(jù)G.verticesi.firstarc=NULL; /初始化指向鏈表指針getchar();/過濾回車printf(按照： 尾頂點(diǎn)名-頭頂點(diǎn)名,權(quán)值 輸入數(shù)據(jù):如A-B,8 n);for (k=0; kG.arcnum; k+) scanf(%c-%c,%d,&v,&w,&q);getchar();for(i=0;iG.vexnum; i+) if(G.verticesi.data=v) break;/查找出v在vertices中的位置i if(i=G.vexnum) cerrvertex ERROR!;exit(1); for(j=0;jG.vexnum; j+) if(G.verticesj.data=w) break;/查找出w在vertices中的位置i if(j=G.vexnum) cerradjvex=j; /置入弧尾頂點(diǎn)號p-info =q; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesi.firstarc; /插入鏈表G.verticesi.firstarc=p; /無向圖和網(wǎng)的邊結(jié)點(diǎn)依附于i,j兩個(gè)頂點(diǎn),兩方均應(yīng)添加邊 p=(EdgeNode *)malloc(sizeof(EdgeNode);/申請弧結(jié)點(diǎn)p-adjvex=i; /置入弧尾頂點(diǎn)號p-info =q; /圖的權(quán)值默認(rèn)為無窮大 p-next=G.verticesj.firstarc; /插入鏈表G.verticesj.firstarc=p; void dfsAdjoin(ALGraph G,int i,bool *visited) /深度優(yōu)先搜索p266couti:G.verticesi.data adjvex;if(visitedj=false)dfsAdjoin(G,j,visited);p=p-next ;void bfsAdjoin(ALGraph G,int i,bool *visited) /廣度優(yōu)先搜索p268const int MSize=30;int qMSize=0;int front=0,rear=0;coutG.verticesi.dataadjvex;if(!visitedj)coutG.verticesj.datanext;/*完成函數(shù)*void countdig(ALGraph G) /請完成計(jì)算圖的入度或初度if(G.kind=DG|G.kind=DN)/計(jì)算有向圖或網(wǎng)的個(gè)頂點(diǎn)的入度與初度int outD,inD;EdgeNode *p,*k;int i,j;for(i=0;inext)outD+;for(j=0;jnext)if(G.verticesk-adjvex.data=G.verticesi.data)inD+;printf(%c：出度是%d,入度是%dn,G.verticesi.data,outD,inD);else/ 計(jì)算無向圖或網(wǎng)的度int Du;EdgeNode *p,*k;int i,j;for(i=0;inext)Du+;printf(%c：度是%dn,G.verticesi.data,Du); void PrintALGraph(ALGraph &G)/打印鄰接表 EdgeNode *p;int i; for (i=0; i,i,G.verticesi.data); else printf(%d | %c ,i,G.verticesi.data); p=G.verticesi.firstarc