邻接表是图的另一种有效的存储表示方法. 每个顶点u建立一个单链表, 链表中每个结点代表一条边<u, v>, 为边结点. 每个单链表相当于邻接矩阵的一行. adjVex域指示u的一个邻接点v, nxtArc指向u的下一个边结点. 如果是网, 增加一个w域存储边上的权值. 构造函数完成对一维指针数组a的动态空间存储分配, 并对其每个元素赋初值NULL. 析构函数首先释放邻接表中所有结点, 最后释放一维指针数组a所占的空间. 包含的函数Exist(): 若输入的u, v无效, 则函数返回false. 否则从a[u]指示的边结点开始, 搜索adjVex值为v的边结点, 代表边<u, v>, 若搜索成功, 返回true, 否则返回false. 函数Insert(): 若输入的u, v无效, 则插入失败, 返回Failure. 否则从a[u]指示的边开始, 搜索adjVex值为v的边结点, 若不存在这样的边结点, 则创建代表边<u, v>的新边结点, 并将其插在由指针a[u]所指示的单链表最前面, 并e++. 否则表示<u, v>是重复边, 返回Duplicate. 函数Remove(): 若输入的u, v无效, 则删除失败, 返回Failure. 否则从a[u]指示的边开始, 搜索adjVex值为v的边结点, 若存在这样的边, 删除边, e--, 返回Success. 否则表示不存边<u, v>, 返回NotPresent. 实现代码: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "queue" #include "stack" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" #include "list" #include "string" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure }; template <class T> struct ENode { ENode() { nxtArc = NULL; } ENode(int vertex, T weight, ENode *nxt) { adjVex = vertex; w = weight; nxtArc = nxt; } int adjVex; T w; ENode *nxtArc; /* data */ }; template <class T> class Graph { public: virtual ~Graph() {} virtual ResultCode Insert(int u, int v, T &w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v) const = 0; /* data */ }; template <class T> class LGraph: public Graph<T> { public: LGraph(int mSize); ~LGraph(); ResultCode Insert(int u, int v, T &w); ResultCode Remove(int u, int v); bool Exist(int u, int v) const; int Vertices() const { return n; } void Output(); protected: ENode<T> **a; int n, e; /* data */ }; template <class T> void LGraph<T>::Output() { ENode<T> *q; for(int i = 0; i < n; ++i) { q = a[i]; while(q) { cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')'; q = q -> nxtArc; } cout << endl; } cout << endl << endl; } template <class T> LGraph<T>::LGraph(int mSize) { n = mSize; e = 0; a = new ENode<T>*[n]; for(int i = 0; i < n; ++i) a[i] = NULL; } template <class T> LGraph<T>::~LGraph() { ENode<T> *p, *q; for(int i = 0; i < n; ++i) { p = a[i]; q = p; while(p) { p = p -> nxtArc; delete q; q = p; } } delete []a; } template <class T> bool LGraph<T>::Exist(int u, int v) const { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false; ENode<T> *p = a[u]; while(p && p -> adjVex != v) p = p -> nxtArc; if(!p) return false; return true; } template <class T> ResultCode LGraph<T>::Insert(int u, int v, T &w) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(Exist(u, v)) return Duplicate; ENode<T> *p = new ENode<T>(v, w, a[u]); a[u] = p; e++; return Success; } template <class T> ResultCode LGraph<T>::Remove(int u, int v) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; ENode<T> *p = a[u], *q = NULL; while(p && p -> adjVex != v) { q = p; p = p -> nxtArc; } if(!p) return NotPresent; if(q) q -> nxtArc = p -> nxtArc; else a[u] = p -> nxtArc; delete p; e--; return Success; } int main(int argc, char const *argv[]) { LGraph<int> lg(4); int w = 4; lg.Insert(1, 0, w); lg.Output(); w = 5; lg.Insert(1, 2, w); lg.Output(); w = 3; lg.Insert(2, 3, w); lg.Output(); w = 1; lg.Insert(3, 0, w); lg.Output(); w = 1; lg.Insert(3, 1, w); lg.Output(); return 0; } ~~~