數(shù)據(jù)結(jié)構(gòu)實驗

實驗十圖的建立與遍歷實驗?zāi)康模?） 掌握圖的含義。（2） 掌握用鄰接矩陣和鄰接鏈表的方法描述圖的存儲結(jié)構(gòu)。（3） 理解并掌握深度優(yōu)先遍歷方法和廣度優(yōu)先遍歷方法的存儲結(jié)構(gòu)。實驗內(nèi)容（1） 建立無向圖的鄰接矩陣，并實現(xiàn)插入、刪除邊的功能。（2） 建立有向圖的鄰接表，并實現(xiàn)插入、刪除邊的功能。（3） 實現(xiàn)該圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷。實驗要求（1） 根據(jù)實驗內(nèi)容編寫程序，上機調(diào)試并獲得運行結(jié)果（2） 撰寫實驗報告準(zhǔn)備工作本次實驗將建立如圖所示有向圖和無向圖，并會根據(jù)此進(jìn)行插入，刪除，遍歷操作5.關(guān)鍵操作與算法⑴建立鄰接矩陣算法思想；建立鄰接矩陣即用一維數(shù)存儲圖中的頂點信息，用二維數(shù)組（矩陣）存儲圖中各頂點之間的鄰接關(guān)系。假設(shè)圖G（V，E）有n個確定的頂點，即V={V,V,…，Vn-1},則表示G中各頂點相鄰關(guān)系的是一個n*n的矩陣，矩陣的元素值為fl,（vi.Vj）或＜Vi,Vj＞是E中的邊0,（饑，幻）或＜的＞物〉不是E中的邊若G是帶權(quán)圖（網(wǎng)），則鄰接矩陣可定義為A［如］=IWij,（Vi.Vj）或＜Vi,Vj〉是E中的邊8,（S,巧）或＜Vi,Vj＞不是A［如］=其中，w表示邊（V，V）或Vv，V＞上的權(quán)值；8表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)，代表此路不通；若v1=v1，則A[i][j]的值取0。算法如下；voidCreateMGragh(GraphMatrix*g){inti,j,k,t;floatw；//權(quán)值printf("請輸入無向網(wǎng)的頂點個數(shù)(不超過%d個)："，MAXVEX);scanf("%d”,&g->vexNum);printf("\n請輸入各頂點信息：\n");getchar();//吞掉上一步的回車for(i=0;i<g->vexNum;i++)gets(g->vexs[i]);//輸入各個頂點信息for(i=0;i<g->vexNum;i++)for (j =0;j<g->vexNum;j++){g->arcs[i][j]=0;//初始化鄰接矩陣}printf("\n");printf(-請輸入圖的邊數(shù)(不超過％d個)："，(g->vexNum*(g->vexNum-1))/2);scanf("%d",&k);//邊的數(shù)目，這里的后面不用加getchar()，因為后面的一個輸入的是一個整型類型for(t=0;t<k;t++){printf(-\n請輸入第％d條邊的相關(guān)信息(起始頂點(序號從0開始)終止頂點權(quán)值，如0310.3)\n”,t+1);scanf("%d%d%f”,&i,&j,&w);g->arcs[i][j]=w; //無向網(wǎng)的權(quán)是對稱的g->arcs[j][i]=w;}}⑵創(chuàng)建鄰接表算法步驟；鄰接表(AdjacencyList)是圖的另一種存儲方式，它是一種將順序存儲與鏈?zhǔn)酱鎯ο嗪系拇鎯Ψ椒?。該方法是為圖中每個頂點都建立一個單鏈表，即對于圖G中的每個頂點v，將v1的所有鄰接點v都鏈在一個單鏈表里，該單鏈表稱為頂點v1的鄰接表(鏈?zhǔn)酱鎯?gòu))，再將所有頂點的鄰接表表頭集中放到一個一維數(shù)組(順序存儲結(jié)構(gòu))中，兩者一起就成了圖的鄰接表結(jié)構(gòu)。算法如下；voidCreateALGragh(GraphList*g){inti,j,k;EdgeNode*s;floatw;printf(-請輸入有向網(wǎng)的頂點個數(shù)，(不超過％d個)："，MAXVEX);scanf("%d”,&g->VexNum);printf("請輸入各個頂點的信息：\n");getchar();

for(i=0;i<g->VexNum;i++){gets(g->vexs[i].vertex);g->vexs[i].firstarc=NULL;//這里vex[i].firstarc的點是因為vex[i]為結(jié)構(gòu)體，所以引用它其中的內(nèi)容使需要用”.”運算符}printf("\n");printf("請輸入圖的邊數(shù)(不超過％d個)："，g->VexNum*(g->VexNum-1));scanf("%d”,&g->EdgeNum);for(k=0;k<g->EdgeNum;k++){printf(-\n請輸入第％d條邊的相關(guān)信息(起始頂點(序號從0開始)終止頂點權(quán)值，如0310.3)\n”,k+1);scanf("%d%d%f”,&i,&j,&w);s=(EdgeNode*)(malloc(sizeof(EdgeNode)));s->endvex=j;s->next=g->vexs[i].firstarc;s->weight=w;g->vexs[i].firstarc=s;}}⑶無向網(wǎng)深度優(yōu)先遍歷算法過程；假設(shè)初始狀態(tài)是未被訪問過的圖中所有頂點，則深度優(yōu)先搜索可從圖中某個頂點V出發(fā)，首先訪問該頂點，然后從V的所有未被訪問的鄰接點中選擇某一個鄰接點w訪問，然后再從w的所有未被訪問的鄰接點中選擇某一個鄰接點x訪問，依此類推，直至圖中所有和有路徑相通的頂點都被訪問過為止；若此時圖中仍有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問過為止。算法如下；1.2.voidMUDGDFS(GraphMatrix*g,int是否被訪問過的判斷基準(zhǔn){v,intvisited[])//visited數(shù)組是用來判斷某節(jié)點.DataTypew;visited[v]=TRUE;printf(1.2.voidMUDGDFS(GraphMatrix*g,int是否被訪問過的判斷基準(zhǔn){v,intvisited[])//visited數(shù)組是用來判斷某節(jié)點.DataTypew;visited[v]=TRUE;printf("%d\t",v);for(w=MUDGFirstAdjacent(g,v);w!=ERROR;w=MUDGNextAdjacent(g,v,0.w)){if(visited[w]!=TRUE)MUDGDFS(g,w,visited);//該頂點沒有被訪問過11.}⑷有向網(wǎng)廣度優(yōu)先算法步驟；搜索過程為從圖中某頂點v出發(fā)，訪問了頂點v后，再依次訪問v的所有未曾訪問過的鄰接點，然后再分別從這些鄰接點出發(fā)依次訪問它們的所有未曾訪問過的鄰接點，遵循“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點”的訪問原則，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。此時圖中若還有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為新的出發(fā)點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索遍歷圖的過程類似于樹的按層次遍歷的過程。算法如下；voidLUDGBFS(GraphList*g,intv,intvisited]])2.{3.DataTypev1,v2;4.SeqQueue*q=SetSeqQueue();型2.{3.DataTypev1,v2;4.SeqQueue*q=SetSeqQueue();型5.SeqQueueINQueue(q,v);6.printf("%d\t”,v);7.visited[v]=TRUE;8.while(!SeqQueueISEmpty(q))9.{10.SeqQueueOUTQueue(q,&v1);中11.v2=LUDGFirstAdjacent(g,v1);12.while(v2!=ERROR)13.{14.if(visited[v2]!=TRUE)再改變visited標(biāo)志〃初始頂點入隊〃初始頂點被訪問〃對頭元素出隊，并將對頭元素保存到v1//鄰接頂點存在時進(jìn)行循環(huán)〃如果鄰接頂點未被訪問則入隊，訪問，15.{16.SeqQueueINQueue(q,v2);17.printf("%d\t",v2);18.visited[v2]=TRUE;19.}20.v2=LUDGNextAdjacent(g,v1,21. }22.23. }24.}v2); 〃取v1的下一個頂點6.源代碼#include<string.h>#include<malloc.h>#include<limits.h>#include<stdio.h>#include<stdlib.h>

#include<io.h>#include<math.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR-1#defineINFEASIBLE-1#defineMAXNAME20#defineMAXVEX30#defineMAXNUM30typedefintDataType;typedefcharVexType[MAXNAME];//頂點信息最長為20個字符typedeffloatAdjType;19.//定義一個隊列(方便后面使用廣度優(yōu)先遍歷)typedefstruct{DataTypedata[MAXNUM];intfront,rear;}SeqQueue;//置空隊SeqQueue*SetSeqQueue(){SeqQueue*q=(SeqQueue*)malloc(sizeof(SeqQueue));if(q==NULL)printf("溢出??！\n");elseq->front= q->rear=0;returnq;TOC\o"1-5"\h\z}//判斷隊空函數(shù)intSeqQueueISEmpty(SeqQueue*q){if(q-front==q->rear){returnTRUE;}else{returnFALSE;}}//入隊voidSeqQueueINQueue(SeqQueue*q,DataTypex)

TOC\o"1-5"\h\z{if(q->front==(q->rear+1)%MAXNUM)printf("隊滿溢出！\n");else{q->rear++;q->data[q->rear%MAXNUM]=x;}}//出隊voidSeqQueueOUTQueue(SeqQueue*q,DataType*x){if(q->front==q->rear)printf("隊空！\n");else{q->front++;*x=q->data[q->front%MAXNUM];}}//隊列部分結(jié)束69./*一.建立無向網(wǎng)鄰接矩陣1.建立無向網(wǎng)的鄰接矩陣2.實現(xiàn)插入的功能3.實現(xiàn)刪除邊的功能*/76.//定義圖的鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)typedefstruct{intvexNum;VexTypevexs[MAXVEX];AdjTypearcs[MAXVEX][MAXVEX];}GraphMatrix;//建立無向網(wǎng)的鄰接矩陣voidCreateMGragh(GraphMatrix*g){inti,j,k,t;floatw;//權(quán)值printf(-請輸入無向網(wǎng)的頂點個數(shù)(不超過％d個)："，MAXVEX);scanf("%d”,&g->vexNum);printf("\n請輸入各頂點信息：\n");getchar();//吞掉上一步的回車for(i=0;i<g->vexNum;i++)

gets(g->vexs[i]);//輸入各個頂點信息for(i=0;i<g->vexNum;i++)for (j=0;j<g->vexNum;j++){g->arcs[i][j]=0;//初始化鄰接矩陣}printf("\n");printf(-請輸入圖的邊數(shù)(不超過％d個)："，(g->vexNum*(g->vexNum-1))/2);scanf("%d",&k);//邊的數(shù)目，這里的后面不用加getchar()，因為后面的一個輸入的是一個整型類型for(t=0;t<k;t++){printf(-\n請輸入第％d條邊的相關(guān)信息(起始頂點(序號從0開始)終止頂點權(quán)值，如0310.3)\n”,t+1);scanf("%d%d%f”,&i,&j,&w);g->arcs[i][j]=w; //無向網(wǎng)的權(quán)是對稱的g->arcs[j][i]=w;}}111.112.//無向網(wǎng)實現(xiàn)插入邊voidInsertAMArc(GraphMatrix*g,inti,intj,floatweight)TOC\o"1-5"\h\z{g->arcs[i][j]=weight;g->arcs[j][i]=weight;printf("\n插入成功！\n");}120.//無向網(wǎng)實現(xiàn)刪除邊voidDeleteAMArc(GraphMatrix*g,inti,intj){g->arcs[i][j]=0;g->arcs[j][i]=0;printf("\n刪除成功！\n");}128.//求無向網(wǎng)中與頂點i鄰接的第一個頂點(為之后的廣度優(yōu)先做準(zhǔn)備)130.intMUDGFirstAdjacent(GraphMatrix*g,inti)34.intt;132.133.134.intt;for(t=0;t<g->vexNum;t++){136.}137.returnERROR;135.}139.if(g->arcs[i][t]!=0)return135.}139.140.//求無向網(wǎng)中與頂點i相對于頂點j的下一個鄰接頂點（為之后的廣度優(yōu)先遍歷做準(zhǔn)備）141.intMUDGNextAdjacent(GraphMatrix*g,inti,intj)142.{143.intt;144.for(t=j+1;t<g->vexNum;t++)145.{146.if(g->arcs[i][t]!=0)returnt;147.}148.returnERROR;149.}150.151./*152.二.建立有向網(wǎng)鄰接表153.1.建立有向網(wǎng)的鄰接表154.2.實現(xiàn)插入的功能155.3.實現(xiàn)刪除邊的功能156.*/157.//建立圖的數(shù)據(jù)結(jié)構(gòu)typedefstructEdgeNode{/*1.圖的邊結(jié)構(gòu)定義*/160. intendvex;//邊頂點的索引161. AdjTypeweight;//邊的權(quán)，非帶權(quán)圖可以忽略structEdgeNode*next;}EdgeNode;〃形成鏈表typedefstruct{/*2.圖的頂點結(jié)構(gòu)定義*/166. VexTypevertex;〃頂點信息167. EdgeNode*firstarc;//邊表頭指針168.}VexNode;//頂點typedefstruct{/*3.圖的鄰接表結(jié)構(gòu)*/171. intVexNum;//圖頂點個數(shù)intEdgeNum;VexNodevexs[MAXVEX];}GraphList;//圖邊的條數(shù)175./*在建立鄰接表時要切記注意鄰接表的具體結(jié)構(gòu)以便后面去進(jìn)行遍歷，它不同于鄰接矩陣在遍歷的時候是按照從0到n-1的順序來的，它是根據(jù)具體的鏈?zhǔn)浇Y(jié)構(gòu)得來所以在進(jìn)行創(chuàng)建林杰表示一定要注意插入頂點的先后順序注：最好是先把鄰接表給畫出來，然后再去進(jìn)行輸入，在頂點直接連著的后面那個邊節(jié)點一定是對于這個頂點的邊來說，最后插入*/voidCreateALGragh(GraphList*g){inti,j,k;EdgeNode*s;floatw;printf(-請輸入有向網(wǎng)的頂點個數(shù)，(不超過％d個)："，MAXVEX);scanf("%d”,&g->VexNum);printf("請輸入各個頂點的信息：\n");getchar();for(i=0;i<g->VexNum;i++){gets(g->vexs[i].vertex);g->vexs[i].firstarc=NULL;//這里vex[i].firstarc的點是因為vex[i]為結(jié)構(gòu)體，所以引用它其中的內(nèi)容使需要用”.”運算符}printf("\n");printf("請輸入圖的邊數(shù)(不超過％d個)："，g->VexNum*(g->VexNum-1));scanf("%d”,&g->EdgeNum);for(k=0;k<g->EdgeNum;k++){printf(-\n請輸入第％d條邊的相關(guān)信息(起始頂點(序號從0開始)終止頂點權(quán)值，如0310.3)\n”,k+1);scanf("%d%d%f”,&i,&j,&w);s=(EdgeNode*)(malloc(sizeof(EdgeNode)));s->endvex=j;s->next=g->vexs[i].firstarc;s->weight=w;g->vexs[i].firstarc=s;TOC\o"1-5"\h\z}}208.//有向網(wǎng)實現(xiàn)插入邊voidInsertALArc(GraphList*g,inti,intj,floatw){EdgeNode*s;s=(EdgeNode*)(malloc(sizeof(EdgeNode)));s->endvex =j;s->next= g->vexs[i].firstarc;s->weight =w;g->vexs[i].firstarc=s;printf("\n插入成功！\n");

}220.//有向網(wǎng)實現(xiàn)刪除邊voidDeleteALArc(GraphList*g,inti,intj){EdgeNode*s,*temp;s=(EdgeNode*)(malloc(sizeof(EdgeNode)));temp=(EdgeNode*)(malloc(sizeof(EdgeNode)));int k=0;s = g->vexs[i].firstarc;k = s->endvex;while(k!=j){temp=s;s=s->next;k=s->endvex;}if(k == g->vexs[i].firstarc->endvex)g->vexs[i].firstarc =s->next;elsetemp->next=s->next;printf("\n 刪除成功!\n");TOC\o"1-5"\h\z}//求有向網(wǎng)中與頂點i鄰接的第一個頂點(為之后的廣度優(yōu)先做準(zhǔn)備)intLUDGFirstAdjacent(GraphList*g,inti){if(g->vexs[i].firstarc!=NULL)returng->vexs[i].firstarc->endvex;elsereturnERROR;}248.//求有向網(wǎng)中與頂點i相對于頂點j的下一個鄰接頂點(為之后的廣度優(yōu)先遍歷做準(zhǔn)備)intLUDGNextAdjacent(GraphList*g,inti,intj){EdgeNode*p;p=g->vexs[i].firstarc;while(p!=NULL){if(p->endvex==j){if(p->next!=NULL)returnp->next->endvex;elsereturnERROR;}p = p->next;}

264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299263.return263.returnERROR;./*三.深度優(yōu)先遍歷與廣度優(yōu)先遍歷(無向網(wǎng)，有向網(wǎng))*/.//無向網(wǎng)(鄰接矩陣實現(xiàn)的無向網(wǎng))實現(xiàn)深度優(yōu)先遍歷.voidMUDGDFS(GraphMatrix*g,intv,intvisited[])//visited數(shù)組是用來判斷某節(jié)點是否被訪問過的判斷基準(zhǔn).{. DataTypew;. visited[v]=TRUE;. printf("%d\t”,v);.for(w=MUDGFirstAdjacent(g,v);w!=ERROR;w=MUDGNextAdjacent(g,v,w)). {. if(visited[w]!=TRUE)//該頂點沒有被訪問過. MUDGDFS(g,w,visited);//遞歸訪問，實際上也是回到上一步所執(zhí)行的函數(shù)，這里的遞歸可以仔細(xì)思考. }.}..//有向網(wǎng)(鄰接表實現(xiàn)的有向網(wǎng))實現(xiàn)深度優(yōu)先遍歷.voidLUDGDFS(GraphList*g,intv,intvisited[])//visited數(shù)組是用來判斷某節(jié)點是否被訪問過的判斷基準(zhǔn).{. printf("%d\t",v);. EdgeNode*p;. visited[v]=TRUE; //以上是輸出頂點信息，并置訪問標(biāo)志. p=g->vexs[v].firstarc; 〃取出鄰接頂點的鏈表頭while(p). {. if(visited[p->endvex]!=TRUE). LUDGDFS(g,p->endvex,visited);〃未訪問過，則遞歸訪問. p=p->next; //取下一鄰接點，實際上也是回到上一步執(zhí)行的函數(shù)，這里的遞歸可以仔細(xì)思考. }.}..//無向網(wǎng)(鄰接矩陣實現(xiàn)的無向網(wǎng))實現(xiàn)廣度優(yōu)先遍歷.voidMUDGBFS(GraphMatrix*g,intv,intvisited]]).{.DataTypev1,v2;

300.SeqQueue*q=SetSeqQueue();//隊列元素的類型為DataType(int)類型301.SeqQueueINQueue(q,v);〃初始頂點入隊302.printf("%d\t”,v);303.visited[v]=TRUE;〃初始頂點被訪問304.while(!SeqQueueISEmpty(q))305.{306.SeqQueueOUTQueue(q,&v1);〃對頭元素出隊，并將對頭元素保存到v1中307.v2=MUDGFirstAdjacent(g,v1);308.while(v2!=ERROR)//鄰接頂點存在時進(jìn)行循環(huán)309.{310.if(visited[v2]!=TRUE)〃如果鄰接頂點未被訪問則入隊，訪問，再改變visited標(biāo)志311.{312.SeqQueueINQueue(q,v2);313.printf("%d\t",v2);314.visited[v2]=TRUE;315.}316.v2=MUDGNextAdjacent(g,v1,v2); 〃取v1的下一個頂點317.}318.319.}}321.//有向網(wǎng)(鄰接表實現(xiàn)的有向網(wǎng))實現(xiàn)廣度優(yōu)先遍歷voidLUDGBFS(GraphList*g,intv,intvisited]])324.{325.DataTypev1,v2;326.SeqQueue*q=SetSeqQueue();//隊列元素的類型為DataType(int)類型327.SeqQueueINQueue(q,v);〃初始頂點入隊328.printf("%d\t",v);329.visited[v]=TRUE;〃初始頂點被訪問330.while(!SeqQueueISEmpty(q))331.{332.SeqQueueOUTQueue(q,&v1);〃對頭元素出隊，并將對頭元素保存到v1中333.v2=LUDGFirstAdjacent(g,v1);334.while(v2!=ERROR)//鄰接頂點存在時進(jìn)行循環(huán)335.{336.if(visited[v2]!=TRUE)〃如果鄰接頂點未被訪問則入隊，訪問，再改變visited標(biāo)志337.{

338.339.338.339.340.341.342.343.344.345.346.347.348.349.350.351.352.353.354.355.356.357.358.359.360.361.362.363.364.365.366.367.368.369.370.371.372.373.374.375.376.377.378.379.380.381.printf("%d\t”,v2);visited[v2]=TRUE;}v2=LUDGNextAdjacent(g,v1,v2); 〃取v1的下一個頂點}}}/*總結(jié)(廣度優(yōu)先(DFS)與深度優(yōu)先(BFS)算法效率比較)：空間復(fù)雜度都相同，都是O(n)(DFS借用棧，BFS借用隊列)時間復(fù)雜度只與存儲結(jié)構(gòu)(鄰接矩陣或鄰接表)有關(guān),而與搜索路徑(廣