本书用C++作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组、栈、伫列、鍊表、树和图，以及构成所有软体基础的排序散列技术。此外，本书还介绍了各种高级或特殊数据结构，如优先权伫列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在最优、最差情形下的複杂度分析。本书的更新版已涵盖了C++语言的最新特性。

本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材，也可以作为研究生第一学年的“高等数据结构”课程的教材，同时，本书所介绍的各种算法的C++语言实现，对有关专业人员也具有很好的参考价值。

EllisHorowitz，是南加州大学计算机与电子工程系的教授。Horowitz博士已编着了10多本教材，并发表了大量学术论文。

SartajSahni，是佛罗里达大学计算机与信息科学系的杰出教授和讲座教授。Sahni博士已发表300多篇学术研究论文，编着了15本教材。

DineshMehta，是科罗拉多矿业大学教授，数学与计算机科学系的副主任。Mehta博士已发表30多篇期刊和会议论文。

第1章基本概念1

1.1概述：系统生命周期1

1.2面向对象的程式设计3

1.2.1算法分解与面向对象分解3

1.2.2基本定义和面向对象编程的概念3

1.2.3程式设计语言的演化和C++语言历史4

1.3数据抽象和封装4

1.4C++语言基础8

1.4.1C++程式的组织结构8

1.4.2C++语言的作用域9

1.4.3C++的语句与操作符10

1.4.4C++语言中的数据声明10

1.4.5C++语言的注释11

1.4.6C++语言的输入输出11

1.4.7C++语言的函式13

1.4.8C++语言的参数传递13

1.4.9C++语言的函式名重载14

1.4.10内联函式14

1.4.11C++语言的动态记忆体分配15

1.4.12例外15

1.5算法规範17

1.5.1概述17

1.5.2递归算法20

1.6标準模板库24

1.7性能分析和度量27

1.7.1性能分析28

1.7.2性能度量45

1.7.3测试数据的生成50

1.8参考文献和推荐读物54第2章数组55

2.1抽象数据类型和C++类55

2.1.1C++类介绍55

2.1.2C++语言中的数据抽象和封装56

2.1.3声明类对象和调用成员函式56

2.1.4特别类操作57

2.1.5其他主题60

2.1.6ADT和C++类60

2.2将数组作为一种抽象数据类型62

2.3多项式抽象数据类型64

2.3.1多项式的表示65

2.3.2多项式的加法67

2.4稀疏矩阵71

2.4.1绪论71

2.4.2稀疏矩阵的表示法72

2.4.3转置一个矩阵73

2.4.4矩阵的乘法76

2.5多维数组的表示81

2.6字元串抽象数据类型84

2.6.1一种简单的字元串模式匹配算法85

2.6.2字元串模式匹配：Knuth-Morris-Pratt算法85

2.7参考文献和推荐读物89

2.8附加习题89数据结构基础（C++语言版）（第2版）目录第3章栈和伫列94

3.1C++模板94

3.1.1模板函式94

3.1.2用模板表示容器类96

3.2栈的抽象数据类型99

3.3伫列抽象数据类型103

3.4C++中的子类型和继承109

3.5一个迷宫问题112

3.6计算表达式116

3.6.1表达式116

3.6.2后缀表达式118

3.6.3中缀表达式转换成后缀表达式119

3.7附加习题122第4章鍊表124

4.1单鍊表和链124

4.2用C++语言表示鍊表126

4.2.1在C++语言中定义结点126

4.2.2用C++语言设计一个鍊表类127

4.2.3C++语言中的指针操作130

4.2.4鍊表的控制操作131

4.3链的模板类134

4.3.1用模板实现鍊表134

4.3.2鍊表叠代器135

4.3.3鍊表操作138

4.3.4类的重用140

4.4循环鍊表141

4.5可用空间鍊表143

4.6链式栈和链式伫列144

4.7多项式146

4.7.1多项式的表示146

4.7.2多项式相加147

4.7.3用循环鍊表表示多项式150

4.8等价类152

4.9稀疏矩阵157

4.9.1稀疏矩阵的表示157

4.9.2稀疏矩阵的输入159

4.9.3删除稀疏矩阵160

4.10双向鍊表162

4.11广义表165

4.11.1广义表的表示165

4.11.2表的递归算法168

4.11.3引用计数、共享和递归表171第5章树176

5.1概述176

5.1.1术语表176

5.1.2树的表示178

5.2二叉树180

5.2.1抽象数据类型180

5.2.2二叉树的性质181

5.2.3二叉树的表示183

5.3二叉树的遍历和叠代程式185

5.3.1概述185

5.3.2中序遍历185

5.3.3先序遍历187

5.3.4后序遍历187

5.3.5叠代中序遍历188

5.3.6层次遍历190

5.3.7不使用栈的遍历191

5.4补充的二叉树操作193

5.4.1複製二叉树193

5.4.2检测相等193

5.4.3满足性问题194

5.5线索二叉树196

5.5.1线索196

5.5.2线索二叉树的中序遍历197

5.5.3线上索二叉树上插入一个结点198

5.6堆200

5.6.1优先伫列200

5.6.2大顶堆的定义201

5.6.3大顶堆的插入202

5.6.4大顶堆的删除203

5.7二叉查找树205

5.7.1定义205

5.7.2二叉查找树的查找206

5.7.3二叉查找树的插入208

5.7.4二叉查找树的删除209

5.7.5二叉树的连线和分裂210

5.7.6二叉查找树的高度212

5.8选择树213

5.8.1概述213

5.8.2胜者树213

5.8.3败者树214

5.9森林215

5.9.1将森林转换成二叉树215

5.9.2森林的遍历216

