0%

算法复习

数据结构研究组织大量数据的方法,算法分析则是对算法运行时间的评估。

算法是为求解一个问题需要遵循的、被清除地指定的简单指令的集合。

数据结构在计算机科学界至今没有一个标准的定义

普遍认可的算法的定义:算法是解决特定问题求解步骤的描述。

算法的特性:

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

引论

  • 数学知识

    级数:

  • 证明方法

    • 归纳法
    • 反证法
  • 递归简论

    • 设计递归的基本法则:
      1. 基准情形
      2. 不断推进
      3. 设计效益:假设所有的递归调用都能运行。
      4. 合成效益法则:不要做重复性工作。

算法分析

  • 数学基础

    $O(f(N))$ 上限

    $Ω(f(N))$ 下限

    $Θ(f(N))$ 相等

    $o(f(N))$ 小于

表、栈和队列

    • 数组
    • 链表
  • 中缀表达式转换为后缀表达式:

    中缀表达式可以通过栈转换成后缀表达式,P54

后缀表达式转换成表达式树同样借助栈:P71

扫描后缀表达式,若遇到operator,构造单节点树,入栈;

若遇到operand,从栈中弹出两棵树,以operand为根,合并弹出的两棵树,将得到的树入栈

时间复杂度=表达式的长度

  • 队列

    1
    2
    3
    4
    5
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    • CreateQueue()
    • IsFull()
    • IsEmpty()
    • Enqueue()
    • Dequeue()
    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
    // 队列的数组实现
    // Created by aoyun on 2019/11/24.
    //
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>

    #define ERROR -1

    typedef int ElementType;
    typedef int Position;
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    typedef struct QNode *Queue;

    static Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue) malloc(sizeof(struct QNode));
    Q->Data = (ElementType *) malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = -1; // ZJU代码有错
    Q->MaxSize = MaxSize;
    return Q;
    }

    static bool IsFull(Queue Q) {
    return ((Q->Rear + 1) % Q->MaxSize == Q->Front);
    }

    /**
    *
    * @param Q
    * @param X
    * @return 是否入队成功,队列已满会失败
    */
    static bool AddQ(Queue Q, ElementType X) {
    if (IsFull(Q)) {
    printf("队列满");
    return false;
    } else {
    Q->Rear = (Q->Rear + 1) % Q->MaxSize; // 队尾向后移
    Q->Data[Q->Rear] = X;
    return true;
    }
    }

    static bool IsEmpty(Queue Q) {
    return (Q->Front == Q->Rear);
    }

    ElementType DeleteQ(Queue Q) {
    if (IsEmpty(Q)) {
    printf("队列空");
    return ERROR;
    } else {
    Q->Front = (Q->Front + 1) % Q->MaxSize;
    return Q->Data[Q->Front];
    }
    }

    int main() {
    Queue Q = CreateQueue(4);
    AddQ(Q, 1);
    AddQ(Q, 2);
    AddQ(Q, 3);
    AddQ(Q, 4);
    printf("\n%d", DeleteQ(Q));
    }

  • 二叉树

    最多两个子节点

  • 二叉查找树

    每一个根节点,左子树的所有元素比根节点小,右子树相反。

  • AVL树

    有条件的平衡树

  • 伸展树

  • 树的遍历

  • B-树

    在2m阶B树中关键码个数n与B树高度h之间的关系为 $h≤log_m((n+1)/2)+1$

散列

  • 散列函数
  • 分离链接法
  • 开放定址法
  • 再散列
  • 可扩散列

优先队列

  • 二叉堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*----------- 建造最大堆 -----------*/
    /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
    void PercDown(MaxHeap H, int p) {
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; /* 取出根结点存放的值 */
    for (Parent = p; Parent * 2 <= H->Size;) {
    Child = Parent * 2;
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
    Child++; /* Child指向左右子结点的较大者 */
    if (X >= H->Data[Child])
    break; /* 找到了合适位置 */
    else /* 下滤X */
    H->Data[Parent] = H->Data[Child];
    Parent = Child;
    }
    H->Data[Parent] = X;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void MaxDown(MaxHeap H, int p) {
    int Parent, Child; // Parent-父节点在数组中的指针 Child-子节点在数组中的指针
    int X;
    X = H->Data[p];
    for (Parent = p; Parent * 2 < H->Size;) { // 从上往下,找p的正确位置
    Child = Parent * 2; // Child在Parent*2处
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) {
    Child++; // 找到较大的Child
    }
    if (X > H->Data[Child]) { // p就是正确位置
    break;
    } else { // 子节点更大,把子节点数值赋值到父节点位置
    H->Data[Parent] = H->Data[Child];
    }
    Parent = Child; // 父节点转到Child位置,重新开始新的一轮寻找父节点正确位置的过程
    }
    H->Data[Parent] = X;
    }
  • 应用

  • d-堆

  • 左式堆

  • 斜堆

  • 二项队列

