Sartaj Sahni，多年来一直从事数据结构和算法方面的研究和教育工作，具有丰富的教学经验，曾获得IEEE计算机协会1997年Taylor L. Booth教育奖。他撰写了多部有关数据结构和算法方面的着作。本书是他在该领域为广大读者奉献的又一力作 。

译者简介：

汪诗林，1968年3月生，国防科技大学计算机学院在职博士。近年来主要从事计算机软体、资料库、多媒体及虚拟现实等领域的教学和研究工作，独立完成多项软体研製任务，共发表教学和科研论文近30篇，获部委级科技进步成果二等奖2项，三等奖4项，获校级优秀教学成果三等奖1项。编写及编译教材各1部(《数字逻辑》、《最新人工智慧语言——CommonLisp及CLOS的系统开发方法》)。1997年参加全国第一届863高级技术人才培训班。

王广芳，1938年2月生，国防科技大学计算机学院教授。多年来从事计算机软体的教学工作和科研工作，特别是数据结构、作业系统的教学与研究工作。编着出版《数据结构》、《作业系统原理与方法》、((作业系统原理》等教材。曾获国家级优秀教学成果一等奖1项，部委级优秀教学成果二等奖1项。参加多项有关计算机软体的研製工作，特别是有关作业系统的研製工作，曾获部委级科技进步一等奖2项、二等奖3项、3等奖2项。

《数据结构、算法与套用:C++语言描述》为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，《数据结构、算法与套用:C++语言描述》不仅仅介绍了理论知识，还提供了50多个套用实例及600多道练习题。

“纵览全书可以看出作者具有丰富的教材编写经验。它是一本新的、有关数据结构和算法的教材，适合于当前计算机本科教学的需要。”

——Sang W.Lee，密西根大学

“注重套用不仅可以使课堂教学更生动，而且可以激励学生投身于相关的套用。”

——Yu Lo C.Chang，新汉普郡大学

译者序

前言

第一部分 预备知识

第1章 C++程式设计1

1.1 引言1

1.2 函式与参数2

1.2.1 传值参数2

1.2.2 模板函式3

1.2.3 引用参数3

1.2.4 常量引用参数4

1.2.5 返回值4

1.2.6 递归函式5

1.3 动态存储分配9

1.3.1 操作符new9

1.3.2 一维数组9

1.3.3 异常处理10

1.3.4 操作符delete10

1.3.5 二维数组10

1.4 类13

1.4.1 类Currency13

1.4.2 使用不同的描述方法18

1.4.3 操作符重载20

1.4.4 引发异常22

1.4.5 友元和保护类成员23

1.4.6 增加#ifndef, #define和#endif语句24

1.5 测试与调试24

1.5.1 什幺是测试24

1.5.2 设计测试数据26

1.5.3 调试28

1.6 参考及推荐读物29

第2章 程式性能30

2.1 引言30

2.2 空间複杂性31

2.2.1 空间複杂性的组成31

2.2.2 举例35

2.3 时间複杂性37

2.3.1 时间複杂性的组成37

2.3.2 操作计数37

2.3.3 执行步数44

2.4 渐进符号（O、 健?、 o）55

2.4.1 大写O符号56

2.4.2 椒??58

2.4.3 符号59

2.4.4 小写o符号60

2.4.5 特性60

2.4.6 複杂性分析举例61

2.5 实际複杂性66

2.6 性能测量68

2.6.1 选择实例的大小69

2.6.2 设计测试数据69

2.6.3 进行实验69

2.7 参考及推荐读物74

第二部分 数据结构

第3章 数据描述75

3.1 引言75

3.2 线性表76

3.3 公式化描述77

3.3.1 基本概念77

3.3.2 异常类NoMem79

3.3.3 操作79

3.3.4 评价83

3.4 鍊表描述86

3.4.1 类ChainNode 和Chain86

3.4.2 操作88

3.4.3 扩充类Chain91

3.4.4 鍊表遍历器类92

3.4.5 循环鍊表93

3.4.6 与公式化描述方法的比较94

3.4.7 双向鍊表95

3.4.8 小结96

3.5 间接定址99

3.5.1 基本概念99

3.5.2 操作100

3.6 模拟指针102

3.6.1 SimSpace的操作103

3.6.2 採用模拟指针的鍊表106

3.7 描述方法的比较110

3.8 套用111

3.8.1 箱子排序111

3.8.2 基数排序116

3.8.3 等价类117

3.8.4 凸包122

3.9 参考及推荐读物127

第4章 数组和矩阵128

4.1 数组128

4.1.1 抽象数据类型128

4.1.2 C++数组129

4.1.3 行主映射和列主映射129

4.1.4 类Array1D131

4.1.5 类Array2D133

4.2 矩阵137

4.2.1 定义和操作137

4.2.2 类Matrix138

4.3 特殊矩阵141

4.3.1 定义和套用141

4.3.2 对角矩阵143

4.3.3 三对角矩阵144

4.3.4 三角矩阵145

4.3.5 对称矩阵146

4.4 稀疏矩阵149

4.4.1 基本概念149

4.4.2 数组描述149

4.4.3 鍊表描述154

第5章 堆叠161

5.1 抽象数据类型161

5.2 派生类和继承162

5.3 公式化描述163

5.3.1 Stack的效率164

5.3.2 自定义Stack164

5.4 鍊表描述166

5.5 套用169

5.5.1 括弧匹配169

5.5.2 汉诺塔170

5.5.3 火车车厢重排172

5.5.4 开关盒布线176

5.5.5 离线等价类问题178

5.5.6 迷宫老鼠180

5.6 参考及推荐读物188

第6章 伫列189

6.1 抽象数据类型189

6.2 公式化描述190

6.3 鍊表描述194

6.4 套用197

6.4.1 火车车厢重排197

6.4.2 电路布线201

6.4.3 识别图元204

6.4.4 工厂仿真206

6.5 参考及推荐读物217

第7章 跳表和散列218

7.1 字典218

7.2 线性表描述219

7.3 跳表描述222

7.3.1 理想情况222

7.3.2 插入和删除223

7.3.3 级的分配224

7.3.4 类SkipNode224

7.3.5 类SkipList225

7.3.6 複杂性229

7.4 散列表描述229

7.4.1 理想散列229

7.4.2 线性开型定址散列230

7.4.3 鍊表散列234

7.5 套用——文本压缩238

7.5.1 LZW压缩239

7.5.2 LZW压缩的实现239

7.5.3 LZW解压缩243

7.5.4 LZW解压缩的实现243

7.6 参考及推荐读物247

第8章 二叉树和其他树248

8.1 树248

8.2 二叉树251

8.3 二叉树的特性252

8.4 二叉树描述253

8.4.1 公式化描述253

8.4.2 鍊表描述254

8.5 二叉树常用操作256

8.6 二叉树遍历256

8.7 抽象数据类型BinaryTree259

8.8 类BinaryTree260

8.9 抽象数据类型及类的扩充263

8.9.1 输出263

8.9.2 删除264

8.9.3 计算高度264

8.9.4 统计节点数265

8.10 套用265

8.10.1 设定信号放大器265

8.10.2 线上等价类268

8.11 参考及推荐读物275

第9章 优先伫列276

9.1 引言276

9.2 线性表277

9.3 堆278

9.3.1 定义278

9.3.2 最大堆的插入279

9.3.3 最大堆的删除279

9.3.4 最大堆的初始化280

9.3.5 类MaxHeap281

9.4 左高树285

9.4.1 高度与宽度优先的最大及最小左高树285

9.4.2 最大HBLT的插入287

9.4.3 最大HBLT的删除287

9.4.4 合併两棵最大HBLT287

9.4.5 初始化最大HBLT289

9.4.6 类MaxHBLT289

9.5 套用293

9.5.1 堆排序293

9.5.2 机器调度294

9.5.3 霍夫曼编码297

9.6 参考及推荐读物302

第10章 竞赛树303

10.1 引言303

10.2 抽象数据类型WinnerTree306

10.3 类WinnerTree307

10.3.1 定义307

10.3.2 类定义307

10.3.3 构造函式、析构函式及Winner函式308

10.3.4 初始化赢者树308

10.3.5 重新组织比赛310

10.4 输者树311

10.5 套用312

10.5.1 用最先匹配法求解箱子装载问题312

10.5.2 用相邻匹配法求解箱子装载问题316

第11章 搜寻树319

11.1 二叉搜寻树320

11.1.1 基本概念320

11.1.2 抽象数据类型BSTree和IndexedBSTree321

11.1.3 类BSTree322

11.1.4 搜寻322

11.1.5 插入323

11.1.6 删除324

11.1.7 类DBSTree326

11.1.8 二叉搜寻树的高度327

11.2 AVL树328

11.2.1 基本概念328

11.2.2 AVL树的高度328

11.2.3 AVL树的描述329

11.2.4 AVL搜寻树的搜寻329

11.2.5 AVL搜寻树的插入329

11.2.6 AVL搜寻树的删除332

11.3 红－黑树334

11.3.1 基本概念334

11.3.2 红－黑树的描述336

11.3.3 红－黑树的搜寻336

11.3.4 红－黑树的插入336

11.3.5 红－黑树的删除339

11.3.6 实现细节的考虑及複杂性分析343

11.4 B－树344

11.4.1 索引顺序访问方法344

11.4.2 m 叉搜寻树345

11.4.3 m 序B－树346

11.4.4 B－树的高度347

11.4.5 B－树的搜寻348

11.4.6 B－树的插入348

11.4.7 B－树的删除350

11.4.8 节点结构353

11.5 套用354

11.5.1 直方图354

11.5.2 用最优匹配法求解箱子装载问题357

11.5.3 交叉分布359

11.6 参考及推荐读物363

第12章 图365

12.1 基本概念365

12.2 套用366

12.3 特性368

12.4 抽象数据类型Graph和Digraph370

12.5 无向图和有向图的描述371

12.5.1 邻接矩阵371

12.5.2 邻接压缩表373

12.5.3 邻接鍊表374

12.6 网路描述375

12.7 类定义376

12.7.1 不同的类376

12.7.2 邻接矩阵类377

12.7.3 扩充Chain类380

12.7.4 类LinkedBase381

12.7.5 连结类382

12.8 图的遍历386

12.8.1 基本概念386

12.8.2 邻接矩阵的遍历函式387

12.8.3 邻接鍊表的遍历函式388

12.9 语言特性389

12.9.1 虚函式和多态性389

12.9.2 纯虚函式和抽象类391

12.9.3 虚基类391

12.9.4 抽象类和抽象数据类型393

12.10 图的搜寻算法394

12.10.1 宽度优先搜寻394

12.10.2 类Network395

12.10.3 BFS的实现395

12.10.4 BFS的複杂性分析396

12.10.5 深度优先搜寻397

12.11 套用399

12.11.1 寻找路径399

12.11.2 连通图及其构件400

12.11.3 生成树402

第三部分 算法设计方法

第13章 贪婪算法405

13.1 最最佳化问题405

13.2 算法思想406

13.3 套用409

13.3.1 货箱装船409

13.3.2 0/1背包问题 410

13.3.3 拓扑排序412

13.3.4 二分覆盖415

13.3.5 单源最短路径421

13.3.6 最小耗费生成树424

13.4 参考及推荐读物433

第14章 分而治之算法434

14.1 算法思想434

14.2 套用440

14.2.1 残缺棋盘440

14.2.2 归併排序443

14.2.3 快速排序447

14.2.4 选择452

14.2.5 距离最近的点对454

14.3 解递归方程462

14.4 複杂性的下限463

14.4.1 最小最大问题的下限464

14.4.2 排序算法的下限465

第15章 动态规划467

15.1 算法思想467

15.2 套用469

15.2.1 0/1背包问题469

15.2.2 图像压缩471

15.2.3 矩阵乘法链476

15.2.4 最短路径480

15.2.5 网路的无交叉子集483

15.2.6 元件摺叠486

15.3 参考及推荐读物491

第16章 回溯492

16.1 算法思想492

16.2 套用496

16.2.1 货箱装船496

16.2.2 0/1背包问题503

16.2.3 最大完备子图506

16.2.4 旅行商问题508

16.2.5 电路板排列510

第17章 分枝定界516

17.1 算法思想516

17.2 套用519

17.2.1 货箱装船519

17.2.2 0/1背包问题526

17.2.3 最大完备子图528

17.2.4 旅行商问题529

17.2.5 电路板排列532