计算机科学丛书·数据结构、算法与应用：C++语言描述（原书第2版）

图书标准信息

• 作者 [美]萨特吉·萨尼（Sartaj Sahni） 著；王立柱、刘志红 译
• 出版社 机械工业出版社
• 出版时间 2015-04
• 版次 1
• ISBN 9787111496007
• 定价 79.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 544页
• 字数 100千字
• 正文语种 简体中文
• 丛书 计算机科学丛书

【内容简介】

　　《数据结构、算法与应用——C++语言描述》是享有盛誉的数据结构教科书的第2版。它完整地包含了基本数据结构的内容，是CS2课程的理想用书。作者SartajSahni通过循循善诱的讲解、直观具体的讨论和基于现实的应用，让读者轻松、愉快地学习。新版书着重利用标准模板库(STL)，把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。
　　书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例，涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起，使理论与实践统一，从而让概念容易理解，使学生增加学习动力和兴趣。
　　《计算机科学丛书·数据结构、算法与应用：C++语言描述（原书第2版）》采用的实用教学方法，不仅充实了理论概念，而且大量的习题让学生有了实践机会（书中有800多道练习题，包括理解题和简单的编程题和工程设计题）。除此之外，本书的配套网站上包含书中的所有程序、示例数据、运行结果、部分练习的解答和带有结果的示例测试。

【作者简介】

　　SartajSahni，佛罗里达大学计算机与信息科学工程系杰出教授，欧洲科学院院士，美国电气和电子工程师协会（IEEE）、美国计算机协会（ACM）、美国科学促进会（AAAS）和明尼苏达超级计算机研究所的成员，坎普尔印度理工学院（lIT）的杰出校友。Sahni博士获得1997年IEEE计算机分会的TaylorLBooth教育奖，2003年IEEE计算机分会的W．WallaceMcDowell奖和2003年ACM的KarlKarlstrom杰出教育家奖。他目前还担任ACM《ComputingSurveys》期刊的总编辑，还是17个期刊编委会成员。他在坎普尔印度理工学院获得电子工程学士学位，在康奈尔大学获得计算机科学硕士和博士学位，发表过250多篇论文，编写了15本教科书，研究成果所涉及的领域包括有效算法的设计与分析、并行计算、互联网、自动化设计和医用算法。

【目录】

DataStructures，Algorithms，andApplicationsinC++，SecondEdition
出版者的话
译者序
前言
第一部分预备知识
第1章C++回顾
1.1引言
1.2函数与参数
1.2.1传值参数
1.2.2模板函数
1.2.3引用参数
1.2.4常量引用参数
1.2.5返回值
1.2.6重载函数
1.3异常
1.3.1抛出异常
1.3.2处理异常
1.4动态存储空间分配
1.4.1操作符new
1.4.2一维数组
1.4.3异常处理
1.4.4操作符delete
1.4.5二维数组
1.5自有数据类型
1.5.1类currency
1.5.2一种不同的描述方法
1.5.3操作符重载
1.5.4友元和保护性类成员
1.5.5增加#ifndef、#define和#endif语句
1.6异常类illegalParameterValue
1.7递归函数
1.7.1递归的数学函数
1.7.2归纳
1.7.3C++递归函数
1.8标准模板库
1.9测试与调试
1.9.1什么是测试
1.9.2测试数据的设计
1.9.3调试
1.10参考及推荐读物
第2章程序性能分析
2.1什么是程序性能
2.2空间复杂度
2.2.1空间复杂度的组成
2.2.2举例
2.3时间复杂度
2.3.1时间复杂度的组成
2.3.2操作计数
2.3.3最好、最坏和平均操作计数
2.3.4步数
第3章渐近记法
3.1引言
3.2渐近记法
3.2.1大Ο记法
3.2.2渐近记法Ω和Θ
3.3渐近数学（可选）
3.3.1大O记法
3.3.2Ω记法
3.3.3Θ记法
3.3.4小ο记法
3.3.5特性
3.4复杂度分析举例
3.5实际复杂度
3.6参考及推荐读物
第4章性能测量
4.1引言
4.2选择实例的大小
4.3设计测试数据
4.4实验设计
4.5高速缓存
4.5.1简单计算机模型
4.5.2缓存未命中对运行时间的影响
4.5.3矩阵乘法
4.6参考及推荐读物

