目录


第1章绪论1
1.1时间复杂度1
1.2空间复杂度2
第2章数组与链表3
2.1数组结构4
2.1.1数组的创建与基本操作4
2.1.2数组内存特性分析7
2.1.3内存中的多维数组13
2.2链表结构17
2.2.1基本概念普及17
2.2.2链表内存特性分析19
2.2.3链表衍生结构27
第3章栈和队列54
3.1栈结构55
3.1.1栈结构概述55
3.1.2栈结构的实现55
3.1.3栈结构的应用场景56
3.2队列结构63
3.2.1队列结构概述63
3.2.2队列结构的实现64
3.2.3队列结构的应用场景65
3.2.4队列结构的衍生68
第4章递归、查找与排序73
4.1递归73
4.1.1简单的递归案例74
4.1.2递归结构基础75
4.1.3递归结构进阶78
4.2查找79
4.2.1二分查找79
4.2.2插值查找84
4.2.3斐波那契查找89
4.3排序96
4.3.1排序算法的稳定性96
4.3.2冒泡排序97
4.3.3选择排序101
4.3.4插入排序105
4.3.5希尔排序110
4.3.6归并排序115
4.3.7快速排序123
4.3.8堆排序131
4.3.9计数排序141
4.3.10桶排序147
第5章字符串152
5.1基本概念与实现152
5.1.1字符串的基本概念152
5.1.2Java中的String类153
5.2字符串匹配算法156
5.2.1通用定义156
5.2.2BF算法156
5.2.3RK算法161
5.2.4KMP算法168
5.2.5BM算法183
5.2.6Sunday算法196
第6章树结构203
6.1树结构基础204
6.1.1树的基础概念204
6.1.2树的遍历操作206
6.2二叉树216
6.2.1二叉树的定义216
6.2.2二叉树的基本性质217
6.2.3满二叉树和完全二叉树217
6.2.4二叉树的遍历操作219
6.2.5通过深度优先遍历序列构建二叉树230
6.2.6树、森林与二叉树的转换238
6.3哈夫曼树与哈夫曼编码译码器248
6.3.1哈夫曼树的构建248
6.3.2获取明文字符的哈夫曼编码249
6.3.3文本编码与译码250
6.4线索二叉树与Morris遍历250
6.4.1线索二叉树的节点定义方式251
6.4.2二叉树的线索化251
6.4.3线索二叉树的遍历261
6.4.4二叉树的Morris遍历274
6.5二叉排序树286
6.5.1二叉排序树的结构特点286
6.5.2二叉排序树的增删查找287
6.5.3二叉排序树退化为单链表的情况295
6.6平衡二叉树（AVL树）296
6.6.1AVL树节点的旋转方式296
6.6.2节点增删导致不平衡的情况304
6.6.3AVL树与平衡二叉树的对比307
6.7234树308
6.7.1234树的结构特点308
6.7.2234树的增删查找310
6.8红黑树318
6.8.1红黑树的平衡策略与染色规则318
6.8.2234树向红黑树的转换319
6.8.3红黑树的节点增删与结构调整323
6.9B树与B+树338
6.9.1B树结构338
6.9.2B+树结构339
6.9.3B树与B+树在实际应用方面的区别341
6.10字典树（Trie树）344
6.10.1字典树的结构特点344
6.10.2字典树的基本功能与实现方式346
6.10.3字典树的时间复杂度与空间复杂度357
6.11树状数组358
6.11.1前置知识: 非负整数的lowBit操作358
6.11.2树状数组的构建方式359
6.11.3树状数组的基本操作364
6.11.4差分数组与基本操作367
第7章堆结构378
7.1堆结构基础379
7.2二叉堆380
7.2.1二叉堆的存储方式与特性380
7.2.2二叉堆的元素添加操作381
7.2.3二叉堆的堆顶元素删除操作383
7.2.4二叉堆与TopK问题386
7.3左式堆与斜堆387
7.3.1左式堆388
7.3.2斜堆395
7.4二项堆401
7.4.1二项树结构401
7.4.2二项堆的结构特点404
7.4.3二项堆的合并操作405
7.4.4二项堆的元素添加操作409
7.4.5二项堆的堆顶元素删除操作412
第8章散列表416
8.1散列表的基本概念417
8.2散列函数的常见实现方式420
8.2.1前置知识: 整数的模运算421
8.2.2直接定址法425
8.2.3除留余数法425
8.2.4数字分析法426
8.2.5平方取中法427
8.2.6折叠法427
8.2.7随机数法428
8.2.8全域散列法428
8.3散列表常见实现方式429
8.3.1开放地址法实现散列表430
8.3.2链地址法实现散列表434
8.3.3完全散列的实现434
8.4散列表的平均查找长度437
8.5Java中的散列表440
8.5.1Java中的hashCode()与equals()方法440
8.5.2HashMap类与HashSet类443
第9章图结构448
9.1图结构基础449
9.1.1图的基础概念449
9.1.2图的表示方式453
9.1.3图的遍历操作456
9.2无向带权图的最小生成树问题461
9.2.1普里姆算法462
9.2.2克鲁斯卡尔算法465
9.2.3普里姆算法与克鲁斯卡尔算法的比较468
9.3有向带权图的最短路径问题469
9.3.1迪杰斯特拉算法求解有向带权图的单源最短路径469
9.3.2弗洛伊德算法求解有向带权图的多源最短路径473
9.4AOV网和拓扑排序问题479
9.5AOE网和关键路径问题484
参考文献489