信科实验15_用邻接矩阵表示带权无向图类Graphmtx定义(4学时,8章)

1、数据结构与算法实验20141614310045信息与计算科学0712王平张思惠16实验15用邻接矩阵表示带权无向图的类Graphmtx定义（验证，4学时）（第08章 图）术语：带权无向图的模板基类Graph，用邻接矩阵表示带权无向图的类Graphmtx类Graphmtx的成员和友元函数序号函数函数原型说明1输入，提取操作符>>重载friend istream& operator>>(istream&,Graphmtx<T,E>&);待实现，题1友元函数2输出，插入操作符<<重载friend ostream& ope

2、rator<<(ostream&,Graphmtx<T,E>&);待实现，题1友元函数3构造函数Graphmtx(int sz=DefaultVertices);待实现，题14析构函数Graphmtx();已实现，题15取第i个顶点名称T getValue(int i);已实现，题16取边权值E getWeight(int v1,int v2);已实现，题17取顶点v的第一个邻接顶点int getFirstNeighbor(int v);待实现，题2从位置0开始查找到第一个邻接顶点8取v的邻接顶点w的下一邻接顶点int getNextNeighbor(i

3、nt v,int w);待实现，题2从w的下一个位置开始查找到第一个邻接顶点9插入顶点bool insertVertex(const T& vertex);待实现，题110插入边bool insertEdge(int v1,int v2,E weight);待实现，题111删除顶点bool removeVertex(int v);待实现，题212删除边bool removeEdge(int v1,int v2);待实现，题213给出顶点的位置int getVertexPos(const T& vertex);已实现，题1带权无向图的模板基类Graph/带权无向图的模板基类（抽象

4、基类）/文件名：p349_Graph.h#include<iostream>using namespace std;#ifndef GRAPH_H#define GRAPH_Hconst int maxWeight=0x7FFFFFFF;/代表无穷大，32位二进制数const int DefaultVertices=30; /默认最大顶点数template<class T,class E>/顶点类型T，边权值类型E，E一般为某一整数类型class Graph/图的类定义public:Graph(int sz=DefaultVertices) /构造函数Graph()/析

5、构函数bool GraphEmpty()const/判图空否。有边否？ return numEdges=0; bool GraphFull()const/判图满否。与存储容量有关。 return numVertices=maxVertices |numEdges=maxVertices*(maxVertices-1)/2; /邻接矩阵计边int NumberOfVertices() return numVertices; /返回当前顶点数int NumberOfEdges() return numEdges; /返回当前边数virtual T getValue(int i)=0; /取顶点i的

6、值，i不合理返回0，纯虚函数virtual E getWeight(int v1,int v2)=0;/取边(v1,v2)上的权值virtual int getFirstNeighbor(int v)=0; /取顶点v的第一个邻接顶点virtual int getNextNeighbor(int v,int w)=0; /取邻接顶点w的下一个邻接顶点virtual bool insertVertex(const T &vertex)=0; /插入一个顶点vertexvirtual bool insertEdge(int v1,int v2,E cost)=0; /插入边(v1,v2)，

7、边权值为costvirtual bool removeVertex(int v)=0; /删去顶点v和关联边virtual bool removeEdge(int v1,int v2)=0; /在图中删去边(v1,v2)virtual int getVertexPos(T vertex)=0; /给出顶点vertex在图中的位置protected:int maxVertices; /图中最大顶点数int numEdges; /当前边数int numVertices; /当前顶点数;#endif/虚函数可加上"=0"改为纯虚函数/*虚函数：若需通过基类指针指向派生类的对象，并

8、访问某个与基类同名的成员，则首先在基类中将这个同名函数说明为虚函数。纯虚函数：是一个在基类中声明的虚函数，它在该基类中没有定义具体的操作内容，要求各派生类根据实际需要定义自己的版本。带有纯虚函数的类是抽象类。抽象类的主要作用：通过它为一个类族建立一个公共的接口，使它们能够更有效地发挥多态特性。抽象类处于类层次的上层，一个抽象类自身无法实例化。*/1. 插入、输入输出（P351355）(1) 下面是用邻接矩阵表示带权无向图的类定义的头文件，其中有5个函数要给出它们的实现。该类是派生类，基类是Graph。/文件名：p351_Graphmtx.h#include<assert.h>#in

9、clude"p349_Graph.h"template<class T,class E>/顶点类型T，边权值类型E，两者一般为某一整数类型class Graphmtx:public Graph<T,E>friend istream& operator>><T>(istream&,Graphmtx<T,E>&);/(1-4)输入friend ostream& operator<<<T>(ostream&,Graphmtx<T,E>&)

