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

1、海南大学信息科学技术学院实验报告实验课程：数据结构与算法实验成绩指导教帅王平学号：20141614310045姓名：张思惠班级：信息与计算科学<H1,:一161207实验15用邻接矩阵表示带权无向图的类Graphmtx定义（验证，4学时）（第08章图）术语：带权无向图的模板基类Graph,用邻接矩阵表示带权无向图的类Graphmtx类Graphmtx的成员和友元函数序号函数函数原型说明1输入，提取操作符>>玲friendistream&operator>>(istream&,Graphmtx<T,E>&);待实现，题1友元函数2

2、输出，插入操作符<<玲friendostream&operator<<(ostream&,Graphmtx<T,E>&);待实现，题1友元函数3构造函数Graphmtx(intsz=DefaultVertices);待实现，题14析构函数Graphmtx();已实现，题15取第i个顶点名称TgetValue(inti);已实现，题16取边权值EgetWeight(intv1,intv2);已实现，题17取顶点v的个邻接顶点intgetFirstNeighbor(intv);待实现，题2从位置0开始查找到第一个邻接顶点8取v的邻接顶点w

3、的下一邻接顶点intgetNextNeighbor(intv,intw);待实现，题2从w的下一个位置开始查找到个邻接顶点9插入顶点boolinsertVertex(constT&vertex);待实现，题110插入边boolinsertEdge(intv1,intv2,Eweight);待实现，题111删除顶点boolremoveVertex(intv);待实现，题212删除边boolremoveEdge(intv1,intv2);待实现，题213给出顶点的位置intgetVertexPos(constT&vertex);已实现，题1带权无向图的模板基类Graph带权无向图的

4、模板基类(抽象基类)文件名：p349_Graph.h#include<iostream>usingnamespacestd;#ifndefGRAPH_H#defineGRAPH_HconstintmaxWeight=0x7FFFFFFF;代表无穷大，32位二进制数constintDefaultVertices=30;/默认最大顶点数template<classT,classE>顶点类型T,边权值类型E,E一般为某一整数类型classGraph/图的类定义public:Graph(intsz=DefaultVertices)/构造函数Graph()/析构函数boolGra

5、phEmpty()const判图空否。有边否？returnnumEdges=0;boolGraphFull()const判图满否。与存储容量有关。returnnumVertices=maxVertices|numEdges=maxVertices*(maxVertices-1)/2;邻接矩阵计边intNumberOfVertices()returnnumVertices;/返回当前顶点数intNumberOfEdges()returnnumEdges;返回当前边数virtualTgetValue(inti)=0;/取顶点i的值，i不合理返回0,纯虚函数virtualEgetWeight(int

6、v1,intv2)=0;取边(v1,v2)上的权值virtualintgetFirstNeighbor(intv)=0;/取顶点v的第一个邻接顶点virtualintgetNextNeighbor(intv,intw)=0;/取邻接顶点w的下一个邻接顶点virtualboolinsertVertex(constT&vertex)=0;/插入个顶点vertexvirtualboolinsertEdge(intv1,intv2,Ecost)=0;插入边(v1,v2),边权值为costvirtualboolremoveVertex(intv)=0;/删去顶点v和关联边virtualboolr

7、emoveEdge(intv1,intv2)=0;/在图中删去边(v1,v2)virtualintgetVertexPos(Tvertex)=0;给出顶点vertex在图中的位置protected:intmaxVertices;/图中最大顶点数intnumEdges;/当前边数intnumVertices;/当前顶点数;#endif虚函数可加上"=0"改为纯虚函数/*虚函数：若需通过基类指针指向派生类的对象，并访问某个与基类同名的成员，则首先在基类中将这个同名函数说明为虚函数。纯虚函数：是一个在基类中声明的虚函数，它在该基类中没有定义具体的操作内容，要求各派生类根据实际需要

