int n,e, k,j, Name Type name, tail, head DistType weight Node Table= 创建顶点表 new Vertex<Nametype>[Max vertices]; cin>> na 入顶点个数 for(inti=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 )i
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 Name Type, class Disttype> Graph<NameType, DistType>: Graphoi for (int i=0; i< Numvertices; i++)i Edge< DistType> p= Node Tableliadi; while(p! =NULL) /条边释放 NodeTablelil.adj=p-link; delete p; p= Node Tablelil.adj;) delete l nodeTable /释放顶点表 邻接表部分成员函数的实现
} 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<Name'Type, DistType>:: GetvertexPos( const NameType vertex)( 据顶点名rte查找该顶点在邻接表中的笕置 for int i=0; i<Numvertices; i++) if( Node Tablei data =- vertex)return i return-l template <Class Name Type, class DistType> int Graph<Name Type, DistType>:: GetFirstNeighbor( const int v)i ∥查找顶点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= Node Tablelv]adji; if(p!=NULL)return p-dest; return -1 顶点不存在 template <Class Name Type, class DistTypeType int Graph<Name Type, DistType>:: GetNextNeighbor( const int vl, const int v2)( ∥查找顶点ν在接顶点卩后下一个邻接顶点 if(v1l=-1){ EagesDistType> p= NodeTablelvl]adji;
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)t if(p-dest -=v2 & p-link!=NULL return p-link-dest 回下一个邻接顶点在邻接表中的位置 else p=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 }