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

1、上機(jī)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)七、圖算法上機(jī)實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康模? .了解熟知圖的定義和圖的根本術(shù)語,掌握?qǐng)D的幾種存儲(chǔ)結(jié)構(gòu).2 .掌握鄰接矩陣和鄰接表定義及特點(diǎn),并通過實(shí)例解析掌握鄰接矩陣和鄰接表的類型定義.3 .掌握?qǐng)D的遍歷的定義、復(fù)雜性分析及應(yīng)用,并掌握?qǐng)D的遍歷方法及其根本思想.二、實(shí)驗(yàn)內(nèi)容：1 .建立無向圖的鄰接矩陣2 .圖的深度優(yōu)先搜索3 .圖的廣度優(yōu)先搜索三、實(shí)驗(yàn)步驟及結(jié)果：1.建立無向圖的鄰接矩陣：1源代碼：#include"stdio.h"#include"stdlib.h"#defineMAXSIZE30typedefstructcharvertexMA

2、XSIZE;/頂點(diǎn)為字符型且頂點(diǎn)表的長度小于MAXSIZEintedgesMAXSIZEMAXSIZE;/邊為整形且edges為鄰近矩陣MGraph;/MGraph為采用鄰近矩陣存儲(chǔ)的圖類型voidCreatMGraph(MGraph*g,inte,intn)/建立無向圖白鄰近矩陣g->egdes,n為頂點(diǎn)個(gè)數(shù),e為邊數(shù)inti,j,k;printf("Inputdataofvertexs(0n-1):n");for(i=0;i<n;i+)g->vertexi=i;/讀入頂點(diǎn)信息for(i=0;i<n;i+)for(j=0;j<n;j+)g-&