10、;/(1-5)输出public:Graphmtx(int sz=DefaultVertices); /(1-1)构造函数Graphmtx() deleteVerticesList; deleteEdge; /析构函数T getValue(int i)/取顶点i的值，i不合理返回NULL=0 return (i>=0 && i<numVertices)?VerticesListi:NULL; E getWeight(int v1,int v2) /取边(v1,v2)上的权值 return (v1!=-1 && v2!=-1)?Edgev1v2:0; b

11、ool insertVertex(const T &vertex); /(1-2)插入顶点vertexbool insertEdge(int v1,int v2,E cost); /(1-3)插入边(v1,v2)，权值为costint getFirstNeighbor(int v) return 0; /(2-1)取顶点v的第一个邻接顶点int getNextNeighbor(int v,int w) return 0; /(2-2)取v邻接顶点w的下一邻接顶点bool removeVertex(int v) return true; /(2-3)删去顶点v和与它关联的边bool re

12、moveEdge(int v1,int v2) return true; /(2-4)在图中删去边(v1,v2)int getVertexPos(T vertex) /给出顶点vertex在图中的位置，数组下标for(int i=0;i<numVertices;i+)if(VerticesListi=vertex) return i;return -1;private:T *VerticesList;/顶点表，一维数组E *Edge;/邻接矩阵，二维数组;/(1-1) Graphmtx构造函数p352/(1-2) insertVertex插入顶点p353/(1-3) insertEdge

13、插入边p353/(1-4) 输入图p354/(1-5) 输出图p355(2) 主函数#include"p351_Graphmtx.h"void main()Graphmtx<char, int> G;cin>>G;cout<<G;() 完成5个函数的实现，并给出类Graphmtx的定义和实现。#include<assert.h>#include"p349_Graph.h"template<class T,class E>/顶点类型T，边权值类型E，两者一般为某一整数类型class Graphmt

14、x:public Graph<T,E>friend istream& operator>><T>(istream&,Graphmtx<T,E>&);/(1-4)输入friend ostream& operator<<<T>(ostream&,Graphmtx<T,E>&);/(1-5)输出public:Graphmtx(int sz=DefaultVertices); /(1-1)构造函数Graphmtx() deleteVerticesList; deleteE

15、dge; /析构函数T getValue(int i)/取顶点i的值，i不合理返回NULL=0 return (i>=0 && i<numVertices)?VerticesListi:NULL; E getWeight(int v1,int v2) /取边(v1,v2)上的权值 return (v1!=-1 && v2!=-1)?Edgev1v2:0; bool insertVertex(const T &vertex); /(1-2)插入顶点vertexbool insertEdge(int v1,int v2,E cost); /(1-

16、3)插入边(v1,v2)，权值为costint getFirstNeighbor(int v) return 0; /(2-1)取顶点v的第一个邻接顶点int getNextNeighbor(int v,int w) return 0; /(2-2)取v邻接顶点w的下一邻接顶点bool removeVertex(int v) return true; /(2-3)删去顶点v和与它关联的边bool removeEdge(int v1,int v2) return true; /(2-4)在图中删去边(v1,v2)int getVertexPos(T vertex) /给出顶点vertex在图中的

17、位置，数组下标for(int i=0;i<numVertices;i+)if(VerticesListi=vertex) return i;return -1;private:T *VerticesList;/顶点表，一维数组E *Edge;/邻接矩阵，二维数组;template<class T,class E>Graphmtx<T,E>:Graphmtx(int sz) /(1-1) Graphmtx构造函数p352maxVertices = sz; numVertices = 0; numEdges = 0;int i,j;VerticesList = new

18、 TmaxVertices;Edge = (E *) new E * maxVertices;for(i=0; i<maxVertices; i+)Edgei=new EmaxVertices;for(i=0; i<maxVertices; i+)for(j=0; j<maxVertices; j+)Edgeij=(i=j)? 0:maxWeight;template<class T,class E>bool Graphmtx<T,E>:insertVertex(const T &vertex) /(1-2) insertVertex插入顶点p

19、353if (numVertices = maxVertices) return false;VerticesListnumVertices+ = vertex;return true;template<class T,class E>bool Graphmtx<T,E>:insertEdge(int v1,int v2,E cost) /(1-3) insertEdge插入边p353if(v1>-1 && v2<numVertices && v2>-1 && v2<numVertices &

20、;& Edgev1v2 = maxWeight) Edgev1v2 = Edgev2v1 = cost;numEdges+;return true;else return false;template<class T,class E>istream& operator>> (istream& in ,Graphmtx<T,E>& G) /(1-4) 输入图p354int i,j,k,n,m; T el,e2; E weight;cout<<"Input data:"<<endl;co

