图  数据结构

2/22/2017来源:ASP.NET技巧人气:337

#ifndef _GRAPH_H #define _GRAPH_H #define  DEFAULT_VERTEX_SIZE 10 template<class Type> class Graph; class Edge { public: Edge(int num):dest(num),link(NULL) {} ~Edge() {} int dest; Edge* link; }; template<class Type> class Vertex { friend Graph<Type>; public: Vertex():data(Type()),adj(NULL) {} ~Vertex() {} PRivate: Edge *adj; Type data; }; template<class Type> class Graph { public: Graph(int sz=DEFAULT_VERTEX_SIZE) { MaxVertices=sz>DEFAULT_VERTEX_SIZE?sz:DEFAULT_VERTEX_SIZE; NumVertices=NumEdge=0; NodeTable=new Vertex<Type>[MaxVertices]; } ~Graph() { Edge *t; for(int i=0;i<NumVertices;++i)     {         Edge *w;         t=NodeTable[i].adj;         while(t!=NULL)         {             w=t;             t=t->link;             delete w;         }     }     delete[] NodeTable;     ////// } int GetPosOfVertex(const Type &v)const {     for(int i=0;i<NumVertices;++i)     {         if(NodeTable[i].data==v)         return i;     }     return -1; } void InsertVertex(const Type &val) { if(NumVertices<MaxVertices) {     NodeTable[NumVertices++].data=val; } } bool InsertEdge(const Type &vertex1, const Type &vertex2) {         int v1 = GetPosOfVertex(vertex1);         int v2 = GetPosOfVertex(vertex2);         if(v1==-1 || v2==-1)             return false;         //v1 --> v2         Edge *e = new Edge(v2);         e->link = NodeTable[v1].adj;         NodeTable[v1].adj = e;         //v2 --> v1         e = new Edge(v1);         e->link = NodeTable[v2].adj;         NodeTable[v2].adj = e;         NumEdge++;         return true;     } /* bool InsertEdge(const Type &v1,const Type &v2) {     int V1=GetPosOfVertex(v1);     int V2=GetPosOfVertex(v2);     if(V1==-1||V2==-1)     return false;     //v1-->v2     cout<<"v1: "<<V1<<"  v2:  "<<V2<<endl;     Edge *s=new Edge(V2);     s->link=NodeTable[V1].adj;     NodeTable[V1].adj=s;     //v2-->v1     Edge *s1=new Edge(V1);     s1->link=NodeTable[V2].adj;     NodeTable[V1].adj=s1;     ++NumEdge;     return true; } */ int NumOfVertex()const {     return NumVertices; } int NumOfEdge()const {     return NumEdge; } int GetFirstNeighbor(const Type &vertex)const {     int v=GetPosOfVertex(vertex);     if(v==-1)     return -1;    if(    NodeTable[v].adj!=NULL)        return NodeTable[v].adj->dest;     else     return -1; } int GetNextNeighbor(const Type &vertex1,const Type &vertex2)const {     int v1=GetPosOfVertex(vertex1);     int v2=GetPosOfVertex(vertex2);     if(v1==-1||v2==-1)     return -1;     if(NodeTable[v1].adj==NULL)     return -1;     Edge *t=NodeTable[v1].adj;     while(t!=NULL&&t->dest!=v2)     t=t->link;     if(t==NULL)     return -1;     else     if(t->link!=NULL)     return t->link->dest; } bool RemoveEdge(const Type &vertex1,const Type &vertex2) {     int v1=GetPosOfVertex(vertex1);     int v2=GetPosOfVertex(vertex2);     if(v1==-1||v2==-1)     return false;     Edge *t=NodeTable[v1].adj;     Edge *p=t;     while(t!=NULL&&t->dest!=v2)     {         p=t;         t=t->link;     }     if(t==NULL)         return false;     else     {         if(p==t)         {             Edge *w=NodeTable[v1].adj;             NodeTable[v1].adj=NodeTable[v1].adj->link;             delete w;         }         else         {             Edge *w=p->link;             p->link=t->link;             delete w;         }     //         t=p=NodeTable[v2].adj;         while(t->dest!=v1)         {             p=t;             t=t->link;         }         if(t==p)         {             Edge *w=NodeTable[v2].adj;             NodeTable[v2].adj=NodeTable[v2].adj->link;             delete w;         }         else         {                 Edge *w=p->link;             p->link=t->link;             delete w;         }         --NumEdge;         return true;     } } bool RemoveVertex(const Type &vertex) {     int v=GetPosOfVertex(vertex);     if(v==-1)     return false;     Edge* t=NodeTable[v].adj;     while(t!=NULL)     {         Edge *p=NodeTable[t->dest].adj;         Edge *p1=p;         while(p!=NULL)         {             while(p->dest!=v)             {                 p1=p;                 p=p->link;             }             if(p==p1)             {                 Edge *w=NodeTable[t->dest].adj;                 NodeTable[t->dest].adj=NodeTable[t->dest].adj->link;                 delete w;                 break;             }             else             {                 Edge* w=p1->link;                 p1->link=p->link;                 delete w;                 break;             }         }         p1=t;         t=t->link;         delete p1;         --NumEdge;     }     if(v!=NumVertices-1)     {         NodeTable[v].data=NodeTable[NumVertices-1].data;         NodeTable[v].adj=NodeTable[NumVertices-1].adj;         Edge *t1=NodeTable[NumVertices-1].adj;         while(t1!=NULL)         {             Edge *p3=NodeTable[t1->dest].adj;             while(p3->dest!=NumVertices-1)             p3=p3->link;             p3->dest=v;             t1=t1->link;         }     }     --NumVertices;     return true; } void ShowGraph() {     for(int i=0;i<NumVertices;++i)     {         cout<<i<<"  "<<NodeTable[i].data<<"  "<<"-->";         Edge* e=NodeTable[i].adj;         while(e!=NULL)         {             cout<<e->dest<<"-->";             e=e->link;         }         cout<<"NUL"<<endl;;     } } private: Vertex<Type>*NodeTable; int MaxVertices; int NumVertices; int NumEdge; }; #endif