NameType Get Value(int 1) f return i>=0 & i< Num Vertices NodeTableli. data: NULL; J int NumberOf Vertices() f return Num Vertices; int NumberOfEdges(f return Num Edges; 3 void Insert Vertex( Type vertex ) void Remove Vertex( int v ); void InsertEdge( int vl, int v2, float weight ) void RemoveEdge( int vI int v2 ) float Get Weight( int vI, int v2 ) int GetFirstNeighbor( int v)
NameType GetValue ( int i ) { return i >= 0 && i < NumVertices ? NodeTable[i].data : NULL; } int NumberOfVertices ( ) { return NumVertices; } int NumberOfEdges ( ) { return NumEdges; } void InsertVertex ( Type vertex ); void RemoveVertex ( int v ); void InsertEdge ( int v1, int v2, float weight ); void RemoveEdge ( int v1, int v2 ); float GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v );
int GetNextNeighbor( int v, int w); 邻接表的构造函数和析构函数 template <class Type> Graph <Type>:: Graph( int sz= DefaultSize ) Num Vertices(O) Max Vertices(sz), Num Edges(OR int n, e, k,j; Type name, tail, head; float weight; NodeTable ∥创建顶点表 new Vertex<Type>[Max Vertices
int GetNextNeighbor ( int v, int w ); } template <class Type> Graph <Type> :: Graph ( int sz = DefaultSize ) : NumVertices (0), MaxVertices (sz), NumEdges (0){ int n, e, k, j; Type name, tail, head; float weight; NodeTable = //创建顶点表 new Vertex<Type>[MaxVertices];
cIn>>n; /入顶点个数 for(inti=0;1<n;i++)/入各顶点信息 i cin > name; Insert Vertex( name ); cIn>>e /入边条数 for(1=0;i<e;i++){/逐条边输入 cin >>tail > head > weight k- Get VertexPos( tail )i j=Get Vertex Pos( head ) InsertEdge(k, j,weight);∥插入边
cin >> n; //输入顶点个数 for ( int i = 0; i < n; i++) //输入各顶点信息 { cin >> name; InsertVertex ( name ); } cin >> e; //输入边条数 for ( i = 0; i < e; i++) { //逐条边输入 cin >> tail >> head >> weight; k = GetVertexPos ( tail ); j = GetVertexPos ( head ); InsertEdge ( k, j, weight ); //插入边 } }
template <class Type> Graph <Type>:: Graphs for( int 1=0; 1< Num Vertices; 1++)t Edge<Type>*p= Node Table[i]adj while(p =null)( ∥/逐条边释放 NodeTable i] adj=p- > link delete p p=Node]. adi delete node table, /释放顶点表
template <class Type> Graph <Type> :: ~Graph ( ) { for ( int i = 0; i < NumVertices; i++ ) { Edge<Type> *p = NodeTable[i].adj; while ( p != NULL ) { //逐条边释放 NodeTable[i].adj = p->link; delete p; p = NodeTable[i].adj; } } delete [ ] NodeTable; //释放顶点表 }
邻接表部分成员函数的实现 template <class Type> int Graph <Type> Get VertexPos( const Type vertex ∥根据顶点名 vertex查找它在邻接表中位置 for( int 1=0; 1< Num Vertices; 1++) if( NodeTablei]data ==vertex) return 1; return-l template < Class Type> int Graph <Type>:: GetFirstNeighbor (int v)( ∥查找顶点V第一个邻接顶点在邻接表中位置
template <class Type> int Graph <Type> :: GetVertexPos ( const Type vertex ) { //根据顶点名vertex查找它在邻接表中位置 for ( int i = 0; i < NumVertices; i++ ) if ( NodeTable[i].data == vertex ) return i; return -1; } template <Class Type> int Graph <Type> :: GetFirstNeighbor ( int v ) { //查找顶点 v 第一个邻接顶点在邻接表中位置