浙大城院數據結構實驗報告report13

浙江大學城市學院實驗報告課程名稱數據結構基礎實驗項目名稱實驗十三圖的基本操作—鄰接表存儲結構學生姓名專業(yè)班級學號實驗成績指導老師（簽名）日期頭文件AdjLink.h，在該文件中定義圖的鄰接表存儲結構，并編寫圖的初始化、建立圖、輸出圖、輸出圖的每個頂點的度圖的深度優(yōu)先遍歷函數與廣度優(yōu)先遍歷函數等基本操作實現函數。同時在主函數文件test5_2.cpp中調用這些函數進行驗證。三.函數的功能說明及算法思路（包括每個函數的功能說明，及一些重要函數的算法實現思路）這里針對的都是無向無權圖結構類型定義//邊表結點//頂點表結點//圖類型typedefstructnodetypedefstruct{typedefstruct{{intadjvex;//鄰接點域 VertexTypevertex;//頂點域AdjListadjlist;//鄰接表node*next;//鏈域EdgeNode*firstedge;//邊表頭指針intn,e;//圖中當前頂點數和邊數}EdgeNode;}VertexNode;}ALGraph;//圖類型typedefVertexNodeAdjList[MaxVertexNum];//AdjList是鄰接表類型基本面函數1.voidCreatALGraph(ALGraph*G)//構造圖{定義邊表結點s；讀入頂點數和邊數；讀入頂點信息，并將邊表置為空；依次讀入<入度點vi，出度點vj>邊的信息直到輸入的邊數達到要求{ 為s開辟新空間，鄰接點序號為j，并將鄰接點指針為i頂點的頭指針值，將新結點*S插入頂點Vi的邊表頭部 為s再開辟新空間，鄰接點序號為i，并將鄰接點指針為j頂點的頭指針值，將新結點*S插入頂點Vj的邊表頭部}}voidDFS(ALGraph*G,inti)//以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索voidDFSTraverseM(ALGraph*G)//對整個圖進行深度搜索4.voidBFS(ALGraph*G,intk)//以Vk為源點對用鄰接鏈表表示的圖G進行廣度優(yōu)先搜索5.voidBFSTraverseM(ALGraph*G){//對整個圖進行廣度搜索廣度搜索時要建立隊列并寫隊列的相應函數6.voidPrintALGraph(ALGraph*G){//輸出表四.實驗結果與分析（包括運行結果截圖、結果分析等）五.心得體會（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）失敗點:1.scanf();輸入格式上面出錯，沒有嚴格按照要求輸出所以常常運行到一半就出錯誤2.在剛開始的時候以為頂點Vertexnode中VerTex輸入的是地址值，學習點：1.typedefenum{FALSE,TRUE}Boolean;聲明了一個枚舉類型一般形式為：enum[枚舉名]{枚舉元素列表}；

也可以聲明沒有枚舉名的枚舉類型，就是像你給的那種，后邊的bool是枚舉類型的變量，可以對其進行賦值，不過只能用FALSE或者TRUE進行賦值?！靖戒?---源程序】test5_2.cpp#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include"AdjLink.h"voidmain(){inti;ALGraph*G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);PrintALGraph(G);printf("PrintGraphDFS:\n");DFSTraverseM(G);printf("\n");printf("PrintGraphBFS:\n");BFSTraverseM(G);printf("\n");}AdjLink.h#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100#defineQueueSize30typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];typedefcharVertexType;typedefintEdgeType;typedefstructnode//邊表結點{intadjvex;//鄰接點域node*next;//鏈域}EdgeNode;typedefstruct{//頂點表結點VertexTypevertex;//頂點域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是鄰接表類型typedefstruct{AdjListadjlist;//鄰接表intn,e;//圖中當前頂點數和邊數}ALGraph;//圖類型/*=========建立無向圖鄰接表算法=======*/voidCreatALGraph(ALGraph*G){inti,j,k;EdgeNode*s;//定義邊表結點printf("請輸入頂點數和邊數(輸入格式為:頂點數，邊數):\n");scanf("%d,%d",&(G->n),&(G->e));//讀入頂點數和邊數printf("請輸入頂點信息(輸入格式為:頂點號<CR>)每個頂點以回車作為結束:\n");for(i=0;i<G->n;i++)//建立邊表{ scanf("\n%c",&(G->adjlist[i].vertex));//讀入頂點信息 G->adjlist[i].firstedge=NULL;//邊表置為空表}printf("請輸入邊的信息(輸入格式:i,j):\n");for(k=0;k<G->e;k++){//建立邊表 scanf("\n%d,%d",&i,&j);//讀入邊（Vi，Vj）的頂點對序號 s=newEdgeNode; s->adjvex=j;//鄰接點序號為j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s;//將新結點*S插入頂點Vi的邊表頭部 s=newEdgeNode; s->adjvex=i;//鄰接點序號為i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s;//將新結點*S插入頂點Vj的邊表頭部}}voidPrintALGraph(ALGraph*G){//輸出表 inti; for(i=0;i<G->n;i++){ printf("%d->",i); while(G->adjlist[i].firstedge!=NULL){ printf("%d->",G->adjlist[i].firstedge->adjvex); G->adjlist[i].firstedge=G->adjlist[i].firstedge->next; } printf("\n");}}/*=======深度優(yōu)先遍歷的遞歸算法======*/voidDFS(ALGraph*G,inti){//以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索EdgeNode*p;printf("vsitvertex:%c\n",G->adjlist[i].vertex);//訪問頂點Vivisited[i]=TRUE;//標記Vi已訪問p=G->adjlist[i].firstedge;//取Vi邊表的頭指針while(p){//依次搜索Vi的鄰接點Vj，這里j=p->adjvex if(!visited[p->adjvex])//若Vj尚未被訪問 DFS(G,p->adjvex);//則以Vj為出發(fā)點向縱深搜索 p=p->next;//找Vi的下一個鄰接點}}voidDFSTraverseM(ALGraph*G){inti;for(i=0;i<G->n;i++) visited[i]=FALSE;//標志向量初始化for(i=0;i<G->n;i++) if(!visited[i])//Vi未訪問過 DFS(G,i);//以Vi為源點開始DFS搜索}/*==========BFS：廣度優(yōu)先遍歷=========*/typedefstruct{ intfront; intrear; intcount; intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){ Q->front=Q->rear=0; Q->count=0;}intQueueEmpty(CirQueue*Q){ returnQ->count=QueueSize;}intQueueFull(CirQueue*Q){ returnQ->count==QueueSize;}voidEnQueue(CirQueue*Q,intx){ if(QueueFull(Q)) printf("Queueoverflow"); else { Q->count++; Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; }}intDeQueue(CirQueue*Q){ inttemp; if(QueueEmpty(Q)) { printf("Queueunderflow"); returnNULL; } else { temp=Q->data[Q->front]; Q->count--; Q->front=(Q->front+1)%QueueSize; returntemp; }}voidBFS(ALGraph*G,intk){//以Vk為源點對用鄰接鏈表表示的圖G進行廣度優(yōu)先搜索inti; CirQueueQ; EdgeNode*p; InitQueue(&Q);//隊列初始化 printf("Visitvertex:%c\n",G->adjlist[k].vertex); visited[k]=TRUE; EnQueue(&Q,k); while(!QueueEmpty(&Q)){ i=DeQueue(&Q); p=G->adjlist[i].firstedge; while(p){ if(!vi