圖的基本操作-數(shù)據(jù)實驗報告書(共11頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗報告書實驗內(nèi)容：圖的基本操作* 計科111* 前言計算機(jī)編程中加工處理的對象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)計算機(jī)編程僅僅了解計算機(jī)語言是不夠的，還必須掌握數(shù)據(jù)的組織、存儲和運算的一般方法，這便是數(shù)據(jù)結(jié)構(gòu)課程中所研究的內(nèi)容，也是我們編寫計算機(jī)程序的重要基礎(chǔ)，由于它對計算機(jī)學(xué)科起到承前啟后的作用，因此本課程被列為計算機(jī)等相關(guān)專業(yè)最重要的專業(yè)基礎(chǔ)課；同時數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)教學(xué)的一門核心課程。計算機(jī)各領(lǐng)域都要用到各種數(shù)據(jù)結(jié)構(gòu)，而且要從事計算機(jī)科學(xué)與技術(shù)工作，尤其是計算機(jī)領(lǐng)域的軟件開發(fā)工作，必須具備較強(qiáng)的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容豐富、學(xué)習(xí)量大，實

2、踐性強(qiáng)；隱含在各部分內(nèi)容中的方法和技術(shù)多；算法設(shè)計具有動態(tài)性和抽象性等特點，看懂聽明白與掌握會應(yīng)用之間有相當(dāng)大的一段距離。所以學(xué)生必須多實踐才能進(jìn)一步加深對課程的理解，理解和掌握算法設(shè)計所需的方法和技術(shù)，為整個專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。一、實驗?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識。2、熟練掌握圖的存儲結(jié)構(gòu)。3、熟練掌握圖的兩種遍歷算法。二、實驗內(nèi)容問題描述對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷?；疽笠脏徑颖頌榇鎯Y(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列?！緶y試數(shù)據(jù)】由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。三、實驗前的準(zhǔn)

3、備工作1、掌握圖的相關(guān)概念。2、掌握圖的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進(jìn)行分析。3、 算法設(shè)計1、 程序所需頭文件已經(jīng)預(yù)處理宏定義和結(jié)構(gòu)體定義如下#include<iostream.h>#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struc

4、t Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;2、 隊列的定義及相關(guān)函數(shù)的實現(xiàn) struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NULL)Q->fron

5、t=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;3、 創(chuàng)建無向圖void CreatAdjList(Graph* G)

6、int i,j,k;edgenode* p1;edgenode* p2;cout<<"請輸入頂點數(shù)和邊數(shù):"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"開始輸入頂點表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"開始輸入邊表信息:"&

7、lt;<endl;for (k=0;k<G->arcnum;k+)cout<<"請輸入邊<Vi,Vj>對應(yīng)的頂點:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj

8、.edgelink=p2;/因為是無向圖，所以有兩次建立邊表的過程4、 深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Graph *G

9、,char c)/深度優(yōu)先遍歷cout<<"該圖的深度優(yōu)先遍歷結(jié)果為:"<<endl;int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化為0，即未訪問狀態(tài)int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根據(jù)字符查找序號m=i;DFS(G,i,visit);break;/繼續(xù)訪問未被訪問的結(jié)點for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i

10、,visit);cout<<endl;5、 廣度優(yōu)先遍歷void BFS(Graph* G,int v,int visit)QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink

11、;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)cout<<"該圖的廣度優(yōu)先遍歷結(jié)果為:"<<endl;int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->vex

12、num;i+)if (G->adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/繼續(xù)訪問未被訪問的結(jié)點for(i=0;i<G->vexnum;i+)if(visitedi=0)BFS(G,i,visited);cout<<endl;4、 調(diào)試與測試 我們開始測試數(shù)據(jù)，如圖： 由圖可知，我們得出了結(jié)果。五、總結(jié)通過做這次實驗，發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)這門課中還有很多不足有很多知識還沒掌握，所以在寫程序的時候出現(xiàn)了很多的錯誤，及還有很多的知識不以靈活運用。因為以前C語言沒有掌握好，所以這次做本次實驗還是有點吃力，剛開始完全沒有思，后

13、來經(jīng)過查找資料，在自己的努力下和同學(xué)的幫助下，終于完了本次實驗。還要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數(shù)據(jù)的輸入有問題，結(jié)果當(dāng)然也就不可能正確了。只有正確的輸入數(shù)據(jù)，建立圖，才能得出正確的遍歷結(jié)果。此次實驗發(fā)現(xiàn)的自己的不足，我相信在以后的學(xué)習(xí)中，我會更加的努力。六、源代碼#include<iostream.h>#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* e

14、dgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/隊列的定義及相關(guān)函數(shù)的實現(xiàn)struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NULL)

15、Q->front=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;/創(chuàng)建圖void CreatAdjList(Gra

16、ph* G)int i,j,k;edgenode* p1;edgenode* p2;cout<<"請輸入頂點數(shù)和邊數(shù):"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"開始輸入頂點表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"開始輸入邊表信息:&

17、quot;<<endl;for (k=0;k<G->arcnum;k+)cout<<"請輸入邊<Vi,Vj>對應(yīng)的頂點:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adj

18、listsj.edgelink=p2;/因為是無向圖，所以有兩次建立邊表的過程/深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Grap

19、h *G,char c)/深度優(yōu)先遍歷cout<<"該圖的深度優(yōu)先遍歷結(jié)果為:"<<endl;int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化為0，即未訪問狀態(tài)int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根據(jù)字符查找序號m=i;DFS(G,i,visit);break;/繼續(xù)訪問未被訪問的結(jié)點for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i,visit);cout<<endl;/廣度優(yōu)先遍歷void BFS(Graph* G,int v,int visit)QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "vi