1，链表
链表可以使用结构体+指针的方式实现，但是这种方式的效率很低
链表中最常用的是邻接表（n个链表），邻接表的作用主要是存储树和图
所以这里分别介绍了使用数组来实现单链表和双链表的方法
单链表
const int N = 1e5 + 10;
//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx表示当前已经用到了哪个点
int e[N], ne[N], head, idx;
//初始化
void init() {
head = -1;
idx = 0;
}
//将x插到头节点后面
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//将x插到下标为k的节点后面
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//将下标为k的节点后面的节点删除
void remove(int k) {
ne[k] = ne[ne[k]];
}
双链表
const int N = 1e5 + 10;
//e[i]表示下标为i的值
//l[i]表示下标为i的左指针
//r[i]表示下标为i的右指针
//idx表示当前可用的下标
int e[N], l[N], r[N], idx;
//初始化
void init() {
//0和1分别表示头和尾，0的右边是1，1的左边是0，idx从2开始
r[0] = 1;
l[1] = 0;
idx = 2;
}
//在下标为a的节点右边插入x
void insert(int a, int x) {
//先设置idx的值，左右指针
e[idx] = x;
r[idx] = r[a];
l[idx] = l[r[a]];
//然后将a后面的节点的左指针指向idx
l[r[a]] = idx;
//将a的右指针指向idx
r[a] = idx;
idx++;
}
//删除下标为a的节点
void remove(int a) {
l[r[a]] = l[a];
r[l[a]] = r[a];
}
2，栈和队列
因为个人比较喜欢用c++里面的STL库，所以不怎么用到数组模拟栈和队列，所以只介绍一下STL里面的栈、队列、优先队列、双端队列
stack
栈，特点是：“先进后出”
头文件：#include< stack >
stack<Type> stk;//定义栈，Type为数据类型
stk.size();//返回栈中的元素个数
stk.empty();//判断栈是否为空
stk.push(x);//向栈顶插入一个元素x
stk.top();//返回栈顶元素
stk.pop(); //弹出栈顶元素
queue
队列，特点是：“先进先出”
queue<T> q;//定义队列，Type为数据类型
q.push(x);//把x放进队列
q.front();//返回队首元素，但不会删除
q.pop();//删除队首元素
q.back();//返回队尾元素，但不会删除
q.size();//返回队列中的元素个数
q.empty();//判断队列是否为空
priority_queue
优先队列，是数据结构中的堆，默认大根堆，按照从小到大排列
priority_queue<int> q;//定义优先队列，Type为数据类型
q.empty();//判断优先队列是否为空
q.pop();//删除第一个元素
q.push(x);//添加一个元素x
q.size();//返回优先队列中的元素个数
q.top();//返回优先队列中有最高优先级的元素
如果想变成小根堆
1. 插入的时候直接插入-x
2. 定义直接定义成小根堆
priority_queue<Type,vector<Type>,greater<Type>> q;//定义小根堆，Type为数据类型
deque
双端队列，是一种随机访问的数据类型，提供了在序列两端快速插入和删除的功能，deque类似于vector
deque<Type> q;////定义双端队列，Type为数据类型
q.push_back(x);//在队尾添加元素x
q.push_front(x);//在队头添加元素x
q.pop_back();//删除队尾元素
q.pop_front();//删除队头元素
q.front();//获得队头元素
q.back();//获得队尾元素
q.size();//返回队列中的元素个数
q.empty();//判断队列是否为空
3，单调栈
int n;
stack<int> stk;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
//如果栈不为空，并且栈顶元素大于等于x，弹出栈顶元素
while (stk.size() && stk.top() >= x) stk.pop();
//如果栈不为空，栈顶元素即为最近的小于x的数
if (stk.size()) cout << stk.top() << " ";
//否则，不存在
else cout << -1 << " ";
stk.push(x);
}
4，单调队列
int n, k;
//单调队列，队头为答案
deque<int> q;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
//输出滑动窗口中的最小值
for (int i = 0; i < n; i++) {
//如果队列不为空，并且窗口长度大于k，说明队头元素滑出窗口
if (q.size() && i - q.front() + 1 > k) q.pop_front();
//如果队列不为空，并且队尾大于等于a[i]，弹出队尾
while (q.size() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
if (i + 1 >= k) cout << a[q.front()] << " ";
}
cout << endl;
q.clear();
//输出滑动窗口中的最大值
for (int i = 0; i < n; i++) {
if (q.size() && i - q.front() + 1 > k) q.pop_front();
while (q.size() && a[q.back()] <= a[i]) q.pop_back();
q.push_back(i);
if (i + 1 >= k) cout << a[q.front()] << " ";
}
5，KMP
int n, m;
//字符串S，模式串P
cin >> n >> p + 1 >> m >> s + 1;
//求p的next数组，相当于p与p本身做匹配
for (int i = 2, j = 0; i <= n; i++) {
//如果j不为0，并且p[i]不等于p[j + 1]，那j跳到next[j]
while (j && p[i] != p[j + 1]) j = ne[j];
//如果匹配，j++
if (p[i] == p[j + 1]) j++;
//每次记录next[i]
ne[i] = j;
}
//匹配
for (int i = 1, j = 0; i <= m; i++) {
//如果j不为0，并且s[i]和p[j + 1]不匹配，那j就跳到next[j]
while (j && s[i] != p[j + 1]) j = ne[j];
//如果匹配，j++
if (s[i] == p[j + 1]) j++;
//如果j等于p的长度
if (j == n) {
//输出起始位置
cout << i - n << " ";
//继续匹配下一个
j = ne[j];
}
}
6，并查集
//返回x的祖先节点 + 路径压缩
int find(int x) {
//祖先节点的父节点是自己本身
//将x的父亲置为x父亲的祖先节点,实现路径的压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
cin >> n >> m;
//初始化，将当前数据的父节点指向自己
for (int i = 1; i <= n; i++) p[i] = i;
while (m--) {
char op;
int a, b;
cin >> op >> a >> b;
if (op == 'M') {
//将a，b所在集合合并，即将一方设为另一方的父节点
//p[find(a)] = find(b)或者p[find(b)] = find(a);
//把a祖先节点的父节点设为b的祖先节点
p[find(a)] = find(b);
}
else {
//如果a，b的祖先节点一样，说明在一个集合
if (find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
