数据结构 C++语言版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构 C++语言版PDF格式电子书版下载

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

第1章 绪论1

1.1 计算机与算法2

1.1.1 古埃及人的绳索2

1.1.2 欧几里德的尺规3

1.1.3 起泡排序4

1.1.4 算法5

1.1.5 算法效率8

1.2 复杂度度量8

1.2.1 问题规模、运行时间及时间复杂度9

1.2.2 渐进复杂度9

1.2.3 空间复杂度11

1.3 复杂度分析12

1.3.1 常数复杂度O（1）12

1.3.2 对数复杂度O（logn）13

1.3.3 线性复杂度O（n）14

1.3.4 多项式复杂度O（polynomial（n））15

1.3.5 指数复杂度O（2n）15

1.3.6 复杂度层次16

1.3.7 输入规模16

1.4 递归17

1.4.1 线性递归17

1.4.2 递归分析18

1.4.3 递归模式20

1.4.4 递归消除22

1.4.5 二分递归24

1.5 抽象数据类型27

习题28

第2章 向量31

2.1 从数组到向量32

2.1.1 数组32

2.1.2 向量32

2.2 接口33

2.2.1 ADT接口33

2.2.2 操作实例34

2.2.3 Vector模板类34

2.3 构造与析构36

2.3.1 默认构造方法36

2.3.2 基于复制的构造方法36

2.3.3 析构方法37

2.4 动态空间管理37

2.4.1 静态空间管理37

2.4.2 可扩充向量38

2.4.3 扩容38

2.4.4 分摊分析39

2.4.5 缩容40

2.5 向量41

2.5.1 直接引用元素41

2.5.2 置乱器41

2.5.3 判等器与比较器42

2.5.4 无序查找43

2.5.5 插入44

2.5.6 删除45

2.5.7 唯一化46

2.5.8 遍历47

2.6 有序向量49

2.6.1 比较器49

2.6.2 有序性甄别49

2.6.3 唯一化49

2.6.4 查找52

2.6.5 二分查找（版本A）53

2.6.6 Fibonacci查找56

2.6.7 二分查找（版本B）59

2.6.8 二分查找（版本C）60

2.7 排序与下界61

2.7.1 有序性61

2.7.2 排序及其分类62

2.7.3 下界62

2.7.4 比较树63

2.7.5 估计下界64

2.8 排序器64

2.8.1 统一入口64

2.8.2 起泡排序65

2.8.3 归并排序66

习题69

第3章 列表73

3.1 从向量到列表74

3.1.1 从静态存储到动态存储74

3.1.2 由秩到位置75

3.1.3 列表75

3.2 接口75

3.2.1 列表节点75

3.2.2 列表76

3.3 列表79

3.3.1 头、尾节点79

3.3.2 默认构造方法79

3.3.3 由秩到位置的转换80

3.3.4 查找80

3.3.5 插入81

3.3.6 基于复制的构造83

3.3.7 删除84

3.3.8 析构85

3.3.9 唯一化86

3.3.10 遍历86

3.4 有序列表87

3.4.1 唯一化87

3.4.2 查找88

3.5 排序器88

3.5.1 统一入口88

3.5.2 插入排序89

3.5.3 选择排序91

3.5.4 归并排序92

习题94

第4章 栈与队列97

4.1 栈98

4.1.1 概述98

4.1.2 ADT接口99

4.1.3 操作实例99

4.1.4 Stack模板类99

4.2 栈与递归100

4.2.1 递归的实现101

4.2.2 避免递归102

4.3 典型应用103

4.3.1 逆序输出103

4.3.2 递归嵌套105

4.3.3 延迟缓冲108

4.3.4 逆波兰表达式113

4.4 试探回溯法116

4.4.1 试探与回溯116

4.4.2 八皇后117

4.4.3 迷宫寻径119

4.5 队列122

4.5.1 概述122

4.5.2 ADT接口122

4.5.3 操作实例123

4.5.4 Queue模板类124

4.6 队列应用124

4.6.1 循环分配器124

4.6.2 银行服务模拟125

习题126

第5章 二叉树129

5.1 二叉树及其表示130

5.1.1 树130

5.1.2 二叉树131

5.1.3 多叉树132

5.2 编码树134

5.2.1 二进制编码134

5.2.2 二叉编码树136

5.3 二叉树的实现137

5.3.1 二叉树节点137

5.3.2 二叉树节点操作接口140

5.3.3 二叉树141

5.4 Huffman编码146

5.4.1 PFC编码146

5.4.2 最优编码树149

5.4.3 Huffman编码树152

5.4.4 Huffman编码算法154

5.5 遍历160

5.5.1 递归式遍历161

5.5.2 迭代版先序遍历163

5.5.3 迭代版中序遍历165

5.5.4 迭代版后序遍历169

5.5.5 层次遍历171

习题172

第6章 图175

6.1 概述176

6.2 抽象数据类型179

6.2.1 操作接口179

6.2.2 Graph模板类180

6.3 邻接矩阵181

6.3.1 原理181

6.3.2 实现182

6.3.3 时间性能184

6.3.4 空间性能184

6.4 邻接表184

6.4.1 原理184

6.4.2 复杂度184

6.5 图遍历算法概述185

6.6 广度优先搜索186

6.6.1 策略186

6.6.2 实现186

6.6.3 实例187

6.6.4 复杂度187

6.6.5 应用188

6.7 深度优先搜索188

6.7.1 策略188

6.7.2 实现189

6.7.3 实例190

6.7.4 复杂度191

6.7.5 应用192

6.8 拓扑排序192

6.8.1 应用192

6.8.2 有向无环图193

6.8.3 算法193

