鄰接表是圖的另一種有效的存儲表示方法. 每個頂點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; } ~~~