排序

  • 冒泡排序

  • 选择排序

  • 插入排序

    向扑克牌一样,把新元素插入到正确的位置

  • 希尔排序

    缩小增量的插入排序

  • 堆排序

    1. 堆的构造
    2. 下沉排序

    利用堆的性质进行排序

  • 归并排序

    分治。先分,分成小单位;再治,对小单位排序;最后合并。

  • ==快速排序==

  • 桶排序

    知道元素的范围

  • 基数排序

    次位优先

  • 表排序

    大型结构的排序,移动不能

  • 外部排序

屏幕截图_216_.png

不相交集

图论算法

  • 定义
  • 拓扑排序
  • 最短路径
    • Dijkstra算法 单源最短路径
    • Floyd算法 多源最短
  • 网络流
  • 最小生成树
    • Prim
    • Kruskal
  • 深度优先搜索
  • NP-完全性

算法设计技巧

  • 贪婪算法

  • 分治算法

  • 动态规划

    核心思想:

    将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

  • 随机化算法

  • 回溯算法

更多

广度优先搜索

复杂度总结

  • BuildHeap
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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
//
// Created by aoyun on 2019/11/24.
//
#include <stdlib.h>
#include <stdio.h>

#define ElementType int

/**
* <p>插入排序</p>
* 把元素插到正确的位置
* @param A 待排序数组
* @param N 数组元素个数
*/
static void InsertionSort(ElementType A[], int N) { /* 插入排序 */
int P, i;
ElementType Tmp;

for (P = 1; P < N; P++) {
Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
for (i = P; i > 0 && A[i - 1] > Tmp; i--) /*从后向前*/
A[i] = A[i - 1]; /*依次与已排序序列中元素比较并右移*/
A[i] = Tmp; /* 放进合适的位置 */
}
}

/**
* <p>希尔排序</p>
*
* @param A
* @param N
*/
void ShellSort(ElementType A[], int N) { /* 希尔排序 - 用Sedgewick增量序列 */
int Si, D, P, i;
ElementType Tmp;
/* 这里只列出一小部分增量 */
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

// 找到合适的初始增量
for (Si = 0; Sedgewick[Si] >= N; Si++); /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
for (P = D; P < N; P++) { /* 插入排序*/
Tmp = A[P];
for (i = P; i >= D && A[i - D] > Tmp; i -= D)
A[i] = A[i - D];
A[i] = Tmp;
}
}

void Swap(ElementType *a, ElementType *b) {
ElementType t = *a;
*a = *b;
*b = t;
}

static void PercDown(ElementType A[], int p, int N) { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;

X = A[p]; /* 取出根结点存放的值 */
for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
Child = Parent * 2 + 1;
if ((Child != N - 1) && (A[Child] < A[Child + 1]))
Child++; /* Child指向左右子结点的较大者 */
if (X >= A[Child]) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}

/**
* 利用堆的特性排序
* @param A
* @param N
*/
void HeapSort(ElementType A[], int N) { /* 堆排序 */
int i;

for (i = N / 2 - 1; i >= 0; i--)/* 建立最大堆 */
PercDown(A, i, N);

for (i = N - 1; i > 0; i--) {
/* 删除最大堆顶 */
Swap(&A[0], &A[i]); /* 见代码7.1 */
PercDown(A, 0, i);
}
}

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void
Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;

LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;

while (L <= LeftEnd && R <= RightEnd) {
if (A[L] <= A[R])
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}

while (L <= LeftEnd)
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while (R <= RightEnd)
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

for (i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd) { /* 核心递归排序函数 */
int Center;

if (L < RightEnd) {
Center = (L + RightEnd) / 2;
Msort(A, TmpA, L, Center); /* 递归解决左边 */
Msort(A, TmpA, Center + 1, RightEnd); /* 递归解决右边 */
Merge(A, TmpA, L, Center + 1, RightEnd); /* 合并两段有序序列 */
}
}

void MergeSort(ElementType A[], int N) { /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *) malloc(N * sizeof(ElementType));

if (TmpA != NULL) {
Msort(A, TmpA, 0, N - 1);
free(TmpA);
} else printf("空间不足");
}

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length) { /* 两两归并相邻有序子列 */
int i, j;

for (i = 0; i <= N - 2 * length; i += 2 * length)
Merge(A, TmpA, i, i + length, i + 2 * length - 1);
if (i + length < N) /* 归并最后2个子列*/
Merge(A, TmpA, i, i + length, N - 1);
else /* 最后只剩1个子列*/
for (j = i; j < N; j++) TmpA[j] = A[j];
}

