大数据结构实验报告材料-图实验.doc
word图实验一， 邻接矩阵的实现1. 实验目的（1） 掌握图的逻辑结构（2） 掌握图的邻接矩阵的存储结构（3） 验证图的邻接矩阵存储与其遍历操作的实现2. 实验内容（1） 建立无向图的邻接矩阵存储（2） 进展深度优先遍历（3） 进展广度优先遍历3设计与编码MGraph.h#ifndef MGraph_H#define MGraph_Hconst int MaxSize = 10;template<class DataType>class MGraphpublic:MGraph(DataType a, int n, int e);MGraph()void DFSTraverse(int v);void BFSTraverse(int v);private:DataType vertexMaxSize;int arcMaxSizeMaxSize;int vertexNum, arum;#endif#include<iostream>using namespace std;#include "MGraph.h"extern int visitedMaxSize;template<class DataType>MGraph<DataType>:MGraph(DataType a, int n, int e)int i, j, k;vertexNum = n, arum = e;for(i = 0; i < vertexNum; i+)vertexi = ai;for(i = 0;i < vertexNum; i+)for(j = 0; j < vertexNum; j+)arcij = 0;for(k = 0; k < arum; k+)cout << "Please enter two vertexs number of edge: "cin >> i >> j;arcij = 1;arcji = 1;template<class DataType>void MGraph<DataType>:DFSTraverse(int v)cout << vertexv;visitedv = 1;for(int j = 0; j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)DFSTraverse(j);template<class DataType>void MGraph<DataType>:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;cout << vertexv;visitedv = 1;Q+rear = v;while(front != rear)v = Q+front;for(int j = 0;j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)cout << vertexj;visitedj = 1;Q+rear = j;#include<iostream>using namespace std;#include "MGraph.h"extern int visitedMaxSize;template<class DataType>MGraph<DataType>:MGraph(DataType a, int n, int e)int i, j, k;vertexNum = n, arum = e;for(i = 0; i < vertexNum; i+)vertexi = ai;for(i = 0;i < vertexNum; i+)for(j = 0; j < vertexNum; j+)arcij = 0;for(k = 0; k < arum; k+)cout << "Please enter two vertexs number of edge: "cin >> i >> j;arcij = 1;arcji = 1;template<class DataType>void MGraph<DataType>:DFSTraverse(int v)cout << vertexv;visitedv = 1;for(int j = 0; j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)DFSTraverse(j);template<class DataType>void MGraph<DataType>:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;cout << vertexv;visitedv = 1;Q+rear = v;while(front != rear)v = Q+front;for(int j = 0;j < vertexNum; j+)if(arcvj = 1 && visitedj = 0)cout << vertexj;visitedj = 1;Q+rear = j;4. 运行与测试5. 总结与心得通过该实验的代码编写与调试，熟悉了邻接矩阵在图结构中的应用，在调试过程中遇到很多的问题，在解决问题过程中也使我的写代码能力得到提升二， 邻接表的实现1. 实验目的（1） 掌握图的逻辑结构（2） 掌握图的邻接表存储结构（3） 验证图的邻接表存储与其遍历操作的实现2. 实验内容（1） 建立一个有向图的邻接表存储结构（2） 对建立的有向图进展深度优先遍历（3） 对建立的有向图进展广度优先遍历3. 设计与编码#ifndef ALGraph_H#define ALGraph_Hconst int MaxSize = 10;struct Arodeint adjvex;Arode * next;template<class DataType>struct VertexNodeDataType vertex;Arode * firstedge;template<class DataType>class ALGraphpublic:ALGraph(DataType a, int n, int e);ALGraph();void DFSTraverse(int v);void BFSTraverse(int v);private:VertexNode<DataType> adjlistMaxSize;int vertexNum, arum;#endif#include<iostream>using namespace std;#include"ALGraph.h"extern int visitedMaxSize;template<class DataType>ALGraph<DataType>:ALGraph(DataType a, int n, int e)Arode * s;int i, j, k;vertexNum = n; arum = e;for(i = 0; i < vertexNum; i+)adjlisti.vertex = ai;adjlisti.firstedge = NULL;for(k = 0; k < arum; k+)cout << "Please enter the edge of the serial number of two vertices: "cin >> i >> j;s = new Arode; s->adjvex = j;s->next = adjlisti.firstedge;adjlisti.firstedge = s;template<class DataType>ALGraph<DataType>:ALGraph()Arode * p = NULL;for(int i = 0; i < vertexNum; i+)p = adjlisti.firstedge;while(p != NULL)adjlisti.firstedge = p->next;delete p;p = adjlisti.firstedge;template<class DataType>void ALGraph<DataType>:DFSTraverse(int v)Arode * p = NULL; int j;cout << adjlistv.vertex;visitedv = 1;p = adjlistv.firstedge;while(p != NULL)j = p->adjvex;if(visitedj = 0) DFSTraverse(j);p = p->next;template<class DataType>void ALGraph<DataType>:BFSTraverse(int v)int QMaxSize;int front = -1, rear = -1;Arode * p = NULL;cout << adjlistv.vertex; visitedv = 1; Q+rear = v;while(front != rear)v = Q+front;p = adjlistv.firstedge;while(p != NULL)int j = p->adjvex;if(visitedj = 0)cout << adjlistj.vertex; visitedj = 1; Q+rear = j;p = p->next;#include<iostream>using namespace std;#include"ALGraph.cpp"int visitedMaxSize = 0;int main()char ch = 'A','B','C','D','E'int i;ALGraph<char> ALG(ch, 5, 6);for(i = 0; i < MaxSize; i+)visitedi = 0;cout << "Depth-first traverse sequence is: "ALG.DFSTraverse(0);cout << endl;for(i = 0; i < MaxSize; i+)visitedi = 0;cout << "Breadth-first traverse sequence is: "ALG.BFSTraverse(0);cout << endl;return 0;4. 运行与调试5. 总结与心得通过该实验，掌握了图的邻接表存储结构14 / 14
