内容简介
本书是作者根据他在滑铁卢大学计算机工程学院教授数据结构与算法课程的经验编写而成的。它采用C++面向对象的设计模式，不仅系统全面地介绍了各种传统的数据结构，还把它们按照类和类层次的现代理念予以展开，进而达到抽象结构与实际设计的统一。本书的后三章通过引入抽象问题求解的概念，集中讲述了算法技术和各算法之间的关系。另外，作者运用一定的数学工具以及必要的分析技术和分析理论，对每种数据结构及相关算法都进行了时间和空间效率分析。 作为教科书，本书作者还在每章后面布置了习题和设计项目，并在全书的后面给出了问题参考答案，希望读者能从其中汲取宝贵的知识与经验。
目录
第1章 概要 1.1 本书的主要内容 1.2 面向对象的设计 1.3 对象分级与设计方法 1.4 需要了解的C＋＋特性 1.5 本书是如何组织的？ 第2章 算法分析 2.1 一个细化的计算机模型 2.1.1 基本公理 2.1.2 例1：算术级数求和 2.1.3 数组下标操作 2.1.4 例2：霍纳（Horner）法则 2.1.5 分析递归函数 2.1.6 例3：找出数组中元素 2.1.7 平均运行时间 2.1.8 关于调和数 2.1.9 情况与情况的运行时间 2.1.10 的公理 2.2 一个简化的计算机模型 2.2.1 例1：求几何级数之和 2.2.2 关于算术级数求和 2.2.3 例2：再次求几何级数之和 2.2.4 关于几何级数求和 2.2.5 例3：幂计算 2.2.6 例4：再三求几何级数之和 习题 设计项目 第3章 渐近表示法 3.1 渐近上界——大O表示法 3.1.1 一个简单的例子 3.1.2 大O表示法中的错误与陷阱 3.1.3 大O的特性 3.1.4 多项式 3.1.5 对数 3.1.6 紧凑大O界 3.1.7 大O表示法中更多的错误与陷阶 3.1.8 常用的大O表达式 3.2 渐近下界——表示法 3.2.1 一个简单的例子 3.2.2 再次关于多项式 3.3 更多的表示法——及小o表示法 3.4 算法渐近分析 3.4.1 运行时间分析的大O规则 3.4.2 例1：求级数的前项和 3.4.3 例2：Fibonacci数 3.4.4 例3：桶式排序 3.4.5 现实检查 3.4.6 检查你的分析 习题 设计项目 第4章 基本数据结构 4.1 动态数组 4.1.1 缺省构造函数 4.1.2 数组构造函数 4.1.3 备份构造函数 4.1.4 析构函数 4.1.5 数组成员函数 4.1.6 数组下标操作符 4.1.7 数组大小的重调 4.2 单链表 4.2.1 链表的实现 4.2.2 链表元素 4.2.3 缺省构造函数 4.2.4 析构函数与Purge成员函数 4.2.5 存取器 4.2.6 First与Last函数 4.2.7 前插 4.2.8 添加 4.2.9 备份构造函数与赋值操作符 4.2.10 析取函数 4.2.11 InsertAfter与InsertBefore函数 4.3 多维数组 4.3.1 数组下标计算 4.3.2 二维数组的实现 4.3.3 C＋＋中多维数组的下标 4.3.4 例：规范矩阵相乘 习题 设计项目 第5章 数据类型与抽象 5.1 抽象数据类型 5.2 设计模式 5.2.1 类层次 5.2.2 对象 5.2.3 NullObject单元集类 5.2.4 内嵌类型的对象包装 5.2.5 容器 5.2.6 访问者 5.2.7 迭代器 5.2.8 NullIterator类 5.2.9 直接存储与间接存储 5.2.10 被包含对象的所有权 5.2.11 关联 5.2.12 可搜索容器 习题 设计项目 第6章 栈. 队列及双端队列 6.1 栈 6.1.1 栈的数组表示法 6.1.2 栈的链表表示法 6.1.3 应用 6.2 队列 6.2.1 队列的数组表示法 6.2.2 队列的链表表示法 6.2.3 应用 6.3 双端队列 6.3.1 双端队列的数组表示法 6.3.2 双端队列的链表表示法 6.3.3 双向链表及循环链表 习题 设计项目 第7章 有序线性表与排序表 7.1 有序线性表 7.1.1 有序线性表的数组表示法 7.1.2 有序线性表的链表表示法 7.1.3 比较ListASArray和ListASlinkedList 7.1.4 应用 7.2 排序表 7.2.1 排序表的数组表示法 7.2.2 排序表的链表表示法 7.2.3 比较SortedListAsArray和SortedListAslinkedList 7.2.4 应用 习题 设计项目 第8章 散列. 哈希表及分散表 8.1 散列的基本知识 8.1.1 关键字和散列函数 8.2 散列法 8.2.1 相除散列法 8.2.2 平方取中散列法 8.2.3 相乘散列法 8.2.4 Fibonacci散列法 8.3 散列函数的实现 8.3.1 整型关键字 8.3.2 浮点型关键字 8.3.3 字符串关键字 8.3.4 散列对象 8.3.5 散列容器 8.3.6 使用关联 8.4 哈希表 8.4.1 拉链法 8.4.2 平均情况分析 8.5 分散表 8.5.1 链式分散表 8.5.2 平均情况分析 8.6 使用开地址法的分散表 8.6.1 线性探查 8.6.2 二次探查 8.6.3
