1仿耽，鏈表
鏈表可以使用結(jié)構(gòu)體+指針的方式實(shí)現(xiàn)眯搭，但是這種方式的效率很低
鏈表中最常用的是鄰接表（n個(gè)鏈表）窥翩，鄰接表的作用主要是存儲(chǔ)樹和圖
所以這里分別介紹了使用數(shù)組來(lái)實(shí)現(xiàn)單鏈表和雙鏈表的方法
單鏈表
const int N = 1e5 + 10;
//head表示頭節(jié)點(diǎn)的下標(biāo)
//e[i]表示節(jié)點(diǎn)i的值
//ne[i]表示節(jié)點(diǎn)i的next指針是多少
//idx表示當(dāng)前已經(jīng)用到了哪個(gè)點(diǎn)
int e[N], ne[N], head, idx;
//初始化
void init() {
head = -1;
idx = 0;
}
//將x插到頭節(jié)點(diǎn)后面
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//將x插到下標(biāo)為k的節(jié)點(diǎn)后面
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//將下標(biāo)為k的節(jié)點(diǎn)后面的節(jié)點(diǎn)刪除
void remove(int k) {
ne[k] = ne[ne[k]];
}
雙鏈表
const int N = 1e5 + 10;
//e[i]表示下標(biāo)為i的值
//l[i]表示下標(biāo)為i的左指針
//r[i]表示下標(biāo)為i的右指針
//idx表示當(dāng)前可用的下標(biāo)
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;
}
//在下標(biāo)為a的節(jié)點(diǎn)右邊插入x
void insert(int a, int x) {
//先設(shè)置idx的值，左右指針
e[idx] = x;
r[idx] = r[a];
l[idx] = l[r[a]];
//然后將a后面的節(jié)點(diǎn)的左指針指向idx
l[r[a]] = idx;
//將a的右指針指向idx
r[a] = idx;
idx++;
}
//刪除下標(biāo)為a的節(jié)點(diǎn)
void remove(int a) {
l[r[a]] = l[a];
r[l[a]] = r[a];
}
2繁扎，棧和隊(duì)列
因?yàn)閭€(gè)人比較喜歡用c++里面的STL庫(kù)幔荒，所以不怎么用到數(shù)組模擬棧和隊(duì)列，所以只介紹一下STL里面的棧梳玫、隊(duì)列爹梁、優(yōu)先隊(duì)列、雙端隊(duì)列
stack
棧提澎，特點(diǎn)是：“先進(jìn)后出”
頭文件：#include< stack >
stack<Type> stk;//定義棧姚垃，Type為數(shù)據(jù)類型
stk.size();//返回棧中的元素個(gè)數(shù)
stk.empty();//判斷棧是否為空
stk.push(x);//向棧頂插入一個(gè)元素x
stk.top();//返回棧頂元素
stk.pop(); //彈出棧頂元素
queue
隊(duì)列，特點(diǎn)是：“先進(jìn)先出”
queue<T> q;//定義隊(duì)列盼忌，Type為數(shù)據(jù)類型
q.push(x);//把x放進(jìn)隊(duì)列
q.front();//返回隊(duì)首元素积糯，但不會(huì)刪除
q.pop();//刪除隊(duì)首元素
q.back();//返回隊(duì)尾元素掂墓，但不會(huì)刪除
q.size();//返回隊(duì)列中的元素個(gè)數(shù)
q.empty();//判斷隊(duì)列是否為空
priority_queue
優(yōu)先隊(duì)列，是數(shù)據(jù)結(jié)構(gòu)中的堆看成，默認(rèn)大根堆君编，按照從小到大排列
priority_queue<int> q;//定義優(yōu)先隊(duì)列，Type為數(shù)據(jù)類型
q.empty();//判斷優(yōu)先隊(duì)列是否為空
q.pop();//刪除第一個(gè)元素
q.push(x);//添加一個(gè)元素x
q.size();//返回優(yōu)先隊(duì)列中的元素個(gè)數(shù)
q.top();//返回優(yōu)先隊(duì)列中有最高優(yōu)先級(jí)的元素
如果想變成小根堆
1. 插入的時(shí)候直接插入-x
2. 定義直接定義成小根堆
priority_queue<Type,vector<Type>,greater<Type>> q;//定義小根堆川慌，Type為數(shù)據(jù)類型
deque
雙端隊(duì)列吃嘿，是一種隨機(jī)訪問(wèn)的數(shù)據(jù)類型，提供了在序列兩端快速插入和刪除的功能梦重，deque類似于vector
deque<Type> q;////定義雙端隊(duì)列兑燥，Type為數(shù)據(jù)類型
q.push_back(x);//在隊(duì)尾添加元素x
q.push_front(x);//在隊(duì)頭添加元素x
q.pop_back();//刪除隊(duì)尾元素
q.pop_front();//刪除隊(duì)頭元素
q.front();//獲得隊(duì)頭元素
q.back();//獲得隊(duì)尾元素
q.size();//返回隊(duì)列中的元素個(gè)數(shù)
q.empty();//判斷隊(duì)列是否為空
3，單調(diào)棧
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的數(shù)
if (stk.size()) cout << stk.top() << " ";
//否則蚓胸，不存在
else cout << -1 << " ";
stk.push(x);
}
4挣饥，單調(diào)隊(duì)列
int n, k;
//單調(diào)隊(duì)列，隊(duì)頭為答案
deque<int> q;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
//輸出滑動(dòng)窗口中的最小值
for (int i = 0; i < n; i++) {
//如果隊(duì)列不為空赢织，并且窗口長(zhǎng)度大于k亮靴，說(shuō)明隊(duì)頭元素滑出窗口
if (q.size() && i - q.front() + 1 > k) q.pop_front();
//如果隊(duì)列不為空，并且隊(duì)尾大于等于a[i]于置，彈出隊(duì)尾
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();
//輸出滑動(dòng)窗口中的最大值
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數(shù)組八毯，相當(dāng)于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的長(zhǎng)度
if (j == n) {
//輸出起始位置
cout << i - n << " ";
//繼續(xù)匹配下一個(gè)
j = ne[j];
}
}
6乳讥，并查集
//返回x的祖先節(jié)點(diǎn) + 路徑壓縮
int find(int x) {
//祖先節(jié)點(diǎn)的父節(jié)點(diǎn)是自己本身
//將x的父親置為x父親的祖先節(jié)點(diǎn),實(shí)現(xiàn)路徑的壓縮
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
cin >> n >> m;
//初始化，將當(dāng)前數(shù)據(jù)的父節(jié)點(diǎn)指向自己
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所在集合合并云石，即將一方設(shè)為另一方的父節(jié)點(diǎn)
//p[find(a)] = find(b)或者p[find(b)] = find(a);
//把a(bǔ)祖先節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為b的祖先節(jié)點(diǎn)
p[find(a)] = find(b);
}
else {
//如果a，b的祖先節(jié)點(diǎn)一樣研乒，說(shuō)明在一個(gè)集合
if (find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
