数据结构与算法 Java语言描述2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

数据结构与算法 Java语言描述PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

前言1

第1章 算法及其复杂度1

1.1 计算机与算法1

1.1.1 过指定垂足的直角边1

1.1.2 三等分线段2

1.1.3 排序3

1.1.4 算法的定义5

1.2.2 时间复杂度及其度量6

1.2.1 三个层次6

1.2 算法性能的分析与评价6

1.2.3 空间复杂度8

1.3 算法复杂度及其分析8

1.3.1 O(1)——取非极端元素8

1.3.2 O(logn)——进制转换9

1.3.3 O(n)——数组求和10

1.3.4 O(n2)——起泡排序10

1.4 计算模型11

1.4.1 可解性11

1.3.5 O(2r)——幂函数11

1.4.2 有效可解12

1.4.3 下界12

1.5 递归12

1.5.1 线性递归13

1.5.2 递归算法的复杂度分析16

1.5.3 二分递归17

1.5.4 多分支递归20

2.1 栈23

第2章 栈与队列23

2.1.1 栈ADT24

2.1.2 基于数组的简单实现25

2.1.3 Java虚拟机中的栈28

2.1.4 栈应用实例30

2.2 队列34

2.2.1 队列ADT34

2.2.2 基于数组的实现36

2.2.3 队列应用实例38

2.3.1 单链表39

2.3 链表39

2.3.2 基于单链表实现栈43

2.3.3 基于单链表实现队列44

2.4 位置45

2.4.1 位置ADT45

2.4.2 位置接口46

2.5 双端队列46

2.5.1 双端队列ADT46

2.5.2 双端队列接口47

2.5.3 双向链表48

2.5.4 基于双向链表实现的双端队列49

第3章 向量、列表与序列55

3.1 向量与数组55

3.1.1 向量ADT56

3.1.2 基于数组的简单实现58

3.1.3 基于可扩充数组的实现59

3.1.4 java.util.ArrayList类和java.util.Vector类62

3.2.2 由秩到位置63

3.2.1 基于节点的操作63

3.2 列表63

3.2.3 列表ADT64

3.2.4 基于双向链表实现的列表67

3.3 序列72

3.3.1 序列ADT72

3.3.2 基于双向链表实现序列73

3.3.3 基于数组实现序列75

3.4 迭代器75

3.4.1 迭代器ADT76

3.4.2 迭代器接口77

3.4.3 迭代器的实现77

3.4.4 Java中的列表及迭代器79

第4章 树81

4.1 术语及性质81

4.1.1 节点的深度、树的深度与高度82

4.1.2 节点的度与内部节点、外部节点82

4.1.4 祖先、后代、子树和节点的高度83

4.1.3 路径83

4.1.5 共同祖先及最低共同祖先84

4.1.6 有序树、m叉树84

4.1.7 二叉树85

4.1.8 满二叉树与完全二叉树85

4.2 树ADT及其实现86

4.2.1 “父亲－长子－弟弟”模型86

4.2.2 树ADT87

4.2.4 基于链表实现树88

4.2.3 树的Java接口88

4.3 树的基本算法90

4.3.1 getSize()——统计（子）树的规模90

4.3.2 getHeight()——计算节点的高度90

4.3.3 getDepth()——计算节点的深度90

4.3.4 前序、后序遍历91

4.3.5 层次遍历92

4.3.6 树迭代器93

4.4.2 二叉树的Java接口95

4.4 二叉树ADT及其实现95

4.4.1 二叉树ADT95

4.4.3 二叉树类的实现98

4.5 二叉树的基本算法103

4.5.1 getSize()、getHeight()和getDepth()103

4.5.2 updateSize()103

4.5.3 updateHeight()104

4.5.4 updateDepth()105

4.5.5 secede()105

4.5.6 attachL()和attachR()106

4.5.7 二叉树的遍历107

4.5.8 直接前驱、直接后继的定位算法107

4.6 完全二叉树的Java实现108

4.6.1 完全二叉树的Java接口108

4.6.2 基于向量的实现109

第5章 优先队列113

5.1 优先级、关键码、全序关系与优先队列113

5.2.1 条目114

5.2 条目与比较器114

5.2.2 比较器115

5.2.3 Comparator接口及其实现116

5.3 优先队列ADT及其Java接口117

5.3.1 优先队列的ADT描述117

5.3.2 优先队列的Java接口118

5.3.3 基于优先队列的排序器119

5.5.1 基于无序列表的实现及分析120

5.5 用列表实现优先队列120

5.4 用向量实现优先队列120

5.5.2 基于有序列表的实现及分析122

5.6 选择排序与插入排序124

5.6.1 选择排序124

5.6.2 插入排序124

5.6.3 效率比较125

5.7 堆的定义及性质125

5.7.1 堆结构125

5.8 用堆实现优先队列126

5.7.2 完全性126

5.8.1 基于堆的优先队列及其实现127

5.8.2 插入与上滤129

5.8.3 删除与下滤130

5.8.4 改变任意节点的关键码132

5.8.5 建堆132

5.9 堆排序133

5.9.1 直接堆排序133

5.9.2 就地堆排序134

5.10.1 二叉编码树136

5.10 Huffman编码树136

5.10.2 最优编码树137

5.10.3 Huffman编码与Huffman编码树138

5.10.4 Huffman编码树的构造算法141

