int n, e, k, j; Name Type name, tail, head; DistType weight NodeTable= 创建顶点表 new Vertex<Nametype> Max vertices]; cin>>na 入顶点个数 for(inti=0;i<H;计++)∥输入各顶点信息 i cin > name; Inservertex( name );3 cin>>es 入边条数 for(i=0;i<e;i++){/永边输入 cin>> tail > head >> weights k= Getvertex Pos( tail); j-GetvertexPos( head) InsertEdge(k,j, weight
int n, e, k, j; NameType name, tail, head; DistType weight; NodeTable = //创建顶点表 new Vertex<Nametype>[MaxVertices]; cin >> n; //输入顶点个数 for ( int i = 0; i < n; i++) //输入各顶点信息 { cin >> name; InserVertex ( 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 NameType, class DistType> Graph<NameType, DistType>:: Graph(( for( int i=0; i< Numvertices; i++)t Edge<DistType> p=NodelTableliadj while(p =NULL)( /条边释放 Node].adi=p-link; delete p; p=Node[iladj;) delete [i node tables 释放顶点表 邻接表部分成员函数的实现
} template <class NameType, class DistType> Graph<NameType, DistType>::~Graph ( ) { for ( int i = 0; i < NumVertices; i++ ) { Edge<DistType> *p = NodeTable[i].adj; while ( p != NULL ) { //逐条边释放 NodeTable[i].adj = p→link; delete p; p = NodeTable[i].adj; } } delete [ ] NodeTable; //释放顶点表 } 邻接表部分成员函数的实现
template <class NameType, class DistType> int Graph<NameType, DistType>:: GetvertexPos( const Name Type vertex i /根据顶点名re查找该顶点在邻接表中的位置 for( int i=0; i <Num vertices; i++) if( Node Tablelidata = vertex)return i return -1 template <Class Name'Type, class DistType> int Graph<Name Type, DistType>:: GetFirstNeighbor( const int v)& 查找顶点的第一个邻接顶点在邻接表中的位置
template <class NameType, class DistType> int Graph<NameType, DistType>:: GetVertexPos ( Const NameType & vertex ) { //根据顶点名vertex查找该顶点在邻接表中的位置 for ( int i =0; i <NumVertices; i++ ) if ( NodeTable[i].data == vertex ) return i; return -1; } template <Class NameType, class DistType> int Graph<NameType, DistType>:: GetFirstNeighbor ( const int v ) { //查找顶点 v 的第一个邻接顶点在邻接表中的位置
if(v!=-1){ /若顶点存在 Edge<DistType> p= NodeTablelv] adj; if(p!=NULL) return p-dest return -1 若顶点不存在 template <Class NameType, class DistTypeType> int Graph<Name Type, DistType>:: GetNextNeighbor( const int vI, const int v2)t 查找顶点川在邻接顶点后下一个邻接顶点 if (v1!=-1)t EagesDistType> *p= Node Tablelvl] adj
if ( v != -1 ) { //若顶点存在 Edge<DistType> *p = NodeTable[v].adj; if ( p != NULL ) return p→dest; } return -1; //若顶点不存在 } template <Class NameType, class DistTypeType> int Graph<NameType, DistType>:: GetNextNeighbor( const int v1, const int v2 ) { //查找顶点 v1 在邻接顶点 v2 后下一个邻接顶点 if ( v1 != -1 ) { Edge<DistType> *p = NodeTable[v1].adj;
while(p!=NUll)( if (p-dest==v2 &&p-link!=NULL return p-link-→desa /回下一个邻接顶点在邻接表中的位置 else=p-link return-1;∥没有查到下一个邻接顶点返回-1
while ( p != NULL ) { if ( p→dest == v2 && p→link != NULL ) return p→link→dest; //返回下一个邻接顶点在邻接表中的位置 else p = p→link; } } return -1; //没有查到下一个邻接顶点返回-1 }