Type Get Value( int 1) i return 1>=0 & 1< Num Vertices Node Tableli] data: NULL; 3 int NumberOfVertices f return Num Vertices;) int NumberofEdges (( return NumEdges; void Insert Vertex( Type vertex ) void Remove Vertex(int v); void InsertEdge( int vI, int v2, float weight ) void RemoveEdge( int vl, int v2) float Get Weight int vI, int v2) int GetFirstNeighbor( int v );
Type 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(0) Max Vertices(sz), NumEdges(O)R 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<m;i++)/输入各顶点信息 i cin > name; Insert Vertex( name ) cin>> e. /输入边条数 for(i=0;1<e;i++){/条边输入 cin >> tail > head > weight k=Get VertexPos( tail ) j=Get VertexPos( 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 i=0; 1< Num Vertices; i++)i Edge*p=NodeTableli] adj while(p =NULL)( //逐条边释放 NodeTableli] adj=p->link delete p p= Node Table[i] adj delete nodetable; ∥释放顶点表
template <class Type> Graph <Type> :: ~Graph ( ) { for ( int i = 0; i < NumVertices; i++ ) { Edge *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 Vertex Pos( const Type vertex& 根据顶点名 vertex.查找它在邻接表中位置 for( int i=0; 1< Num Vertices; 1++) if( Node Tablei] data=- vertex) return return -1; template <Class Type> int Graph <Type>:: Get FirstNeighbor( int v)t ∥查找顶点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 第一个邻接顶点在邻接表中位置