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

图书标准信息

• 作者 萨尼（Sartaj Sahni）、汪诗林、孙晓东 著
• 出版社 机械工业出版社
• 出版时间 2000-01
• 版次 1
• ISBN 9787111076452
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 535页
• 正文语种 简体中文
• 丛书 计算机科学丛书

【内容简介】

　　《数据结构、算法与应用：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操作符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.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类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.1Stack的效率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.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抽象数据类型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.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和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.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