【数据结构】图的存储(十字链表)

弧节点 

• tailvex数据域：存储弧尾一端顶点在顺序表中的位置下标；
• headvex 数据域：存储弧头一端顶点在顺序表中的位置下标；
• hlink 指针域：指向下一个以当前顶点作为弧头的弧；
• tlink 指针域：指向下一个以当前顶点作为弧尾的弧；
• info 指针：存储弧的其它信息，例如有向网中弧的权值。如果不需要存储其它信息，可以省略。

 顶点节点

• data 数据域：用来存储顶点的信息；
• firstin 指针域：指向一个链表，链表中记录的都是以当前顶点为弧头的弧的信息；
• firstout 指针域：指向另一个链表，链表中记录的是以当前顶点为弧尾的弧的信息。

       就类似这种结构图：

大家别看他有这么多变量，其实理解起来很简单，十字链表是有向图的一种存储方式。

顶点节点中的firstout管理的是所有的弧尾，而弧节点的tlink负责链接。

顶点节点中的firstin管理的是所有的弧头 ，而弧节点的hlink负责链接。

---

在编写代码中，我给弧节点增加了两个指针分别是hprelink与tprelink。

这两个指针的意义是：

hprelink: 指向上一个以当前顶点作为弧头的弧；

tprelink：指向上一个以当前顶点作为弧尾的弧；

其实就是双链表的思想，为什么想用双链表，其实我在实现删除的时候：当我以头结点进行firstout遍历后找到当前顶点为弧尾的弧后，发现还要遍历一遍firstin找到当前顶点为弧头的弧。所以就寻思用双链表吧。其实如果不用双链表也大差不差只不过要多遍历一次，都是要找到这个节点的前一个节点和后一个节点，进行节点维护。

我觉得写代码中有一些心得值得分享的：在删除节点的时候吧，我总是把弧头与弧尾放到一块分析，比如：弧头前一个节点如果为空弧尾前一个节点如果不为空，弧头后一个节点如果为空弧尾后一个节点如果为空.......分析了一大坨。漏洞百出，逻辑没有闭合（痛苦了很长时间）。后来，我就逐个分析把他们分开了，删除这个节点的本质其实就是维护这个节点的前弧头一个节点，和后弧头一个节点，如果前为空....如果后为空....。之后分析弧尾也是这个套路。后来我总结一下：维护一个位置，其实就是分析前一个位置与后一个位置，不用管这个节点位置本身在头还是尾还是中间。