3、gt;edgesij=0;/初始化鄰接矩陣for(k=1;k<=e;k+)/輸入e條邊printf("Inputedgesof(i,j):");scanf("%d,%d",&i,&j);g->edgesij=1;g->edgesji=1;)voidmain()(inti,j,n,e;MGraph*g;/建立指向采用鄰接矩陣存儲(chǔ)圖類型指針g=(MGraph*)malloc(sizeof(MGraph);/生成采用鄰接舉證存儲(chǔ)圖類型的存儲(chǔ)空間printf("InputsizeofMGraph:");/輸入

4、鄰接矩陣的大小scanf("%d",&n);printf("Inputnumberofedge:");/輸入鄰接矩陣的邊數(shù)scanf("%d",&e);CreatMGraph(g,e,n);/生成存儲(chǔ)圖的鄰接矩陣printf("OutputMGraph:n");/輸出存儲(chǔ)圖的鄰接矩陣for(i=0;i<n;i+)(for(j=0;j<n;j+)printf("%4d",g->edgesij);printf("n");)2)運(yùn)行結(jié)果:Inpur

5、sizeofHGi*aph=4Inputnuinjjepofe-4Inputdataofuei*texsCSn1>:Input:edgfesInputedgesInput;elitesInputedQfesof<i,j5他:Lof<i,j>：0,3of<i,j>=1.3o£<i,j>=1,2OutputHGi*dph-0101101101001130Py-essanvlieytocontinue2.圖的深度優(yōu)先搜索:1源代碼:#include"stdio.h"#include"stdlib.h"#

6、defineMAXSIZE30typedefstructnode/鄰接表結(jié)點(diǎn)intadjvex;/鄰接點(diǎn)域structnode*next;指向下一個(gè)鄰接邊結(jié)點(diǎn)的指針域EdgeNode;/鄰接表結(jié)點(diǎn)類型typedefstructvnode/頂點(diǎn)表結(jié)點(diǎn)intvertex;/頂點(diǎn)域EdgeNode*firstedge;指向鄰接表第一個(gè)鄰接邊節(jié)點(diǎn)的指針VertexNode;/頂點(diǎn)表結(jié)點(diǎn)類型voidCreatAdjlist(VertexNodeg,inte,intn)/建立無向圖白鄰接表,n為頂點(diǎn)數(shù),e為邊數(shù),g口存儲(chǔ)n個(gè)頂點(diǎn)表結(jié)點(diǎn)EdgeNode*p;inti,j,k;printf("Inp

7、utdataofvetex(0n-1);n");for(i=0;i<n;i+)/建立有n個(gè)頂點(diǎn)的頂點(diǎn)表gi.vertex=i;/讀入頂點(diǎn)i信息gi.firstedge=NULL;/初始化指向頂點(diǎn)i的鄰接表表頭指針for(k=1;k<=e;k+)/輸入e條邊printf("Inputedgeof(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=j;/在頂電vi的鄰接表中添加鄰接點(diǎn)為j的結(jié)點(diǎn)p->next=

8、gi.firstedge;/插入是在鄰接表表頭進(jìn)行的gi.firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=i;/在頂電vj的鄰接表中添加鄰接點(diǎn)為i的結(jié)點(diǎn)p->next=gj.firstedge;/插入是在鄰接表表頭進(jìn)行的gj.firstedge=p;)intvisitedMAXSIZE;/MAXSIZE為大于或等于無向圖頂點(diǎn)個(gè)數(shù)的常量voidDFS(VertexNodeg,inti)EdgeNode*p;printf("%4d",gi.vertex);輸出頂點(diǎn)i信息,即訪問頂點(diǎn)ivisited

9、i=1;p=gi.firstedge;/根據(jù)頂點(diǎn)i的指針firstedge查找其鄰接表的第一個(gè)鄰接邊結(jié)點(diǎn)while(p!=NULL)if(!visitedp->adjvex)/如果鄰接的這個(gè)邊結(jié)點(diǎn)未被訪問過DFS(g,p->adjvex);/對(duì)這個(gè)邊結(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索p=p->next;/查找頂點(diǎn)i的下一個(gè)鄰接邊結(jié)點(diǎn))voidDFSTraverse(VertexNodeg,intn)深度優(yōu)先搜索遍歷以鄰接表存儲(chǔ)的圖,其中g(shù)為頂點(diǎn)數(shù),n為頂點(diǎn)個(gè)數(shù)inti;for(i=0;i<n;i+)visitedi=0;/訪問標(biāo)志置0for(i=0;i<n;i+)/對(duì)n個(gè)頂點(diǎn)的

10、圖查找未訪問過的頂點(diǎn)并由該頂點(diǎn)開始遍歷if(!visitedi)/當(dāng)visitedi等于0時(shí)即頂點(diǎn)i未訪問過DFS(g,i);/從未訪問過的頂點(diǎn)i開始遍歷voidmain()inte,n;VertexNodegMAXSIZE;定義頂點(diǎn)表結(jié)點(diǎn)類型數(shù)組gprintf("Inputnumberofnode:n");/輸入圖中節(jié)點(diǎn)個(gè)數(shù)邊的個(gè)數(shù)scanf("%d",&n);printf("Inputnumberofedge:n");/輸入圖中邊的個(gè)數(shù)scanf("%d",&e);printf("Ma

11、keadjlist:n");CreatAdjlist(g,e,n);/建立無向圖的鄰接表printf("DFSTraverse:n");DFSTraverse(g,n);/徐度優(yōu)先遍歷以鄰接表存儲(chǔ)的無向圖printf("n");)2)運(yùn)行結(jié)果：r1-1斕施闔跳實(shí)惹內(nèi)容152Debugl52-exe"rnputnumberofnode：Inputnumbero£eds(e-4MaHeadjlist：Inputdataofvetex<0""n-l)；Inputedgeofj>：0,1Inputed

12、geofti,：6,3Inputedgeof：1,3InputedgeofCi,J)：1,2DFSTpauepse；0312Pi'assanyIteytocontinue3.圖的廣度優(yōu)先搜索：1)源代碼：#include"stdio.h"#include"stdlib.h"#defineMAXSIZE30typedefstructnode1/鄰接表結(jié)點(diǎn)intadjvex;/鄰接點(diǎn)域structnode1*next;/指向下一個(gè)鄰接邊結(jié)點(diǎn)的指針域EdgeNode;/鄰接表結(jié)點(diǎn)類型typedefstructvnode/頂點(diǎn)表結(jié)點(diǎn)intvertex;/

13、頂點(diǎn)域EdgeNode*firstedge;指向鄰接表第一個(gè)鄰接邊結(jié)點(diǎn)的指針域VertexNode;/頂點(diǎn)表結(jié)點(diǎn)類型voidCreatAdjlist(VertexNodeg,inte,intn)建立無向圖的鄰接表,n為頂點(diǎn)數(shù),e為邊數(shù),g口存儲(chǔ)n個(gè)頂點(diǎn)表結(jié)點(diǎn)EdgeNode*p;inti,j,k;printf("Inputdataofvetex(0n-1):n");for(i=0;i<n;i+)/建立有n個(gè)頂點(diǎn)的頂點(diǎn)表gi.vertex=i;/讀入頂點(diǎn)i信息gi.firstedge=NULL;/初始化指向頂點(diǎn)i的鄰接表表頭指針for(k=1;k<=e;k+)/輸

14、入e條邊printf("Inputedgeof(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=j;/在定點(diǎn)vi的鄰接表中添加鄰接點(diǎn)為j的結(jié)點(diǎn)p->next=gi.firstedge;/插入是在鄰接表表頭進(jìn)行的gi.firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=i;/在頂電vj的鄰接表中添加鄰接點(diǎn)為i的結(jié)點(diǎn)p->next=gj.firsted

15、ge;/插入是在鄰接表表頭進(jìn)行的gj.firstedge=p;typedefstructnodeintdata;structnode*next;QNode;/鏈隊(duì)列結(jié)點(diǎn)的類型typedefstructQNode*front,*rear;/將頭、尾指針納入到一個(gè)結(jié)構(gòu)體的鏈隊(duì)列LQueue;/鏈隊(duì)列類型voidInit_LQueue(LQueue*q)/創(chuàng)立一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)列QNode*p;*q=(LQueue*)malloc(sizeof(LQueue);/申請(qǐng)帶頭、尾指針的鏈隊(duì)列p=(QNode*)malloc(sizeof(QNode);/申請(qǐng)鏈隊(duì)列的頭結(jié)點(diǎn)p->next=NULL;

16、/頭結(jié)點(diǎn)的next指針置為空(*q)->front=p;/隊(duì)頭指針指向頭結(jié)點(diǎn)(*q)->rear=p;/隊(duì)尾指針指向頭結(jié)點(diǎn)intEmpty_LQueue(LQueue*q)/判隊(duì)空if(q->front=q->rear)/隊(duì)為空return1;elsereturn0;voidIn_LQueue(LQueue*q,intx)/入隊(duì)QNode*p;p=(QNode*)malloc(sizeof(QNode);/申請(qǐng)新鏈隊(duì)列結(jié)點(diǎn)p->data=x;p->next=NULL;/新結(jié)點(diǎn)作為隊(duì)尾結(jié)點(diǎn)時(shí)其next域?yàn)榭誵->rear->next=p;/將新結(jié)點(diǎn)

17、*p鏈到原隊(duì)尾結(jié)點(diǎn)之后q->rear=p;/使隊(duì)尾指針指向新的隊(duì)尾結(jié)點(diǎn)*pvoidOut_LQueue(LQueue*q,int*x)/出隊(duì)QNode*p;if(Empty_LQueue(q)printf("Queueisempty!n");/對(duì)空,出隊(duì)失敗else(p=q->front->next;指針p指向鏈隊(duì)列第一個(gè)數(shù)據(jù)結(jié)點(diǎn)(即對(duì)頭結(jié)點(diǎn))q->front->next=p->next;頭結(jié)點(diǎn)的next指針指向鏈隊(duì)列第二個(gè)數(shù)據(jù)結(jié)點(diǎn)(即刪除第一個(gè)數(shù)據(jù)結(jié)點(diǎn))*x=p->data;/將刪除的對(duì)頭結(jié)點(diǎn)數(shù)據(jù)經(jīng)由x返回free(p);if(q

18、->front->next=NULL)/出隊(duì)后隊(duì)為空,那么置為空隊(duì)列q->rear=q->front;intvisitedMAXSIZE;/MAXSIZE為大于或等于無向圖頂點(diǎn)個(gè)數(shù)的常量voidBFS(VertexNodeg,LQueue*Q,inti)/廣度優(yōu)先搜索遍歷鄰接表存儲(chǔ)的圖,g為頂點(diǎn)表,Q為隊(duì)指針,i為第i個(gè)頂點(diǎn)intj,*x=&j;EdgeNode*p;printf("%4d",gi.vertex);輸出頂點(diǎn)i信息,即訪問頂點(diǎn)ivisitedi=1;/置頂點(diǎn)i為訪問過標(biāo)志In_LQueue(Q,i);/頂點(diǎn)i入隊(duì)Qwhile(!

19、Empty_LQueue(Q)當(dāng)隊(duì)Q非空時(shí)Out_LQueue(Q,x);對(duì)頭頂點(diǎn)出隊(duì)并送j(暫記為頂點(diǎn)j)p=gj.firstedge;/根據(jù)頂點(diǎn)j的表頭指針查找其鄰接表的第一個(gè)鄰接邊結(jié)點(diǎn)while(p!=NULL)if(!visitedp->adjvex)/如果鄰接的這個(gè)邊結(jié)點(diǎn)未被訪問過printf("%4d",gp->adjvex.vertex);/輸出這個(gè)鄰接邊結(jié)點(diǎn)的頂點(diǎn)信息visitedp->adjvex=1;/置該鄰接邊結(jié)點(diǎn)為訪問過標(biāo)志In_LQueue(Q,p->adjvex);將該鄰接邊結(jié)點(diǎn)送人隊(duì)Qp=p->next;/在頂電j的鄰接表中查找j的下一個(gè)鄰接邊結(jié)點(diǎn))voidmain()(inte,n;VertexNodegMAXSIZE;/定義頂點(diǎn)表結(jié)點(diǎn)類型數(shù)組gLQueue*q;printf("Inputnumberofnode:n"