一、链表的理论部分

https://zhuanlan.zhihu.com/p/29627391

单链表

image.png

单链表删除结点

image.png

单链表添加结点

image.png

双向链表

image.png

双向链表删除结点

image.png

双向链表添加结点

image.png

循环链表

https://zhuanlan.zhihu.com/p/360567636
一个结点
image.png

循环链表头插法

image.png

循环链表在指定位置插入结点

image.png

循环链表删除结点

image.png

二、链表的技术部分

单链表 邻接表

https://www.acwing.com/problem/content/828/
image.png
image.png

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. int m;
  8. int hh, e[N], ne[N], idx;
  10. void add_to_head(int x){
  11.     e[idx] = x, ne[idx] = hh, hh = idx++;
  12. }
  14. void add_to_node(int k, int x){
  15.     e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
  16. }
  18. void remove(int k){
  19.     ne[k] = ne[ne[k]];
  20. }
  22. int main(){
  23.     hh = -1;
  25.     cin >> m;
  26.     while (m--){
  27.         string op;
  28.         cin >> op;
  30.         if (op[0] == 'H'){
  31.             int x;
  32.             cin >> x;
  33.             add_to_head(x);
  34.         }
  35.         else if (op[0] == 'D'){
  36.             int k;
  37.             cin >> k;
  39.             if (k == 0) hh = ne[hh];  //如何删除的是头结点
  40.             else remove(k - 1);
  41.         }
  42.         else{
  43.             int k, x;
  44.             cin >> k >> x;
  45.             add_to_node(k - 1, x);
  46.         }
  47.     }
  49.     for (int i = hh; i != -1; i = ne[i]) printf("%d ", e[i]);
  50.     puts("");
  52.     return 0;
  53. }

image.png

头插法演示
8202b6c10561485792a9dd9a9f975e2a.gif

单链表 结构体 TLE

  1. // new Node(); 非常慢，链表大小1e4 1e5就会超时
  2. // 这部分代码，希望大家能看懂C语言的指针，不推荐这种写法
  4. #include <bits/stdc++.h>
  5. #include <stddef.h>  
  6. // How to fix C error ‘NULL undeclared’
  7. // https://techoverflow.net/2019/06/20/how-to-fix-c-error-null-undeclared/
  9. using namespace std;
  11. const int N = 1e5 + 10;
  13. struct Node{
  14.     int data, id;
  15.     Node *next;
  16. };
  18. int m, idx;
  19. Node *head;
  21. void add_to_head(int x){
  22.     Node *t = new Node();
  23.     t->data = x;
  24.     t->next = head;
  25.     t->id = idx++;
  27.     head = t;
  28. }
  30. void add_to_node(int k, int x){
  31.     Node *t = head;
  32.     while (t->next != NULL){
  33.         if (t->id == k) break;
  34.         t = t->next;
  35.     }
  37.     Node *nw = new Node();
  38.     nw->data = x;
  39.     nw->id = idx++;
  40.     nw->next = t->next;
  42.     t->next = nw;
  43. }
  45. void remove(int k){
  46.     Node *t = head;
  47.     while (t->next != NULL){
  48.         if (t->id == k) break;
  49.         t = t->next;
  50.     }
  52.     Node *p = t->next;
  53.     t->next = p->next;
  54.     delete p;
  55. }
  57. int main(){
  58.     head = new Node;
  59.     head->next = NULL;
  61.     cin >> m;
  62.     while (m--){
  63.         string op;
  64.         cin >> op;
  66.         if (op[0] == 'H'){
  67.             int x;
  68.             cin >> x;
  69.             add_to_head(x);
  70.         }
  71.         else if (op[0] == 'D'){
  72.             int k;
  73.             cin >> k;
  75.             if (k == 0) head = head->next;  //如何删除的是头结点
  76.             else remove(k - 1);
  77.         }
  78.         else{
  79.             int k, x;
  80.             cin >> k >> x;
  81.             add_to_node(k - 1, x);
  82.         }
  83.     }
  85.     while (head->next != NULL){
  86.         printf("%d ", head->data);
  87.         head = head->next;
  88.     }
  89.     puts("");
  91.     return 0;
  92. }

