數(shù)據(jù)結(jié)構(gòu)實驗4

1、學(xué) 生 實 驗 報 告學(xué) 院： 軟件與通信工程學(xué)院 課程名稱： 物聯(lián)網(wǎng)工程 專業(yè)班級： 物聯(lián)網(wǎng)141 姓 名： 李依凡 學(xué) 號： 0144356 學(xué)生實驗報告（理、工科類專業(yè)用）學(xué)生姓名李依凡學(xué)號0144356同組人無實驗項目圖的遍歷操作必修 選修 演示性實驗 驗證性實驗 操作性實驗 綜合性實驗實驗地點H114實驗儀器臺號B01指導(dǎo)教師蔣娜實驗日期及節(jié)次2015.12.09第四次試驗一、實驗綜述通過上機操作，力求能夠加深學(xué)生對課堂講授內(nèi)容的理解，掌握基本數(shù)據(jù)結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)的基本操作實現(xiàn)和在求解實際問題中的應(yīng)用，進(jìn)一步熟悉高級程序設(shè)計語言的編程環(huán)境及其編程規(guī)則，同時培養(yǎng)

2、學(xué)生書寫規(guī)范文檔的習(xí)慣，要求學(xué)生具有編制相當(dāng)規(guī)模的程序的能力，養(yǎng)成良好的程序設(shè)計風(fēng)格。對學(xué)生上機實驗的要求如下：（1）上機實驗之前，學(xué)生應(yīng)當(dāng)為每次上機的內(nèi)容作好充分準(zhǔn)備。對每次上機需要完成的題目進(jìn)行認(rèn)真的分析，列出實驗具體步驟，寫出符合題目要求的程序清單，準(zhǔn)備出調(diào)試程序使用的數(shù)據(jù)，以便提高上機實驗的效率。（2）按照實驗?zāi)康暮蛯嶒瀮?nèi)容以及思考題的要求進(jìn)行上機操作。錄入程序，編譯調(diào)試，反復(fù)修改，直到使程序正常運行，得出正確的輸出結(jié)果為止。（3）根據(jù)實驗結(jié)果，寫出實驗報告。實驗報告應(yīng)當(dāng)包括：實驗題目，實驗?zāi)康?，實驗要求，程序?qū)崿F(xiàn)，實驗結(jié)果以及分析討論等內(nèi)容。2、實驗儀器、設(shè)備或軟件硬件最低要求：58

3、6微型計算機，主頻450MHZ以上，內(nèi)存64MB以上，硬盤10G，有軟驅(qū)。每個學(xué)生每次上機實驗使用一臺計算機。軟件：Turbo C或Visual C+6.0二、實驗過程（實驗步驟、記錄、數(shù)據(jù)、分析）實驗要求：以鄰接矩陣方式來保存圖，實現(xiàn)這種存儲方式下創(chuàng)建一個圖的算法。然后分別使用深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法對剛才創(chuàng)建的圖進(jìn)行遍歷。實驗內(nèi)容：1、以鄰接矩陣方式來保存圖，實現(xiàn)這種存儲方式下創(chuàng)建一個圖的算法。2、創(chuàng)建一個圖，然后對這個圖進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷深度優(yōu)先遍歷程序#include<iostream>#include<stdlib.h>using nam

4、espace std;#define TRUE 1 #define FALSE 0 #define ERROR -1 #define OK 1 #define MaxInt 0 #define MAX_VERTEX_NUM 10 #define MAX_EDGE_NUM 20 typedef enum DG,DN,UDG,UDNGraphkind; typedef char VertexType; /定頂點數(shù)據(jù)類型為字符型typedef struct ArcCell int adj; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef

5、struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; Graphkind kind; AMGraph; typedef struct ArcNode int adjvex; int weight; struct ArcNode *nextarc; ArcNode; typedef struct VNode int data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnu

6、m,arcnum; int kind; ALGraph; int LocateVex(AMGraph G,VertexType v1) int i; for(i=0;i<G.vexnum;i+) if(G.vexsi=v1) return i; return -1; typedef struct Node/結(jié)點類型int data; struct Node *next; QueueNode;bool visitedMAX_VERTEX_NUM; /定義數(shù)組int CreatDN(AMGraph &G) / 采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)G VertexType v1,v2; in

7、t j,i; cout<<"輸入你所要的頂點數(shù)以及弧數(shù)，以空格隔開:" cin>>G.vexnum>>G.arcnum; cout<<"輸入頂點向量:" for(i=0;i<G.vexnum;i+) cin>>G.vexsi; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij.adj=MaxInt; for(int k=0;k<G.arcnum;+k) /構(gòu)造鄰接矩陣 cout<<"請輸入一

