5555 干货太多了来不及写，先(写) 水一个框架吧。
第二讲 数据结构
2.1 单链表
结构体加指针方式
-
数组模拟（笔试题中new一个节点很慢）
- 用到最多的是邻接表（存储图和树）
单链表.png
#include<isotream>
using namespace std;
const int N =1e6+10;
//head
//e[i]
//ne[i]
//idx
int head,e[N],ne[N],idx;
//initiate
void init()
{
head = -1;
idx = 0
}
//add_head
void add_to_head(int x)
{
e[idx]=x;
ne[idx]=head;
head =idx;
idx++;
}
// insert x after idx k
void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//remove node after idx k
void remove( ){
ne[k]=ne[ne[k]]
}
int main()
{
}
- 邻接表就是把每个节点所有邻边存下来，其实就是一堆单链表
2.2 双链表
- 优化某些问题
#include<iostream>
using namespace std;
const int N=1e6+10;
int m;
int e[N],l[N],r[N],idx;
//init
void init(){
}
//add
void add(int k,int x){
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
r[k]=idx;
l[r[idx]]=idx;
}
//remove
void remove(int k){
r[l[k]]= r[k];
l[r[k]]= l[k];
}
2.3 栈
- 先进后出的一种数据结构
#include<iostream>
using namespace std;
cosnt int N=1e6+10;
int stk[N],tt;
//insert
stk[++tt]=x;
//pop
tt--;
//is_empty
if(tt>0) not empty;
else empty;
//top
stk[tt];
int main()
{
}
2.4 队列
- 先进先出的一种数据结构
2.5 单调栈
- 给定序列，左边离他最近的满足某个性质的数
2.6 单调队列
- 求滑动窗口最大值和最小值
- 先考虑暴力做法
- 再考虑把没有用到的元素删除
- 查看剩下元素单调性，再做优化
- 取出极值用端点
- 找某个值可以用二分
2.7 KMP
2.8 Trie树
- 用来高效、快速存储和查找字符串集合的数据结构
Trie.png
2.9 并查集
- 将两个集合合并
- 询问两个元素是否在一个集合中
- 基本原理：每个集合用一棵树表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点
- 问题1：如何判断是否为树根
- 问题2：如何求x的集合编号
- 并查集优化：路径压缩优化
- 可以在并查集中维护一些额外信息。
2.10 堆
-
基本操作
插入一个数
求集合当中最小值
删除最小值
删除任意一个元素
修改任意一个元素
-
堆是一个完全二叉树
- 除了最后一层节点，其余节点满
- 最后一层节点从左到右排列
堆状（或者完全二叉树结构）可以用一维数组去存储
2.11 哈希表
主要作用是将较大的元素集合对象映射到较小的集合中
-
存储结构
- 开放寻址法
- 拉链法
字符串哈希方式
