圖的基本操作實(shí)驗(yàn)報(bào)告.doc

實(shí)驗(yàn)五 圖的基本操作一、實(shí)驗(yàn)?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識(shí)。2、熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。3、熟練掌握?qǐng)D的兩種遍歷算法。二、實(shí)驗(yàn)內(nèi)容問(wèn)題描述對(duì)給定圖，實(shí)現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷?；疽笠脏徑颖頌榇鎯?chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶(hù)指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪(fǎng)問(wèn)序列。【測(cè)試數(shù)據(jù)】由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握?qǐng)D的相關(guān)概念。2、掌握?qǐng)D的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。3、掌握?qǐng)D的兩種遍歷算法的實(shí)現(xiàn)。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書(shū)寫(xiě)。2、實(shí)驗(yàn)上要寫(xiě)出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。五、算法設(shè)計(jì)1、 程序所需頭文件已經(jīng)預(yù)處理宏定義和結(jié)構(gòu)體定義如下#include#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;2、 創(chuàng)建無(wú)向圖void CreatAdjList(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;cout請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):G-vexnumG-arcnum;cout開(kāi)始輸入頂點(diǎn)表:endl;for (i=0;ivexnum;i+)cinG-adjlistsi.vertex;G-adjlistsi.edgelink=NULL;cout開(kāi)始輸入邊表信息:endl;for (k=0;karcnum;k+)cout請(qǐng)輸入邊對(duì)應(yīng)的頂點(diǎn):;cinij;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.edgelink=p2;/因?yàn)槭菬o(wú)向圖，所以有兩次建立邊表的過(guò)程3、 深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit)coutadjlistsi.vertexadjlistsi.edgelink;if(G-adjlistsi.edgelink&!visitp-endver)DFS(G,p-endver,visit);void DFStraversal(Graph *G,char c)/深度優(yōu)先遍歷cout該圖的深度優(yōu)先遍歷結(jié)果為:endl;int visitMaxVerNum;for(int i=0;ivexnum;i+)visiti=0;/全部初始化為0，即未訪(fǎng)問(wèn)狀態(tài)int m;for (i=0;ivexnum;i+)if (G-adjlistsi.vertex=c)/根據(jù)字符查找序號(hào)m=i;DFS(G,i,visit);break;/繼續(xù)訪(fǎng)問(wèn)未被訪(fǎng)問(wèn)的結(jié)點(diǎn)for(i=0;ivexnum;i+)if(visiti=0)DFS(G,i,visit);coutfront=Q-rear=NULL;EnQueue(Q,v);while(Q-rear!=NULL)int e=0;DeQueue(Q,&e);coutadjlistse.vertexadjlistse.edgelink;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;ivexnum;i+)visitedi=0;int m;for (i=0;ivexnum;i+)if (G-adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/繼續(xù)訪(fǎng)問(wèn)未被訪(fǎng)問(wèn)的結(jié)點(diǎn)for(i=0;ivexnum;i+)if(visitedi=0)BFS(G,i,visited);coutendl;六、調(diào)試與測(cè)試 測(cè)試數(shù)據(jù)，如圖：七、總結(jié)通過(guò)做這次實(shí)驗(yàn)，發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)這門(mén)課中還有很多不足有很多知識(shí)還沒(méi)掌握，所以在寫(xiě)程序的時(shí)候出現(xiàn)了很多的錯(cuò)誤，及還有很多的知識(shí)不以靈活運(yùn)用。C+沒(méi)有掌握好，所以這次做本次實(shí)驗(yàn)還是吃力，剛開(kāi)始完全沒(méi)有思路，后來(lái)經(jīng)過(guò)查找資料，在自己的努力下和同學(xué)的幫助下，終于完了本次實(shí)驗(yàn)，此次實(shí)驗(yàn)發(fā)現(xiàn)的自己的不足，在以后的學(xué)習(xí)中，我會(huì)更加的努力。八、源代碼#include#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/隊(duì)列的定義及相關(guān)函數(shù)的實(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-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(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;cout請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):G-vexnumG-arcnum;cout開(kāi)始輸入頂點(diǎn)表:endl;for (i=0;ivexnum;i+)cinG-adjlistsi.vertex;G-adjlistsi.edgelink=NULL;cout開(kāi)始輸入邊表信息:endl;for (k=0;karcnum;k+)cout請(qǐng)輸入邊對(duì)應(yīng)的頂點(diǎn):;cinij;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.edgelink=p2;/因?yàn)槭菬o(wú)向圖，所以有兩次建立邊表的過(guò)程/深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit)coutadjlistsi.vertexadjlistsi.edgelink;if(G-adjlistsi.edgelink&!visitp-endver)DFS(G,p-endver,visit);void DFStraversal(Graph *G,char c)/深度優(yōu)先遍歷cout該圖的深度優(yōu)先遍歷結(jié)果為:endl;int visitMaxVerNum;for(int i=0;ivexnum;i+)visiti=0;/全部初始化為0，即未訪(fǎng)問(wèn)狀態(tài)int m;for (i=0;ivexnum;i+)if (G-adjlistsi.vertex=c)/根據(jù)字符查找序號(hào)m=i;DFS(G,i,visit);break;/繼續(xù)訪(fǎng)問(wèn)未被訪(fǎng)問(wèn)的結(jié)點(diǎn)for(i=0;ivexnum;i+)if(visiti=0)DFS(G,i,visit);coutfront=Q-rear=NULL;EnQueue(Q,v);while(Q-rear!=NULL)int e=0;DeQueue(Q,&e);coutadjlistse.vertexadjlistse.edgelink;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;ivexnum;i+)visitedi=0;int m;for (i=0;ivexnum;i+)if (G-adjlistsi.ver