第二部分数据结构
第5章线性表——数组描述
5.1数据对象和数据结构
5.2线性表数据结构
5.2.1抽象数据类型linearList 
5.2.2抽象类linearList
5.3数组描述
5.3.1描述
5.3.2变长一维数组
5.3.3类arrayList
5.3.4C++迭代器
5.3.5arrayList的一个迭代器
5.4vector的描述
5.5在一个数组中实现的多重表
5.6性能测量
5.7参考及推荐读物
第6章线性表——链式描述
6.1单向链表
6.1.1描述
6.1.2结构chainNode
6.1.3类chain
6.1.4抽象数据类型linearList的扩充
6.1.5类extendedChain
6.1.6性能测量
6.2循环链表和头节点
6.3双向链表
6.4链表用到的词汇表
6.5应用
6.5.1箱子排序
6.5.2基数排序
6.5.3凸包
6.5.4并查集
第7章数组和矩阵
7.1数组
7.1.1抽象数据类型
7.1.2C++数组的索引
7.1.3行主映射和列主映射
7.1.4用数组的数组来描述
7.1.5行主描述和列主描述
7.1.6不规则二维数组
7.2矩阵
7.2.1定义和操作
7.2.2类matrix
7.3特殊矩阵
7.3.1定义和应用
7.3.2对角矩阵
7.3.3三对角矩阵
7.3.4三角矩阵
7.3.5对称矩阵
7.4稀疏矩阵
7.4.1基本概念
7.4.2用单个线性表描述
7.4.3用多个线性表描述
7.4.4性能测量
第8章栈
8.1定义和应用
8.2抽象数据类型
8.3数组描述
8.3.1作为一个派生类实现
8.3.2类arrayStack
8.3.3性能测量
8.4链表描述
8.4.1类derivedLinkedStack
8.4.2类linkedStack
8.4.3性能测量
8.5应用
8.5.1括号匹配
8.5.2汉诺塔
8.5.3列车车厢重排
8.5.4开关盒布线
8.5.5离线等价类问题
8.5.6迷宫老鼠
8.6参考及推荐读物
第9章队列
9.1定义和应用
9.2抽象数据类型
9.3数组描述
9.3.1描述
9.3.2类arrayQueue
9.4链表描述
9.5应用
9.5.1列车车厢重排
9.5.2电路布线
9.5.3图元识别
9.5.4工厂仿真
9.6参考及推荐读物
第10章跳表和散列
10.1字典
10.2抽象数据类型
10.3线性表描述
10.4跳表表示（可选）
10.4.1理想情况
10.4.2插入和删除
10.4.3级的分配
10.4.4结构skipNode
10.4.5类skipList
10.4.6skipList方法的复杂度
10.5散列表描述
10.5.1理想散列
10.5.2散列函数和散列表
10.5.3线性探查
10.5.4链式散列
10.6一个应用——文本压缩
10.6.1LZW压缩
10.6.2LZW压缩的实现
10.6.3LZW解压缩
10.6.4LZW解压缩的实现
10.6.5性能评价
10.7参考及推荐读物
第11章二叉树和其他树
11.1树
11.2二叉树
11.3二叉树的特性
11.4二叉树的描述
11.4.1数组描述
11.4.2链表描述
11.5二叉树常用操作
11.6二叉树遍历
11.7抽象数据类型BinaryTree
11.8类linkedBinaryTree
11.9应用
11.9.1设置信号放大器
11.9.2并查集
11.10参考及推荐读物
第12章优先级队列
12.1定义和应用
12.2抽象数据类型
12.3线性表
12.4堆
12.4.1定义
12.4.2大根堆的插入
12.4.3大根堆的删除
12.4.4大根堆的初始化
12.4.5类maxHeap
12.4.6堆和STL
12.5左高树
12.5.1高度优先与宽度优先的最大及最小左高树
12.5.2最大HBLT的插入
12.5.3最大HBLT的删除
12.5.4两棵最大HBLT的合并
12.5.5初始化
12.5.6类maxHblt
12.6应用
12.6.1堆排序
12.6.2机器调度
12.6.3霍夫曼编码
12.7参考及推荐读物
第13章竞赛树
13.1赢者树和应用
13.2抽象数据类型WinnerTree
13.3赢者树的实现
13.3.1表示
13.3.2赢者树的初始化
13.3.3重新组织比赛
13.3.4类completeWinnerTree
13.4输者树
13.5应用
13.5.1用最先适配法求解箱子装载问题
13.5.2用相邻适配法求解箱子装载问题
13.6参考及推荐读物
第14章搜索树
14.1定义
14.1.1二叉搜索树
14.1.2索引二叉搜索树
14.2抽象数据类型
14.3二叉搜索树的操作和实现
14.3.1类binarySearchTree
14.3.2搜索
14.3.3插入
14.3.4删除
14.3.5二叉搜索树的高度
14.4带有相同关键字元素的二叉搜索树
14.5索引二叉搜索树
14.6应用
14.6.1直方图
14.6.2箱子装载问题的最优匹配法
14.6.3交叉分布
第15章平衡搜索树
15.1AVL树
15.1.1定义
15.1.2AVL树的高度
15.1.3AVL树的描述
15.1.4AVL搜索树的搜索
15.1.5AVL搜索树的插入
15.1.6AVL搜索树的删除
15.2红-黑树
15.2.1基本概念
15.2.2红-黑树的描述
15.2.3红-黑树的搜索
15.2.4红-黑树的插入
15.2.5红-黑树的删除
15.2.6实现细节的考虑及复杂性分析
15.3分裂树
15.3.1介绍
15.3.2分裂树的操作
15.3.3折算复杂性
15.4B-树
15.4.1索引顺序访问方法
15.4.2m叉搜索树
15.4.3m阶B-树
15.4.4B-树的高度
15.4.5B-树的搜索
15.4.6B-树的插入
15.4.7B-树的删除
15.4.8节点结构
15.5参考及推荐读物
第16章图
16.1基本概念
16.2应用和更多的概念
16.3特性
16.4抽象数据类型graph
16.5无权图的描述
16.5.1邻接矩阵
16.5.2邻接链表
16.5.3邻接数组
16.6加权图的描述
16.7类实现
16.7.1不同的类
16.7.2邻接矩阵类
16.7.3扩充chain类
16.7.4链表类
16.8图的遍历
16.8.1广度优先搜索
16.8.2广度优先搜索的实现
16.8.3方法graph：：bfs的复杂性分析
16.8.4深度优先搜索
16.8.5深度优先搜索的实现
16.8.6方法graph：：dfs的复杂性分析
16.9应用
16.9.1寻找一条路径
16.9.2连通图及其构成
16.9.3生成树

