邻接表是图的另一种有效的存储表示方法. 每个顶点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;}
可就是这样，还是有人，期望过多的温暖。