8、條邊依附的定點:" cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij.adj=1; G.arcsji=G.arcsij; return OK; void dispAMGraph(AMGraph G) /顯示圖的鄰接矩陣圖 cout<<"圖的鄰接矩陣是："<<endl; for(int i=0;i<G.vexnum;i+) for(int j=0;j<G.vexnum;j+) cout<<""<<

9、;G.arcsij.adj; cout<<endl; void DFSTraverse(AMGraph G,int v)/對圖G作深度優(yōu)先遍歷。 int w; cout<<G.vexsv<<"" visitedv=true; for(w=0;w<G.vexnum;w+) if(!visitedw)&&(!G.arcsvw.adj=0) DFSTraverse(G,w); void Traverse(AMGraph G)/輸出遍歷結(jié)果int v; for(v=0;v<G.vexnum;v+) visitedv=f

10、alse; cout<<"深度優(yōu)先遍歷的結(jié)果:" for(v=0;v<G.vexnum;v+) if(!visitedv) DFSTraverse(G,v); cout<<endl; void main() AMGraph G; cout<<"建立有向圖"<<endl; CreatDN(G);dispAMGraph(G);Traverse(G);cout<<endl; 廣度優(yōu)先遍歷#include<iostream>#include<stdlib.h>using n

11、amespace std;#define TRUE 1 #define FALSE 0 #define ERROR -1 #define OK 1 #define MaxInt 0 #define MAX_VERTEX_NUM 10 #define MAX_EDGE_NUM 20 typedef enum DG,DN,UDG,UDNGraphkind; typedef char VertexType; /定頂點數(shù)據(jù)類型為字符型typedef struct ArcCell int adj; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typede

12、f struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; Graphkind kind; AMGraph; typedef struct ArcNode int adjvex; int weight; struct ArcNode *nextarc; ArcNode; typedef struct VNode int data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vex

13、num,arcnum; int kind; ALGraph; int LocateVex(AMGraph G,VertexType v1) int i; for(i=0;i<G.vexnum;i+) if(G.vexsi=v1) return i; return -1; typedef struct Node/結(jié)點類型int data; struct Node *next; QueueNode; typedef struct /鏈隊列類型QueueNode *front;QueueNode *rear;LinkQueue; int InitQueue(LinkQueue *Q)/構(gòu)造一個

14、空隊列Q Q->front=(QueueNode*)malloc(sizeof(QueueNode); if(Q->front!=NULL) Q->rear=Q->front; Q->front->next=NULL; return(OK); else return(FALSE); int EnQueue(LinkQueue *Q,int x)/ 插入QueueNode *p; p=(QueueNode*)malloc(sizeof(QueueNode); if(p!=NULL) p->data=x; p->next=NULL; Q->re

15、ar->next=p; Q->rear=p; return(OK); else return(FALSE); int DeQueue(LinkQueue *Q,int *x) QueueNode *p; if(Q->front=Q->rear) return(FALSE); p=Q->front->next; Q->front->next=p->next; if(Q->rear=p) Q->rear=Q->front; *x=p->data; free(p); return(OK); int QueueEmpty(L

16、inkQueue *Q)/隊空 if(Q->front=Q->rear) return(OK); else return(FALSE); bool visitedMAX_VERTEX_NUM; /定義數(shù)組int CreatDN(AMGraph &G) / 采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)G VertexType v1,v2; int j,i; cout<<"輸入你所要的頂點數(shù)以及弧數(shù)，以空格隔開:" cin>>G.vexnum>>G.arcnum; cout<<"輸入頂點向量:" for(

17、i=0;i<G.vexnum;i+) cin>>G.vexsi; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij.adj=MaxInt; for(int k=0;k<G.arcnum;+k) /構(gòu)造鄰接矩陣 cout<<"請輸入一條邊依附的定點:" cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij.adj=1; G.arcsji=G.arcsij; return OK; v

18、oid dispAMGraph(AMGraph G) /顯示圖的鄰接矩陣圖 cout<<"圖的鄰接矩陣是："<<endl; for(int i=0;i<G.vexnum;i+) for(int j=0;j<G.vexnum;j+) cout<<""<<G.arcsij.adj;/輸出cout<<endl; void BFSTraverse(AMGraph G,int v)/對圖G作廣度優(yōu)先遍歷。 int vi,vj; LinkQueue Q; visitedv=true;InitQueue(&Q);/ 置空的輔助隊列Q EnQueue(&Q,v); while(!QueueEmpty(&Q) DeQueue(&Q,&vi); cout<<G.vexsvi<<"" for(vj=0;vj&l