C++算法之旅、05 基础篇 | 第二章 数据结构

常用代码模板2——数据结构 - AcWing
笔试用数组模拟而不是结构体

使用结构体指针，new Node() 非常慢，创建10万个节点就超时了，做笔试题不会用这种方式（优化是提前初始化好数组，但这样跟数组模拟没区别了，而且代码量很长）

单链表（数组）

使用两个数组，e存储val，ne存储next。空节点next用-1表示
826 ⭐

826. 单链表 - AcWing题库
第1个插入的点下标为0，第5个插入点下标为4，第k个插入点下标为k-1；

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
5. using namespace std;
7. const int N = 1e5 + 10;
9. // head指向头结点，e[i]表示节点值，ne[i]表示节点next
10. // idx指向可用空间（当前可以用的最新点下标）
11. // 算法题不用考虑浪费的空间
12. int head, e[N], ne[N], idx;
14. void init() {
15.     head = -1;
16.     idx = 0;
17. }
19. // x 插到头结点后面
20. void add_to_head(int x) {
21.     e[idx] = x;
22.     ne[idx] = head;
23.     head = idx++;
24. }
26. // x 插到下标k的点后面
27. void add(int k, int x) {
28.     e[idx] = x;
29.     ne[idx] = ne[k];
30.     ne[k] = idx++;
31. }
33. // 将下标 k 后面点删掉
34. void remove(int k) {
35.     // if (ne[k] == -1) return; 题目保证合法不考虑边界情况
36.     ne[k] = ne[ne[k]];
37. }
39. int main() {
40.     int m;
41.     cin >> m;
42.     init();
43.     while (m--) {
44.         char c;
45.         int k, x;
46.         cin >> c;
47.         if (c == 'H') {
48.             cin >> x;
49.             add_to_head(x);
50.         } else if (c == 'D') {
51.             cin >> k;
52.             if (!k)
53.                 head = ne[head];  // 特判删除头结点(链表第一个有效元素)
54.             else
55.                 remove(k - 1);
56.         } else if (c == 'I') {
57.             cin >> k >> x;
58.             add(k - 1, x);
59.         }
60.     }
61.     for (int i = head; i != -1; i = ne[i]) {
62.         cout << e[i] << " ";
63.     }
65.     return 0;
66. }

复制代码

837 ⭐⭐

837. 连通块中点的数量 - AcWing题库
保证根节点的nums有意义

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
5. using namespace std;
7. const int N = 1e5 + 10;
9. int e[N], l[N], r[N], idx;
11. void init() {
12.     r[0] = 1;
13.     l[1] = 0;
14.     idx = 2;
15. }
17. // 在下标k点的右边插入x（可以转化成左边）
18. void add(int k, int x) {
19.     e[idx] = x;
20.     r[idx] = r[k];
21.     l[idx] = k;
22.     r[k] = idx;
23.     l[r[idx]] = idx;
24.     idx++;
25. }
27. // 删除下标k的点
28. void remove(int k) {
29.     l[r[k]] = l[k];
30.     r[l[k]] = r[k];
31. }
33. int main() {
34.     int m;
35.     cin >> m;
36.     init();
37.     while (m--) {
38.         string s;
39.         int k, x;
40.         cin >> s;
41.         if (s == "L") {
42.             cin >> x;
43.             add(0, x);
44.         } else if (s == "R") {
45.             cin >> x;
46.             add(l[1], x);
47.         } else if (s == "D") {
48.             cin >> k;
49.             remove(k - 1 + 2);
50.         } else if (s == "IL") {
51.             cin >> k >> x;
52.             add(l[k - 1 + 2], x);
53.         } else if (s == "IR") {
54.             cin >> k >> x;
55.             add(k - 1 + 2, x);
56.         }
57.     }
58.     for (int i = r[0]; i != 1; i = r[i]) {
59.         cout << e[i] << " ";
60.     }
61.     return 0;
62. }

复制代码

哈希表

情景

• 把 1e5 个值域 -1e9~1e9 的数（值域大，个数少）映射到 1e5 的范围的哈希函数
  
