《算法竞赛进阶指南》0x13 链表与邻接表

一只野生彩色铅笔

发布于 2022-10-31 11:02:39

6990

发布于 2022-10-31 11:02:39

文章被收录于专栏：彩铅的随笔博客

链表基本概念

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素

它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳

链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：

链表因其链状的结构，能方便地删除、插入数据，操作次数是

O(1)

。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是

O(n)

数组可以方便地寻找并读取数据，在随机访问中操作次数是

O(1)

。但删除、插入的操作次数是 O(n) 次

双向链表的指针实现方式：

struct Node
{
    int value; // data
    Node *prev, *next; // pointers
};

Node *head, *tail;

void initialize() // create an empty list
{
    head = new Node();
    tail = new Node();
    head->next = tail;
    tail->prev = head;
}

void insert(Node *p, int value) // insert data after p
{
    q = new Node();
    q->value = value;
    p->next->prev = q; q->next = p->next;
    p->next = q; q->prev = p;
}

void remove(Node *p) // remove p
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
}

void recycle() // release memory
{
    while (head != tail)
    {
        head = head->next;
        delete head->prev;
    }
    delete tail;
}

双向链表的静态数组实现方式：

struct Node
{
    int value;
    int prev, next;
} node[SIZE];
int head, tail, tot;

void initialize()
{
    tot = 2;
    head = 1, tail = 2;
    node[head].next = tail;
    node[tail].prev = head;
}

int insert(int p, int value)
{
    int q = ++ tot;
    node[q].value = value;
    node[node[p].next].prev = q;
    node[q].next = node[p].next;
    node[p].next = q; node[q].prev = p;
    return q;
}

void remove(int p)
{
    node[node[p].prev].next = node[p].next;
    node[node[p].next].prev = node[p].prev;
}

void clear()
{
    memset(node, 0, sizeof(node));
    head = tail = tot = 0;
}

邻接表基本概念

邻接表一般实现使用一个 vector<int> 来存每一个点的出边

竞赛里常用的是 链式前向星 存图方式，即数组模拟邻接表

int h[N], e[N], w[N], ne[N], idx;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

// 邻接表：访问从x出发的所有边
for (int i = h[x]; ~i; i = ne[i])
{
    int y = e[i], z = w[i];
    // 一条有向边(x, y)，权值为z
}

习题

邻值查找

题目描述

给定一个长度为

的序列

，

中的数各不相同。

对于

中的每一个数

A_i

，求：

[ \min_{1≤j<i}|A_i−A_j| ]

以及令上式取到最小值的

（记为

P_i

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

A_j

较小的那个。

输入格式

第一行输入整数

，代表序列长度。

第二行输入

个整数

A_1…A_n

，代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共

n−1

行，每行输出两个整数，数值之间用空格隔开。

分别表示当

取

2∼n

时，对应的

\min\limits_{1≤j<i}|A_i−A_j|

和

P_i

的值。

数据范围

n≤10^5, |A_i|≤10^9

输入样例：

3
1 5 3

输出样例：

4 1
2 1

解析

维护这种类似问题的数据结构太多了，可以上线段树、树状数组、平衡树，但是本题的链表解法非常的巧妙，值得一写

链表解法是一种离线做法，步骤如下：

将原数组带着下标一起，按照元素的值从小到大顺排，然后以此顺序建立双向链表

找到原数组中下标为

的元素在双向链表中的位置

l_i

则

\forall i\in [1, n-1]

，欲使

|A_n−A_i|

最小，显然

A_i

必然在顺排后的新数组中与

A_n

相邻

因此直接找

l_i

的前驱和后继的最小值即是

|A_n−A_i|

的最小值

然后在双向链表中删去

l_i

，接着处理原数组中第

A_{n-1}

个数

删去的原因是，前缀中的邻值不包含大于当前下标的元素

sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
    pos[a[i].y] = insert(node[tail].prev, a[i].x, a[i].y);
for (int i = n; i > 1; i -- )
{
    int s = 2e9, idx = -1;
    Node &t = node[pos[i]];
    if (t.prev != head && s > abs(t.value - node[t.prev].value))
    {
        s = abs(t.value - node[t.prev].value);
        idx = node[t.prev].pos;
    }
    if (t.next != tail && s > abs(t.value - node[t.next].value))
    {
        s = abs(t.value - node[t.next].value);
        idx = node[t.next].pos;
    }
    res[i] = {s, idx};
    remove(pos[i]);
}

动态中位数

题目描述

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

输入格式

第一行输入一个整数

，代表后面数据集的个数，接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数

，代表数据集中包含数据的个数，

一定为奇数，数据之间用空格隔开。

数据集的剩余行由数据集的数据构成，每行包含

个数据，最后一行数据量可能少于

个，数据之间用空格隔开。

输出格式

对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。

数据集的剩余行由输出的中位数构成，每行包含

个数据，最后一行数据量可能少于

个，数据之间用空格隔开。

输出中不应该存在空行。

数据范围

1≤P≤1000

1≤M≤99999

, 所有

相加之和不超过

5×10^5

。

输入样例：

3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

输出样例：

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

解析

对顶堆的做法在之前排序章节讲过了，说一下链表做法

同上一题一样是离线做法，同时维护数组内元素的值和原始下标，然后将数组按元素值从小到大排序

然后按照当前顺排顺序建立双向链表，显然对于

个数来说，中位数位于

\lfloor\dfrac{n + 1}{2}\rfloor

的位置

将指针移动到该位置，便是第

轮的中位数答案，记录下该答案并保留指针位置，接着要分类讨论回滚到前一轮

要删掉的数字就是中位数
1. 当前是奇数轮：则中位数左右两侧元素数量相同，回滚直接往前移动一位即可
2. 当前是偶数轮：则中位数位于左侧元素最后一位，回滚直接往后移动一位即可
要删掉的数字不是中位数
1. 当前是奇数轮：
  1. 要删的数字位于中位数右侧：回滚直接往前移动一位即可
  2. 要删的数字位于中位数左侧：回滚不需要移动中位数指针
2. 当前是偶数轮：
  1. 要删的数字位于中位数右侧：回滚不需要移动中位数指针
  2. 要删的数字位于中位数左侧：回滚直接往后移动一位即可

最终输出所有答案即可，~~离线回滚真好玩（bushi）~~

sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ )
    pos[a[i].y] = insert(node[tail].prev, a[i].x, a[i].y);
node[head].value = -INF, node[tail].value = INF;
int midx = head;
for (int i = 1; i <= n + 1 >> 1; i ++ ) midx = node[midx].next;
for (int i = n; i; i -- )
{
    res[i] = node[midx].value;
    Node &t = node[pos[i]];
    if (t.pos == node[midx].pos) //删掉的是中位数
    {
        if (i & 1) midx = node[midx].prev;
        else midx = node[midx].next;
    }
    else
    {
        if (i & 1 && pos[i] > midx) midx = node[midx].prev;
        else if (i & 1 ^ 1 && pos[i] < midx) midx = node[midx].next;
    }
    remove(pos[i]);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-04，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

编程算法

登录后参与评论

0 条评论

热度