数据结构实验4

学生实验报告

学院：软件与通信工程学院

课程名称：物联网工程

专业班级：物联网141

姓名：李依凡

学号：0144356

学生实验报告

（理、工科类专业用）

一、实验综述

通过上机操作，力求能够加深学生对课堂讲授内容的理解，掌握基本数据结构：集合、线性结构、树形结构、网状结构的基本操作实现和在求解实际问题中的应用，进一步熟悉高级程序设计语言的编程环境及其编程规则，同时培养学生书写规范文档的习惯，要求学生具有编制相当规模的程序的能力，养成良好的程序设计风格。

对学生上机实验的要求如下：

（1）上机实验之前，学生应当为每次上机的内容作好充分准备。对每次上机需要完成的题目进行认真的分析，列出实验具体步骤，写出符合题目要求的程序清单，准备出调试程序使用的数据，以便提高上机实验的效率。

（2）按照实验目的和实验内容以及思考题的要求进行上机操作。录入程序，编译调试，反复修改，直到使程序正常运行，得出正确的输出结果为止。

（3）根据实验结果，写出实验报告。实验报告应当包括：实验题目，实验目的，实验要求，程序实现，实验结果以及分析讨论等内容。

2、实验仪器、设备或软件

硬件最低要求：586微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。每个学生每次上机实验使用一台计算机。

软件：Turbo C或Visual C++6.0

二、实验过程（实验步骤、记录、数据、分析）

实验要求：

以邻接矩阵方式来保存图，实现这种存储方式下创建一个图的算法。然后分别使用深度优先遍历算法和广度优先遍历算法对刚才创建的图进行遍历。

实验内容：

1、以邻接矩阵方式来保存图，实现这种存储方式下创建一个图的算法。

2、创建一个图，然后对这个图进行深度优先遍历和广度优先遍历

深度优先遍历

程序

#include

#include

using namespace 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,UDN}Graphkind;

typedef char VertexType; //定顶点数据类型为字符型

typedef struct ArcCell

{int adj; }

ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_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,AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

int kind;

}ALGraph;

int LocateVex(AMGraph G,VertexType v1)

{

int i;

for(i=0;i

{

if(G.vexs[i]==v1)

return i;

}

return -1;

}

typedef struct Node//结点类型

{

int data;

struct Node *next;

}QueueNode;

bool visited[MAX_VERTEX_NUM]; //定义数组

int CreatDN(AMGraph &G) // 采用邻接矩阵表示法，构造无向网G {

VertexType v1,v2;

int j,i;

cout<<"输入你所要的顶点数以及弧数，以空格隔开:";

cin>>G.vexnum>>G.arcnum;

cout<<"输入顶点向量:";

for(i=0;i

cin>>G.vexs[i];

for(i=0;i

for(j=0;j

G.arcs[i][j].adj=MaxInt;

for(int k=0;k

{

cout<<"请输入一条边依附的定点:";

cin>>v1>>v2;

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j].adj=1;

G.arcs[j][i]=G.arcs[i][j];

}

return OK;

}

void dispAMGraph(AMGraph G) //显示图的邻接矩阵图

{

cout<<"图的邻接矩阵是："<

for(int i=0;i

{

for(int j=0;j

cout<<""<

cout<

}

}

void DFSTraverse(AMGraph G,int v)//对图G作深度优先遍历。{

int w;

cout<

visited[v]=true;

for(w=0;w

if((!visited[w])&&(!G.arcs[v][w].adj==0))

DFSTraverse(G,w);

}

void Traverse(AMGraph G)//输出遍历结果

{

int v;

for(v=0;v

visited[v]=false;

cout<<"深度优先遍历的结果:";

for(v=0;v

{

if(!visited[v])

{

DFSTraverse(G,v);

cout<

}

}