• \(h(x) \in (0,1e5) = x\ mod\ 1e5\)  模数一般要取质数，离2的整数幂尽可能远
  
• 发生冲突：两个不同值域的数映射成了同一个数
  

存储结构-解决冲突的方式 ⭐
算法题99%一般只有添加、查找，若要实现删除不会真删掉，开一个bool数组标记删除

• 开放寻址法（常用）
  
  
  
  • 开一个一维数组，范围是题目数据范围的2~3倍，即 2e5 ~ 3e5 区间的质数，该数组存储实际的 x 值
    
  • 计算哈希值，如果哈希值已被占用，则移动到下一个位置，从前往后找
    
  • h(11) = 3 在 数组[3] 存入 11，h(4) = 3 在数组[4] 存入 4
    
  • 与拉链法不同，查询函数返回 x 所在的位置，如果 x 不存在返回应该存储的位置
    
  • 需要约定一个标志，不在 x 的值域范围内，表示当前位置为空，如 0x3f3f3f3f
    
  
  
• 拉链法
  
  
  
  • 开一个一维数组 \([0,大于1e5的最小质数]\) 存储所有哈希值对应的链表
    
  • h(11) = 3 在 数组[3] 开一条链，插入 11
    
  • 若 h(4) = 3 在 数组[3] 已开的链插入 4
    
  • 期望情况下，每条链长度 1，时间复杂度 \(O(1)\)
    
  
  

字符串哈希-字符串前缀哈希法（特殊）
应用：可以快速判断一个字符串某两段是否相同。KMP望而却步（KMP擅长循环节），极困难题可用这种方法

• 先预处理所有前缀的哈希，h[0] = 0, h[1] = "A" 的hash，h[2] = "AB" 的hash...
  
  
  
  • 把字符串看成 P 进制的数，然后模 Q
    
  
  
• **某个字符不能映射成 0，否则 AA 跟 A 两个哈希都是 0 **
  
• 该哈希法假定人品足够好，不考虑冲突
  
• 经验值：当 p = 131 或 13331，Q 取 \(2^{64}\) (用 unsinged long long可以不取模，溢出相当于取模)
  

⭐ 我们可以利用前缀哈希算出任意子段的哈希值

• 预处理前缀 h(i) = h(i-1) * p + str
  

与整数离散化的区别
整数离散化需要保序，而且不会发生冲突，每一个元素都有唯一确定的位置（1 ~ n）
840 ⭐拉链法

840. 模拟散列表 - AcWing题库
h 数组维护 N 条链，空节点表示-1，e 数组与 ne 数组维护链上的每一个节点，idx为每个节点分配唯一标识符；插入操作从链表头结点插入

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
5. using namespace std;
7. const int N = 1e5 + 10;
9. int stk[N], tt;
11. int main() {
12.     int m;
13.     cin >> m;
14.     while (m--) {
15.         string s;
16.         int x;
17.         cin >> s;
18.         if (s == "push") {
19.             cin >> x;
20.             stk[++tt] = x;
21.         } else if (s == "pop") {
22.             tt--;
23.         } else if (s == "empty") {
24.             if (tt > 0)
25.                 puts("NO");
26.             else
27.                 puts("YES");
28.         } else if (s == "query") {
29.             cout << stk[tt] << endl;
30.         }
31.     }
32.     return 0;
33. }

复制代码

