数据结构（C++）——图（邻接表）

数据结构（C++）——图（邻接表）

以邻接矩阵的形式存储图结构，当e远远小于n^2时，大量的元素都是0。显然，这么多的0元素肯定会造成存储空间的巨大浪费。所以我们将邻接矩阵改进为邻接表。

为此，需要把邻接矩阵的各行分别组织为一个单链表。

如图：

代码：

#include"AllHead.h"
#define MAXSIZE 10
class EdgeNode;template<class T>
class GrapHL;template<class T>
class VertexList
{friend class GrapHL<T>;
private:T data;EdgeNode *link;
public:VertexList():link(NULL){}~VertexList(){}
};
class EdgeNode
{
public:int dest;EdgeNode *next;
public:EdgeNode(){next = NULL;}~EdgeNode(){}
};
template<class T>
class GrapHL
{
private:VertexList<T> *myv;int maxSize;//最大int numVertexs;int numEdges;
public:GrapHL(int sz=MAXSIZE){maxSize = sz<=MAXSIZE?MAXSIZE:sz;myv = new VertexList<T>[maxSize];numVertexs = 0;numEdges = 0;}~GrapHL(){}
public:int RemoveVertex(T x){int countEdge = 0;int v = GetVerticespos(x);EdgeNode *fp1 = myv[v].link;int temppos;while(fp1 != NULL){++countEdge;temppos = (*fp1).dest;EdgeNode *fp2 = myv[temppos].link;EdgeNode *fp3 = NULL;if((*fp2).dest == v){myv[temppos].link = (*fp2).next;}else{while(fp2!=NULL && (*fp2).dest!=v){fp3 = fp2;fp2 = (*fp2).next;}(*fp3).next = (*fp2).next;free(fp2);}myv[v].link = (*fp1).next;free(fp1);fp1 = myv[v].link;	}myv[v].data = myv[numVertexs-1].data;myv[v].link = myv[numVertexs-1].link;fp1 = myv[v].link;EdgeNode *fpm = NULL;while(fp1 != NULL){temppos = (*fp1).dest;fpm = myv[temppos].link;while(fpm!=NULL && (*fpm).dest!=numVertexs-1)fpm = (*fpm).next;(*fpm).dest = v;fp1 = (*fp1).next;}--numVertexs;numEdges-=countEdge;return OK;}int RemoveEdge(T x1, T x2){int v1 = GetVerticespos(x1);//Aint v2 = GetVerticespos(x2);//Bif(v1 == -1||v2 == -1){cout<<"有一个节点不存在"<<endl;return ERROR;}EdgeNode *fp1 = myv[v1].link;EdgeNode *fp2 = NULL;if((*fp1).dest == v2){myv[v1].link = (*fp1).next;}else{while(fp1!=NULL && (*fp1).dest!=v2){fp2 = fp1;fp1 = (*fp1).next;}if(fp1 == NULL){cout<<"不存在"<<x1<<"--"<<x2<<"这条边...."<<endl;return FALSE;}(*fp2).next = (*fp1).next;}free(fp1);--numEdges;return OK;}int GetNextNeighbor(T x1,T x2){if(numVertexs == 0){cout<<"空(GetFirstNeighbor)...";return ERROR;}int v1 = GetVerticespos(x1);int v2 = GetVerticespos(x2);EdgeNode *fp = myv[v1].link;while(fp!=NULL && (*fp).dest != v2)fp = (*fp).next;if(fp == NULL){cout<<"不存在有过链接.....";return ERROR;}fp = (*fp).next;if(fp != NULL)return (*fp).dest;else{cout<<"没有下一个结点....";return ERROR;}}int GetFirstNeighbor(T x){if(numVertexs == 0){cout<<"空(GetFirstNeighbor)...";return ERROR;}int v = GetVerticespos(x);EdgeNode *fp = myv[v].link;if(fp != NULL)return (*fp).dest;else{cout<<x<<" :没有链接的结点....";return ERROR;}}int GetVerticespos(T x){if(numVertexs == 0){cout<<"空(Getpos)....";return FALSE;}int i;for(i=0;i<numVertexs;i++){if(myv[i].data == x)return i;}return -1;}
public:int NumOfVertices(){return numVertexs;}int NumOfEdge(){return numEdges;}int InsertVertex(T x){if(numVertexs >= maxSize){cout<<"空间已满不能插入...."<<endl;return ERROR;}myv[numVertexs++].data = x;return TRUE;}int InsertEdge(T x1,T x2)//A,B{int v1 = GetVerticespos(x1);//Aint v2 = GetVerticespos(x2);//Bif(v1 == -1||v2 == -1){cout<<"有一个节点不存在"<<endl;return ERROR;}EdgeNode *p1 = new EdgeNode;(*p1).dest = v2;(*p1).next = myv[v1].link;myv[v1].link = p1;EdgeNode *p2 = new EdgeNode;(*p2).dest = v1;(*p2).next = myv[v2].link;myv[v2].link = p2;++numEdges;}void showGrap(){for(int i=0; i<numVertexs; ++i){cout<<myv[i].data<<"-->";EdgeNode *e = myv[i].link;while(e != NULL){cout<<e->dest<<"-->";e = e->next;}cout<<"Nul."<<endl;}}};

#if 0
#include"graphl.h"
int main()
{GrapHL<char> gl;gl.InsertVertex('A');gl.InsertVertex('B');gl.InsertVertex('C');gl.InsertVertex('D');gl.InsertVertex('E');gl.InsertVertex('F');gl.InsertVertex('G');gl.InsertVertex('H');gl.InsertVertex('I');gl.InsertEdge('A','D');gl.InsertEdge('A','B');gl.InsertEdge('A','C');gl.InsertEdge('B','E');//gl.InsertEdge('B','C');gl.InsertEdge('F','C');gl.InsertEdge('F','D');gl.InsertEdge('F','H');gl.InsertEdge('E','G');gl.InsertEdge('H','I');
//	gl.RemoveEdge('A','B');
//	gl.RemoveEdge('A','C');
//	gl.RemoveEdge('G','C');gl.showGrap();cout<<gl.NumOfVertices()<<endl;cout<<gl.NumOfEdge()<<endl;cout<<gl.GetFirstNeighbor('I')<<endl;cout<<gl.GetNextNeighbor('A','D')<<endl;cout<<gl.GetNextNeighbor('C','G')<<endl;cout<<"--------------------------"<<endl;gl.RemoveVertex('C');gl.showGrap();cout<<gl.NumOfVertices()<<endl;cout<<gl.NumOfEdge()<<endl;return 0;
}