第1章 数据结构基础 1
常见考点 1
1.1数据结构的概念 1
1.1.1要点归纳 1
1.1.2面试题解析 2
1.2算法描述和分析 5
1.2.1要点归纳 5
1.2.2面试题解析 6
1.3算法设计手段——递归 8
1.3.1要点归纳 8
1.3.2面试题解析 16
1.4自测题和参考答案 31
1.4.1自测题 31
1.4.2参考答案 33
第2章 线性表Ⅰ——数组 36
常见考点 36
2.1线性表顺序存储结构 36
2.1.1要点归纳 36
2.1.2面试题解析 38
2.2数组的基本算法设计 39
2.2.1要点归纳 39
2.2.2面试题解析 45
2.3有序数组的算法设计 55
2.3.1要点归纳 55
2.3.2面试题解析 59
2.4多维数组 63
2.4.1要点归纳 63
2.4.2面试题解析 64
2.5自测题和参考答案 70
2.5.1自测题 70
2.5.2参考答案 71
第3章 线性Ⅱ——链表 77
常见考点 77
3.1线性表链式存储结构概述 77
3.1.1要点归纳 77
3.1.2面试题解析 78
3.2单链表算法设计 79
3.2.1要点归纳 79
3.2.2面试题解析 82
3.3双链表算法设计 101
3.3.1要点归纳 101
3.3.2面试题解析 101
3.4循环链表算法设计 104
3.4.1要点归纳 104
3.4.2面试题解析 104
3.5自测题和参考答案 113
3.5.1自测题 113
3.5.2参考答案 114
第4章 字符串 121
常见考点 121
4.1字符串基础 121
4.1.1要点归纳 121
4.1.2面试题解析 122
4.2字符串匹配算法设计 133
4.2.1要点归纳 133
4.2.2面试题解析 135
4.3自测题和参考答案 146
4.3.1自测题 146
4.3.2参考答案 147
第5章 栈 149
常见考点 149
5.1栈基本算法设计 149
5.1.1要点归纳 149
5.1.2面试题解析 151
5.2栈应用算法设计 155
5.2.1要点归纳 155
5.2.2面试题解析 156
5.3自测题和参考答案 179
5.3.1自测题 179
5.3.2参考答案 180
第6章 队列 184
常见考点 184
6.1队列基本算法设计 184
6.1.1要点归纳 184
6.1.2面试题解析 186
6.2队列应用算法设计 189
6.2.1要点归纳 189
6.2.2面试题解析 191
6.3自测题和参考答案 201
6.3.1自测题 201
6.3.2参考答案 202
第7章 树和二叉树 205
常见考点 205
7.1树 205
7.1.1要点归纳 205
7.1.2面试题解析 208
7.2二叉树概念 210
7.2.1要点归纳 210
7.2.2面试题解析 212
7.3二叉树遍历及算法设计 216
7.3.1要点归纳 216
7.3.2面试题解析 223
7.4哈夫曼树 262
7.4.1要点归纳 262
7.4.2面试题解析 263
7.5自测题和参考答案 265
7.5.1自测题 265
7.5.2参考答案 267
第8章 图 274
常见考点 274
8.1图的概念和存储结构 274
8.1.1要点归纳 274
8.1.2面试题解析 277
8.2图的遍历算法及其应用 280
8.2.1要点归纳 280
8.2.2面试题解析 286
8.3图的应用 302
8.3.1要点归纳 302
8.3.2面试题解析 304
8.4自测题和参考答案 340
8.4.1自测题 340
8.4.2参考答案 344
第9章 查找 352
常见考点 352
9.1顺序表的查找 352
9.1.1要点归纳 352
9.1.2面试题解析 354
9.2二叉排序树和平衡二叉树 366
9.2.1要点归纳 366
9.2.2面试题解析 367
9.3 B树和B+树 381
9.3.1要点归纳 381
9.3.2面试题解析 382
9.4哈希表查找 382
9.4.1要点归纳 382
9.4.2面试题解析 386
9.5自测题和参考答案 393
9.5.1自测题 393
9.5.2参考答案 395
第10章 排序 399
常见考点 399
10.1插入排序 399
10.1.1要点归纳 399
10.1.2面试题解析 402
10.2交换排序 404
10.2.1要点归纳 404
10.2.2面试题解析 406
10.3选择排序 416
10.3.1要点归纳 416
10.3.2面试题解析 418
10.4归并排序 423
10.4.1要点归纳 423
10.4.2面试题解析 424
10.5基数排序和桶排序 429
10.5.1要点归纳 429
10.5.2面试题解析 431
10.6外排序 435
10.6.1要点归纳 435
10.6.2面试题解析 436
10.7自测题和参考答案 437
10.7.1自测题 437
10.7.2参考答案 438
附录A 算法索引 443