21、ut<<"Please input number of points: "in>>n;cout<<"Please input number of lines: "in>>m;for(i=0;i<n;i+) cout<<"Please input the name of the point of number "<<i+1<<" "in>>el;G.insertVertex(el);i=0;cout<<&

22、quot;Please input the information of lines Example: ponit1 point2 length:"<<endl;while(i<m)in>>el>>e2>>weight;j=G.getVertexPos(el);k=G.getVertexPos(e2);if(j=-1|k=-1)cout<<"The information of this line was wrong, please input again!"<<endl;elseG.i

23、nsertEdge(j,k,weight);i+;return in;template<class T,class E>ostream& operator<< (ostream& out,Graphmtx<T,E>& G)/(1-5) 输出图p355int i,j,n,m; T e1,e2; E w;n=G.NumberOfVertices(); m=G.NumberOfEdges();out<<"Return result:"<<endl;out<<"Number o

24、f points & lines: "out<<n<<":"<<m<<endl;out<<"Output "<<endl;for(i=0; i<n; i+)for(j=0; j<n; j+)w=G.getWeight(i, j);if(w>0 && w<maxWeight)e1=G.getValue(i); e2=G.getValue(j);out<<"("<<e1<<&

25、quot;,"<<e2<<","<<w<<")"<<endl;return out;() 对下面给出的带权无向图的运行结果。4 3 0 1 2 5 6 10 28 25 16 14 24 22 18 12 2. 删除、邻接顶点（P351355）(1) 在上题的类中需要给出另外4个成员函数的实现。/用邻接矩阵表示带权无向图的类定义/文件名：p351_Graphmtx.h#include<assert.h>#include"p349_Graph.h"temp

26、late<class T,class E>/顶点类型T，边权值类型E，两者一般为某一整数类型class Graphmtx:public Graph<T,E>friend istream& operator>><T>(istream&,Graphmtx<T,E>&);/(1-4)输入friend ostream& operator<<<T>(ostream&,Graphmtx<T,E>&);/(1-5)输出public:Graphmtx(int sz=D

27、efaultVertices); /(1-1)构造函数Graphmtx() deleteVerticesList; deleteEdge; /析构函数T getValue(int i)/取顶点i的值，i不合理返回NULL=0 return (i>=0 && i<numVertices)?VerticesListi:NULL; E getWeight(int v1,int v2) /取边(v1,v2)上的权值 return (v1!=-1 && v2!=-1)?Edgev1v2:0; bool insertVertex(const T &ver

28、tex); /(1-2)插入顶点vertexbool insertEdge(int v1,int v2,E cost); /(1-3)插入边(v1,v2)，权值为costint getFirstNeighbor(int v); /(2-1)取顶点v的第一个邻接顶点int getNextNeighbor(int v,int w); /(2-2)取v邻接顶点w的下一邻接顶点bool removeVertex(int v); /(2-3)删去顶点v和与它关联的边bool removeEdge(int v1,int v2); /(2-4)在图中删去边(v1,v2)int getVertexPos(T

29、vertex) /给出顶点vertex在图中的位置，数组下标for(int i=0;i<numVertices;i+)if(VerticesListi=vertex) return i;return -1;private:T *VerticesList;/顶点表，一维数组E *Edge;/邻接矩阵，二维数组;/上题的函数实现复制到此处;/(2-1) getFirstNeighbor获取顶点第一个邻接顶点p352/(2-2) getNextNeighbor获取顶点的下一个邻接顶点p353/(2-3) removeVertex删除顶点p353/(2-4) removeEdge删除边p354(

30、2) 主函数#include"p351_Graphmtx.h"void main()Graphmtx<char,int> G;cin>>G;cout<<G;char current,first,next;int v,w;for(int v=0,w;(current=G.getValue(v)!=NULL;v+)cout<<"当前顶点是"<<current;w=G.getFirstNeighbor(v);first=G.getValue(w);if(first!=NULL)cout<<

