《数据结构与算法分析》复习笔记

不过我喝咖啡从来不是为了提神的 这个世界上唯一提神的东西就是你今天必须完成的事情呀

博士只考一门数据结构与算法分析,如果这都考不过那就真的重在参与了。本文把看完书以后手撸的代码贴出来,留个纪念。

1月4日写了一天没保存就 init 0 了 >_<
以后还是老老实实用VIM编辑好了,最起码有swp文件

说实话冯舜玺译的《数据结构与算法分析》实在是有点难懂(骂街的话省略一百万字……)。 想算法入门的童鞋还是去看看《大话数据结构》《啊哈!算法》之类的书吧。


0x04 树

遍历

  • 前序遍历(ListDIR):根节点->左子树->右子树
  • 中序遍历:左子树->根节点->右子树
  • 后序遍历:左子树->右子树->根节点

二叉查找树

  • 左子树 < 根 < 右子树
  • Find/FindMin/FindMax/[Insert] 递归
  • Delete 懒惰删除

平衡(AVL)二叉树 带有平衡条件的二叉查找树

  • 单旋
  • 双旋

伸展树


0x05 散列


0x06 堆(优先队列)

优先队列:最高级先出 二叉堆(孩子比根大)∈ 完全二叉树 堆==>二叉堆

数组存储

  • 0位置是哑信息(小于堆中的任何值)
  • 根从[1]位置开始

构建堆

  1. 随便放
  2. N/2 -> 0 下滤

插入

  1. 放到数组最后
  2. 上滤(如果比根小就与根交换)
  3. 因为0位置是标记(dummy),所以不用判断是否终止

删除最小值

  1. 弹出第一个
  2. 末尾的放到第一个
  3. 下滤(小的儿子如果比根小,与根交换)
  4. 巧妙地防止没有右儿子 if(Child != H.size && H[Child+1]<H[Child])Child++;

降低值–>上滤
增加值–>下滤
删除–>降低为最小值,删除最小值

d-堆–>树浅,insert快

左式堆 –> 左式堆是专门用来解优先队列合并的麻烦(任意二叉堆的合并都必须重新合并,O(N)的时间)。趋向于非常不平衡

  1. 零路径长度:到没有两个儿子的节点最短距离
  2. 零路径长:左儿子≧右儿子,父节点= min{儿子} +1(这条性质导致了左式堆的严重左偏)
  3. 根值大的堆与根值小的堆的右子堆合并(根值:根位置的元素值,并非零路径长度)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
