山东大学数据结构实验报告八

《山东大学数据结构实验报告八》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东大学软件工程学院数据结构课程实验报告 学号：姓名：班级：软件工程2014级2班实验题目：图的操作实验学时：实验日期：2015.12.9实验目的：掌握图的基本概念，描述方法；遍历方法。硬件环境： 实验室软件环境：VistualStudio2013实验步骤与内容：实验内容：1、创建图类。二叉树的存储结构使用邻接矩阵或链表。2、提供操作:遍历、BFS、DFS3、对建立好的图，执行上述各操作。4、输出生成树。5、输出最小生成树。代码体：Adjacencywdigraph.h#ifndefADJACENCYWDIGRAPH_H#defineADJACENCYWDIGRAPH_HclassA

2、djacencyWDigraph{friendclassAdjacencyWGraph;public:AdjacencyWDigraph(intVertices=10,intnoEnge=0);~AdjacencyWDigraph();boolExist(inti,intj)const;intEdges()const{returne;}intVertices()const{returnn;}AdjacencyWDigraph&Add(inti,intj,constint&w=1);AdjacencyWDigraph&Delete(inti,intj);intOutDegree(int

3、i)const;intInDegree(inti)const;voidInitializePos(){pos=newint[n+1];}voidDeactivatePos(){delete[]pos;}intBegin(inti);intNextVertex(inti);voidBFS(intv,intreach[],intlabel=1);voidDFS(intv,intreach[],intlabel=1);boolConnected(int&x);int**SpanningTree();int**SpanningMinTree();voidOutPut();private:in

4、tMinNum();intMin(intv,intreach[]);boolConnecting(inti);voiddfs(intv,intreach[],intlabel);intNoEdge,n,e;int**a;int*pos;};#endifAdjacencywdigraph.cpp#include#includeusingnamespacestd;#include"adjacencywdigraph.h"AdjacencyWDigraph::AdjacencyWDigraph(intVertices,intnoEdge){n=Vertic

5、es;e=0;NoEdge=noEdge;a=newint*[n+1];for(inti=1;i<=n;i++)a[i]=newint[n+1];for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)a[i][j]=NoEdge;}AdjacencyWDigraph::~AdjacencyWDigraph(){for(inti=1;i<=n;i++)delete[]a[i];delete[]a;}boolAdjacencyWDigraph::Exist(inti,intj)const{if(i<1

6、

7、j<1

8、

9、i>n

10、

11、j>n

12、

13、a[i][j]==NoEdg

14、e)returnfalse;returntrue;}AdjacencyWDigraph&AdjacencyWDigraph::Add(inti,intj,constint&w){if(i<1

15、

16、j<1

17、

18、i>n

19、

20、j>n)cout<<"错误!点"<

21、if(i<1

22、

23、j<1

24、

25、i>n

26、

27、j>n

28、

29、a[i][j]==NoEdge)cout<<"错误!该边不存在,无法删除"<

30、

31、i>n){cout<<"错误,该点不存在!"<