双链表 邻接表

https://www.acwing.com/problem/content/829/
image.png
image.png

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. int m;
  8. int e[N], L[N], R[N], idx;
  10. // k -> idx -> R[k]
  11. void insert(int k, int x){
  12.     e[idx] = x;
  13.     R[idx] = R[k];   // 先把idx挂好
  14.     L[idx] = k;
  15.     L[R[k]] = idx;   // 然后弄原来的结点
  16.     R[k] = idx++;
  17. }
  19. void remove(int k){
  20.     L[R[k]] = L[k];
  21.     R[L[k]] = R[k];
  22. }
  24. int main(){
  25.     // r[0] 指向第一个点，0 1两个点作为两端，r[0] = 1, l[1] = 0 模拟成环
  26.     // 用0, 1表示左端点、右端点，第一个数从idx = 2开始
  27.     R[0] = 1, L[1] = 0, idx = 2;
  29.     cin >> m;
  30.     while (m--){
  31.         string op;
  32.         cin >> op;
  34.         if (op == "L"){
  35.             int x;
  36.             cin >> x;
  37.             insert(0, x);
  38.         }
  39.         if (op == "R"){
  40.             int x;
  41.             cin >> x;
  42.             insert(L[1], x);
  43.         }
  44.         if (op == "D"){
  45.             int k;
  46.             cin >> k;
  47.             remove(k+1);
  48.         }
  49.         if (op == "IL"){
  50.             int k, x;
  51.             cin >> k >> x;
  52.             insert(L[k+1], x);  // 2-index
  53.         }
  54.         if (op == "IR"){
  55.             int k, x;
  56.             cin >> k >> x;
  57.             insert(k+1, x);
  58.         }
  59.     }
  61.     for (int i = R[0]; i != 1; i = R[i]) printf("%d ", e[i]);
  62.     puts("");
  64.     return 0;
  65. }

循环链表 结构体

  1. // 约瑟夫环问题
  2. // 1~n个人，从第1个人开始报数，数到m的人出列
  3. // 如此循环，直到最后一个人出列为止
  4. // 输出出列的顺序
  6. #include <bits/stdc++.h>
  8. using namespace std;
  10. struct node{
  11.     int id;
  12.     node *next;
  13. };
  15. node *head, *r;
  16. int n, m;
  18. int main(){
  19.     cin >> n >> m;
  20.     head = new node();
  21.     head->id = 1;
  22.     head->next = NULL;
  24.     r = head;
  26.     for (int i = 2; i <= n; i++){
  27.         node *p = new node();
  28.         p->id = i;
  29.         p->next = NULL;
  31.         r->next = p;
  32.         r = p;
  33.     }
  35.     r->next = head;
  36.     r = head;
  38.     for (int i = 1; i <= n; i++){
  39.         for (int j = 1; j <= m - 2; j++) r = r->next;   //r走到了m-1的位置上
  40.         cout << r->next->id << ' ';                     //m-1的下一个是m
  42.         r->next = r->next->next;                        //删除结点
  43.         r = r->next;                                    //挪到下一个从1开始数
  44.     }
  45.     puts("");
  47.     return 0;
  48. }

三、栈

学习顺序：

  1. 学会使用STL的基本用法
  2. 学会使用STL解决问题
  3. 学会用一维数组模拟栈，解决问题

栈是只能在某一端插入和删除的特殊线性表

stack stk

  1. stack<int> s;
  2. s.push(3);
  3. s.push(2);
  4. s.push(5);
  5. cout << s.top(); // 5
  7. s.pop();
  8. cout << s.top(); // 2

一维数组模拟栈