840 ⭐开放寻址法

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
4. #include <unordered_map>
6. using namespace std;
8. const int N = 1e5 + 10;
10. int op[N], num[N], opt = -1, numt = -1;
12. unordered_map<char, int> priority;
14. // 计算后缀表达式
15. void eval() {
16.     auto b = num[numt--];
17.     auto a = num[numt--];
18.     auto c = op[opt--];
19.     int res;
20.     if (c == '-')
21.         res = a - b;
22.     else if (c == '+')
23.         res = a + b;
24.     else if (c == '*')
25.         res = a * b;
26.     else if (c == '/')
27.         res = a / b;
28.     num[++numt] = res;
29. }
31. int main() {
32.     priority = {{'-', 1}, {'+', 1}, {'*', 2}, {'/', 2}};
33.     string str;
34.     cin >> str;
35.     for (int i = 0; i < str.size(); i++) {
36.         if (isdigit(str[i])) {
37.             int j = i, res = 0;
38.             while (isdigit(str[j])) res = res * 10 + str[j++] - '0';
39.             num[++numt] = res;
40.             i = j - 1;
41.         } else if (str[i] == '(')
42.             op[++opt] = str[i];
43.         else if (str[i] == ')') {
44.             while (op[opt] != '(') eval();
45.             opt--;
46.         } else {
47.             while (opt >= 0 && priority[str[i]] <= priority[op[opt]]) eval();
48.             op[++opt] = str[i];
49.         }
50.     }
51.     while (opt >= 0) eval();
52.     cout << num[numt];
53.     return 0;
54. }

复制代码

841 ⭐⭐ 字符串哈希

841. 字符串哈希 - AcWing题库
如下的朴素算法会超时

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
4. #include <stack>
5. #include <unordered_map>
7. using namespace std;
9. stack<int> num;
10. stack<char> op;
12. void eval() {
13.     auto b = num.top();
14.     num.pop();
15.     auto a = num.top();
16.     num.pop();
17.     auto c = op.top();
18.     op.pop();
19.     int x;
20.     if (c == '+')
21.         x = a + b;
22.     else if (c == '-')
23.         x = a - b;
24.     else if (c == '*')
25.         x = a * b;
26.     else
27.         x = a / b;
28.     num.push(x);
29. }
31. int main() {
32.     unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
33.     string str;
34.     cin >> str;
35.     for (int i = 0; i < str.size(); i++) {
36.         auto c = str[i];
37.         if (isdigit(c)) {
38.             // 第一类双指针
39.             int x = 0, j = i;
40.             while (j < str.size() && isdigit(str[j]))
41.                 x = x * 10 + str[j++] - '0';
42.             i = j - 1;  // 考虑i++
43.             num.push(x);
44.         } else if (c == '(')
45.             op.push(c);
46.         else if (c == ')') {
47.             while (op.top() != '(') eval();
48.             op.pop();
49.         } else {
50.             while (op.size() && pr[op.top()] >= pr[c]) eval();
51.             op.push(c);
52.         }
53.     }
54.     while (op.size()) eval();
55.     cout << num.top() << endl;
57.     return 0;
58. }

复制代码

p 数组提前存储预处理的 p 次方的值，减少计算量

1. #include <algorithm>
2. #include <cstdio>
3. #include <iostream>
5. using namespace std;
7. const int N = 1e5 + 10;
9. int que[N], st = -1, ed = -1;
11. int main() {
12.     int m;
13.     cin >> m;
14.     while (m--) {
15.         string str;
16.         int x;
17.         cin >> str;
18.         if (str == "push") {
19.             cin >> x;
20.             que[++ed] = x;
21.         } else if (str == "pop") {
22.             st++;
23.         } else if (str == "empty") {
24.             if (st == ed)
25.                 puts("YES");
26.             else
27.                 puts("NO");
28.         } else if (str == "query") {
29.             cout << que[st + 1] << endl;
30.         }
31.     }
33.     return 0;
34. }

复制代码

STL

size()、empty() 所有容器都有，时间复杂度 \(O(1)\)
clear() 并不是所有容器都有，队列、优先队列、栈；范围遍历可以遍历所有容器
⭐ 系统为某一个程序分配空间时，所需的时间与空间大小无关，与申请次数有关

vector

变长数组，倍增，支持比较运算（字典序（4个3小于3个4））。有erase但用得不多
插入操作\(O(1)\)：插入1e6次，申请空间的次数 \(log_21e6\) ，拷贝的次数均摊是 1 （数组大小从1到1e6，总共拷贝次数是1e6（1+2+4+8+...））
[code]#include #include using namespace std;int main() {    // ^ 定义一个长度为10的vector，每个数都是3    vector a(10, 3);    vector b[10];    a.push_back(1);    cout