数据结构算法与应用(C++语言描述原书第2版)/计算机科学丛书

萨特吉·萨尼编著的《数据结构算法与应用：C ++语言描述（原书第2版）》共分三个部分。第一部 分从第1章到第4章，旨在复习C++程序设计的概念以 及程序性能的分析和测量方法。第二部分从第5章到 第16章，研究数据结构，包括线性表的数组描述和链 式描述，以及用这两种描述方法描述的数组和矩阵、 栈、队列、字典、二叉树、优先级队列、竞赛树和图 等数据结构。第三部分从第17章到第21童，研究常用 算法，包括贪婪算法、分而治之算法、动态规划、回 溯算法和分支定界算法。 本书内容广博、组织合理、论述清晰、循序渐进 ，每章包含丰富的习题，对程序性能的分析和测量系 统且细致，不仅是数据结构和算法的经典教材，而且 是计算机科学与工程领域的理想参考书。

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

出版者的话 译者序 前言 第一部分 预备知识 第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.3 C++递归函数 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章 线性表——数组描述 第6章 线性表——链式描述 第7章 数组和矩阵 第8章 栈 第9章 队列 第10章 跳表和散列 第11章 二叉树和其他树 第12章 优先级队列 第13章 竞赛树 第14章 搜索树 第15章 平衡搜索树 第16章 图 第三部分 算法设计方法 第17章 贪婪算法 第18章 分而治之 第19章 动态规划 第20章 回溯法 第21章 分支定界