5.10.5 基于优先队列的Huffman编码树构造算法143

第6章 映射与词典145

6.1 映射145

6.1.1 映射的ADT描述146

6.1.2 映射的Java接口147

6.1.3 判等器148

6.1.4 java.util包中的映射类149

6.1.5 基于列表实现映射类149

6.2 散列表151

6.2.1 桶及桶数组151

6.2.2 散列函数151

6.2.3 散列码152

6.2.4 压缩函数154

6.2.5 冲突的普遍性154

6.2.6 解决冲突155

6.2.7 基于散列表实现映射类159

6.2.8 装填因子与重散列161

6.3 无序词典162

6.3.1 无序词典的ADT描述162

6.3.2 无序词典的Java接口163

6.3.3 列表式无序词典及其实现164

6.3.4 散列表式无序词典及其实现166

6.4 有序词典168

6.4.2 二分查找169

6.4.1 全序关系与有序查找表169

6.4.3 有序词典的ADT描述170

6.4.4 有序词典的Java接口171

6.4.5 基于有序查找表实现有序词典171

第7章 查找树175

7.1 二分查找树176

7.1.1 定义176

7.1.2 查找算法176

7.1.3 完全查找算法179

7.1.4 插入算法180

7.1.5 删除算法182

7.1.6 二分查找树节点类的实现183

7.1.7 二分查找树类的实现184

7.1.8 二分查找树的平均性能187

7.2 AVL树188

7.2.1 平衡二分查找树188

7.2.2 等价二分查找树188

7.2.3 等价变换189

7.2.4 AVL树190

7.2.5 插入节点后的重平衡191

7.2.6 节点删除后的重平衡195

7.2.7 AVL树的Java实现198

7.3 伸展树201

7.3.1 数据局部性201

7.3.2 逐层伸展201

7.3.3 双层伸展203

7.3.4 分摊复杂度205

7.3.5 伸展树的Java实现207

7.3.6 插入210

7.3.7 删除211

7.4 B－树212

7.4.1 分级存储212

7.4.2 B－树的定义213

7.4.3 关键码的查找214

7.4.4 性能分析214

7.4.5 上溢节点的处理216

7.4.6 关键码的插入217

7.4.7 下溢节点的处理220

7.4.8 关键码的删除221

第8章 排序223

8.1 归并排序223

8.1.1 分治策略223

8.1.2 时间复杂度224

8.1.3 归并算法225

8.1.4 Mergesort的Java实现226

8.2 快速排序227

8.2.1 分治策略227

8.2.2 轴点228

8.2.3 划分算法228

8.2.4 Quicksort的Java实现229

8.2.5 时间复杂度230

8.3复杂 度下界231

8.3.1 比较树与基于比较的算法232

8.3.2 下界232

9.1 串及其ADT描述235

第9章 串235

9.2 串模式匹配236

9.2.1 概念与记号236

9.2.2 问题237

9.2.3 算法效率的测试与评价238

9.3 蛮力算法238

9.3.1 算法描述238

9.3.2 算法实现239

9.4.1 蛮力算法的改进240

9.3.3 算法分析240

9.4 KMP算法240

9.4.2 next[]表的定义及含义242

9.4.3 KMP算法描述243

9.4.4 next[]表的特殊情况243

9.4.5 next[]表的构造243

9.4.6 next[]表的改进244

9.4.7 KMP算法的Java实现245

9.5 BM算法247

9.4.8 性能分析247

9.5.1 坏字符策略248

9.5.2 好后缀策略250

9.5.3 BM算法251

9.5.4 BM算法的Java实现252

9.5.5 性能255

第10章 图257

10.1 概述257

10.1.3 简单图258

10.1.2 度258

10.1.1 无向图、混合图及有向图258

10.1.4 图的复杂度259

10.1.5 子图、生成子图与限制子图259

10.1.6 通路、环路及可达分量260

10.1.7 连通性、等价类与连通分量261

10.1.8 森林、树以及无向图的生成树262

10.1.9 有向图的生成树263

10.1.10 带权网络263

10.2.1 图264

10.2 抽象数据类型264

10.2.2 顶点265

10.2.3 边267

10.3 邻接矩阵268

10.3.1 表示方法268

10.3.2 时间性能268

10.3.3 空间性能269

10.4 邻接表270

10.4.1 顶点表和边表270

10.4.2 顶点与邻接边表271

10.4.3 边273

10.4.4 基于邻接表实现图结构275

10.5 图遍历及其算法模板277

10.6 深度优先遍历279

10.6.1 深度优先遍历算法279

10.6.2 边分类280

10.6.3 可达分量与DFS树281

10.6.4 深度优先遍历算法模板282

10.6.5 可达分量算法284

10.6.6 单强连通分量算法285

10.6.7 强连通分量分解算法286

10.6.8 浓缩图与弱连通性286

10.7 广度优先遍历287

10.7.1 广度优先遍历算法287

10.7.2 边分类288

10.7.3 可达分量与BFS树289

10.7.4 广度优先遍历算法模板289

10.7.5 最短距离算法290

10.8 最佳优先遍历291

10.8.1 最佳优先遍历算法291

10.8.2 最佳优先遍历算法模板292

10.8.3 最短路径294

10.8.4 最短路径序列296

10.8.5 Dijkstra算法297

10.8.6 最小生成树300

10.8.7 Prim-Jarnik算法302

DSA类关系图307