實驗十二圖的基本操作—鄰接矩陣存儲結(jié)構(gòu)

1、浙江大學(xué)城市學(xué)院實驗報告課程名稱 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 實驗項目名稱 實驗十二 圖的基本操作鄰接矩陣存儲結(jié)構(gòu) 學(xué)生姓名 專業(yè)班級 學(xué)號 實驗成績 指導(dǎo)老師（簽名 ） 日期 一. 實驗?zāi)康暮鸵?、掌握圖的存儲結(jié)構(gòu)：鄰接矩陣。2、學(xué)會對圖的存儲結(jié)構(gòu)進(jìn)行基本操作。二. 實驗內(nèi)容1、圖的鄰接矩陣定義及實現(xiàn)：建立頭文件adjmatrix.h，在該文件中定義圖的鄰接矩陣存儲結(jié)構(gòu)，并編寫圖的初始化、建立圖、輸出圖、輸出圖的每個頂點(diǎn)的度等基本操作實現(xiàn)函數(shù)。同時建立一個驗證操作實現(xiàn)的主函數(shù)文件test5_1.cpp，編譯并調(diào)試程序，直到正確運(yùn)行。 2、選做：編寫圖的深度優(yōu)先遍歷函數(shù)與廣度優(yōu)先遍歷函數(shù)，要求把這兩個函數(shù)

2、添加到頭文件adjmatrix.h中，并在主函數(shù)文件test5_1.cpp中添加相應(yīng)語句進(jìn)行測試。3、填寫實驗報告，實驗報告文件取名為report12.doc。4、上傳實驗報告文件report12.doc及源程序文件test5_1.cpp、adjmatrix.h到ftp服務(wù)器上自己的文件夾下。三. 函數(shù)的功能說明及算法思路 （包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路）鄰接矩陣表示法的c語言描述：typedef structvexlist vexs; /頂點(diǎn)數(shù)據(jù)元素adjmatrix ga; /二維數(shù)組作鄰接矩陣int n; /頂點(diǎn)數(shù)int k1,k2; /k1為有無向，k2為有無權(quán)

3、graph;const int maxvertexnum = 10; /*圖的最大頂點(diǎn)數(shù)*/const int maxedgenum = 100; /*圖的最大邊數(shù)*/const int maxvalue = 10000; /*無窮大的具體值*/typedef int weighttype; /*定義權(quán)的類型*/typedef char vertextype;typedef vertextype vexlistmaxvertexnum; /*定義頂點(diǎn)數(shù)組類型*/typedef int adjmatrixmaxvertexnummaxvertexnum; /*定義鄰接矩陣類型*/抽象數(shù)據(jù)類型：a

4、dt graph is data: graph(v, e ) 其中： v = vi | 0=i=0, vi vertextype 是頂點(diǎn)的有窮集合； e = (x, y) | x, y v 或 e = | x, y v 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊集合。 存儲類型用adjmatrix表示 operations: void initmatrix( adjmatrix ga, int k)/初始化算法（假設(shè)頂點(diǎn)信息僅是序號） void creatematrix( adjmatrix ga, int n, char *s, int k1, int k2)/建立圖的鄰接矩陣算法 void pri

5、ntmatrix( adjmatrix ga, int n, int k1, int k2)/根據(jù)圖的鄰接矩陣輸出圖的頂點(diǎn)集和邊集 void printdegree(vexlist v,adjmatrix ga,int n,int k1)/計算各個頂點(diǎn)的度 void dfsmatrix(adjmatrix ga,int i,int n,bool *visited)/深度優(yōu)先遍歷 void bfsmatrix( adjmatrix ga,int i,int n,bool *visited)/廣度優(yōu)先遍歷end度的算法：void printdegree(vexlist v,adjmatrix ga

6、,int n,int k1)數(shù)組vi存放所有頂點(diǎn)，根據(jù)邊結(jié)點(diǎn)的指針數(shù)組計算該結(jié)點(diǎn)的度;若圖是有向圖，則查找所有邊結(jié)點(diǎn)的鄰接點(diǎn)域，如果是當(dāng)前結(jié)點(diǎn)的位置，就將該結(jié)點(diǎn)對應(yīng)的度+1。隊列：typedef char elemtype;struct queueelemtype *queue;int front,rear;int maxsize;operations:void initqueue(queue &q) /初始化循環(huán)隊列qint emptyqueue(queue q)/判斷隊列是否為空，空返回1，否則返回0void enqueue(queue &q,elemtype item)/ 入隊列elem

7、type outqueue(queue &q) / 出隊列end queue四. 實驗結(jié)果與分析（包括運(yùn)行結(jié)果截圖、結(jié)果分析等）無向無權(quán)圖：無向有權(quán)圖：有向無權(quán)圖：有向有權(quán)圖：五. 心得體會（記錄實驗感受、上機(jī)過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）在計算度的編程上出現(xiàn)了問題，計算void printdegree(vexlist v,adjmatrix ga,int n,int k1)時，vi是存放頂點(diǎn)的數(shù)組，但是在main()函數(shù)里面忘記使用數(shù)組，結(jié)果編譯是正確的但是輸出來是一堆亂碼。最后改了好久才想起來，在前面加上cout請輸入圖的頂點(diǎn)集合(如:abc)endl;for(i

8、=0; ig.vexsi;【附錄-源程序】test5_1.cpp：#include#include#include#include#includeconst int maxvertexnum = 10; /*圖的最大頂點(diǎn)數(shù)*/const int maxedgenum = 100; /*圖的最大邊數(shù)*/const int maxvalue = 10000; /*無窮大的具體值*/typedef int weighttype; /*定義權(quán)的類型*/typedef char vertextype;typedef vertextype vexlistmaxvertexnum; /*定義頂點(diǎn)數(shù)組類型*/

9、typedef int adjmatrixmaxvertexnummaxvertexnum; /*定義鄰接矩陣類型*/#include adjmatrix.h void main()graph g;/鄰接矩陣int i;coutg.n;cout請輸入圖的頂點(diǎn)集合(如:abc)endl;for(i=0; ig.vexsi;coutg.k1g.k2;bool *visited=new boolg.n; /定義并動態(tài)分配標(biāo)志數(shù)組initmatrix(g.ga,g.k2);couta;creatematrix(g.ga,g.n,a,g.k1,g.k2);printdegree(g.vexs,g.ga,

10、g.n,g.k1);cout按圖的鄰接矩陣得到的深度優(yōu)先遍歷序列:endl;for(i=0;ig.n;i+) visitedi=false;dfsmatrix(g.ga,0,g.n,visited);coutendl;cout按圖的鄰接矩陣得到的廣度優(yōu)先遍歷序列:endl;for(i=0;ig.n;i+) visitedi=false;bfsmatrix(g.ga,0,g.n,visited);coutendl;printmatrix(g.ga,g.n,g.k1,g.k2);adjmatrix.htypedef structvexlist vexs; /頂點(diǎn)數(shù)據(jù)元素adjmatrix ga;

