行业知识
二、数据结构——单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表等内容。
2026-11-05 00:42:09
来源：互联网转载
�� 对于链表来说，由于new操作时间太长，因此，算法题中一般使用静态链表。
1.单链表
采用数组实现单链表，可以直接开两个数据，一个数组存放数值，另外一个数据存放下一个元素（指针）。
示例:实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；删除第 k 个插入的数后面的数；
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n个数，则按照插入的时间顺序，这 n 个数依次为：第 1个插入的数，第 2个插入的数，…第 n 个插入的数。
#include #include using namespace std; const int N = 100010;int c = 10; int value[N]; int ne[N]; int head,tal; // tal表示尾部元素在数组中的位置 void init(){ head = -1; tal = 0; fill_n(&ne[0], sizeof(ne) / sizeof(ne[0]), -1); } void insert_head(int x){ value[tal] = x; // 存放元素 ne[tal] = head; // x指向head指向的元素 head = tal++; // 新的head指向x } void insert_k(int k,int x){ // 在数组第k个位置后插入元素,注意不是链表 value[tal] = x; // 存放节点元素 ne[tal] = ne[k]; // value[k]指向x ne[k] = tal++; // x指向原value[k]下一个元素 } void remove_k(int k){ // 此处没有释放空间,算法题一般不必考虑释放空间 int tmp = ne[k]; // 保留删除前第k个元素的下一个位置 ne[k] = ne[ne[k]]; // 第k个元素指向下一个元素的下个元素 ne[tmp] = -1; // 删除元素的下一个元素位置指向-1 } int main(){ int m; cin >> m; // m次操作 int k,x; // k为位置,x为元素 char O; // 操作符 init(); // 初始化 while(m--){ cin >> O; if(O == 'H'){cin >> x; insert_head(x);} // 头差一个元素 else if(O == 'D') // 删除一个元素 { cin >> k; if(k == 0) head = ne[head]; else remove_k(k-1);} else if(O == 'I'){cin >> k >> x; insert_k(k-1,x);} // 第k个位置插入一个元素 } for(int i = head;i!=-1;i=ne[i]) printf("%d ",value[i]); return 0; } 2.双链表
双链表使用两个数组分别表示前驱和后继，并用1个数据存储值。
插入操作：头插入，需要改头指针
中间插入，需要防止断链
尾部插入需注意改尾指针。
实现一个双链表，双链表初始为空，支持 5种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
代码实现：在代码实现中，左侧插入考虑了节点为第一个节点，右侧插入考虑了最后一个节点。同时，为了在O(1)时间复杂度完成尾插，设置了表尾指针。
#include #include using namespace std;const int N = 100010;int value[N];int l[N],r[N];int head,tal,idx; // tal表示尾部元素在数组中的位置void init(){ idx = 0; fill_n(&l[0], sizeof(l) / sizeof(l[0]), -1); // 数组初始化为-1 fill_n(&r[0], sizeof(r) / sizeof(r[0]), -1); head = -1; tal = -1; } void insert_head(int x){ value[idx] = x; // 存放元素 r[idx] = head; // x指向第一个元素 if(tal == -1) tal = idx; // 当前表为空,尾指针指向x else l[head] = idx; // 表不为空,第一个元素的前驱指向x head = idx++; // 新的head指向x } void insert_tal(int x){ value[idx] = x; // 存放元素 l[idx] = tal; // x的左指针指向最后一个元素 if(head == -1) head = idx; // 表位空,头指针指向x else r[tal] = idx; // 表不为空,最后一个元素的后继指向x tal = idx++; // 新的tal指向x } void insert_Rk(int k,int x){ // 在数组第k个位置后插入元素,注意不是链表 value[idx] = x; // 存放节点元素 if(r[k] == -1) {l[idx] = tal; r[idx] = -1; r[tal] = idx;tal = idx++;} // 当前节点为最后一个节点 else{ l[idx] = k; r[idx] = r[k]; l[r[k]] = idx; r[k] = idx++; } } void insert_Lk(int k,int x){ // 在数组第k个位置前插入元素,注意不是链表 value[idx] = x; // 存放节点元素 if(l[k] == -1) {r[idx] = head; l[idx] = -1; l[head] = idx;head = idx++;} // 当前节点在第一个节点 else{ l[idx] = l[k]; r[idx] = k; r[l[k]] = idx; l[k] = idx++; } }void remove_k(int k){ // 此处没有释放空间,算法题一般不必考虑释放空间 if(head == k) head = r[k]; if(tal == k) tal = l[k]; l[r[k]] = l[k]; r[l[k]] = r[k]; }int main(){ int m; cin >> m; // m次操作 int k,x; // k为位置,x为元素 string O; // 操作符 init(); // 初始化 while(m--){ cin >> O; if(O == "L"){cin >> x; insert_head(x);} // 头差一个元素 else if(O == "R"){cin >> x; insert_tal(x); } else if(O == "D") // 删除一个元素 { cin >> k; remove_k(k-1); } else if(O == "IL"){ cin >> k >> x; insert_Lk(k-1,x); } // 第k个位置插入一个元素 else{cin >> k >> x; insert_Rk(k-1,x);} } for(int i = head;i!=-1;i=r[i]) printf("%d ",value[i]); return 0; } 3.栈
栈是先进后出的数据结构，top初始时指向0，代表指向下一个空位置，
- 入栈时，先入元素，top++，
- 出栈时，top--；再出元素。
- top==0判空，top==n-1判满
#include #include using namespace std;const int N = 100010;int sstack[N],top;void init(){ top = 0; // top 指向下一个空位置}void s_empty(){ // top指向0栈空,否则不空 if(top) printf("NO\n"); else printf("YES\n");}void push(int x){ // 入栈,元素先入栈,top++ sstack[top++] = x;}int pop(){ // 出栈:top先减减，再出栈 return sstack[--top];}int query(){ // 查询栈顶元素 int id = top-1; return sstack[id];}int main(){ int m; cin >> m; string op; int x; init(); while(m--){ cin >> op; if(op=="push") {cin >> x; push(x);} else if(op=="pop") int r = pop(); else if(op == "empty") s_empty(); else printf("%d\n",query()); }}应用：表达式求值
算法思想:
使用一个数栈，一个符号栈，从左向右扫描表达式，若：
- 符号栈为空，直接入栈
- 栈顶元素为(，直接入栈
- 当前符号优先级大于栈顶元素，直接入栈
- 否则从符号栈中弹出一个符号，并从数栈中弹出2个数字进行运算,直到满足相应入栈条件
#include #include #include #include #include using namespace std;const int N = 100010;stack op;stack number;void eval(){ // 实现运算 int b = number.top(); // 栈是后进先出,第一个先出的元素是第二个操作数,第二个出的元素是第一个操作数 number.pop(); int a = number.top(); number.pop(); char c = op.top(); // 符号 op.pop(); if(c=='+') number.push(a+b); else if(c=='-') number.push(a-b); else if(c=='*') number.push(a*b); else number.push(a/b);}int main(){ unordered_map pr = {{'+',1},{'-',1},{'*',2},{'/',2}}; string A; // 表达式 cin >> A; int n,j; for(int i=0;ipr[op.top()]) op.push(A[i]); // 当前符号优先级大于栈顶元素直接入栈 else{ while(!op.empty() && pr[A[i]]> m; string op; int x; init(); while(m--){ cin >> op; if(op=="push") {cin >> x; en_queue(x);} else if(op=="pop") printf("%d\n",de_queue()); else if(op == "empty") { if(q_empty()) printf("YES"); else printf("NO"); } else printf("%d\n",query()); }}5.单调栈
单调栈的应用场景为给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
算法分析:如果采用暴力解，则需要2重循环，时间复杂度为O(n^2)。降低时间复杂度可以采用单调栈的方式，即对于元素a[i]，若栈中元素大于a[i]，则退栈，这样，每个元素进战出栈1次，时间复杂度为O(n).
#include #include using namespace std;const int N = 100010;int s[N]; // 栈int top =0; // 栈顶指针int main(){ int n; // 整数序列长度 int x; // 当前数x scanf("%d",&n); for(int i=0;i=x) top--; // 如果栈顶元素大于当前元素,元素出栈 if(top == 0) printf("-1 "); // 出栈后栈顶为空，输出-1 else printf("%d ",s[top-1]); // 如果栈不为空,栈顶元素即为所求 s[top++] = x; } } }6.单调队列
单调队列的应用是找滑动窗口的最大值和最小值，这里的单调队列可以看做一个两头出一头进的双端队列，首先，使用队列实现滑动窗口，然后在队尾一侧使用栈构建单调队列，从而找最大值与最小值。
#include #include using namespace std;const int N= 1e6+10;int q[N],a[N]; // q为双端队列，存储数组下标,a为数组int r,f; // 队列首尾指针int main(){ int n,k; // n为整数序列长度,k为窗口大小 scanf("%d%d",&n,&k); // n为序列长度,k为滑动窗口大小 for(int i=0;i> s+1; int i,j; for(i=2,j=0;i i & 1; // 右移i位或1,即判断第i位是0还是1 if(!son[p][s]) son[p][s] = ++idx; // 以创建节点的id作为子节点索引 p = son[p][s]; // 进入子节点 }}int query(int x){ int p = 0; int s; int res = 0; for(int i=30;i>=0;i--){ s = x >> i & 1; // 右移i位或1,即判断第i位是0还是1 if(son[p][!s]) {res += 1