31、"，第一个邻接顶点是"<<first;next=G.getValue(G.getNextNeighbor(v,w);if(next!=NULL) cout<<"，下一个邻接顶点是"<<next;else cout<<"，没有下一个邻接顶点"else cout<<"，没有邻接顶点"cout<<endl;v=G.getVertexPos('g');G.removeVertex(v);cout<<"删除顶点g后：

32、"<<endl;cout<<G;v=G.getVertexPos('a'); w=G.getVertexPos('b');G.removeEdge(v,w);cout<<"删除边(a,b)后："<<endl;cout<<G;() 完成4个成员函数的实现，给出类Graphmtx的定义和实现。#include<assert.h>#include" p351_Graphmtx.h "template<class T,class E>/顶

33、点类型T，边权值类型E，两者一般为某一整数类型class Graphmtx:public Graph<T,E>friend istream& operator>><T>(istream&,Graphmtx<T,E>&);/(1-4)输入friend ostream& operator<<<T>(ostream&,Graphmtx<T,E>&);/(1-5)输出public:Graphmtx(int sz=DefaultVertices); /(1-1)构造函数Gr

34、aphmtx() deleteVerticesList; deleteEdge; /析构函数T getValue(int i)/取顶点i的值，i不合理返回NULL=0 return (i>=0 && i<numVertices)?VerticesListi:NULL; E getWeight(int v1,int v2) /取边(v1,v2)上的权值 return (v1!=-1 && v2!=-1)?Edgev1v2:0; bool insertVertex(const T &vertex); /(1-2)插入顶点vertexbool in

35、sertEdge(int v1,int v2,E cost); /(1-3)插入边(v1,v2)，权值为costint getFirstNeighbor(int v); /(2-1)取顶点v的第一个邻接顶点int getNextNeighbor(int v,int w); /(2-2)取v邻接顶点w的下一邻接顶点bool removeVertex(int v); /(2-3)删去顶点v和与它关联的边bool removeEdge(int v1,int v2); /(2-4)在图中删去边(v1,v2)int getVertexPos(T vertex) /给出顶点vertex在图中的位置，数组下

36、标for(int i=0;i<numVertices;i+)if(VerticesListi=vertex) return i;return -1;private:T *VerticesList;/顶点表，一维数组E *Edge;/邻接矩阵，二维数组;template<class T,class E>Graphmtx<T,E>:Graphmtx(int sz) /(1-1) Graphmtx构造函数p352maxVertices = sz; numVertices = 0; numEdges = 0;int i,j;VerticesList = new TmaxV

37、ertices;Edge = (E *) new E * maxVertices;for(i=0; i<maxVertices; i+)Edgei=new EmaxVertices;for(i=0; i<maxVertices; i+)for(j=0; j<maxVertices; j+)Edgeij=(i=j)? 0:maxWeight;template<class T,class E>bool Graphmtx<T,E>:insertVertex(const T &vertex) /(1-2) insertVertex插入顶点p353if

38、(numVertices = maxVertices) return false;VerticesListnumVertices+ = vertex;return true;template<class T,class E>bool Graphmtx<T,E>:insertEdge(int v1,int v2,E cost) /(1-3) insertEdge插入边p353if(v1>-1 && v2<numVertices && v2>-1 && v2<numVertices &&

39、 Edgev1v2 = maxWeight) Edgev1v2 = Edgev2v1 = cost;numEdges+;return true;else return false;template<class T,class E>istream& operator>> (istream& in ,Graphmtx<T,E>& G) /(1-4) 输入图p354int i,j,k,n,m; T el,e2; E weight;cout<<"Input data:"<<endl;cout<

40、<"Please input number of points: "in>>n;cout<<"Please input number of lines: "in>>m;for(i=0;i<n;i+) cout<<"Please input the name of the point of number "<<i+1<<" "in>>el;G.insertVertex(el);i=0;cout<<"P

41、lease input the information of lines Example: ponit1 point2 length:"<<endl;while(i<m)in>>el>>e2>>weight;j=G.getVertexPos(el);k=G.getVertexPos(e2);if(j=-1|k=-1)cout<<"The information of this line was wrong, please input again!"<<endl;elseG.insertE

42、dge(j,k,weight);i+;return in;template<class T,class E>ostream& operator<< (ostream& out,Graphmtx<T,E>& G)/(1-5) 输出图p355int i,j,n,m; T e1,e2; E w;n=G.NumberOfVertices(); m=G.NumberOfEdges();out<<"Return result:"<<endl;out<<"Number of poin

43、ts & lines: "out<<n<<":"<<m<<endl;out<<"Output "<<endl;for(i=0; i<n; i+)for(j=0; j<n; j+)w=G.getWeight(i, j);if(w>0 && w<maxWeight)e1=G.getValue(i); e2=G.getValue(j);out<<"("<<e1<<","<<e2<<