第五次實(shí)驗(yàn)題目與報(bào)告書-軟件111-112

淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書課程名：《數(shù)據(jù)結(jié)構(gòu)》題目：圖形數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)班級：學(xué)號：姓名：評語：評語：成績：指導(dǎo)教師：批閱時間：年月日《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 -PAGE1-圖形數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告要求1目的與要求:1）掌握圖的鄰接矩陣、鄰接表、十字鏈表、鄰接多重鏈表存儲結(jié)構(gòu)表示及其創(chuàng)建算法的c語言實(shí)現(xiàn)；2）掌握圖的深度優(yōu)先搜索遍歷算法和圖的廣度優(yōu)先搜索遍歷算法及C語言實(shí)現(xiàn)（預(yù)習(xí)）；3）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）；4）認(rèn)真書寫實(shí)驗(yàn)報(bào)告,并按時提交（第12周周一提交）。2實(shí)驗(yàn)內(nèi)容或題目題目：一、圖形數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)——圖的建立與遍歷。內(nèi)容：使用鄰接矩陣和鄰接表儲表示分別實(shí)現(xiàn)如下給定的圖1和或圖2所示圖的物理存儲結(jié)構(gòu)。在1）所建立的圖形存儲結(jié)構(gòu)上分別實(shí)現(xiàn)深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷，并給出遍歷結(jié)果（序列）。圖1圖1無向圖V1V2V4V5V3V7V6V8V1V1V2V4V5V3V7V6V8例2有向圖3實(shí)驗(yàn)步驟與源程序（學(xué)生自己填寫）4測試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）（學(xué)生自己填寫）5結(jié)果分析與實(shí)驗(yàn)體會（學(xué)生自己填寫）2.版面格式：（1）各級標(biāo)題：黑體，小四，段前/段后：6磅（2）正文內(nèi)容：宋體、五號，行間距1.25倍；（3）程序代碼：宋體、五號，單倍行間距；（4）A4紙，上、下、左、右邊距：2厘米注：藍(lán)色字體部分為注釋，正式報(bào)告中將其刪除。舉例：使用鄰接矩陣創(chuàng)建圖形結(jié)構(gòu)本次實(shí)驗(yàn)有向網(wǎng)/*頭文件#include"stdlib.h"#include"stdio.h"#defineMAX_VERTEX_NUM10/*最多頂點(diǎn)個數(shù)*/#defineINFINITY32768/*表示極大值，即∞*/#defineTrue1#defineFalse0#defineError-1#defineOk1typedefenum{DG,DN,UDG,UDN}GraphKind;/*圖的種類：DG表示有向圖,DN表示有向網(wǎng),UDG表示無向圖,UDN表示無向網(wǎng)*/typedefcharVertexData;/*假設(shè)頂點(diǎn)數(shù)據(jù)為字符型*/typedefstructArcNode{ intadj;/*對于無權(quán)圖，用1或0表示是否相鄰；對帶權(quán)圖，則為權(quán)值類型*/}ArcNode;typedefstruct{ VertexDatavexs[MAX_VERTEX_NUM];/*頂點(diǎn)向量*/ ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接矩陣*/ intvexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/ GraphKindkind;/*圖的種類標(biāo)志*/}AdjMatrix;/*(AdjacencyMatrixGraph)*/intLocateVertex(AdjMatrix*G,VertexDatav)/*求頂點(diǎn)位置函數(shù)*/{ intj=Error,k; for(k=0;k<G->vexnum;k++) if(G->vexs[k]==v) { j=k; break; } return(j);}頭文件結(jié)束/創(chuàng)建程序如下intCreateDN(AdjMatrix*G)/*創(chuàng)建一個有向網(wǎng)*/{ inti,j,k,weight; VertexDatav1,v2; printf("輸入圖的弧數(shù)和頂點(diǎn)數(shù)\n"); fflush(stdin);scanf("%d,%d",&G->arcnum,&G->vexnum);/*輸入圖的頂點(diǎn)數(shù)和弧數(shù)*/for(i=0;i<G->vexnum;i++)/*初始化鄰接矩陣*/ for(j=0;j<G->vexnum;j++) G->arcs[i][j].adj=INFINITY;for(i=0;i<G->vexnum;i++)//輸入頂點(diǎn)字符循環(huán) {printf("輸入圖的頂點(diǎn)\n"); fflush(stdin); scanf("%c",&G->vexs[i]);/*輸入圖的頂點(diǎn)*/ } for(k=0;k<G->arcnum;k++) { printf("輸入一條弧的兩個頂點(diǎn)及權(quán)值\n"); fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個頂點(diǎn)及權(quán)值*/ i=LocateVertex(G,v1); j=LocateVertex(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ } return(Ok);}//深度優(yōu)先搜索遍歷圖—鄰接矩陣voidDepth1(AdjMatrixg1,intvo){ intvj; printf("%c",g1.vexs[vo]); visited[vo]=True; for(vj=0;vj<g1.vexnum1;vj++) if((!visited[vj])&&(g1.arcs[vo][vj].adj==1)) Depth1(g1,vj);}voidBreadth1(AdjMatrixg1,intvo){ intvi,vj; LinkQueueQ; InitQueue(&Q); visited[vo]=True; EnterQueue(&Q,vo); while(!IsEmpty(&Q)) { DeleteQueue(&Q,&vi); printf("%c",g1.vexs[vi]); for(vj=0;vj<g1.vexnum1;vj++) if((!visited[vj])&&(g1.arcs[vi][vj].adj==1)) { visited[vj]=True; EnterQueue(&Q,vj); } }}voidTraverse1(AdjMatrixg1)//鄰接矩陣存儲結(jié)構(gòu)的深度和廣度優(yōu)先搜索遍歷{ intvi; for(vi=0;vi<g1.vexnum1;vi++)//深度遍歷鄰接矩陣 visited[vi]=False; printf("\nTheorderofG1Depth\n"); for(vi=0;vi<g1.vexnum1;vi++) { if(!visited[vi]) { Depth1(g1,vi); printf("\n"); } }//廣度優(yōu)先搜索遍歷——鄰接矩陣 for(vi=0;vi<g1.vexnum1;vi++) visited[vi]=False; print