基础数据结构 - 链表与邻接表

目录

• 邻接表

数组是一种支持随机访问，但不支持在任意位置插入或删除元素的数据结构。
链表是一种支持任意位置插入或删除，但只能按顺序依次访问其中的元素。

正规的链表是通过动态分配内存、指针等实现，为了避免内存泄漏、方便调试，在竞赛中使用数组模拟链表，下标模拟指针这种做法。

这里贴出Acwing上单链表、双链表的代码模板：

单链表：

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

【例题】邻值查找

给定一个长度为 n n n 的序列 A A A， A A A 中的数各不相同。

对于 A A A 中的每一个数 A i A_i Ai​，求：

m i n 1 ≤ j < i ∣ A i − A j ∣ min_{1\le jmin1≤j<i​∣Ai​−Aj​∣
以及令上式取到最小值的 j j j（记为 P i P_i Pi​）。若最小值点不唯一，则选择使 A j A_j Aj​ 较小的那个。

数据范围
n ≤ 1 0 5 , ∣ A i ∣ ≤ 1 0 9 n\le10^5,|A_i|\le10^9 n≤105,∣Ai​∣≤109

分析：

方法一：平衡树（STL set）

使用 STL 里的 set 处理就很轻松了，因为对于每一个 A i A_i Ai​ 找的是在 i i i 之前的数字中的 A j A_j Aj​ ，故遍历序列 A A A ，在插入 A i A_i Ai​ 之前，查找在 set 中第一个大于它的元素，那么答案要么是它，要么是它的前驱元素。

代码如下：

#include 
using namespace std;
const int INF = 0x3f3f3f3f;

struct Node {
    int id;
    int v;
    bool operator < (const Node &W) const {
        if(v == W.v) return id < W.id;
        return v < W.v;
    }
};

set<Node> s;
int main()
{
    int n,cnt = 1;
    cin >> n;
    vector<Node> a(n);

    for(auto &it : a) {
        cin >> it.v;
        it.id = cnt++;
    }

    s.insert(a[0]);

    for(int i = 1; i < n; ++i) {
        auto pre_it = (s.upper_bound(a[i]));
        auto last_it = pre_it;

        if(pre_it != s.begin())
            pre_it--;

        int res = abs(a[i].v - pre_it->v), id = pre_it -> id;

        if(last_it != s.end() && res > abs(a[i].v - last_it->v)) {
            res = abs(a[i].v - last_it->v);

            id = last_it -> id;
        }

        cout << res << ' ' << id << endl;

        s.insert(a[i]);
    }

    return 0;
}

方法二：链表

利用链表易删除的特性，我将序列 A A A 排序，然后插入带链表中，接着使用另一个数组 B B B ，其中 B i B_i Bi​ 代表原序列 A A A 中 A i A_i Ai​ 在链表中的指针。

因为链表有序，所以对于 A n A_n An​ 而言，它的 A j A_j Aj​ 就一定是前驱或者后驱，然后在将它从链表中删除，那么这样逆序找到的答案就都是符合答案的。

代码如下：

#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f; 
struct Node {
    int id, v;
    bool operator < (const Node &W) const {
        if(v == W.v) return  id < W.id;
        return v < W.v;
    }
} a[N];
int b[N];

struct NodeL {
    int id, v;
    int pe, ne;
} node[N];

int h, t, idx;

void init() {
    h = 0, t = 1;
    node[h].ne = t;
    node[t].pe = h;
    idx = 2;
}

int insert(int p, int v, int id) {
    node[idx] = {id, v, p, node[p].ne};
    node[node[p].ne].pe = idx;
    node[p].ne = idx++;
    return idx - 1;
}

void remove(int p) {
    node[node[p].pe].ne = node[p].ne;
    node[node[p].ne].pe = node[p].pe;
}




int main()
{
    init();

    int n; 
    scanf("%d", &n);

    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i].v);
        a[i].id = i + 1;
    }

    sort(a, a + n);

    int last = h;

    for(int i = 0; i < n; ++i) {
        last = insert(last, a[i].v, a[i].id);
        b[a[i].id - 1] = last;
    }

    vector<PII> ans;

    for(int i = n - 1; i >= 1; --i) {
        int j = b[i];

        int res, id;

        int l = node[j].pe, r = node[j].ne;
        if(l != 0 && r != 1) {
            if(abs(node[l].v - node[j].v) <= abs(node[r].v - node[j].v)) {
                res = abs(node[l].v - node[j].v), id = node[l].id;
            } else {
                res = abs(node[r].v - node[j].v), id = node[r].id;
            }
        } else if(l != 0) {
            res = abs(node[l].v - node[j].v), id = node[l].id;
        } else {
            res = abs(node[r].v - node[j].v), id = node[r].id;
        }


        ans.push_back({res, id});
        remove(j);
    }

    reverse(ans.begin(), ans.end());

    for(auto it : ans) {
        cout << it.first << ' ' << it.second << endl;
    }

    return 0;
}

【例题】动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

数据范围
1 ≤ P ≤ 1000 , 1 ≤ M ≤ 99999 1\le P\le1000, 1\le M\le99999 1≤P≤1000,1≤M≤99999, 所有 M M M 相加之和不超过 5 × 1 0 5 5\times10^5 5×105。

分析：

如果从整数序列正着求，那么就只能使用在线做法的对顶堆，反之我们反着求，那么就可以和上面链表做法类似的一种离线做法。

将整个序列读入后，我们就已经知道了此时的中位数位置了，将他删除后，得到的我们也可以知道此时的中位数位置，不过为了快速访问，所以我们使用 H a s h Hash Hash 表来记录指针位置就可以解决了。

邻接表

邻接表其实就是数组加链表的组合数据结构，对于每一个数组元素都是一个链表的表头。一般用于图的储存，也有 H a s h Hash Hash 表里面的拉链法储存。

这里贴一个 Acwing 的模板：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

书上提到了一种优化储存双向图的方法，利用整数对于 1 1 1 的异或运算具有成对变化的性质，故程序最初 idx=2 ，然后双向边就会储存在下标 “ 2 2 2 和 3 3 3 ”、 “ 4 4 4 和 5 5 5 ”、 “ 6 6 6 和 7 7 7 ” ···的位置上。所以如果 e[i] 是第 i i i 条边的起点，那么 e[i ^ 1] 就是第 i i i 条边的终点。