基础数据结构详解及 C++ 模板实现

序言

介绍链表、单链表、双链表、栈、队列、单调栈、单调队列及其模板。

链表

在图论中经常使用，建议掌握静态链表（链式前向星即数组模拟链表）。动态链表速度较慢，算法竞赛中通常使用静态实现。

单链表

单链表由 e[N] 和 ne[N] 组成，分别记录节点的值和下个节点的下标。空节点下标用 -1 表示。

构建链表

const int N = 100010;
// head 表示头节点的下标
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少，即下一个点的下标
// idx 存取当前已经用到的点
int head, e[N], ne[N], idx;

初始化操作

void init(){
    head = -1;
    idx = 0;
}

头插法操作

将新节点插入到头部，这是算法中最常用的操作。

// 将 x 插到头节点
void add_to_head(int x){
    e[idx] = x;       // 当前 idx 节点的值变成 x
    ne[idx] = head;   // idx 指向头节点
    head = idx;       // 头节点指向了新节点 idx
    idx ++;
}

插入节点普通操作

将 x 插入到下标为 k 的点后面。

// 将 x 插到下标为 k 的点后面
void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

删除操作

删除下标为 k 的点后面的点。

// 删除操作
void remove{
    ne[k] = ne[ne[k]];
}