數(shù)據(jù)結(jié)構(gòu)試驗報告-圖的基本操作.doc

中原工學院數(shù)據(jù)結(jié)構(gòu)實驗報告學 院： 計算機學院 專 業(yè)：計算機科學與技術(shù) 班 級： 計科112 姓 名： 康巖巖 學 號： 201100814220 指導老師： 高艷霞 2012-11-22實驗五 圖的基本操作一、實驗?zāi)康?、使學生可以鞏固所學的有關(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ù)】由學生依據(jù)軟件工程的測試技術(shù)自己確定。三、實驗前的準備工作1、掌握圖的相關(guān)概念。2、掌握圖的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析?！驹O(shè)計思路】【代碼整理】#include stdafx.h#include #include using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enumDG,DN,UDG,UDNKind;typedef struct ArcNodeint adjvex; /頂點位置struct ArcNode *nextarc; /下一條弧int *info; /弧信息;typedef structchar info10; /頂點信息ArcNode *fistarc; /指向第一條弧VNode,AdjListMAX_SIZE;typedef structAdjList vertices;int vexnum,arcnum; /頂點數(shù)，弧數(shù)int kind; /圖的種類，此為無向圖ALGraph; /這是隊列的節(jié)點，僅用于廣度優(yōu)先搜索typedef struct Nodeint num;struct Node* next;/隊列的頭和尾typedef structNode * front;Node *rear;PreBit;int LocateVex(ALGraph G,char info);/定位頂點的位置Status addArcNode(ALGraph &G,int adjvex); /圖中加入弧Status CreatGraph(ALGraph&G);/創(chuàng)建圖的鄰接表Status DFSTraverse(ALGraph G);/深度優(yōu)先搜索Status BFSTraverse(ALGraph G);/廣度優(yōu)先搜索Status DFS(ALGraph G,int v);/深度優(yōu)先搜索中的數(shù)據(jù)讀取函數(shù)，用于遞歸bool visitedMAX_SIZE; / 訪問標志數(shù)組/初始化隊列Status init_q(PreBit&P_B)P_B.front=P_B.rear=(Node*)malloc(sizeof(Node);if(!P_B.front)exit(OVERFLOW);P_B.front-next=NULL;/將數(shù)據(jù)入隊Status en_q(PreBit & P_B,int num)Node *p=(Node*)malloc(sizeof(Node);if(!p)exit(OVERFLOW);p-num=num;p-next=NULL;P_B.rear-next=p;P_B.rear=p;return OK;/出隊Status de_q(PreBit & P_B)if(P_B.front=P_B.rear)return ERROR;Node* p=P_B.front-next;P_B.front-next=p-next;if(P_B.rear=p)P_B.rear=P_B.front;free(p);return OK;Status CreatGraph(ALGraph&G)cout請輸入頂點數(shù)目和弧數(shù)目G.vexnumG.arcnum;/依次輸入頂點信息for(int i=0;iG.vexnum;i+)cout請輸入頂點名稱G.;G.verticesi.fistarc=NULL;/依次輸入弧信息for(int k=1;k=G.arcnum;k+)char v110,v210; /用于表示頂點名稱的字符數(shù)組int i,j; /表示兩個頂點的位置BACK: /返回點cout請輸入第k條弧的兩個頂點v1v2;i=LocateVex(G,v1); /得到頂點v1的位置j=LocateVex(G,v2); /得到頂點v2的位置if(i=-1|j=-1) /頭信息不存在則返回重輸cout不存在該節(jié)點!adjvex=adjvex; p-nextarc=G.verticesadjvex.fistarc;/指向頭結(jié)點的第一條弧G.verticesadjvex.fistarc=p; /頭結(jié)點的第一條弧指向p，即將p作為頭結(jié)點的第一條弧return OK;/定位頂點的位置int LocateVex(ALGraph G,char info)for(int i=0;iG.vexnum;i+)if(strcmp(G.,info)=0) /頭結(jié)點名稱與傳入的信息相等，證明該頭節(jié)點存在return i; /此時返回位置return -1;/深度優(yōu)先搜索Status DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;v+)visitedv=false;char v110;int i;BACK:cout請輸入首先訪問的頂點v1;i=LocateVex(G,v1);if(i=-1)cout不存在該節(jié)點!endl;goto BACK;DFS(G,i);return OK;/深度優(yōu)先搜索遞歸訪問圖Status DFS(ALGraph G,int v)visitedv=true;coutG.adjvex)DFS(G,p-adjvex); /遞歸讀取p=p-nextarc;return OK;/廣度優(yōu)先搜索Status BFSTraverse(ALGraph G)for(int v=0;vG.vexnum;v+)visitedv=false;char v110;int v;BACK:cout請輸入首先訪問的頂點v1;v=LocateVex(G,v1);if(v=-1)cout不存在該節(jié)點!endl;goto BACK;PreBit P_B;init_q(P_B);ArcNode *p;visitedv=true;coutG.next-num;/讀出頂點位置de_q(P_B);/頂點已經(jīng)訪問過，將其出隊列p=G.verticesw.fistarc;/得到與頂點相關(guān)的第一條弧 while(p) if(!visitedp-adjvex)en_q(P_B,p-adjvex);/將弧入隊，但不讀取，只是將其放在隊尾p=p-nextarc;return OK;int _