合并方法
1. 根值大的堆(H1)与根值小的堆(H2)的右子堆合并
2. 若H2有右子堆,取出(H3)与H1合并(递归)
3. 若不满足根的左儿子≧右儿子,交换左右孩子
Merge(PriorityQueue H1,H2) //H1<H2
{
if(H1.left==NULL)
H1.left=H2;
else{
H1.right = Merge_(H1.right,H2); //Merge_要判断是否为空和H1,H2的大小
if(H1.left.NP1<H1.right.NP1)
swapChildren(H1)
}
return H1;

二项队列 –> 二项队列是由不同高度堆序树组成的森林

  1. 合并:相同高度的合并,不同高度的添加
  2. 插入=合并
  3. DeleteMin: <1>遍历所有最小节点 <2>将最小点的树DeleteMin并删除 <3>将最小点的树合并到原始二项队列

0x09 图

拓扑排序

  1. 找到没有入边的点
  2. 删除它和它的边
  3. 重复上面两条直到图空为止

最短路 - 广搜 –> 无权图

最短路 - Dijkstra

  1. 选取集合外与起始节点距离最小的点加入集合
  2. 调整所有与集合相邻的节点的最短路径 D(w)=min(D(w),D(v)+j(v,w))
  3. 重复直到集合=全集

最短路 - 有负边 –> 使用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
#适用于有负边的Dijkstra版本
Table T, Queue Q, Start vertex S
While(Q is not Empty){
V=Dequeue(Q)
for each w adjacent V
if (T[V].dist+Cvw<T[w].dist){
T[w].dist=T[v].dist+Cvw
T[w].path=V
if w∉Q
Enqueue(w,Q)
}
}
DisposeQueue(Q)

最短路 - Floyd Wasrshall
NOIP最喜欢这个。碰到最短路题,一分钟敲4行代码就完事

1
2
3
4
for k in G #记住k一定放在最外层循环
for u in G
for v in G
D[u,v]=min(D[u,v],D[u,k]+D[k,v])

如果要记录路径,

  1. 初始化P(u,v)=u
  2. 在循环中if(D[u,k]+D[k,v]<D[u,v]) P(u,v)=P(k,u)

网络流
最大流可能不止一个

最小生成树
prim –> 往树上加最小边
Kruskal –> 选择不成环的最小边


0x07 排序

排序算法还是比较基础的,复习以后有一丢丢启发(竞赛入门水平只会个快排,以前一直把希尔排序跟归并排序搞混、堆排序也从来没用过>_<)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include<stdio.h>
static int N = 10;
int i = 0, j = 0;
void print(int a[]) {
for (int i = 0; i < N; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
///////////////////////////////
// 把第i个元素插入到前面合适的位置(其它元素顺应后移)
//////////////////////////////
void insert_sort(int a[]) {
int tmp, i, j;
for (i = 1; i < N; i++) {
tmp = a[i];
for (j = i; j > 0 && tmp < a[j - 1]; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
///////////////////////////////
//因为插入排序对已经近似排序好的序列时间复杂度低
//分组,执行log(n)次插入排序
///////////////////////////////
void shell_sort(int a[]) {
int gap, i, j, tmp;
for (gap = N / 2; gap > 0; gap /= 2) {
for (i = gap; i < N; i++) {
tmp = a[i];
for (j = i; j >= gap; j -= gap) {
if (a[j - gap] > tmp) { //if不能跟前面的插入排序一样跟for写在一行,否则就失去希尔排序的意义了
a[j] = a[j - gap];
} else {
break;
}
}
a[j] = tmp;
}
}
}
////////////////////////////////
//堆排序:1.构建堆(下滤);2.不断的首尾交换&下滤
//
///////////////////////////////
void perc_down(int a[], int i, int N) {
int tmp = a[i];
int child;
while (i < (N - 1) / 2) { //leftchild<N ==> 2*i+1<N ==> i<N-1
child = 2 * i + 1;
if (a[child] > a[child + 1]) {
child++;
}
if (tmp > a[child]) {
a[i] = a[child];
i = child;
} else {
break;
}
}
a[i] = tmp;
}
void heap_sort(int a[]) {
int tmp;
for (int i = N / 2; i >= 0; i--) {
perc_down(a, i, N);
}
for (int i = N - 1; i > 0; i--) {
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
perc_down(a, 0, i);
printf("%d:\t", i);
print(a);
}
}
////////////////////////////////
//两个有序数组合并成一个有序数组
////////////////////////////////
void merge(int a[], int tmp_array[], int l, int r, int r_end) {
int num = r_end - l + 1;
int tmp_position = l;
int l_end = r - 1;
while (l <= l_end && r <= r_end) {
if (a[l] < a[r]) {
tmp_array[tmp_position++] = a[l++];
} else {
tmp_array[tmp_position++] = a[r++];
}
}
while (l <= l_end) {
tmp_array[tmp_position++] = a[l++];
}
while (r <= r_end) {
tmp_array[tmp_position++] = a[r++];
}
for (i = 0; i < num; i++, r_end--) {
a[r_end] = tmp_array[r_end];
}
}
void msort(int a[], int tmp_array[], int l, int r) {
int center;
if (l < r) {
center = (l + r) / 2;//c-l<=r-c
msort(a, tmp_array, l, center);
msort(a, tmp_array, center + 1, r);
merge(a, tmp_array, l, center + 1, r);
}
}
void merge_sort(int a[]) {
int tmp_array[N];
msort(a, tmp_array, 0, N - 1);
}
/////////////////////////
//高中的时候能一分钟敲完的算法
/////////////////////////
void qsort(int a[], int left, int right) {
int i, j, t, tmp;
if (left > right)
return;
tmp = a[left];
i = left;
j = right;
while (i != j) {
while (a[j] >= tmp && i < j) j--;
while (a[i] <= tmp && i < j) i++;
if (i < j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}//左边大的跟右边小的交换,使得左边的小于tmp,右边的大于tmp
a[left] = a[i];
a[i] = tmp;
//tmp放在中间
qsort(a, left, i - 1);
qsort(a, i + 1, right);
}
void quick_sort(int a[]) {
qsort(a, 0, 9);
}
int main() {
// int a[10] = {4, 85, 3, 234, 45, 346, 345, 122, 30, 12};
// insert_sort(a);
// printf("insert_sort: ");
// print(a);
// int a[10] = {4, 85, 3, 234, 45, 346, 345, 122, 30, 12};
// shell_sort(a);
// printf("shell_sort: ");
// print(a);
//
// int a[10] = {4, 85, 3, 234, 45, 346, 345, 122, 30, 12};
// heap_sort(a);
// printf("heap_sort: ");
// print(a);
// int a[10] = {4, 85, 3, 234, 45, 346, 345, 122, 30, 12};
// merge_sort(a);
// printf("merge_sort: ");
// print(a);
int a[10] = {4, 85, 3, 234, 45, 346, 345, 122, 30, 12};
quick_sort(a);
printf("quick_sort: ");
print(a);
return 0;
}

0x08 并查集

看到书中说的不相交集ATD简直不明所云,看完以后发现这不就是之前学的并查集嘛>_<

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//https://www.cnblogs.com/douzujun/p/6402312.html
#include <iostream>
using namespace std;
const int maxn = 1000 + 100;
int par[maxn]; //父亲, 当par[x] = x时,x是所在的树的根
int Rank[maxn]; //树的高度
const int n = 6;
const int max_num = 10;
//初始化n个元素
void init(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
Rank[i] = 0;
}
}
//查询树的根
int find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
//合并x和y所属集合
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (Rank[x] < Rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (Rank[x] == Rank[y]) Rank[x]++; //如果x,y的树高相同,就让x的树高+1
}
}
//判断x和y是否属于同一个集合
bool same(int x, int y) {
return find(x) == find(y);
}
void printUF() {
printf("num\t\t");
for (int i = 0; i < max_num; i++) {
printf("%d ", i);
}
printf("\npar\t\t");
for (int i = 0; i < max_num; i++) {
printf("%d ", par[i]);
}
printf("\nrank\t");
for (int i = 0; i < max_num; i++) {
printf("%d ", Rank[find(i)]);
}
printf("\n");
}
int main() {
init(max_num);
int a[n] = {1, 2, 5, 6, 4, 7};
int b[n] = {1, 1, 1, 6, 6, 4};
for (int i = 0; i < n; i++) {
unite(a[i], b[i]);
}
printf("初始化:\n");
printUF();
unite(9, 8);
printf("合并(9,8):\n");
printUF();
unite(8, 1);
printf("合并(8,1),此时rank变成2:\n");
printUF();
printf("(1,4)是否在一个集合:\n");
printf("%d\n", same(1, 4));
unite(1, 4);
printf("(1,4)是否在一个集合:\n");
printf("%d\n", same(1, 4));
printUF();
return 0;
}