参考yxc大佬的总结
单链表
C++代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| // head 存储的链表头，e[]存储结点的值，ne[]存储结点的next指针，idx表示当前用到了哪个结点
int head, e[N], ne[N], idx;
// 初始化
void init(){
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a){
e[idx] = a, ne[idx] = head, head = idx++;
}
// 将头结点删除，需要保证头结点的存在
void remove(){
head = ne[head];
}
|
双链表
C++代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // e[]表示结点的值，l[]表示结点的左指针，r[]表示结点的右指针，idx表示当前用到了哪个结点
int e[N], l[N], r[N], idx;
// 初始化
void init(){
// 0是左端点，1是右端点
r[0] = 1, r[1] = 0;
idx = 2;
}
// 在结点a的右边插入一个值数
void insert(int a, int x){
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx++;
}
// 删除结点a
void remove(int a){
l[r[a]] = l[a];
r[l[a]] = r[a];
}
|
栈
C++ 代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // tt 表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[++tt] = x;
// 从栈顶弹出一个数
tt--;
// 栈顶的值，
stk[tt];
// 判断栈是否为空
if (tt > 0){}
|
队列
C++代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // hh表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[++tt] = x;
// 从队头弹出一个数
hh++;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh<=tt){}
|
循环队列
C++代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| // hh 表示=队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt++] = x;
if(tt==N) tt = 0;
// 从队头弹出一个数
hh++;
if(hh==N) hh = 0;
// 队头值
q[hh];
// 判断队列是否为空
if (hh!=tt){}
|
树与图的存储
树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b和b->a。
常用的存储方法有两种：(1)邻接矩阵；(2)邻接表。vector邻接表、数组邻接表、链式前向星
C++代码模板——邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
| // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点。
int h[N], e[N], ne[N], idx;
// 初始化
idx = 0;
memset(h, -1, sizeof(h));
// 添加一条边
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
|
树与图的遍历
深度优先遍历
1
2
3
4
5
6
7
| int dfs(int u){
st[u] = true; // 表示第u个结点访问过了
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]) dfs(j);
}
}
|
宽度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| queue<int> q;
st[1] = true; // 表示1号结点已经被遍历过了
q.push(1);
while(q.size()){
int t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]){
st[j] = true; // 表示 j 已经被访问过了
q.push(j);
}
}
}
|