11、/二維數(shù)組作鄰接矩陣int n; /頂點(diǎn)數(shù)int k1,k2; /k1為有無向，k2為有無權(quán)graph;void initmatrix( adjmatrix ga, int k)/初始化算法 （假設(shè)頂點(diǎn)信息僅是序號）/k=0代表無權(quán)圖，k0代表帶權(quán)圖int i, j;for( i=0; imaxvertexnum; i+)for( j=0; jc1; /讀入第一個字符 if(k1=0 & k2=0) /建立無向無權(quán)圖dosinc1ic2jc3; /讀入一條邊，如 (2,5) gaij = gaji = 1; /相應(yīng)的邊元素置1 sinc1; /讀入, 或 if (c1=) break;whil

12、e (1);else if (k1=0 & k2!=0) /建立無向帶權(quán)圖dosinc1ic2jc3w; /讀入一條邊，如 (2,5)8gaij = gaji = w;sinc1;if (c1=) break;while(1);else if (k1!=0 & k2=0) /建立有向無權(quán)圖do sinc1ic2jc3;gaij = 1; sinc1;if (c1=) break;while(1);else if (k1!=0 & k2!=0) /建立有向帶權(quán)圖do sinc1ic2jc3w;gaij = w;sinc1;if (c1=) break;while(1);void printmat

13、rix( adjmatrix ga, int n, int k1, int k2)/根據(jù)圖的鄰接矩陣輸出圖的頂點(diǎn)集和邊集/ k1=0 代表無向圖否則為有向圖, k2 =0 代表無權(quán)圖否則為帶權(quán)圖int i, j;cout v=; /準(zhǔn)備輸出頂點(diǎn)集for(i=0; in-1; i+)couti,;coutn-1endl;cout e=; /準(zhǔn)備輸出邊集if(k2=0) /無權(quán)圖 for(i=0; in; i+)for(j=0; jn; j+)if( gaij =1 )if(k1=0) /無向圖if(ij)cout(i,j),;else /有向圖couti,j,;else /帶權(quán)圖 for(i=0

14、; in; i+)for(j=0; jn; j+)if(gaij != 0 & gaij != maxvalue )if(k1=0) /無向圖if(ij)cout(i,j)gaij,;else /有向圖couti,j gaij,;coutendl; void printdegree(vexlist v,adjmatrix ga,int n,int k1)/計算各個頂點(diǎn)的度int i,j,d;for(i=0;in;i+)d=0;for(j=0;jn;j+)if(gaij!=0&gaij!=maxvalue)d+;if(k1) /有向圖for(j=0;jn;j+)if(gaji!=0&gaji!=

15、maxvalue)d+;coutvi的度為dendl;/*=選作部分=*/typedef char elemtype;struct queueelemtype *queue;int front,rear;int maxsize;void initqueue(queue &q) /初始化循環(huán)隊列qq.maxsize=10;q.queue=(elemtype *)malloc(sizeof(elemtype)*q.maxsize);q.rear=q.front=0;int emptyqueue(queue q)/判斷隊列是否為空，空返回1，否則返回0return q.front=q.rear;vo

16、id enqueue(queue &q,elemtype item)/ 入隊列if(q.rear+1) % q.maxsize = q.front)/若隊列已滿，重新分配2倍大的空間q.queue=(elemtype *)realloc(q.queue,2*q.maxsize*sizeof(elemtype);if(q.rear != q.maxsize-1) /原隊列尾部內(nèi)容向后移for(int i=0; i=q.rear; i+)q.queuei+q.maxsize = q.queuei;q.rear=q.rear+q.maxsize;q.maxsize=2*q.maxsize; / 插入

17、itemq.rear=(q.rear+1)%q.maxsize;q.queueq.rear=item;elemtype outqueue(queue &q) / 出隊列if(q.front=q.rear) /若空隊列，則結(jié)束運(yùn)行cerr 隊列已空，無法刪除! endl;exit(1); /刪除隊頭元素，并返回該元素q.front=(q.front +1)%q.maxsize;return q.queueq.front;void dfsmatrix(adjmatrix ga,int i,int n,bool *visited) /從vi出發(fā)進(jìn)行dfsint j; couti ; /訪問頂點(diǎn)vi visitedi = 1; /置訪問標(biāo)志 for(j=0; jn; j+ ) /依次訪問vi的未被訪問的所有鄰接點(diǎn) if(gaij != 0 & gaij != maxvalue & !visitedj) dfsmatrix(ga,j,n,visited); void bfsmatrix( adjmatr