数据结构、算法与应用 C++语言描述 原书第2版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构、算法与应用 C++语言描述 原书第2版PDF格式电子书版下载

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

第一部分 预备知识2

第1章 C++回顾2

1.1 引言2

1.2 函数与参数3

1.2.1 传值参数3

1.2.2 模板函数4

1.2.3 引用参数4

1.2.4 常量引用参数5

1.2.5 返回值5

1.2.6 重载函数6

1.3 异常7

1.3.1 抛出异常7

1.3.2 处理异常7

1.4 动态存储空间分配9

1.4.1 操作符new9

1.4.2 一维数组9

1.4.3 异常处理9

1.4.4 操作符delete10

1.4.5 二维数组10

1.5 自有数据类型12

1.5.1 类currency12

1.5.2 一种不同的描述方法18

1.5.3 操作符重载20

1.5.4 友元和保护性类成员22

1.5.5 增加＃ifndef、＃define和＃endif语句23

1.6 异常类illegalParameterValue24

1.7 递归函数25

1.7.1 递归的数学函数25

1.7.2 归纳25

1.7.3 C++递归函数26

1.8 标准模板库30

1.9 测试与调试32

1.9.1 什么是测试32

1.9.2 测试数据的设计34

1.9.3 调试36

1.10 参考及推荐读物37

第2章 程序性能分析38

2.1 什么是程序性能38

2.2 空间复杂度39

2.2.1 空间复杂度的组成39

2.2.2 举例42

2.3 时间复杂度44

2.3.1 时间复杂度的组成44

2.3.2 操作计数45

2.3.3 最好、最坏和平均操作计数48

2.3.4 步数53

第3章 渐近记法64

3.1 引言64

3.2 渐近记法65

3.2.1 大O记法65

3.2.2 渐近记法Ω和Θ67

3.3 渐近数学（可选）69

3.3.1 大O记法69

3.3.2 Ω记法71

3.3.3 Θ记法72

3.3.4 小o记法73

3.3.5 特性73

3.4 复杂度分析举例75

3.5 实际复杂度78

3.6 参考及推荐读物80

第4章 性能测量81

4.1 引言81

4.2 选择实例的大小82

4.3 设计测试数据82

4.4 实验设计82

4.5 高速缓存87

4.5.1 简单计算机模型87

4.5.2 缓存未命中对运行时间的影响87

4.5.3 矩阵乘法88

4.6 参考及推荐读物90

第二部分 数据结构92

第5章 线性表——数组描述92

5.1 数据对象和数据结构92

5.2 线性表数据结构93

5.2.1 抽象数据类型linearList94

5.2.2 抽象类linearList94

5.3 数组描述95

5.3.1 描述95

5.3.2 变长一维数组96

5.3.3 类arrayList97

5.3.4 C++迭代器102

5.3.5 arrayList的一个迭代器103

5.4 vector的描述107

5.5 在一个数组中实现的多重表109

5.6 性能测量111

5.7 参考及推荐读物112

第6章 线性表——链式描述113

6.1 单向链表113

6.1.1 描述113

6.1.2 结构chainNode114

6.1.3 类chain115

6.1.4 抽象数据类型linearList的扩充121

6.1.5 类extendedChain121

6.1.6 性能测量122

6.2 循环链表和头节点126

6.3 双向链表128

6.4 链表用到的词汇表129

6.5 应用130

6.5.1 箱子排序130

6.5.2 基数排序134

6.5.3 凸包135

6.5.4 并查集137

第7章 数组和矩阵146

7.1 数组146

7.1.1 抽象数据类型146

7.1.2 C++数组的索引147

7.1.3 行主映射和列主映射147

7.1.4 用数组的数组来描述148

7.1.5 行主描述和列主描述149

7.1.6 不规则二维数组149

7.2 矩阵151

7.2.1 定义和操作151

7.2.2 类matrix152

7.3 特殊矩阵157

7.3.1 定义和应用157

7.3.2 对角矩阵158

