数据结构实验报告.doc

数据结构实验报告(实验五&& 实验六) ?班级: 软件 121 ?学号: 201200834122 ?姓名: 程猛实验五图的基本操作 1. 问题描述: 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 : 以邻接表存储图的结构,建立一个图的类,并且用数组 visited[i] 标记该节点是否被访问。并由临接表建立邻接矩阵。再由输入的 k值确定访问的起始点。报错机制,当输入的数据,不符合要求时,会提醒。 : 图的点数: 5图的总边数: 5边的起点和终点序号: 12233440 : #include "" #include <iostream> #include <iomanip> using namespace std; #include <> const int MaxV=10; //最多顶点数//定义邻接表中的边节点类型 struct edgenode {int adjvex; //邻接点域 edgenode* next; //指向下一个边节点的链域};//定义邻接表的类型 typedef edgenode** adjlist; //邻接矩阵类的定义 class AdjMatrix {private :char g[MaxV]; //顶点信息数组 int size; //当前顶点数 int GA[MaxV][MaxV]; //定义邻接矩阵 GA int numE; //当前边数 public : //构造函数,初始化图的邻接矩阵 AdjMatrix( int n); //判断图空否 bool GraphEmpty() {return size==0;} //取当前顶点数 int NumV() {return size;} //取当前边数 int NumEdges() {return numE;} //取顶点 i的值 char GetValue( const int i); //取弧<v1,v2> 的权 int GetWeight( const int v1, const int v2); //在位置 pos 处插入顶点 v void InsertV( const char &V, int pos); //插入弧<v1 ,v2> 权为 weight void InsertEdge( const int v1, const int v2, int weight); //建立弧的邻接矩阵 void CreateMatrix( int n); //k1 为则无向否则为有向 k2为则有权,否则无权//从初始点 vi出发深度优先搜索由邻接矩阵表示的图 void dfsMatrix( bool *&visited, int i,int n); //从初始点 vi出发广度优先搜索由邻接矩阵表示的图 void bfsMatrix( bool *&visited, int i,int n); //由图的邻接矩阵的到图的邻接表 void graphChange(adjlist &GL, int n); //检查输入的边序号是否越界,否则重新输入 void check( int n,int &i,int &j); //由图的邻接矩阵建立图 void Creategraph( int n); //对非连通图进行深度优先搜索 void dfsMatrix( int n); //对非连通图进行广度优先搜索 void bfsMatrix( int n); };AdjMatrix::AdjMatrix( int n) {int i,j; for (i=0;i<n;i++) for (j=0;j<n;j++) GA[i][j]=0; size=numE=0; }//建立图的邻接矩阵 void AdjMatrix::CreateMatrix( int n) {int i,j,k,e; cout<< "输入图的总边数: "; cin>>e; cout<< "输入"<<e<< "条无向无权边的起点和终点序号: "<<endl; for (k=1;k<=e;k++) {cin>>i>>j; check(n,i,j); GA[i][j]=GA[j][i]=1; }numE=e; cout<< "创建后的邻接矩阵: "<<endl; for (i=0;i<n;i++) {for (j=0;j<n;j++) cout<<setw(4)<<GA[i][j]; cout<<endl; }}void AdjMatrix::dfsMatrix( bool *&visited, int i,int n) {cout<<g[i]<< ':' <<i<<