https://www.acwing.com/problem/content/830/
image.png
image.png

  1. // tt指针初始化为0，第一个数存在1上，当tt==0的时候，代表空栈
  3. #include <iostream>
  5. using namespace std;
  7. const int N = 1e5 + 10;
  9. int stk[N];
  10. int tt = 0;
  12. int main()
  13. {
  14.     int M;
  15.     cin >> M;
  17.     string op;
  18.     int x;
  19.     while (M--)
  20.     {
  21.         cin >> op;
  23.         if (op == "push")
  24.         {
  25.             cin >> x;
  26.             stk[++tt] = x;
  27.         }
  28.         if (op == "pop")
  29.         {
  30.             tt--;
  31.         }
  32.         if (op == "empty")
  33.         {
  34.             if (tt == 0) cout << "YES" << endl;
  35.             else cout << "NO" << endl;
  36.         }
  37.         if (op == "query")
  38.         {
  39.             cout << stk[tt] << endl;
  40.         }
  41.     }
  43.     return 0;
  44. }

例题，【例1-2】后缀表达式的值

  1. //用一个栈维护数字，用一个栈维护运算符
  2. //这道题目没有括号，另外注意运算数的数值范围比较大
  3. //不开LL见祖宗

例题，表达式括号匹配(stack)

  1. //用一个栈维护左括号和右括号的关系
  2. //右括号，没有左括号配对就是非法
  3. //左括号，最后没有右括号配对就是非法

例题，车厢调度(train)

  1. //第一种方法，把一系列车厢，当成一个数组，1, 2, 3, 4, ..., n
  2. //x读进来了，那么，我们就要认为：x之后的数字，都不应该出现在栈中；x之前的数字没入栈的都应该入栈
  3. //标记在不在栈里的方法，1代表在栈里面，2代表已经出栈
  5. //第二种方法，用一个stack硬来模拟这个进出栈的过程(冷不丁让我重写，我想我是模拟不出来的)
  6. //如果stack空的，把前面没入栈的入栈
  7. //如果stack非空，栈顶元素如果比我大，那是非法的；
  8. //整个过程中，用一个变量tp，初始值设为1，来维护栈顶元素的值

例题，中缀表达式值(expr)

  1. //在这道题目上，我一共花费了4个小时
  2. //所以，我建议你自己做，研究至少花费2个小时。
  3. //可以很好的提升代码能力，加深对栈的理解，对表达式的理解
  5. //第一种方法，直接利用中缀表达式，进行求解，这个方法和前面的题目类似
  7. //第二种方法，中缀读进来，然后转成后缀
  8. //后缀的建立，用一个queue<node>进行维护，node可以是运算数，也可以是运算符
  9. //node需要使用struct定义一下
  11. //关于非法情况的判断
  12. //首先这道题目的数据，没有那么严格，不需要判断除数不能为0的情况
  13. //其他非法，左右括号不匹配问题；只有一位，这一位还是运算符; 上来第一位是+*/运算符，负号是可以的
  14. //中缀表达式，两个运算符连在一块了；右括号没有左括号匹配，左括号没有右括号匹配
  16. //网上能搜到题解，对左括号个数和右括号个数相同作为配对的原则，这个其实不严谨
  17. //运算符优先级，可以写一个函数实现，也可以写一个map预设好

例题，P1981 [NOIP2013 普及组] 表达式求值

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <stack>
  5. #include <unordered_map>
  7. using namespace std;
  9. const int MOD = 10000;
  11. stack<int> num;
  12. stack<char> op;
  14. void eval()
  15. {
  16.     int b = num.top(); num.pop();
  17.     int a = num.top(); num.pop();
  18.     char c = op.top(); op.pop();
  20.     if (c == '+') num.push((a + b) % MOD);
  21.     else num.push(a * b % MOD);
  22. }
  24. int main()
  25. {
  26.     string s;
  27.     cin >> s;
  29.     unordered_map<char, int> pr{{'+', 1}, {'*', 2}};
  31.     for (int i = 0; i < s.size(); i ++ )
  32.     {
  33.         if (isdigit(s[i]))
  34.         {
  35.             int j = i, x = 0;
  36.             while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
  37.             num.push(x % MOD);
  38.             i = j - 1;
  39.         }
  40.         else
  41.         {
  42.             while (op.size() && pr[op.top()] >= pr[s[i]]) eval();
  43.             op.push(s[i]);
  44.         }
  45.     }
  47.     while (op.size()) eval();
  48.     cout << num.top() << endl;
  50.     return 0;
  51. }
  53. // 以后的习题中，会涉及一个表示式树的题目