7.3.3 三对角矩阵159

7.3.4 三角矩阵160

7.3.5 对称矩阵161

7.4 稀疏矩阵164

7.4.1 基本概念164

7.4.2 用单个线性表描述165

7.4.3 用多个线性表描述170

7.4.4 性能测量172

第8章 栈175

8.1 定义和应用175

8.2 抽象数据类型177

8.3 数组描述178

8.3.1 作为一个派生类实现178

8.3.2 类arrayStack179

8.3.3 性能测量181

8.4 链表描述182

8.4.1 类derivedLinkedStack182

8.4.2 类linkedStack183

8.4.3 性能测量184

8.5 应用184

8.5.1 括号匹配184

8.5.2 汉诺塔185

8.5.3 列车车厢重排187

8.5.4 开关盒布线191

8.5.5 离线等价类问题193

8.5.6 迷宫老鼠196

8.6 参考及推荐读物204

第9章 队列205

9.1 定义和应用205

9.2 抽象数据类型206

9.3 数组描述207

9.3.1 描述207

9.3.2 类arrayQueue209

9.4 链表描述212

9.5 应用214

9.5.1 列车车厢重排214

9.5.2 电路布线217

9.5.3 图元识别219

9.5.4 工厂仿真222

9.6 参考及推荐读物234

第10章 跳表和散列235

10.1 字典235

10.2 抽象数据类型236

10.3 线性表描述237

10.4 跳表表示（可选）239

10.4.1 理想情况239

10.4.2 插入和删除241

10.4.3 级的分配241

10.4.4 结构skipNode242

10.4.5 类skipList242

10.4.6 skipList方法的复杂度246

10.5 散列表描述246

10.5.1 理想散列246

10.5.2 散列函数和散列表248

10.5.3 线性探查250

10.5.4 链式散列255

10.6 一个应用——文本压缩260

10.6.1 LZW压缩260

10.6.2 LZW压缩的实现261

10.6.3 LZW解压缩264

10.6.4 LZW解压缩的实现265

10.6.5 性能评价268

10.7 参考及推荐读物269

第11章 二叉树和其他树270

11.1 树270

11.2 二叉树273

11.3 二叉树的特性274

11.4 二叉树的描述275

11.4.1 数组描述275

11.4.2 链表描述276

11.5 二叉树常用操作277

11.6 二叉树遍历277

11.7 抽象数据类型BinaryTree281

11.8 类linkedBinaryTree282

11.9 应用285

11.9.1 设置信号放大器285

11.9.2 并查集288

11.10 参考及推荐读物296

第12章 优先级队列297

12.1 定义和应用297

12.2 抽象数据类型298

12.3 线性表299

12.4 堆299

12.4.1 定义299

12.4.2 大根堆的插入300

12.4.3 大根堆的删除301

12.4.4 大根堆的初始化301

12.4.5 类maxHeap302

12.4.6 堆和STL305

12.5 左高树306

12.5.1 高度优先与宽度优先的最大及最小左高树306

12.5.2 最大HBLT的插入308

12.5.3 最大HBLT的删除308

12.5.4 两棵最大HBLT的合并308

12.5.5 初始化309

12.5.6 类maxHblt310

12.6 应用313

12.6.1 堆排序313

12.6.2 机器调度314

12.6.3 霍夫曼编码317

12.7 参考及推荐读物322

第13章 竞赛树323

13.1 赢者树和应用323

13.2 抽象数据类型WinnerTree326

13.3 赢者树的实现327

13.3.1 表示327

13.3.2 赢者树的初始化328

13.3.3 重新组织比赛328

13.3.4 类completeWinnerTree328

13.4 输者树329

13.5 应用331

13.5.1 用最先适配法求解箱子装载问题331

13.5.2 用相邻适配法求解箱子装载问题335

13.6 参考及推荐读物337

第14章 搜索树338

14.1 定义338

14.1.1 二叉搜索树338

14.1.2 索引二叉搜索树340

14.2 抽象数据类型340

