数据结构、算法与应用：C++语言描述

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

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

　　译者简介：

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

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

译者序
前言
第一部分预备知识
第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操作符new 9
1.3.2一维数组 9
1.3.3异常处理 10
1.3.4操作符delete 10
1.3.5二维数组 10

1.4类 13
1.4.1类Currency 13
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异常类NoMem 79
3.3.3操作 79
3.3.4评价 83

3.4链表描述 86
3.4.1类ChainNode和Chain 86
3.4.2操作 88
3.4.3扩充类Chain 91
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.1SimSpace的操作 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.2C++数组 129
4.1.3行主映射和列主映射 129
4.1.4类Array1D 131
4.1.5类Array2D 133

4.2矩阵 137
4.2.1定义和操作 137
4.2.2类Matrix 138

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.1Stack的效率 164
5.3.2自定义Stack 164
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类SkipNode 224
7.3.5类SkipList 225
7.3.6复杂性 229

7.4散列表描述 229
7.4.1理想散列 229
7.4.2线性开型寻址散列 230
7.4.3链表散列 234

7.5应用——文本压缩 238
7.5.1LZW压缩 239
7.5.2LZW压缩的实现 239
7.5.3LZW解压缩 243
7.5.4LZW解压缩的实现 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抽象数据类型BinaryTree 259
8.8类BinaryTree 260

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类MaxHeap 281

9.4左高树 285
9.4.1高度与宽度优先的最大及最小左高树 285
9.4.2最大HBLT的插入 287
9.4.3最大HBLT的删除 287
9.4.4合并两棵最大HBLT 287
9.4.5初始化最大HBLT 289
9.4.6类MaxHBLT 289

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抽象数据类型WinnerTree 306
10.3类WinnerTree 307
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和IndexedBSTree 321
11.1.3类BSTree 322
11.1.4搜索 322
11.1.5插入 323
11.1.6删除 324
11.1.7类DBSTree 326
11.1.8二叉搜索树的高度 327

11.2AVL树 328
11.2.1基本概念 328
11.2.2AVL树的高度 328
11.2.3AVL树的描述 329
11.2.4AVL搜索树的搜索 329
11.2.5AVL搜索树的插入 329
11.2.6AVL搜索树的删除 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.4B－树 344
11.4.1索引顺序访问方法 344
11.4.2m叉搜索树 345
11.4.3m序B－树 346
11.4.4B－树的高度 347
11.4.5B－树的搜索 348
11.4.6B－树的插入 348
11.4.7B－树的删除 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和Digraph 370
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类LinkedBase 381
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类Network 395
12.10.3BFS的实现 395
12.10.4BFS的复杂性分析 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.20/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.10/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.20/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.20/1背包问题 526
17.2.3最大完备子图 528
17.2.4旅行商问题 529
17.2.5电路板排列 532