四、队列

学习顺序：

  1. 学会使用STL的基本用法
  2. 学会使用STL解决问题
  3. 学会用一维数组模拟队列，解决问题

队列是限定在一端进行插入，另一端进行删除的特殊线性表

queue q

  1. queue<int> q;
  2. q.push(3);
  3. q.push(2);
  4. q.push(5);
  5. cout << q.front(); // 3
  6. q.pop();
  7. cout << q.front(); // 2

例题，2037：【例5.4】约瑟夫问题

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int main()
  6. {
  7.     int n, m;
  8.     cin >> n >> m;
  10.     queue<int> q;
  11.     for (int i = 1; i <= n; i++) q.push(i);
  13.     int k = 0;
  14.     while (!q.empty()){
  15.         k++;
  17.         int t = q.front(); q.pop();
  19.         if (k == m){
  20.             k = 0;
  21.             printf("%d ", t);
  22.             continue;
  23.         }
  25.         q.push(t);
  26.     }
  27.     puts("");
  29.     return 0;
  30. }

一维数组模拟队列

https://www.acwing.com/problem/content/831/
image.png
image.png

  1. // 初始化，int hh = 0, tt = -1;     //Think about it: 莫队不也是这样吗？
  3. #include <iostream>
  5. using namespace std;
  7. const int N = 100010;
  9. int q[N];
  10. int hh = 0, tt = -1;
  12. int main()
  13. {
  14.     int M;
  15.     cin >> M;
  17.     string op;
  18.     int x;
  19.     while (M--)
  20.     {
  21.         cin >> op;
  23.         if (op == "push")
  24.         {
  25.             cin >> x;
  26.             q[++tt] = x; 
  27.         }
  28.         if (op == "pop")
  29.         {
  30.             hh++;            
  31.         }
  32.         if (op == "query")
  33.         {
  34.             cout << q[hh] << endl;
  35.         }
  36.         if (op == "empty")
  37.         {
  38.             if (hh <= tt) cout << "NO" << endl;
  39.             else cout << "YES" << endl;
  40.         }
  41.     }
  43.     return 0;
  44. }

例题，【例2-3】围圈报数

  1. //用queue模拟出圈的过程

例题，猴子选大王

  1. //一般的猴子选大王，约瑟夫环问题，都是玩一个游戏，数一个固定的数m，数到就出圈
  2. //这道题目是，从i个猴子开始数，就使用第i个规则数
  3. //所以，这点在模拟的时候会不同。其他和普通的约瑟夫一样

例题，【例2-1】周末舞会

  1. //模拟两个队伍循环的过程，用两个指针模拟

例题，产生数(Produce)

  1. //这道题目的规则是一位数字，转换成一位数字
  2. //不是多位的转换，没那么复杂，可以直接暴力的干
  3. //遇到坑，还是要多变换姿势求解
  5. //最开始，我自己分析题意是，转换规则，可能是 ab -> cdd，这种变态的模式
  6. //然后我就写了1个小时而已，写不出来了。主要是控制不好字符串替换中间一段的操作，存在开头和去尾的特殊位置
  7. //感觉，这样出测试用例，肯定是一道好模拟题

大纲要求

•【3】链表：单链表、双向链表、循环链表

•【3】栈

•【3】队列