14.3 二叉搜索树的操作和实现341

14.3.1 类binarySearchTree341

14.3.2 搜索342

14.3.3 插入342

14.3.4 删除343

14.3.5 二叉搜索树的高度346

14.4 带有相同关键字元素的二叉搜索树347

14.5 索引二叉搜索树348

14.6 应用349

14.6.1 直方图349

14.6.2 箱子装载问题的最优匹配法351

14.6.3 交叉分布353

第15章 平衡搜索树359

15.1 AVL树360

15.1.1 定义360

15.1.2 AVL树的高度361

15.1.3 AVL树的描述361

15.1.4 AVL搜索树的搜索361

15.1.5 AVL搜索树的插入361

15.1.6 AVL搜索树的删除364

15.2 红-黑树367

15.2.1 基本概念367

15.2.2 红-黑树的描述368

15.2.3 红-黑树的搜索368

15.2.4 红-黑树的插入368

15.2.5 红-黑树的删除371

15.2.6 实现细节的考虑及复杂性分析374

15.3 分裂树376

15.3.1 介绍376

15.3.2 分裂树的操作376

15.3.3 折算复杂性378

15.4 B-树379

15.4.1 索引顺序访问方法379

15.4.2 m叉搜索树380

15.4.3 m阶B-树381

15.4.4 B-树的高度382

15.4.5 B-树的搜索382

15.4.6 B-树的插入382

15.4.7 B-树的删除384

15.4.8 节点结构387

15.5 参考及推荐读物389

第16章 图390

16.1 基本概念390

16.2 应用和更多的概念391

16.3 特性394

16.4 抽象数据类型graph395

16.5 无权图的描述396

16.5.1 邻接矩阵396

16.5.2 邻接链表397

16.5.3 邻接数组398

16.6 加权图的描述400

16.7 类实现400

16.7.1 不同的类400

16.7.2 邻接矩阵类401

16.7.3 扩充chain类405

16.7.4 链表类405

16.8 图的遍历407

16.8.1 广度优先搜索407

16.8.2 广度优先搜索的实现408

16.8.3 方法graph∷bfs的复杂性分析409

16.8.4 深度优先搜索410

16.8.5 深度优先搜索的实现411

16.8.6 方法graph：：dfs的复杂性分析412

16.9 应用412

16.9.1 寻找一条路径412

16.9.2 连通图及其构成414

16.9.3 生成树415

第三部分 算法设计方法420

第17章 贪婪算法420

17.1 最优化问题420

17.2 贪婪算法思想421

17.3 应用424

17.3.1 货箱装载424

17.3.2 0/1背包问题425

17.3.3 拓扑排序427

17.3.4 二分覆盖430

17.3.5 单源最短路径433

17.3.6 最小成本生成树436

17.4 参考及推荐读物445

第18章 分而治之446

18.1 算法思想446

18.2 应用453

18.2.1 残缺棋盘453

18.2.2 归并排序455

18.2.3 快速排序459

18.2.4 选择464

18.2.5 相距最近的点对466

18.3 解递归方程474

18.4 复杂度的下限475

18.4.1 最小最大问题的下限476

18.4.2 排序算法的下限477

第19章 动态规划479

19.1 算法思想479

19.2 应用481

19.2.1 0/1背包问题481

19.2.2 矩阵乘法链484

19.2.3 所有顶点对之间的最短路径489

19.2.4 带有负值的单源最短路径492

19.2.5 网组的无交叉子集496

19.3 参考及推荐读物501

第20章 回溯法502

20.1 算法思想502

20.2 应用506

20.2.1 货箱装载506

20.2.2 0/1背包问题512

20.2.3 最大完备子图515

20.2.4 旅行商问题517

20.2.5 电路板排列519

第21章 分支定界525

21.1 算法思想525

21.2 应用528

21.2.1 货箱装载528

21.2.2 0/1背包问题535

21.2.3 最大完备子图536

21.2.4 旅行商问题538

21.2.5 电路板排列541