實(shí)驗(yàn)報(bào)告院（系）：信息科學(xué)與技術(shù)學(xué)院課程名稱：數(shù)據(jù)結(jié)構(gòu)日期：班級(jí)學(xué)號(hào)實(shí)驗(yàn)室專業(yè)姓名計(jì)算機(jī)號(hào)實(shí)驗(yàn)名稱圖的存儲(chǔ)與基本操作成績(jī)?cè)u(píng)定所用軟件VC或TC教師簽名實(shí)驗(yàn)?zāi)康模?）掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)；（2）實(shí)現(xiàn)圖的鄰接矩陣存儲(chǔ)。（3）掌握?qǐng)D的遍歷方法。實(shí)驗(yàn)準(zhǔn)備復(fù)習(xí)書上有關(guān)內(nèi)容。閱讀實(shí)驗(yàn)內(nèi)容1。編出實(shí)驗(yàn)內(nèi)容2、3的源程序。實(shí)驗(yàn)內(nèi)容二、設(shè)計(jì)算法對(duì)鄰接表表示的無向網(wǎng)進(jìn)行廣度優(yōu)先遍歷。#include<stdio.h>#include<stdlib.h>typedefintDataType;//將隊(duì)列中元素的數(shù)據(jù)類型改為Person//循環(huán)隊(duì)列的類型定義#defineQueueSize100 //應(yīng)根據(jù)具體情況定義該值typedefstruct{ intfront; //頭指針，隊(duì)非空時(shí)指向隊(duì)頭元素 intrear; //尾指針，隊(duì)非空時(shí)指向隊(duì)尾元素的下一位置 intcount; //計(jì)數(shù)器，記錄隊(duì)中元素總數(shù) DataTypedata[QueueSize];}CirQueue;#defineMaxVertexNum100 //最大頂點(diǎn)數(shù)，應(yīng)由用戶定義typedefcharVertexType; //頂點(diǎn)類型應(yīng)由用戶定義typedefstructnode{ //邊表結(jié)點(diǎn) intadjvex; //鄰接點(diǎn)域 structnode*next; //鏈域 //若要表示邊上的權(quán)，則應(yīng)增加一個(gè)數(shù)據(jù)域}EdgeNode;typedefstructvnode{ //頂點(diǎn)表結(jié)點(diǎn) VertexTypevertex; //頂點(diǎn)域 EdgeNode*firstedge; //邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]; //AdjList是鄰接表類型typedefstruct{ AdjListadjlist; //鄰接表 intn,e; //圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}ALGraph; //對(duì)于簡(jiǎn)單的應(yīng)用，無須定義此類型，可直接使用AdjList類型typedefenum{FALSE,TRUE}Boolean; //FALSE為0，TRUE為1Booleanvisited[MaxVertexNum]; //訪問標(biāo)志向量是全局量voidmain(){ voidInitQueue(CirQueue*Q); intQueueEmpty(CirQueue*Q); intQueueFull(CirQueue*Q); voidEnQueue(CirQueue*Q,DataTypex); DataTypeDeQueue(CirQueue*Q); DataTypeQueueFront(CirQueue*Q); voidCreateALGraph(ALGraph*G); voidPrintALGraph(ALGraph*G); voidBFS(ALGraph*G,intk); ALGraphG; CreateALGraph(&G); PrintALGraph(&G); printf("廣度優(yōu)先搜索結(jié)果："); BFS(&G,0); printf("\n");}voidCreateALGraph(ALGraph*G){ //建立無向圖的鄰接表表示 inti,j,k; EdgeNode*s; printf("請(qǐng)輸出頂點(diǎn)數(shù)和邊數(shù)："); scanf("%d%d",&G->n,&G->e); //讀入頂點(diǎn)數(shù)和邊數(shù) printf("請(qǐng)輸出頂點(diǎn)信息："); for(i=0;i<G->n;i++){ //建立頂點(diǎn)表 while((G->adjlist[i].vertex=getchar())=='\n'); //讀入頂點(diǎn)信息 G->adjlist[i].firstedge=NULL; //邊表置為空表 } for(k=0;k<G->e;k++){ //建立邊表 printf("\n請(qǐng)輸出第%d邊的起點(diǎn)、終點(diǎn)：",k+1); scanf("%d%d",&i,&j); //讀入邊(vi,vj)的頂點(diǎn)對(duì)序號(hào) s=(EdgeNode*)malloc(sizeof(EdgeNode)); //生成邊表結(jié)點(diǎn) s->adjvex=j; //鄰接點(diǎn)序號(hào)為j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部 s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=i; //鄰接點(diǎn)序號(hào)為i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; //將新結(jié)點(diǎn)*s插入頂點(diǎn)vj的邊表頭部 }}//打印鄰接表：voidPrintALGraph(ALGraph*G){ inti; EdgeNode*p; for(i=0;i<G->n;i++) { printf("%d%c:\t",i,G->adjlist[i].vertex); p=G->adjlist[i].firstedge; while(p) { printf("%d\t",p->adjvex); p=p->next; } printf("\n"); }}voidInitQueue(CirQueue*Q){ (*Q).front=(*Q).rear=0; (*Q).count=0; //計(jì)數(shù)器置0}intQueueEmpty(CirQueue*Q){ return(*Q).count==0; //隊(duì)列無元素為空}intQueueFull(CirQueue*Q){ return(*Q).count==QueueSize; //隊(duì)中元素個(gè)數(shù)等于QueueSize時(shí)隊(duì)滿}voidEnQueue(CirQueue*Q,DataTypex){ if(QueueFull(Q)) { printf("Queueoverflow"); exit(0); //隊(duì)滿上溢 } (*Q).count++; //隊(duì)列元素個(gè)數(shù)加1 (*Q).data[(*Q).rear]=x; //新元素插入隊(duì)尾 (*Q).rear=((*Q).rear+1)%QueueSize;//循環(huán)意義下將尾指針加1}DataTypeDeQueue(CirQueue*Q){ DataTypetemp; if(QueueEmpty(Q)) { printf("Queueunderflow"); exit(0); //隊(duì)空下溢 } temp=(*Q).data[(*Q).front]; (*Q).count--; //隊(duì)列元素個(gè)數(shù)減1 (*Q).front=((*Q).front+1)%QueueSize;//循環(huán)意義下的頭指針加1 returntemp;}DataTypeQueueFront(CirQueue*Q){ if(QueueEmpty(Q)) { printf("Queueisempty"); exit(0); } return(*Q).data[(*Q).front];}voidBFS(ALGraph*G,intk){ //以vk為源點(diǎn)對(duì)用鄰接表表示的圖G進(jìn)行廣度優(yōu)先搜索 inti; CirQueueQ; //須將隊(duì)列定義中DataType改為int EdgeNode*p; InitQueue(&Q); //隊(duì)列初始化 printf("%c",G->adjlist[k].vertex); //訪問源點(diǎn)vk visited[k]=TRUE; EnQueue(&Q,k); //vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(!QueueEmpty(&Q)){ //隊(duì)非空則執(zhí)行 i=DeQueue(&Q); //相當(dāng)于vi出隊(duì) p=G->adjlist[i].firstedge; //取vi的邊表頭指針 while(p){ //依次搜索vi的鄰接點(diǎn)vj（令p->adjvex=j） if(!vi