6.8.4 实现193

6.8.5 实例194

6.8.6 复杂度194

6.9 双连通域分解195

6.9.1 关节点与双连通域195

6.9.2 蛮力算法195

6.9.3 算法196

6.9.4 实现196

6.9.5 实例198

6.9.6 复杂度199

6.10 优先级搜索199

6.10.1 优先级与优先级数199

6.10.2 基本框架200

6.10.3 复杂度201

6.11 最小支撑树201

6.11.1 支撑树201

6.11.2 最小支撑树201

6.11.3 歧义性201

6.11.4 蛮力算法202

6.11.5 Prim算法202

6.12 最短路径204

6.12.1 最短路径树204

6.12.2 歧义性205

6.12.3 Dijkstra算法205

习题208

第7章 搜索树211

7.1 搜索212

7.1.1 循关键码访问212

7.1.2 词条213

7.1.3 序与比较器213

7.2 二叉搜索树213

7.2.1 顺序性213

7.2.2 中序遍历序列214

7.2.3 BST模板类214

7.2.4 查找算法及其实现215

7.2.5 插入算法及其实现217

7.2.6 删除算法及其实现218

7.3 平衡二叉搜索树220

7.3.1 树高与性能220

7.3.2 理想平衡与适度平衡221

7.3.3 等价二叉搜索树222

7.3.4 等价变换与局部调整222

7.4 AVL树223

7.4.1 AVL树223

7.4.2 节点插入225

7.4.3 节点删除228

7.4.4 统一重平衡算法230

习题232

第8章 高级搜索树235

8.1 伸展树236

8.1.1 局部性236

8.1.2 逐层伸展237

8.1.3 双层伸展238

8.1.4 分摊分析240

8.1.5 伸展树的实现243

8.2 B-树247

8.2.1 多路平衡搜索247

8.2.2 ADT接口及其实现249

8.2.3 关键码查找251

8.2.4 性能分析252

8.2.5 关键码插入253

8.2.6 上溢与分裂254

8.2.7 关键码删除257

8.2.8 下溢与合并258

8.3 红黑树263

8.3.1 概述263

8.3.2 红黑树接口定义265

8.3.3 节点插入算法266

8.3.4 节点删除算法269

8.4 kd-树275

8.4.1 范围查询275

8.4.2 kd-树278

8.4.3 基于2d-树的范围查询算法279

习题280

第9章 词典283

9.1 词典284

9.1.1 操作接口284

9.1.2 操作实例285

9.1.3 接口定义286

9.1.4 判等器286

9.1.5 实现方法287

9.2 跳转表287

9.2.1 Skiplist模板类287

9.2.2 总体逻辑结构288

9.2.3 四联表288

9.2.4 查找290

9.2.5 空间复杂度292

9.2.6 时间复杂度292

9.2.7 插入293

9.2.8 删除296

9.3 散列表298

9.3.1 完美散列298

9.3.2 装填因子与空间利用率299

9.3.3 散列函数300

9.3.4 散列表303

9.3.5 冲突及其排解305

9.3.6 开放定址策略307

9.3.7 查找与删除309

9.3.8 插入310

9.3.9 更多开放定址策略312

9.3.10 散列码转换314

9.4 散列应用316

9.4.1 桶排序316

9.4.2 最大间隙317

9.4.3 基数排序318

习题319

第10章 优先级队列323

10.1 优先级队列324

10.1.1 优先级与优先级队列324

10.1.2 关键码、比较器与偏序关系325

10.1.3 操作接口325

10.1.4 操作实例：选择排序325

10.1.5 接口定义326

10.1.6 应用实例：Huffman编码树326

10.2 堆328

10.2.1 完全二叉堆329

10.2.2 元素插入331

10.2.3 元素删除333

10.2.4 建堆335

10.2.5 就地堆排序338

10.3 左式堆341

10.3.1 堆合并341

10.3.2 单侧倾斜341

10.3.3 PQ_LeftHeap模板类342

10.3.4 空节点路径长度342

10.3.5 左倾性与左式堆343

10.3.6 右侧链343

10.3.7 合并算法344

10.3.8 合并操作merge（）的实现344

10.3.9 实例345

10.3.10 复杂度345

10.3.11 基于合并的插入和删除操作346

习题347

第11章 串349

11.1 串及串匹配350

11.1.1 串350

11.1.2 串匹配351

11.1.3 测评标准与策略352

11.2 蛮力算法353

11.2.1 算法描述353

11.2.2 算法实现353

11.2.3 时间复杂度354

11.3 KMP算法355

11.3.1 构思355

11.3.2 next表356

11.3.3 KMP算法357

11.3.4 next［0］＝-1357

11.3.5 构造next表358

11.3.6 性能分析358

11.3.7 继续改进359

11.4 BM算法361

11.4.1 思路与框架361

11.4.2 坏字符策略362

11.4.3 好后缀策略364

11.4.4 综合性能368

11.5 Karp-Rabin算法369

11.5.1 构思369

11.5.2 算法与实现370

习题373

第12章 排序375

12.1 快速排序376

12.1.1 分治策略376

12.1.2 轴点376

12.1.3 快速排序算法377

12.1.4 快速划分算法377

12.1.5 复杂度379

12.1.6 应对退化381

12.2 选取与中位数382

12.2.1 概述382

12.2.2 主流数383

12.2.3 归并向量的中位数385

12.2.4 基于优先级队列的选取388

12.2.5 基于快速划分的选取389

12.2.6 k-选取算法390

12.3 希尔排序392

12.3.1 递减增量策略392

12.3.2 增量序列394

习题397

附录399

插图索引400

表格索引406

算法索引407

代码索引408

关键词索引414