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

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

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

3、6微型計(jì)算機(jī)，主頻450MHZ以上，內(nèi)存64MB以上，硬盤10G，有軟驅(qū)。每個(gè)學(xué)生每次上機(jī)實(shí)驗(yàn)使用一臺(tái)計(jì)算機(jī)。軟件：Turbo C或Visual C+6.0二、實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）實(shí)驗(yàn)要求：以鄰接矩陣方式來保存圖，實(shí)現(xiàn)這種存儲(chǔ)方式下創(chuàng)建一個(gè)圖的算法。然后分別使用深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法對剛才創(chuàng)建的圖進(jìn)行遍歷。實(shí)驗(yàn)內(nèi)容：1、以鄰接矩陣方式來保存圖，實(shí)現(xiàn)這種存儲(chǔ)方式下創(chuàng)建一個(gè)圖的算法。2、創(chuàng)建一個(gè)圖，然后對這個(gè)圖進(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; /定頂點(diǎn)數(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é)點(diǎn)類型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<<"輸入你所要的頂點(diǎn)數(shù)以及弧數(shù)，以空格隔開:" cin>>G.vexnum>>G.arcnum; cout<<"輸入頂點(diǎn)向量:" 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、條邊依附的定點(diǎn):" 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; /定頂點(diǎn)數(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é)點(diǎn)類型int data; struct Node *next; QueueNode; typedef struct /鏈隊(duì)列類型QueueNode *front;QueueNode *rear;LinkQueue; int InitQueue(LinkQueue *Q)/構(gòu)造一個(gè)

14、空隊(duì)列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)/隊(duì)空 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<<"輸入你所要的頂點(diǎn)數(shù)以及弧數(shù)，以空格隔開:" cin>>G.vexnum>>G.arcnum; cout<<"輸入頂點(diǎn)向量:" 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<<"請輸入一條邊依附的定點(diǎn):" 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);/ 置空的輔助隊(duì)列Q EnQueue(&Q,v); while(!QueueEmpty(&Q) DeQueue(&Q,&vi); cout<<G.vexsvi<<"" for(vj=0;vj&l