算法pdf

【实例截图】

【核心代码】

第 第 1 章 章 内容介绍和授课方式..............................................................................................................................................................................1
1.1 数据结构和算法内容介绍...........................................................................................................................................................................1
1.1.1 先看几个经典的算法面试题................................................................................................................................................1
1.1.2 数据结构和算法的重要性....................................................................................................................................................3
1.1.3 本套数据结构和算法内容介绍............................................................................................................................................4
1.1.4 课程亮点和授课方式............................................................................................................................................................4
第 第 2 章 章 数据结构和算法概述..............................................................................................................................................................................5
2.1.1 数据结构和算法的关系........................................................................................................................................................5
2.2 看几个实际编程中遇到的问题...................................................................................................................................................................5
2.2.1 问题一-字符串替换问题...................................................................................................................................................... 5
2.2.2 一个五子棋程序....................................................................................................................................................................5
2.2.3 约瑟夫(Josephu)问题(丢手帕问题).....................................................................................................................................6
2.2.4 其它常见算法问题:...............................................................................................................................................................6
2.3 线性结构和非线性结构...............................................................................................................................................................................7
2.3.1 线性结构................................................................................................................................................................................7
2.3.2 非线性结构............................................................................................................................................................................7
第 第 3 章 章 稀疏数组和队列......................................................................................................................................................................................8
3.1 稀疏 SPARSEARRAY 数组...............................................................................................................................................................................8
3.1.1 先看一个实际的需求............................................................................................................................................................8
3.1.2 基本介绍................................................................................................................................................................................8
3.1.3 应用实例................................................................................................................................................................................9
3.1.4 课后练习..............................................................................................................................................................................14
3.2 队列.............................................................................................................................................................................................................14
3.2.1 队列的一个使用场景..........................................................................................................................................................14
3.2.2 队列介绍..............................................................................................................................................................................14
3.2.3 数组模拟队列思路..............................................................................................................................................................15
3.2.4 数组模拟环形队列..............................................................................................................................................................21
第 第 4 章 章 链表........................................................................................................................................................................................................28
4.1 链表(L INKED L IST )介绍..............................................................................................................................................................................28
4.2 单链表的应用实例.....................................................................................................................................................................................29
4.3 单链表面试题(新浪、百度、腾讯)..........................................................................................................................................................38
4.4 双向链表应用实例.....................................................................................................................................................................................44
4.4.1 双向链表的操作分析和实现..............................................................................................................................................44
4.4.2 课堂作业和思路提示..........................................................................................................................................................53
4.5 单向环形链表应用场景.............................................................................................................................................................................53
4.6 单向环形链表介绍.....................................................................................................................................................................................53
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 III页
4.7 J OSEPHU 问题...............................................................................................................................................................................................54
4.8 J OSEPHU 问题的代码实现...........................................................................................................................................................................55
第 第 5 章 章 栈............................................................................................................................................................................................................62
5.1 栈的一个实际需求.....................................................................................................................................................................................62
5.2 栈的介绍.....................................................................................................................................................................................................62
5.3 栈的应用场景.............................................................................................................................................................................................63
5.4 栈的快速入门.............................................................................................................................................................................................63
5.5 栈实现综合计算器(中缀表达式)..............................................................................................................................................................68
5.6 逆波兰计算器.............................................................................................................................................................................................77
5.7 中缀表达式转换为后缀表达式.................................................................................................................................................................81
5.7.1 具体步骤如下:.....................................................................................................................................................................81
5.7.2 举例说明:.............................................................................................................................................................................81
5.7.3 代码实现中缀表达式转为后缀表达式............................................................................................................................. 82
5.8 逆波兰计算器完整版.................................................................................................................................................................................91
5.8.1 完整版的逆波兰计算器，功能包括................................................................................................................................. 91
第 第 6 章 章 递归......................................................................................................................................................................................................100
6.1 递归应用场景...........................................................................................................................................................................................100
6.2 递归的概念...............................................................................................................................................................................................100
6.3 递归调用机制...........................................................................................................................................................................................100
6.4 递归能解决什么样的问题.......................................................................................................................................................................102
6.5 递归需要遵守的重要规则.......................................................................................................................................................................103
6.6 递归-迷宫问题..........................................................................................................................................................................................103
6.6.1 迷宫问题............................................................................................................................................................................103
6.6.2 代码实现:...........................................................................................................................................................................103
6.6.3 对迷宫问题的讨论............................................................................................................................................................108
6.7 递归-八皇后问题(回溯算法)...................................................................................................................................................................108
6.7.1 八皇后问题介绍................................................................................................................................................................108
6.7.2 八皇后问题算法思路分析................................................................................................................................................109
6.7.3 八皇后问题算法代码实现................................................................................................................................................110
第 第 7 章 章 排序算法..............................................................................................................................................................................................114
7.1 排序算法的介绍.......................................................................................................................................................................................114
7.2 排序的分类：...........................................................................................................................................................................................114
7.3 算法的时间复杂度...................................................................................................................................................................................114
7.3.1 度量一个程序(算法)执行时间的两种方法.....................................................................................................................114
7.3.2 时间频度............................................................................................................................................................................115
7.3.3 时间复杂度........................................................................................................................................................................117
7.3.4 常见的时间复杂度............................................................................................................................................................117
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 IV页
7.3.5 平均时间复杂度和最坏时间复杂度............................................................................................................................... 120
7.4 算法的空间复杂度简介...........................................................................................................................................................................121
7.4.1 基本介绍............................................................................................................................................................................121
7.5 冒泡排序...................................................................................................................................................................................................121
7.5.1 基本介绍............................................................................................................................................................................121
7.5.2 演示冒泡过程的例子(图解).............................................................................................................................................122
7.5.3 冒泡排序应用实例............................................................................................................................................................122
7.6 选择排序...................................................................................................................................................................................................127
7.6.1 基本介绍............................................................................................................................................................................127
7.6.2 选择排序思想:...................................................................................................................................................................127
7.6.3 选择排序思路分析图:.......................................................................................................................................................128
7.6.4 选择排序应用实例:...........................................................................................................................................................129
7.7 插入排序...................................................................................................................................................................................................134
7.7.1 插入排序法介绍:...............................................................................................................................................................134
7.7.2 插入排序法思想:...............................................................................................................................................................134
7.7.3 插入排序思路图:...............................................................................................................................................................134
7.7.4 插入排序法应用实例:.......................................................................................................................................................135
7.8 希尔排序...................................................................................................................................................................................................140
7.8.1 简单插入排序存在的问题................................................................................................................................................140
7.8.2 希尔排序法介绍................................................................................................................................................................140
7.8.3 希尔排序法基本思想........................................................................................................................................................141
7.8.4 希尔排序法的示意图........................................................................................................................................................141
7.8.5 希尔排序法应用实例:.......................................................................................................................................................142
7.9 快速排序...................................................................................................................................................................................................147
7.9.1 快速排序法介绍:...............................................................................................................................................................147
7.9.2 快速排序法示意图:...........................................................................................................................................................147
7.9.3 快速排序法应用实例:.......................................................................................................................................................148
7.10 归并排序.................................................................................................................................................................................................152
7.10.1 归并排序介绍:.................................................................................................................................................................152
7.10.2 归并排序思想示意图 1-基本思想:................................................................................................................................152
7.10.3 归并排序思想示意图 2-合并相邻有序子序列:............................................................................................................153
7.10.4 归并排序的应用实例:.....................................................................................................................................................153
7.11 基数排序.................................................................................................................................................................................................158
7.11.1 基数排序(桶排序)介绍:..................................................................................................................................................158
7.11.2 基数排序基本思想..........................................................................................................................................................158
7.11.3 基数排序图文说明..........................................................................................................................................................159
7.11.4 基数排序代码实现..........................................................................................................................................................160
7.11.5 基数排序的说明:.............................................................................................................................................................167
7.12 常用排序算法总结和对比.....................................................................................................................................................................167
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 V页
7.12.1 一张排序算法的比较图..................................................................................................................................................167
7.12.2 相关术语解释：..............................................................................................................................................................168
第 第 8 章 章 查找算法..............................................................................................................................................................................................169
8.1 查找算法介绍...........................................................................................................................................................................................169
8.2 线性查找算法...........................................................................................................................................................................................169
8.3 二分查找算法...........................................................................................................................................................................................170
8.3.1 二分查找：........................................................................................................................................................................170
8.3.2 二分查找算法的思路........................................................................................................................................................170
8.3.3 二分查找的代码................................................................................................................................................................171
8.4 插值查找算法...........................................................................................................................................................................................176
8.4.1 插值查找应用案例：........................................................................................................................................................176
8.4.2 插值查找注意事项：........................................................................................................................................................180
8.5 斐波那契(黄金分割法)查找算法............................................................................................................................................................180
8.5.1 斐波那契(黄金分割法)查找基本介绍:............................................................................................................................180
8.5.2 斐波那契(黄金分割法)原理:............................................................................................................................................180
8.5.3 斐波那契查找应用案例：................................................................................................................................................181
第 第 9 章 章 哈希表..................................................................................................................................................................................................185
9.1 哈希表(散列)-G OOGLE 上机题................................................................................................................................................................185
9.2 哈希表的基本介绍...................................................................................................................................................................................185
9.3 GOOGLE 公司的一个上机题:.....................................................................................................................................................................186
第 第 10 章 章 树结构的基础部分............................................................................................................................................................................195
10.1 二叉树.....................................................................................................................................................................................................195
10.1.1 为什么需要树这种数据结构..........................................................................................................................................195
10.1.2 树示意图..........................................................................................................................................................................196
10.1.3 二叉树的概念..................................................................................................................................................................197
10.1.4 二叉树遍历的说明..........................................................................................................................................................198
10.1.5 二叉树遍历应用实例(前序,中序,后序).........................................................................................................................199
10.1.6 二叉树-查找指定节点.................................................................................................................................................... 205
10.1.7 二叉树-删除节点............................................................................................................................................................ 216
10.1.8 二叉树-删除节点............................................................................................................................................................ 220
10.2 顺序存储二叉树.....................................................................................................................................................................................220
10.2.1 顺序存储二叉树的概念..................................................................................................................................................220
10.2.2 顺序存储二叉树遍历......................................................................................................................................................221
10.2.3 顺序存储二叉树应用实例..............................................................................................................................................224
10.3 线索化二叉树.........................................................................................................................................................................................224
10.3.1 先看一个问题..................................................................................................................................................................224
10.3.2 线索二叉树基本介绍......................................................................................................................................................224
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 VI页
10.3.3 线索二叉树应用案例......................................................................................................................................................225
10.3.4 遍历线索化二叉树..........................................................................................................................................................242
10.3.5 线索化二叉树的课后作业:............................................................................................................................................ 243
第 第 11 章 章 树结构实际应用................................................................................................................................................................................244
11.1 堆排序..................................................................................................................................................................................................... 244
11.1.1 堆排序基本介绍..............................................................................................................................................................244
11.1.2 堆排序基本思想..............................................................................................................................................................245
11.1.3 堆排序步骤图解说明......................................................................................................................................................245
11.1.4 堆排序代码实现..............................................................................................................................................................250
11.2 赫夫曼树.................................................................................................................................................................................................254
11.2.1 基本介绍..........................................................................................................................................................................254
11.2.2 赫夫曼树几个重要概念和举例说明..............................................................................................................................254
11.2.3 赫夫曼树创建思路图解..................................................................................................................................................255
11.2.4 赫夫曼树的代码实现......................................................................................................................................................256
11.3 赫夫曼编码.............................................................................................................................................................................................261
11.3.1 基本介绍..........................................................................................................................................................................261
11.3.2 原理剖析..........................................................................................................................................................................261
11.3.3 最佳实践-数据压缩(创建赫夫曼树)..............................................................................................................................264
11.3.4 最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据).................................................................................266
11.3.5 最佳实践-数据解压(使用赫夫曼编码解码)................................................................................................................. 268
11.3.6 最佳实践-文件压缩.........................................................................................................................................................271
11.3.7 最佳实践-文件解压(文件恢复)......................................................................................................................................273
11.3.8 代码汇总，把前面所有的方法放在一起......................................................................................................................275
11.3.9 赫夫曼编码压缩文件注意事项......................................................................................................................................294
11.4 二叉排序树.............................................................................................................................................................................................294
11.4.1 先看一个需求..................................................................................................................................................................294
11.4.2 解决方案分析..................................................................................................................................................................294
11.4.3 二叉排序树介绍..............................................................................................................................................................295
11.4.4 二叉排序树创建和遍历..................................................................................................................................................296
11.4.5 二叉排序树的删除..........................................................................................................................................................296
11.4.6 二叉排序树删除结点的代码实现:.................................................................................................................................298
11.4.7 课后练习：完成老师代码，并使用第二种方式来解决............................................................................................. 309
11.5 平衡二叉树(AVL 树)..............................................................................................................................................................................309
11.5.1 看一个案例(说明二叉排序树可能的问题)...................................................................................................................309
11.5.2 基本介绍..........................................................................................................................................................................310
11.5.3 应用案例-单旋转(左旋转)..............................................................................................................................................310
11.5.4 应用案例-单旋转(右旋转)..............................................................................................................................................312
11.5.5 应用案例-双旋转.............................................................................................................................................................313
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 VII页
第 第 12 章 章 多路查找树........................................................................................................................................................................................328
12.1 二叉树与 B 树........................................................................................................................................................................................ 328
12.1.1 二叉树的问题分析..........................................................................................................................................................328
12.1.2 多叉树..............................................................................................................................................................................328
12.1.3 B 树的基本介绍...............................................................................................................................................................329
12.2 2-3 树........................................................................................................................................................................................................329
12.2.1 2-3 树是最简单的 B 树结构, 具有如下特点:...............................................................................................................329
12.2.2 2-3 树应用案例................................................................................................................................................................ 330
12.2.3 其它说明..........................................................................................................................................................................330
12.3 B 树、B 树和 B*树................................................................................................................................................................................331
12.3.1 B 树的介绍.......................................................................................................................................................................331
12.3.2 B 树的介绍.......................................................................................................................................................................331
12.3.3 B 树的介绍......................................................................................................................................................................332
12.3.4 B*树的介绍......................................................................................................................................................................333
第 第 13 章 章 图........................................................................................................................................................................................................334
13.1 图基本介绍.............................................................................................................................................................................................334
13.1.1 为什么要有图..................................................................................................................................................................334
13.1.2 图的举例说明..................................................................................................................................................................334
13.1.3 图的常用概念..................................................................................................................................................................334
13.2 图的表示方式.........................................................................................................................................................................................336
13.2.1 邻接矩阵..........................................................................................................................................................................336
13.2.2 邻接表..............................................................................................................................................................................336
13.3 图的快速入门案例.................................................................................................................................................................................337
13.4 图的深度优先遍历介绍.........................................................................................................................................................................338
13.4.1 图遍历介绍......................................................................................................................................................................338
13.4.2 深度优先遍历基本思想..................................................................................................................................................338
13.4.3 深度优先遍历算法步骤..................................................................................................................................................338
13.4.4 深度优先算法的代码实现..............................................................................................................................................339
13.5 图的广度优先遍历.................................................................................................................................................................................340
13.5.1 广度优先遍历基本思想..................................................................................................................................................340
13.5.2 广度优先遍历算法步骤..................................................................................................................................................340
13.5.3 广度优先算法的图示......................................................................................................................................................341
13.6 广度优先算法的代码实现.....................................................................................................................................................................341
13.7 图的代码汇总.........................................................................................................................................................................................343
13.8 图的深度优先 VS 广度优先.................................................................................................................................................................351
第 第 14 章 章 程序员常用 10 种算法......................................................................................................................................................................352
14.1 二分查找算法(非递归)..........................................................................................................................................................................352
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 VIII页
14.1.1 二分查找算法(非递归)介绍...........................................................................................................................................352
14.1.2 二分查找算法(非递归)代码实现...................................................................................................................................352
14.2 分治算法.................................................................................................................................................................................................354
14.2.1 分治算法介绍..................................................................................................................................................................354
14.2.2 分治算法的基本步骤......................................................................................................................................................354
14.2.3 分治(Divide-and-Conquer(P))算法设计模式如下：.....................................................................................................355
14.2.4 分治算法最佳实践-汉诺塔............................................................................................................................................355
14.3 动态规划算法.........................................................................................................................................................................................357
14.3.1 应用场景-背包问题........................................................................................................................................................ 357
14.3.2 动态规划算法介绍..........................................................................................................................................................358
14.3.3 动态规划算法最佳实践-背包问题................................................................................................................................358
14.3.4 动态规划-背包问题的代码实现....................................................................................................................................360
14.4 KMP 算法................................................................................................................................................................................................ 363
14.4.1 应用场景-字符串匹配问题............................................................................................................................................364
14.4.2 暴力匹配算法..................................................................................................................................................................364
14.4.3 KMP 算法介绍.................................................................................................................................................................366
14.4.4 KMP 算法最佳应用-字符串匹配问题........................................................................................................................... 366
14.5 贪心算法.................................................................................................................................................................................................374
14.5.1 应用场景-集合覆盖问题................................................................................................................................................ 374
14.5.2 贪心算法介绍..................................................................................................................................................................374
14.5.3 贪心算法最佳应用-集合覆盖........................................................................................................................................375
14.5.4 贪心算法注意事项和细节..............................................................................................................................................380
14.6 普里姆算法.............................................................................................................................................................................................381
14.6.1 应用场景-修路问题........................................................................................................................................................ 381
14.6.2 最小生成树......................................................................................................................................................................381
14.6.3 普里姆算法介绍..............................................................................................................................................................382
14.6.4 普里姆算法最佳实践(修路问题)...................................................................................................................................383
14.7 克鲁斯卡尔算法.....................................................................................................................................................................................388
14.7.1 应用场景-公交站问题.................................................................................................................................................... 388
14.7.2 克鲁斯卡尔算法介绍......................................................................................................................................................388
14.7.3 克鲁斯卡尔算法图解说明..............................................................................................................................................389
3. 1 .1 克 鲁 斯 卡 尔 算 法 图 解 .................................................................................................................................390
3. 1 .2 克 鲁 斯 卡 尔 算 法 分 析 .................................................................................................................................392
3. 1 .3 如 何 判 断 是 否 构 成 回 路 - 举 例 说 明 ( 如 图 ) .................................................................................392
3. 1 .4 克 鲁 斯 卡 尔 算 法 的 代 码 说 明 ................................................................................................................393
14.7.4 克鲁斯卡尔最佳实践-公交站问题................................................................................................................................393
14.8 迪杰斯特拉算法.....................................................................................................................................................................................401
14.8.1 应用场景-最短路径问题................................................................................................................................................ 401
14.8.2 迪杰斯特拉(Dijkstra)算法介绍......................................................................................................................................402
尚硅谷 Java 数据结构和算法
更多 Java –大数据 –前端 –python 人工智能- 区块链 资料下载，可访问百度：尚硅谷官网
第 IX页
14.8.3 迪杰斯特拉(Dijkstra)算法过程......................................................................................................................................402
14.8.4 迪杰斯特拉(Dijkstra)算法最佳应用-最短路径............................................................................................................ 403
14.9 弗洛伊德算法.........................................................................................................................................................................................412
14.9.1 弗洛伊德(Floyd)算法介绍..............................................................................................................................................412
14.9.2 弗洛伊德(Floyd)算法图解分析......................................................................................................................................412
14.9.3 弗洛伊德(Floyd)算法最佳应用-最短路径....................................................................................................................415
14.10 马踏棋盘算法.......................................................................................................................................................................................419
14.10.1 马踏棋盘算法介绍和游戏演示....................................................................................................................................419
14.10.2 马踏棋盘游戏代码实现................................................................................................................................................420