数据结构、算法与应用:C++语言描述(计算机科学丛书)(Data Structures,Algorithms,and Applications in C++)

基本信息·出版社：机械工业出版社

·页码：535 页

·出版日期：2000年

·ISBN：7111076451

·条形码：9787111076452

·包装版本：1版

·装帧：平装

·开本：16

·正文语种：中文

·丛书名：计算机科学丛书

·外文书名：Data Structures,Algorithms,and Applications in C++

产品信息有问题吗？请帮我们更新产品信息。

内容简介《数据结构、算法与应用:C++语言描述》在简要回顾了基本的C++ 程序设计概念的基础上，全面系统地介绍了队列、堆栈、树、图等基本数据结构，以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，《数据结构、算法与应用:C++语言描述》不仅仅介绍了理论知识，还提供了50多个应用实例及600多道练习题。

作者简介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项。

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

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

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

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

编辑推荐《数据结构、算法与应用:C++语言描述》是关于计算机科学与工程领域的基础性研究科目之一：数据结构与算法的专著。《数据结构、算法与应用:C++语言描述》内容广博权威，结构清晰合理，是一本全新的有关数据结构与算法的教材，对于计算机科学与工程领域的从业人员也是一本很好的参考书。

目录

译者序

前言

第一部分 预备知识

第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

……[看更多目录]

序言在可视化程序设计平台广泛流行和应用的今天，程序设计不再是一件神秘的、专业性的工作，很多非计算机专业的人员都可以亲自动手设计应用程序。这似乎让人觉得，只要掌握了一门可视化程序设计语言，人人都可以成为编程高手，但事实并非如此。要想成为一个熟练的专业化程序设计人员，他（她）至少应该满足以下三个条件：一是能够熟练地选择和设计各种数据结构和算法，二是熟练掌握一门程序设计语言，三是熟知应用领域的相关知识。其中后两个条件比较容易实现，而第一个条件则需要花相当的时间和精力才能达到，它是区分一个程序设计人员水平高低的重要标志。之所以如此，是因为在绝大多数应用程序中都需要广泛使用各种各样的数据结构和算法。缺少数据结构和算法的深厚功底，很难设计出高水平的具有专业水准的应用程序。

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

全书共包含三个部分，第一部分主要回顾一些重要的c++程序设计概念以及算法分析与评价的方法。第二部分首先对各种数据描述方法进行了精辟地概括，然后依次介绍了数组、矩阵、堆栈、队列、字典、二叉树、优先队列、竞赛树和图等基本数据结构，对于每一种数据结构都分别采用若干个来自不同领域的应用实例进行了具体的演示。第三部分重点介绍了一些常用的算法设计方法及应用，如贪婪算法、分而治之算法、动态规划方法、回溯算法和分枝定界算法。

本书的最大特色就是强调应用。通过现实生活中的许多应用实例具体演示了书中所介绍的各种数据结构和算法设计方法。根据实例，读者不但可以印证许多基本概念，而且能加深对它们的理解，从而更好地掌握相应的数据结构和算法并能达到熟练应用。通过把应用与理论知识紧密结合，极大地激发了读者学习数据结构和算法的兴趣。

如果你是一名程序设计新手，本书可以为你架起一座桥梁，使你如愿以偿地跨人专业程序设计人员的行列；如果你已经是一名专业程序设计人员，本书可以使你的程序设计水平更上一层楼。当然，如果你是一名计算机专业的在校学生，本书将是一本非常理想的关于数据结构和算法课程的教材或参考书。

参加本书翻译工作的有汪诗林、孙晓东、蒋艳凰、孙海燕、刘娜、郑倩冰、史军慧、陈海燕，由王广芳教授和汪诗林博士完成全书的审校工作。

因时间仓促，翻译若有不妥之处，恳请读者批评指正。

文摘插图：