// 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$

的序列

A

$A$

，

A

$A$

中的数各不相同。

对于

A

$A$

中的每一个数

A_i

$A_{i}$

，求：

≤

∣

−

∣

min_{1\le j<i}|A_i−A_j|

$m i n_{1 \leq j < i} ∣ A_{i} - A_{j} ∣$

以及令上式取到最小值的

j

$j$

（记为

P_i

$P_{i}$

）。若最小值点不唯一，则选择使

A_j

$A_{j}$

较小的那个。

数据范围

≤

∣

≤

n\le10^5,|A_i|\le10^9

$n \leq 1 0^{5}, ∣ A_{i} ∣ \leq 1 0^{9}$

分析：

方法一：平衡树（
STL set
）

使用
STL
里的
set
处理就很轻松了，因为对于每一个

A_i

$A_{i}$

找的是在

i

$i$

之前的数字中的

A_j

$A_{j}$

，故遍历序列

A

$A$

，在插入

A_i

$A_{i}$

之前，查找在
set
中第一个大于它的元素，那么答案要么是它，要么是它的前驱元素。

代码如下：

#include <bits/stdc++.h>
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$

排序，然后插入带链表中，接着使用另一个数组

B

$B$

，其中

B_i

$B_{i}$

代表原序列

A

$A$

中

A_i

$A_{i}$

在链表中的指针。

因为链表有序，所以对于

A_n

$A_{n}$

而言，它的

A_j

$A_{j}$

就一定是前驱或者后驱，然后在将它从链表中删除，那么这样逆序找到的答案就都是符合答案的。

代码如下：

#include <bits/stdc++.h>
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;
}

【例题】

动态中位数

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

数据范围

≤

1000

≤

99999

1\le P\le1000, 1\le M\le99999

$1 \leq P \leq 1000, 1 \leq M \leq 99999$

, 所有

M

$M$

相加之和不超过

5\times10^5

$5 \times 1 0^{5}$

。

分析：

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

将整个序列读入后，我们就已经知道了此时的中位数位置了，将他删除后，得到的我们也可以知道此时的中位数位置，不过为了快速访问，所以我们使用

Hash

$H a s h$

表来记录指针位置就可以解决了。

邻接表

邻接表其实就是数组加链表的组合数据结构，对于每一个数组元素都是一个链表的表头。一般用于图的储存，也有

Hash

$H a s h$

表里面的拉链法储存。

这里贴一个 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$

的异或运算具有成对变化的性质，故程序最初
idx=2
，然后双向边就会储存在下标 “

2

$2$

和

3

$3$

”、 “

4

$4$

和

5

$5$

”、 “

6

$6$

和

7

$7$

” ···的位置上。所以如果
e[i]
是第

i

$i$

条边的起点，那么
e[i ^ 1]
就是第

i

$i$

条边的终点。

原文链接：https://blog.csdn.net/althumi/article/details/124175979

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

目录

邻接表

目录

邻接表

你可能也喜欢