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

　　本书特色：“纵览全书可以看出作者具有丰富的教材编写经验。它是一本新的、有关数据结构与算法的教材，适合于当前计算机本科教学的需要。”——SangW．Lee，密歇根大学“注重应用不仅可以使课堂教学更生动，而且可以激励学生投身于相关的应用。”——YuLoC．Chang，新汉普郡大学本书不同于以往介绍数据结构或介绍算法的书，而是囊括了数据结构及算法，是作者在该领域做出的又一个创新性的贡献。本书的另一个独特之处在于其充分强调了应用性。对于每一种数据结构及算法，都分别采用了若干个来自不同领域的应用进行具体演示。本书为学习和研究数据结构及算法奠定了坚实的基础。本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。本书在简要回顾了基本的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项。

译者序
前言
第一部分 预备知识
第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 操作符new
1.3.2 一维数组
1.3.3 异常处理
1.3.4操作符delete
1.3.5 二维数组
1.4 类
1.4.1 类Currency
1.4.2 使用不同的描述方法
1.4.3 操作符重载
1.4.4 引发异常
1.4.5 友元和保护共成员
1.4.6 增加＃ifnde和,＃define和＃endif语句
1.5 测试与调试
1.5.1 什么是测试问
1.5.2 设计测试数据
1.5.3 调试
1.6 参考及推荐读物
第 2章程序性能
2.1 引言 
2.2 空间复杂性
2.2.1 空间复杂性的组成
2.2.2 举例
2.3 时间复杂性
2.3.1 时间复杂性的组成
2.3.2 操作计数
2.3.3 执行步数
2.4 渐进符号
2.4.1 大写符号
2.4.2 Q符号
2.4.3 O符号
2.4.4 小写O符号
2.4.5 特性
2.4.6 复杂性分析举例
2.5 实际复杂性
2.6 性能测量
2.6.1 选择实例的大小
2.6.2 设计测试数据
2.6.3 进行实验
2.7 参考及推荐读物
第二部分 数据结构
第 3章数据描述
3.1 引言
3.2 线性表
3.3 公式化描述
3.3.1 基本概念
3.3.2 异常类NoMem
3.3.3 操作
3.3.4 评价
3.4 链表描述
3.4.1 类ChainNode和Chain
3.4.2 操作
3.4.3 扩充类Chain
3.4.4 链表遍历器类
3.4.5 循环链表
3.4.6 与公式化描述方法的比较
3.4.7 双向链表
3.4.8 小结
3.5 间接寻址
3.5.1 基本概念
3.5.2 操作
3.6 模拟指针
3.6.1 Simspace的操作
3.6.2 采用模拟指针的链表
3.7 描述方法的比较
3.8 应用
3.8.1 箱子排序
3.8.2 基数排序
3.8.3 等价类
3.8.4 凸包
3.9 参考及推荐读物
第4章数组和矩阵
4.1 数组
4.1.1 抽象数据类型
4.1.2 C++数组
4.1.3 行主映射和列主映射
4.1.4 类ArraylD
4.1.5 类Array2D
4.2 矩阵
4.2.1 定义和操作
4.2.2 类Matrix
4.3 特殊矩阵
4.3.1 定义和应用
4.3.2 对角矩阵
4.3.3 三对角矩阵
4.3.4 三角矩阵
4.3.5 对称矩阵
4.4 稀疏矩阵
4.4.1 基本概念
4.4.2 数组描述
4.4.3 链表描述
第5章堆钱
5.1 抽象数据类型
5.2 派生类和继承
5.3 公式化描述
5.3I Stack的效率
5.3.2 自定义Stack
5.4 链表描述
5.5 应用
5.5.1 括号匹配
5.5.2 汉诺塔
55.3 火车车厢重排
5.5.4 开关盒布线
5.5.5 离线等价类问题
5.5.6 迷宫老鼠
5.6 参考及推荐读物
第6章队列
6.1 抽象数据类型
6.2 公式化描述
6.3 链表描述
6.4 应用
6.4.1 火车车厢重排
6.4.2 电路布线
6.4.3 识别图元
6.4.4 工厂仿真
6.5 参考及推荐读物
第7章跳表和散列
7.1 字典
7.2节线性表描述
7.3 跳表描述
7.3.1 理想情况
7.3.2 插入和删除
7.3.3 级的分配
7.3.4 类skipNode
7.3.5 类SkipLISt
7.3.6 复杂性
7.4 散殒表描述
7.4.1 理想散列
7.4.2 线性开型寻址散到
7.4.3 链大散列
7.5 应用——文本压缩
7.5.1 LZW压缩
7.5.2 LZW压缩的实现
7.5.3 LZW解压缩
7.5.4 LZW解压缩的实现
7.6 参考及推荐读物
第8章二叉树和其他树
8.1 树
8.2 二叉树
8.3 二叉树的特性
8.4 二叉树描述
8.4.1 公式化描述
8.4.2 链表描述
8.5 二叉树常用操作
8.6 二叉树遍历
8.7 抽象数据类型BlnaryTree
8.8 类BinaryTree
8.9 抽象数据类型及类的扩充
8.9.1 输出
8.9.2 删除
8.9.3 计算高度
8.9.4 统计节点数
8.10 应用
8.10.1 设置信号放大器
8.10.2 在线等价类
8.11 参考及推荐读物
第9章优先队列
9.1 引言
9.2 线性表
9.3 堆
9.3.1 定义
9.3.2 最大堆的插入
9.3.3 最大堆的删除
9.3.4 最大堆的初始化
9.3.5 类MaxHeap
9.4 左高树
9.4.1 高度与宽度优先的最大及最小左高树
9.4.2 最大HBLT的插入
9.4.3 最大HBLT的删除
9.4.4 合并两棵最大HBLT
9.4.5 初始化最大HBLT
9.4.6 类MaxHBLT
9.5 应用
9.5.1 堆排序
9.5.2 机器调度
9.5.3 霍夫曼编码
9.6 参考及推荐读物
第10章竞赛树
10.1 引言
10.2 抽象数据类型WinnerTree
10.3 类WnnerTree
10.3.1 定义
10.3.2 类定义
10.3.3 构造函数析构国数及Wuuer函数
10.3.4 初始化赢者树
10.3.5 重新组织比赛
10.4 输者树
10.5 应用
10.5.1 用最先匹配法求解箱子装载问题
10.5.2 用相邻匹配法求解箱子装载问题
第11章搜索树
11.1 二叉搜索树
11.1.1 基本概念
11.1.2 抽象数据类型BSTree和IndexedBSTree
11.1.3 类BSTree
11.1.4 搜索
11.1.5 插入
11.1.6 删除
11.1.7 类DBSTree
11.1.8 二叉搜索树的高度
11.2 AVL树
11.2.1 基本概念
11.2.2 AVL树的高度
11.2.3 AVL树的描述
11.2.4 AVL搜索树的搜索
11.2.5 AVL搜索树的插入
11.2.6 AVL搜索树的删除
11.3 红一黑树
11.3.1 基本概念
11.3.2 红一黑树的描述
11.3.3 红一黑树的搜索
11.3.4 红一黑树的插入
11.3.5 红一黑树的删除
11.3.6 实现细节的考虑及复杂性分析
11.4 B一树
11.4.1 索引顺序访问方法
11.4.2 m叉搜索树
11.4.3 m序B一树
11.4.4 B一树的高度
11.4.5 B一树的搜索
11.4.6 B一树的插入
11.4.7 B一树的删除
11.4.8 节点结构
11.5 应用
11.5.1 直方图
11.5.2 用最优匹配法求解箱子装载问题
11.5.3 交叉分布
11.6 参考及推荐读物
第12章图
12.1 基本概念
12.2 应用
12.3有尽有特性
12.4 抽象数据类型GraPh和DlgraPh
12.5 无向图和有向图的描述
12.5.1 邻接矩阵
12.5.2 邻接压缩表
12.5.3 邻接链表
12.6 网络描述
12.7 类定义
12.7.1 不同的类
12.7.2 邻接矩阵类
12.7.3 扩充Chain类
12.7.4 类LinkedBase
12.7.5 链接类
12.8 图的遍历
12.8.1 基本概念
12.8.2 邻接矩阵的遍历函数
12.8.3 邻接链表的遍历函数
12.9 语言特性
12.9.1 虚函数和多态性
12.9.2 纯虚函数和抽象类
12.9.3 虚基类
12.9.4 抽象类和抽象数据类型
12.10 图的搜索算法
12.10.1宽度优先搜索
12.10.2 类Network
12.10.3 BFS的实现
12.10.4 BFS的复杂性分析
12.10.5 深度优先搜索
12.11 应用
12.11.1 寻找路径
12.11.2 连通图及其构件
12.11.3生成树
第三部分 算法设计方法
第13章 贪婪算法
13.1 最优化问题
13.2 算法思想
13.3 应用
13.3.1 货箱装船
13.3.2 0/昔背包问题
13.3.3 拓扑排序
13.3.4 二分覆盖
13.3.5 单源最短路径
13.3.6 最小耗费生成树
13.4 参考及推荐读物
第 14章分而治之算法
14.1 算法思想
14.2 应用
14.2.1 残缺棋盘
14.2.2 归并排序
14.2.3 快速排序
14.2.4 选择
14.2.5距离最近的点对
14.3 解递归方程
14.4 复杂性的下限
14.4.1 最小最大问题的下限
14.4.2 排序算法的下限
第 15章动态规划
15.1 算法思想
15.2 应用
15.2.1 0/l背包问题
15.2.2 图像压缩
15.2.3 矩阵乘法链
15.2.4 最短路径
15.2.5 网络的无交叉子集
15.2.6 元件折叠
15.3 参考及推荐读物
第 16章回溯
16.1 算法思想
16.2 应用
16.2.1 货箱装船
16.2.2 0/1背包问题
16.2.3 最大完备子图
16.2.4 旅行商问题
16.2.5 电路板排列
第17章分枝定界
17.1 算法思想
17.2 应用
17.2.1 货箱装船
17.2.2 0/1背包问题
17.2.3 最大完备子图
17.2.4 旅行商问题
17.2.5 电路板排列