第三部分算法设计方法
第17章贪婪算法
17.1最优化问题
17.2贪婪算法思想
17.3应用
17.3.1货箱装载
17.3.20/1背包问题
17.3.3拓扑排序
17.3.4二分覆盖
17.3.5单源最短路径
17.3.6最小成本生成树
17.4参考及推荐读物
第18章分而治之
18.1算法思想
18.2应用
18.2.1残缺棋盘
18.2.2归并排序
18.2.3快速排序
18.2.4选择
18.2.5相距最近的点对
18.3解递归方程
18.4复杂度的下限
18.4.1最小最大问题的下限
18.4.2排序算法的下限
第19章动态规划
19.1算法思想
19.2应用
19.2.10/1背包问题
19.2.2矩阵乘法链
19.2.3所有顶点对之间的最短路径
19.2.4带有负值的单源最短路径
19.2.5网组的无交叉子集
19.3参考及推荐读物
第20章回溯法
20.1算法思想
20.2应用
20.2.1货箱装载
20.2.20/1背包问题
20.2.3最大完备子图
20.2.4旅行商问题
20.2.5电路板排列
第21章分支定界
21.1算法思想
21.2应用
21.2.1货箱装载
21.2.20/1背包问题
21.2.3最大完备子图
21.2.4旅行商问题
21.2.5电路板排列