数据结构实验4

1、学 生 实 验 报 告学 院： 软件与通信工程学院 课程名称： 物联网工程 专业班级： 物联网141 姓 名： 李依凡 学 号： 0144356 学生实验报告（理、工科类专业用）学生姓名李依凡学号0144356同组人无实验项目图的遍历操作必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点H114实验仪器台号B01指导教师蒋娜实验日期及节次2015.12.09第四次试验一、实验综述通过上机操作，力求能够加深学生对课堂讲授内容的理解，掌握基本数据结构：集合、线性结构、树形结构、网状结构的基本操作实现和在求解实际问题中的应用，进一步熟悉高级程序设计语言的编程环境及其编程规则，同时培养

2、学生书写规范文档的习惯，要求学生具有编制相当规模的程序的能力，养成良好的程序设计风格。对学生上机实验的要求如下：（1）上机实验之前，学生应当为每次上机的内容作好充分准备。对每次上机需要完成的题目进行认真的分析，列出实验具体步骤，写出符合题目要求的程序清单，准备出调试程序使用的数据，以便提高上机实验的效率。（2）按照实验目的和实验内容以及思考题的要求进行上机操作。录入程序，编译调试，反复修改，直到使程序正常运行，得出正确的输出结果为止。（3）根据实验结果，写出实验报告。实验报告应当包括：实验题目，实验目的，实验要求，程序实现，实验结果以及分析讨论等内容。2、实验仪器、设备或软件硬件最低要求：58

3、6微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。每个学生每次上机实验使用一台计算机。软件：Turbo C或Visual C+6.0二、实验过程（实验步骤、记录、数据、分析）实验要求：以邻接矩阵方式来保存图，实现这种存储方式下创建一个图的算法。然后分别使用深度优先遍历算法和广度优先遍历算法对刚才创建的图进行遍历。实验内容：1、以邻接矩阵方式来保存图，实现这种存储方式下创建一个图的算法。2、创建一个图，然后对这个图进行深度优先遍历和广度优先遍历深度优先遍历程序#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; /定顶点数据类型为字符型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/结点类型int data; struct Node *next; QueueNode;bool visitedMAX_VERTEX_NUM; /定义数组int CreatDN(AMGraph &G) / 采用邻接矩阵表示法，构造无向网G VertexType v1,v2; in

7、t j,i; cout<<"输入你所要的顶点数以及弧数，以空格隔开:" 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) /构造邻接矩阵 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作深度优先遍历。 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)/输出遍历结果int v; for(v=0;v<G.vexnum;v+) visitedv=f

10、alse; cout<<"深度优先遍历的结果:" 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; 广度优先遍历#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; /定顶点数据类型为字符型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/结点类型int data; struct Node *next; QueueNode; typedef struct /链队列类型QueueNode *front;QueueNode *rear;LinkQueue; int InitQueue(LinkQueue *Q)/构造一个

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; /定义数组int CreatDN(AMGraph &G) / 采用邻接矩阵表示法，构造无向网G VertexType v1,v2; int j,i; cout<<"输入你所要的顶点数以及弧数，以空格隔开:" 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) /构造邻接矩阵 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作广度优先遍历。 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