8、定义自己的版本。带有纯虚函数的类是抽象类。抽象类的主要作用：通过它为一个类族建立一个公共的接口，使它们能够更有效地发挥多态特性。抽象类处于类层次的上层，一个抽象类自身无法实例化。*/1.插入、输入输出(P351355(1)下面是用邻接矩阵表示带权无向图的类定义的头文件，其中有5个函数要给出它们的实现。该类是派生类，基类是Graph。/文件名：p351_Graphmtx.h#include<assert.h>#include"p349_Graph.h"template<classT,classE>/顶点类型T,边权值类型E,两者一般为某一整数类型cla

9、ssGraphmtx:publicGraph<T,E>friendistream&operator>><T>(istream&,Graphmtx<T,E>&);(1-4)输入friendostream&operator<<<T>(ostream&,Graphmtx<T,E>&);(1-5)输出public:Graphmtx(intsz=DefaultVertices);/(1-1)构造函数Graphmtx()delete口VerticesList;delete口E

10、dge;/析构函数TgetValue(inti)取顶点i的值，i不合理返回NULL=0return(i>=0&&i<numVertices)?VerticesListi:NULL;EgetWeight(intv1,intv2)取边(v1,v2)上的权值return(v1!=-1&&v2!=-1)?Edgev1v2:0;boolinsertVertex(constT&vertex);/(1-2)插入顶点vertexboolinsertEdge(intv1,intv2,Ecost);/(1-3)插入边(v1,v2),权值为costintgetFi

11、rstNeighbor(intv)return0;/(2-1)取顶点v的第一个邻接顶点intgetNextNeighbor(intv,intw)return0;/(2-2)取v邻接顶点w的下一邻接顶点boolremoveVertex(intv)returntrue;/(2-3)删去顶点v和与它关联的边boolremoveEdge(intv1,intv2)returntrue;/(2-4)在图中删去边(v1,v2)intgetVertexPos(Tvertex)给出顶点vertex在图中的位置，数组下标for(inti=0;i<numVertices;i+)if(VerticesListi

12、=vertex)returni;return-1;private:T*VerticesList;顶点表，一维数组E*Edge;邻接矩阵，二维数组;/(1-1)Graphmtx构造函数p352/(1-2)insertVertex插入顶点p353/(1-3)insertEdge插入边p353(2)主函数#include"p351_Graphmtx.h"voidmain()Graphmtx<char,int>G;cin>>G;cout<<G;(I)完成5个函数的实现，并给出类Graphmtx的定义和实现。#include<assert.h

13、>#include"p349_Graph.h"template<classT,classE>/顶点类型T,边权值类型E,classGraphmtx:publicGraph<T,E>friendistream&operator>><T>(istream&,Graphmtx<Tfriendostream&operator<<<T>(ostream&,Graphmtx<T两者一般为某一整数类型,E>&);/(1-4)输入,E>&);

14、/(1-5)输出public:Graphmtx(intsz=DefaultVertices);/(1-1)构造函数Graphmtx()deleteVerticesList;deleteEdge;/析构函数TgetValue(inti)取顶点i的值，i不合理返回NULL=0return(i>=0&&i<numVertices)?VerticesListi:NULL;EgetWeight(intv1,intv2)/取边(v1,v2)上的权值return(v1!=-1&&v2!=-1)?Edgev1v2:0;boolinsertVertex(constT&

15、amp;vertex);/(1-2)boolinsertEdge(intv1,intv2,Ecost);/(1-3)intgetFirstNeighbor(intv)return0;/(2-1)插入顶点vertexintgetNextNeighbor(intv,intw)return0;/(2-2)boolremoveVertex(intv)returntrue;/(2-3)boolremoveEdge(intv1,intv2)returntrue;/(2-4)插入边(v1,v2),权值为cost取顶点v的第一个邻接顶点取v邻接顶点w的下一邻接顶点删去顶点v和与它关联的边intgetVerte

16、xPos(Tvertex)/给出顶点vertexfor(inti=0;i<numVertices;i+)if(VerticesListi=vertex)returni;return-1;private:T*VerticesList;/顶点表，一维数组E*Edge;/邻接矩阵，二维数组;在图中删去边(v1,v2)在图中的位置，数组下标template<classT,classE>Graphmtx<T,E>:Graphmtx(intsz)(/(1-1)Graphmtx构造函数p352maxVertices=sz;numVertices=0;numEdges=0;int

17、i,j;VerticesList=newTmaxVertices;Edge=(E*)newE*maxVertices;for(i=0;i<maxVertices;i+)Edgei=newEmaxVertices;for(i=0;i<maxVertices;i+)for(j=0;j<maxVertices;j+)Edgeij=(i=j)?0:maxWeight;template<classT,classE>boolGraphmtx<T,E>:insertVertex(constT&vertex)(/(1-2)insertVertex插入顶点p35

18、3if(numVertices=maxVertices)returnfalse;VerticesListnumVertices+=vertex;returntrue;template<classT,classE>boolGraphmtx<T,E>:insertEdge(intv1,intv2,Ecost)/(1-3)insertEdge插入边p353if(v1>-1&&v2<numVertices&&v2>-1&&v2<numVertices&&Edgev1v2=maxWeight)

19、Edgev1v2=Edgev2v1=cost;numEdges+;returntrue;elsereturnfalse;template<classT,classE>istream&operator>>(istream&in,Graphmtx<T,E>&G)/(1-4)输入图p354inti,j,k,n,m;Tel,e2;Eweight;cout<<"Inputdata:"<<endl;cout<<"Pleaseinputnumberofpoints:"in&

20、gt;>n;cout<<"Pleaseinputnumberoflines:"in>>m;for(i=0;i<n;i+)(cout<<"Pleaseinputthenameofthepointofnumber"<<i+1<<""in>>el;G.insertVertex(el);i=0;cout<<"PleaseinputtheinformationoflinesExample:ponit1point2length:"&

21、lt;<endl;while(i<m)(in>>el>>e2>>weight;j=G.getVertexPos(el);k=G.getVertexPos(e2);if(j=-1|k=-1)cout<<"Theinformationofthislinewaswrong,pleaseinputagain!"<<endl;elseG.insertEdge(j,k,weight);i+;returnin;template<classT,classE>ostream&operator<&

22、lt;(ostream&out,Graphmtx<T,E>&G)/(1-5)输出图p355inti,j,n,m;Te1,e2;Ew;n=G.NumberOfVertices();m=G.NumberOfEdges();out<<"Returnresult:"<<endl;out<<"Numberofpoints&lines:"out<<n<<":"<<m<<endl;out<<"Output&q

23、uot;<<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<<","<<w<<")"<<endl;returnout;(n)对下面给出的带权无向图的运行结果2.

24、删除、邻接顶点(P351355(1)在上题的类中需要给出另外4个成员函数的实现。/用邻接矩阵表示带权无向图的类定义/文件名：p351_Graphmtx.h#include<assert.h>#include"p349_Graph.h"template<classT,classE>/顶点类型T,边权值类型E,两者一般为某一整数类型classGraphmtx:publicGraph<T,E>friendistream&operator>><T>(istream&,Graphmtx<T,E>&

25、amp;);/(1-4)输入friendostream&operator<<<T>(ostream&,Graphmtx<T,E>&);/(1-5)输出public:Graphmtx(intsz=DefaultVertices);/(1-1)构造函数Graphmtx()delete口VerticesList;delete口Edge;/析构函数TgetValue(inti)取顶点i的值，i不合理返回NULL=0return(i>=0&&i<numVertices)?VerticesListi:NULL;Eget

26、Weight(intv1,intv2)取边(v1,v2)上的权值return(v1!=-1&&v2!=-1)?Edgev1v2:0;boolinsertVertex(constT&vertex);/(1-2)插入顶点vertexboolinsertEdge(intv1,intv2,Ecost);/(1-3)插入边(v1,v2),权值为costintgetFirstNeighbor(intv);/(2-1)取顶点v的第一个邻接顶点intgetNextNeighbor(intv,intw);/(2-2)取v邻接顶点w的下一邻接顶点boolremoveVertex(intv)

27、;/(2-3)删去顶点v和与它关联的边boolremoveEdge(intv1,intv2);/(2-4)在图中删去边(v1,v2)intgetVertexPos(Tvertex)给出顶点vertex在图中的位置，数组下标for(inti=0;i<numVertices;i+)if(VerticesListi=vertex)returni;return-1;)private:T*VerticesList;顶点表，一维数组E*Edge;邻接矩阵，二维数组)；/上题的函数实现复制到此处；/(2-1)getFirstNeighbor获取顶点第一个邻接顶点p352/(2-2)getNextNei

28、ghbor获取顶点的下一个邻接顶点p353/(2-3)removeVertex删除顶点p353/(2-4)removeEdge删除边p354(2)主函数#include"p351_Graphmtx.h"voidmain()Graphmtx<char,int>G;cin>>G;cout<<G;charcurrent,first,next;intv,w;for(intv=0,w;(current=G.getValue(v)!=NULL;v+)cout<<"当前顶点是"current;w=G.getFirstNe

29、ighbor(v);first=G.getValue(w);if(first!=NULL)cout<<",第一个邻接顶点是"<<first;next=G.getValue(G.getNextNeighbor(v,w);if(next!=NULL)cout<<",下一个邻接顶点是"<<next;elsecout<<",没有下一个邻接顶点")elsecout<<",没有邻接顶点"cout<<endl;)v=G.getVertexPos(

30、'g');G.removeVertex(v);cout<<"删除顶点g后："<<endl;cout<<G;v=G.getVertexPos('a');w=G.getVertexPos('b');G.removeEdge(v,w);cout<<"删除边(a,b)后："<<endl;cout<<G;(I)完成4个成员函数的实现，给出类Graphmtx的定义和实现。#include<assert.h>#include"p

31、351_Graphmtx.h"template<classT,classE>/顶点类型T,边权值类型E,两者一般为某一整数类型classGraphmtx:publicGraph<T,E>friendistream&operator>><T>(istream&,Graphmtx<T,E>&);/(1-4)输入friendostream&operator<<<T>(ostream&,Graphmtx<T,E>&);/(1-5)输出public:G

32、raphmtx(intsz=DefaultVertices);/(1-1)构造函数Graphmtx()delete口VerticesList;deleteEdge;析构函数TgetValue(inti)取顶点i的值，i不合理返回NULL=0return(i>=0&&i<numVertices)?VerticesListi:NULL;EgetWeight(intv1,intv2)/取边(v1,v2)上的权值return(v1!=-1&&v2!=-1)?Edgev1v2:0;boolinsertVertex(constT&vertex);/(1-

33、2)插入顶点vertexboolinsertEdge(intv1,intv2,Ecost);/(1-3)插入边(v1,v2),权值为costintgetFirstNeighbor(intv);/(2-1)取顶点v的第一个邻接顶点intgetNextNeighbor(intv,intw);/(2-2)取v邻接顶点w的下一邻接顶点boolremoveVertex(intv);/(2-3)删去顶点v和与它关联的边boolremoveEdge(intv1,intv2);/(2-4)在图中删去边(v1,v2)intgetVertexPos(Tvertex)/给出顶点vertex在图中的位置，数组下标fo

34、r(inti=0;i<numVertices;i+)if(VerticesListi=vertex)returni;return-1;private:T*VerticesList;/顶点表，一维数组E*Edge;/邻接矩阵，二维数组;template<classT,classE>Graphmtx<T,E>:Graphmtx(intsz)/(1-1)Graphmtx构造函数p352maxVertices=sz;numVertices=0;numEdges=0;inti,j;VerticesList=newTmaxVertices;Edge=(E*)newE*maxV

35、ertices;for(i=0;i<maxVertices;i+)Edgei=newEmaxVertices;for(i=0;i<maxVertices;i+)for(j=0;j<maxVertices;j+)Edgeij=(i=j)?0:maxWeight;template<classT,classE>boolGraphmtx<T,E>:insertVertex(constT&vertex)/(1-2)insertVertex插入顶点p353if(numVertices=maxVertices)returnfalse;VerticesList

36、numVertices+=vertex;returntrue;template<classT,classE>boolGraphmtx<T,E>:insertEdge(intv1,intv2,Ecost)/(1-3)insertEdge插入边p353if(v1>-1&&v2<numVertices&&v2>-1&&v2<numVertices&&Edgev1v2=maxWeight)Edgev1v2=Edgev2v1=cost;numEdges+;returntrue;elseretu

37、rnfalse;template<classT,classE>istream&operator>>(istream&in,Graphmtx<T,E>&G)/(1-4)输入图p354inti,j,k,n,m;Tel,e2;Eweight;cout<<"Inputdata:"<<endl;cout<<"Pleaseinputnumberofpoints:"in>>n;cout<<"Pleaseinputnumberoflines:

38、"in>>m;for(i=0;i<n;i+)cout<<"Pleaseinputthenameofthepointofnumber"<<i+1<<""in>>el;G.insertVertex(el);i=0;cout<<"PleaseinputtheinformationoflinesExample:ponitlpoint2length:"<<endl;while(i<m)in>>el>>e2>&g

39、t;weight;j=G.getVertexPos(el);k=G.getVertexPos(e2);if(j=-1|k=-1)cout<<"Theinformationofthislinewaswrong,pleaseinputagain!"<<endl;elseG.insertEdge(j,k,weight);i+;returnin;template<classT,classE>ostream&operator<<(ostream&out,Graphmtx<T,E>&G)/(1-5)输出

40、图p355inti,j,n,m;Te1,e2;Ew;n=G.NumberOfVertices();m=G.NumberOfEdges();out<<"Returnresult:"<<endl;out<<"Numberofpoints&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<<"(&