5.10离散集合表示217

5.10.1概述217

5.10.2并和查找操作217

5.10.3等价类的套用223

5.11二叉树计数225

5.11.1不同的二叉树225

5.11.2栈排列226

5.11.3矩阵相乘227

5.11.4不同二叉树的个数228

5.12参考文献和推荐读物229第6章图230

6.1图的抽象数据类型230

6.1.1概述230

6.1.2定义231

6.1.3图的表示234

6.2图的基本操作240

6.2.1深度优先搜寻240

6.2.2广度优先搜寻241

6.2.3连通分量242

6.2.4生成树243

6.2.5重连通分量244

6.3最小代价生成树248

6.3.1克鲁斯卡尔算法248

6.3.2普里姆算法251

6.3.3索林算法252

6.4最短路径和传递闭包253

6.4.1单源/多目标：非负权值253

6.4.2单源/多目标：任意权值257

6.4.3多源最短路径259

6.4.4传递闭包260

6.5活动网路263

6.5.1顶点表示活动的网路（AOV网）263

6.5.2用边表示活动的网路（AOE网）267

6.5.3事件最早发生时间的计算269

6.5.4事件最迟发生时间的计算269

6.6参考文献和推荐读物272

6.7附加习题273第7章排序275

7.1目的275

7.2插入排序278

7.3快速排序280

7.4排序算法能够多快283

7.5归併排序284

7.5.1归併284

7.5.2叠代归併285

7.5.3递归归併287

7.6堆排序289

7.7多关键字排序292

7.8链和列表排序295

7.9内部排序总结302

7.10外部排序306

7.10.1概述306

7.10.2k路归併308

7.10.3并行操作的快取处理309

7.10.4顺串产生313

7.10.5顺串的最佳归併315

7.11参考文献和推荐读物318第8章散列319

8.1绪论319

8.2静态散列319

8.2.1哈希表319

8.2.2哈希函式320

8.2.3安全哈希函式323

8.2.4溢出处理325

8.2.5溢出技术的理论分析329

8.3动态散列331

8.3.1动态散列的目的331

8.3.2使用目录的动态散列332

8.3.3不使用目录的动态散列334

8.4布隆过滤器335

8.4.1勘误档案的套用335

8.4.2设计布隆过滤器337

8.5参考文献和推荐读物338第9章优先伫列340

9.1单端和双端优先伫列340

9.2左偏树342

9.2.1高度左偏树342

9.2.2重量左偏树346

9.3二项式堆349

9.3.1代价分摊349

9.3.2二项式堆的定义350

9.3.3二项式堆的插入操作351

9.3.4合併两个二项式堆352

9.3.5删除最小元素352

9.3.6分析354

9.4斐波那契堆356

9.4.1定义356

9.4.2从斐波那契堆中删除元素356

9.4.3减小键值357

9.4.4级联剪下357

9.4.5分析358

9.4.6在最短路径问题上的套用360

9.5配对堆361

9.5.1定义361

9.5.2合併和插入操作362

9.5.3减小键值363

9.5.4删除最小元素363

9.5.5删除任意元素365

9.5.6实现问题365

9.5.7複杂度366

9.6对称最小-最大堆366

9.6.1定义及性质366

9.6.2SMMH的表示367

9.6.3插入操作368

9.6.4删除操作371

9.7区间堆373

9.7.1定义及性质373

9.7.2区间堆的插入操作374

9.7.3删除最小元素376

9.7.4初始化区间堆377

9.7.5区间堆操作的複杂度377

9.7.6互补範围搜寻问题377

9.8参考文献和推荐读物379第10章高效二叉查找树382

10.1最优二叉查找树382

10.2AVL树388

10.3红黑树398

10.3.1定义398

10.3.2红黑树的表示399

10.3.3查找400

10.3.4插入400

10.3.5删除403

10.3.6红黑树的合併403

10.3.7红黑树的分裂404

10.4伸展树406

10.4.1自底向上的伸展树406

10.4.2自顶向下的伸展树409

10.5参考文献和推荐读物413第11章多路查找树415

11.1m路查找树415

11.1.1定义和性质415

11.1.2对m路查找树进行查找416

11.2B-树417

11.2.1定义和性质417

11.2.2B-树的元素个数417

11.2.3插入418

11.2.4删除420

11.3B+树427

11.3.1定义427

11.3.2查找428

11.3.3插入428

11.3.4删除429

11.4参考文献和推荐读物433第12章数字查找结构434

12.1数字查找树434

12.1.1定义434

12.1.2查找、插入和删除434

12.2二叉Trie树和Patricia树435

12.2.1二叉Trie树435

12.2.2压缩二叉Trie树436

12.2.3Patricia树436

12.3多路Trie树440

12.3.1定义440

12.3.2查找Trie树442

12.3.3抽样策略442

12.3.4插入Trie树444

12.3.5从Trie树中删除444

12.3.6不同长度的关键字444

12.3.7Trie树的高度445

12.3.8空间需求与其他结点结构445

12.3.9前缀查找和套用448

12.3.10压缩Trie树449

12.3.11带跳过栏位的压缩Trie树451

12.3.12带标号边的压缩Trie树452

12.3.13压缩Trie树需要的空间453

12.4后缀树454

12.4.1你是否见过这个字元串454

12.4.2后缀树数据结构455

12.4.3查找子串(查找后缀树)457

12.4.4后缀树上的其他技巧458

12.5Trie树和Internet包转发460

12.5.1IP路由460

12.5.21-比特Trie树460

12.5.3固定跨度Trie树461

12.5.4可变跨度Trie树463

12.6参考文献和推荐读物465术语表466

ⅩVII