#pragma once
#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;namespace Cross_linked_list
{template<class W>struct ArcNode{int tailvex;    // 弧尾下标int headvex;    // 弧头下标ArcNode<W>* hlink; // 相同弧头的下一条弧ArcNode<W>* tlink;    // 相同弧尾的下一条弧ArcNode<W>* hprelink;  // 弧头的上一条弧ArcNode<W>* tprelink;    // 弧尾的上一个弧W weight;        // 权值ArcNode(int tail, int head, W w):tailvex(tail), headvex(head), hlink(nullptr), tlink(nullptr), hprelink(nullptr), tprelink(nullptr), weight(w){}};// 顶点结构节点template<class V, class W>struct VexNode{V data;      // 顶点信息ArcNode<W>* firstin; // 指向该顶点的第一条入弧ArcNode<W>* firstout;// 指向该顶点的第一条出弧VexNode(V val):data(val), firstin(nullptr), firstout(nullptr){}};template<class V, class W> class Graph{typedef ArcNode<W> Arc;  typedef VexNode<V, W> Vex; public:// 4 , "ABCD"Graph(int n, const V* ver){// 存储顶点并与下标建立映射_vertexs.reserve(n);_vexstable.resize(n, nullptr); // 初始化为nullptrfor (int i = 0; i < n; i++){_vertexs.push_back(ver[i]);_indexMap[ver[i]] = i;// 创建VexNode对象_vexstable[i] = new Vex(ver[i]); }}~Graph(){// 释放所有顶点和弧节点for (auto vex : _vexstable){// 释放出弧节点Arc* p = vex->firstout;while (p){Arc* temp = p;p = p->tlink;delete temp;}// 释放顶点delete vex;}}void addArc(V src, V dst, W weight){int srci = locateVex(src);int dsti = locateVex(dst);if (srci == -1 || dsti == -1){cout << "顶点不存在！" << endl;return;}Arc* arc = new Arc(srci, dsti, weight);// 获取源顶点和目标顶点的指针Vex* srcVex = _vexstable[srci]; Vex* dstVex = _vexstable[dsti]; // 维护出弧链表（双向）if (srcVex->firstout) {srcVex->firstout->tprelink = arc;}arc->tlink = srcVex->firstout;srcVex->firstout = arc;arc->tprelink = nullptr;// 维护入弧链表（双向）if (dstVex->firstin) {dstVex->firstin->hprelink = arc;}arc->hlink = dstVex->firstin;dstVex->firstin = arc;arc->hprelink = nullptr;}void delEdge(V src, V dst){int srci = locateVex(src);int dsti = locateVex(dst);if (srci == -1 || dsti == -1){cout << "顶点不存在！" << endl;return;}// 查找从srci到dsti的节点Arc* arc = _vexstable[srci]->firstout;Arc* prev = nullptr;while (arc && arc->headvex != dsti){prev = arc;arc = arc->tlink;}if (!arc){cout << "边不存在！" << endl;return;}// 获取源顶点和目标顶点的指针Vex* srcVex = _vexstable[srci];Vex* dstVex = _vexstable[dsti];// 从出弧链表中删除// 如果前节点存在，不存在就更新头节点if (prev)prev->tlink = arc->tlink;elsesrcVex->firstout = arc->tlink;// 如果后节点存在if (arc->tlink)arc->tlink->tprelink = prev;// 从入弧链表中删除if (arc->hprelink)arc->hprelink->hlink = arc->hlink;elsedstVex->firstin = arc->hlink;// 如果后节点存在if (arc->hlink)arc->hlink->hprelink = arc->hprelink;delete arc;}void print(){cout << "映射关系" << endl;for (size_t i = 0; i < _vexstable.size(); ++i){cout << _vexstable[i]->data << ":" << i << endl;}cout << endl;cout << "出弧链表：" << endl;for (size_t i = 0; i < _vexstable.size(); ++i){Arc* p = _vexstable[i]->firstout;cout << "顶点 " << _vexstable[i]->data << "(" << i << ") 的出弧：";while (p){cout << "[" << _vertexs[p->headvex] << ", 权值:" << p->weight << "] ";p = p->tlink;}cout << endl;}cout << endl;cout << "入弧链表：" << endl;for (size_t i = 0; i < _vexstable.size(); ++i){Arc* p = _vexstable[i]->firstin;cout << "顶点 " << _vexstable[i]->data << "(" << i << ") 的入弧：";while (p){cout << "[" << _vertexs[p->tailvex] << "->" << _vexstable[i]->data << ", 权值:" << p->weight << "] ";p = p->hlink;}cout << endl;}}private:// 查找顶点在顶点表中的下标int locateVex(V v){auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{return -1;}}private:vector<Vex*> _vexstable;  // 顶点表map<V, int> _indexMap;    // 映射关系vector<V> _vertexs;       // 顶点集合};void test(){Graph<char, int> g(4, "ABCD"); g.addArc('A', 'B', 1);g.addArc('A', 'C', 1);g.addArc('C', 'D', 1);g.addArc('C', 'A', 1);g.addArc('D', 'A', 1);g.addArc('D', 'C', 1);cout << "\n删除边之前:\n";g.print();g.delEdge('C', 'A');g.delEdge('C', 'D');cout << "\n删除边之后:\n";g.print();}
}

效果展示：