void Merge_Sort(ElementType A[], int N) {
int length;
ElementType *TmpA;

length = 1; /* 初始化子序列长度*/
TmpA = malloc(N * sizeof(ElementType));
if (TmpA != NULL) {
while (length < N) {
Merge_pass(A, TmpA, N, length);
length *= 2;
Merge_pass(TmpA, A, N, length);
length *= 2;
}
free(TmpA);
} else printf("空间不足");
}

/**
* 前中后3值选出pivot
* @param A
* @param Left
* @param Right
* @return
*/
ElementType Median3(ElementType A[], int Left, int Right) {
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right - 1]; /* 返回基准Pivot */
}

void Qsort(ElementType A[], int Left, int Right) { /* 核心递归函数 */
int Pivot, Cutoff, Low, High;

if (Cutoff <= Right - Left) { /* 如果序列元素充分多,进入快排 */
Pivot = Median3(A, Left, Right); /* 选基准 */
Low = Left;
High = Right - 1;
while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/
while (A[++Low] < Pivot);
while (A[--High] > Pivot);
if (Low < High) {
Swap(&A[Low], &A[High]);
} else {
break; // while(1)
}
}
Swap(&A[Low], &A[Right - 1]); /* 将基准换到正确的位置 */
Qsort(A, Left, Low - 1); /* 递归解决左边 */
Qsort(A, Low + 1, Right); /* 递归解决右边 */
} else {
InsertionSort(A + Left, Right - Left + 1); /* 元素太少,用简单排序 */
}
}

void QuickSort(ElementType A[], int N) { /* 统一接口 */
Qsort(A, 0, N - 1);
}

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
int key;
PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];

int GetDigit(int X, int D) { /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;

for (i = 1; i <= D; i++) {
d = X % Radix;
X /= Radix;
}
return d;
}

/**
* <p>基数排序</p>
* 每次选择一个基准,如个位、十位、百位
* @param A
* @param N
*/
void LSDRadixSort(ElementType A[], int N) { /* 基数排序 - 次位优先 */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = 0; i < N; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面开始排序 */
for (D = 1; D <= MaxDigit; D++) { /* 对数据的每一位循环处理 */
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶尾 */
tmp->next = NULL;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {
B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* 下面是收集的过程 */
List = NULL;
for (Di = Radix - 1; Di >= 0; Di--) { /* 将每个桶的元素顺序收集入List */
if (B[Di].head) { /* 如果桶不为空 */
/* 整桶插入List表头 */
B[Di].tail->next = List;
List = B[Di].head;
B[Di].head = B[Di].tail = NULL; /* 清空桶 */
}
}
}
/* 将List倒入A[]并释放空间 */
for (i = 0; i < N; i++) {
tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}

/* 基数排序 - 主位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */

#define MaxDigit 4
#define Radix 10

///* 桶元素结点 */
//typedef struct Node *PtrToNode;
//struct Node{
// int key;
// PtrToNode next;
//};

///* 桶头结点 */
//struct HeadNode {
// PtrToNode head, tail;
//};
typedef struct HeadNode Bucket[Radix];

//int GetDigit ( int X, int D )
//{ /* 默认次位D=1, 主位D<=MaxDigit */
// int d, i;
//
// for (i=1; i<=D; i++) {
// d = X%Radix;
// X /= Radix;
// }
// return d;
//}

void MSD(ElementType A[], int L, int R, int D) { /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
int Di, i, j;
Bucket B;
PtrToNode tmp, p, List = NULL;
if (D == 0) return; /* 递归终止条件 */

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = L; i <= R; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶 */
if (B[Di].head == NULL) B[Di].tail = tmp;
tmp->next = B[Di].head;
B[Di].head = tmp;
}
/* 下面是收集的过程 */
i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
for (Di = 0; Di < Radix; Di++) { /* 对于每个桶 */
if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
p = B[Di].head;
while (p) {
tmp = p;
p = p->next;
A[j++] = tmp->key;
free(tmp);
}
/* 递归对该桶数据排序, 位数减1 */
MSD(A, i, j - 1, D - 1);
i = j; /* 为下一个桶对应的A[]左端 */
}
}
}

void MSDRadixSort(ElementType A[], int N) { /* 统一接口 */
MSD(A, 0, N - 1, MaxDigit);
}

//int main() {
// int a[] = {3, 1, 2};
// QuickSort(a, 3);
//}

摊还分析

高级数据结构及其实现