数据结构与算法—面向对象的C++设计模式 (2009 年度畅销榜NO.3724 )

本书是作者根据他在滑铁卢大学计算机工程学院教授数据结构与算法课程的经验编写而成的。它采用C++面向对象的设计模式，不仅系统全面地介绍了各种传统的数据结构，还把它们按照类和类层次的现代理念予以展开，进而达到抽象结构与实际设计的完美统一。本书的后三章通过引入抽象问题求解的概念，集中讲述了算法技术和各算法之间的关系。另外，作者运用一定的数学工具以及必要的分析技术和分析理论，对每种数据结构及相关算法都进行了时间和空间效率分析。\r\n 作为教科书，本书作者还在每章后面布置了习题和设计项目，并在全书的后面给出了问题参考答案，希望读者能从其中汲取宝贵的知识与经验。

第1章 概要\r\n\r\n1.1 本书的主要内容\r\n1.2 面向对象的设计\r\n1.3 对象分级与设计方法\r\n1.4 需要了解的C＋＋特性\r\n1.5 本书是如何组织的？\r\n\r\n第2章 算法分析\r\n\r\n2.1 一个细化的计算机模型\r\n2.1.1 基本公理\r\n2.1.2 例1：算术级数求和\r\n2.1.3 数组下标操作\r\n2.1.4 例2：霍纳（Horner）法则\r\n2.1.5 分析递归函数\r\n2.1.6 例3：找出数组中最大元素\r\n2.1.7 平均运行时间\r\n2.1.8 关于调和数\r\n2.1.9 最佳情况与最差情况的运行时间\r\n2.1.10 最后的公理\r\n2.2 一个简化的计算机模型\r\n2.2.1 例1：求几何级数之和\r\n2.2.2 关于算术级数求和\r\n2.2.3 例2：再次求几何级数之和\r\n2.2.4 关于几何级数求和\r\n2.2.5 例3：幂计算\r\n2.2.6 例4：再三求几何级数之和\r\n习题\r\n设计项目\r\n\r\n第3章 渐近表示法\r\n\r\n3.1 渐近上界——大O表示法\r\n3.1.1 一个简单的例子\r\n3.1.2 大O表示法中的错误与陷阱\r\n3.1.3 大O的特性\r\n3.1.4 多项式\r\n3.1.5 对数\r\n3.1.6 紧凑大O界\r\n3.1.7 大O表示法中更多的错误与陷阶\r\n3.1.8 常用的大O表达式\r\n3.2 渐近下界——表示法\r\n3.2.1 一个简单的例子\r\n3.2.2 再次关于多项式\r\n3.3 更多的表示法——及小o表示法\r\n3.4 算法渐近分析\r\n3.4.1 运行时间分析的大O规则\r\n3.4.2 例1：求级数的前项和\r\n3.4.3 例2：Fibonacci数\r\n3.4.4 例3：桶式排序\r\n3.4.5 现实检查\r\n3.4.6 检查你的分析\r\n习题\r\n设计项目\r\n\r\n第4章 基本数据结构\r\n\r\n4.1 动态数组\r\n4.1.1 缺省构造函数\r\n4.1.2 数组构造函数\r\n4.1.3 备份构造函数\r\n4.1.4 析构函数\r\n4.1.5 数组成员函数\r\n4.1.6 数组下标操作符\r\n4.1.7 数组大小的重调\r\n4.2 单链表\r\n4.2.1 链表的实现\r\n4.2.2 链表元素\r\n4.2.3 缺省构造函数\r\n4.2.4 析构函数与Purge成员函数\r\n4.2.5 存取器\r\n4.2.6 First与Last函数\r\n4.2.7 前插\r\n4.2.8 添加\r\n4.2.9 备份构造函数与赋值操作符\r\n4.2.10 析取函数\r\n4.2.11 InsertAfter与InsertBefore函数\r\n4.3 多维数组\r\n4.3.1 数组下标计算\r\n4.3.2 二维数组的实现\r\n4.3.3 C＋＋中多维数组的下标\r\n4.3.4 例：规范矩阵相乘\r\n习题\r\n设计项目\r\n\r\n第5章 数据类型与抽象\r\n\r\n5.1 抽象数据类型\r\n5.2 设计模式\r\n5.2.1 类层次\r\n5.2.2 对象\r\n5.2.3 NullObject单元集类\r\n5.2.4 内嵌类型的对象包装\r\n5.2.5 容器\r\n5.2.6 访问者\r\n5.2.7 迭代器\r\n5.2.8 NullIterator类\r\n5.2.9 直接存储与间接存储\r\n5.2.10 被包含对象的所有权\r\n5.2.11 关联\r\n5.2.12 可搜索容器\r\n习题\r\n设计项目\r\n\r\n第6章 栈、队列及双端队列\r\n\r\n6.1 栈\r\n6.1.1 栈的数组表示法\r\n6.1.2 栈的链表表示法\r\n6.1.3 应用\r\n6.2 队列\r\n6.2.1 队列的数组表示法\r\n6.2.2 队列的链表表示法\r\n6.2.3 应用\r\n6.3 双端队列\r\n6.3.1 双端队列的数组表示法\r\n6.3.2 双端队列的链表表示法\r\n6.3.3 双向链表及循环链表\r\n习题\r\n设计项目\r\n\r\n第7章 有序线性表与排序表\r\n\r\n7.1 有序线性表\r\n7.1.1 有序线性表的数组表示法\r\n7.1.2 有序线性表的链表表示法\r\n7.1.3 比较ListASArray和ListASLinkedList\r\n7.1.4 应用\r\n7.2 排序表\r\n7.2.1 排序表的数组表示法\r\n7.2.2 排序表的链表表示法\r\n7.2.3 比较SortedListAsArray和SortedListAsLinkedList\r\n7.2.4 应用\r\n习题\r\n设计项目\r\n\r\n第8章 散列、哈希表及分散表\r\n\r\n8.1 散列的基本知识\r\n8.1.1 关键字和散列函数\r\n8.2 散列法\r\n8.2.1 相除散列法\r\n8.2.2 平方取中散列法\r\n8.2.3 相乘散列法\r\n8.2.4 Fibonacci散列法\r\n8.3 散列函数的实现\r\n8.3.1 整型关键字\r\n8.3.2 浮点型关键字\r\n8.3.3 字符串关键字\r\n8.3.4 散列对象\r\n8.3.5 散列容器\r\n8.3.6 使用关联\r\n8.4 哈希表\r\n8.4.1 拉链法\r\n8.4.2 平均情况分析\r\n8.5 分散表\r\n8.5.1 链式分散表\r\n8.5.2 平均情况分析\r\n8.6 使用开地址法的分散表\r\n8.6.1 线性探查\r\n8.6.2 二次探查\r\n8.6.3 双散列法\r\n8.6.4 开地址法的实现\r\n8.6.5 平均情况分析\r\n8.7 应用\r\n习题\r\n设计项目\r\n\r\n第9章 树\r\n\r\n9.1 基础\r\n9.2 N叉树\r\n9.3 二叉树\r\n9.4 树的遍历\r\n9.5 表达式树\r\n9.6 树的实现\r\n9.6.1 树的遍历\r\n9.6.2 树迭代器\r\n9.6.3 广义树\r\n9.6.4 N叉树\r\n9.6.5 二叉树\r\n9.6.6 二叉树的遍历\r\n9.6.7 树的比较\r\n9.6.8 应用\r\n习题\r\n设计项目\r\n\r\n第10章 查找树\r\n\r\n10.1 基础知识\r\n10.1.1 M路查找树\r\n10.1.2 二叉查找树\r\n10.2 搜索查找树\r\n10.2.1 搜索M路查找树\r\n10.2.2 搜索二叉树\r\n10.3 平均情况分析\r\n10.3.1 搜索成功\r\n10.3.2 递归关系的求解——拓展递归法\r\n10.3.3 搜索失败\r\n10.3.4 查找树的遍历\r\n10.4 查找树的实现\r\n10.4.1 二叉查找树\r\n10.4.2 在二叉查找树中插入数据项\r\n10.4.3 从二叉查找树中删除数据项\r\n10.5 AVL查找树\r\n10.5.1 AVL树的实现\r\n10.5.2 在AVL树中插入数据项\r\n10.5.3 从AVL树中删除数据项\r\n10.6 M路查找树\r\n10.6.1 M路查找树的实现\r\n10.6.2 在M路查找树中查找数据项\r\n10.6.3 在M路查找树中插入数据项\r\n10.6.4 从M路查找树中删除数据项\r\n10.7 B树\r\n10.7.1 B树的实现\r\n10.7.2 在B树中插入数据项\r\n10.7.3 从B树中删除数据项\r\n10.8 应用\r\n习题\r\n设计项目\r\n\r\n第11章 堆和优先队列\r\n\r\n11.1 基础知识\r\n11.2 二叉堆\r\n11.2.1 完全树\r\n11.2.2 二叉堆的实现\r\n11.2.3 在二叉堆中插入数据项\r\n11.2.4 从二叉堆中删除数据项\r\n11.3 左翼堆\r\n11.3.1 左翼树\r\n11.3.2 左翼堆的实现\r\n11.3.3 左翼堆的合并\r\n11.3.4 在左翼堆中插入数据项\r\n11.3.5 从左翼堆中删除数据项\r\n11.4 二项队列\r\n11.4.1 二项树\r\n11.4.2 二项队列\r\n11.4.3 实现\r\n11.4.4 二项队列的合并\r\n11.4.5 在二项队列中插入数据项\r\n11.4.6 从二项队列中删除数据项\r\n11.5 应用\r\n11.5.1 离散事件模拟\r\n11.5.2 实现\r\n习题\r\n设计项目\r\n\r\n第12章 集合、多重集和分区\r\n\r\n12.1 基础知识\r\n12.1.1 集合的实现\r\n12.2 数组和位矢量集合\r\n12.2.1 位矢量集合\r\n12.3 多重集\r\n12.3.1 多重集的数组表示法\r\n12.3.2 多重集的链表表示法\r\n12.4 分区\r\n12.4.1 用森林表示分区\r\n12.4.2 折叠查找\r\n12.4.3 按大小合并\r\n12.4.4 按高度或层号合并\r\n12.5 应用\r\n习题\r\n设计项目\r\n\r\n第13章 动态存储分配：另一种堆\r\n\r\n13.1 基础\r\n13.1.1 C＋＋ Magic\r\n13.1.2 堆\r\n13.2 单链自由存储器\r\n13.2.1 实现\r\n13.3 双链自由存储器\r\n13.3.1 实现\r\n13.4 伙伴存储管理系统\r\n13.4.1 实现\r\n13.5 应用\r\n13.5.1 实现\r\n习题\r\n设计项目\r\n\r\n第14章 算法模式和问题求解\r\n\r\n14.1 蛮干算法和贪心算法\r\n14.1.1 例1：数钱\r\n14.1.2 例2：0／1背包问题\r\n14.2 回溯算法\r\n14.2.1 例1：平衡称\r\n14.2.2 解空间的表示\r\n14.2.3 抽象回溯求解程序\r\n14.2.4 分支界限求解程序\r\n14.2.5 例2：再次分析0／1背包问题\r\n14.3 自顶向下算法：分治算法\r\n14.3.1 例1：二分法查找\r\n14.3.2 例2：求解Fibonacci数\r\n14.3.3 例3：归并排序\r\n14.3.4 分治算法的运行时间\r\n14.3.5 例4：矩阵相乘\r\n14.4 自底向上算法：动态程序设计\r\n14.4.1 例1：广义Fibonacci数\r\n14.4.2 例2：求解二项式系数\r\n14.4.3 应用：排版问题\r\n14.5 随机化算法\r\n14.5.1 产生随机数\r\n14.5.2 随机变量\r\n14.5.3 蒙特卡罗法\r\n14.5.4 模拟退火法\r\n习题\r\n设计项目\r\n\r\n第15章 排序算法和排序器\r\n\r\n15.1 基础知识\r\n15.2 排序和排序器\r\n15.3 插入排序\r\n15.3.1 直接插入排序\r\n15.3.2 平均运行时间\r\n15.3.3 二分法插入排序\r\n15.4 交换排序\r\n15.4.1 冒泡排序\r\n15.4.2 快速排序\r\n15.4.3 运行时间分析\r\n15.4.4 平均运行时间\r\n15.4.5 轴值的选择\r\n15.5 选择排序\r\n15.5.1 直接选择排序\r\n15.5.2 堆排序\r\n15.5.3 堆的建立\r\n15.6 归并排序\r\n15.7 排序算法的下界\r\n15.8 分配排序\r\n15.8.1 桶式排序\r\n15.8.2 基数排序\r\n15.9 算法性能分析\r\n习题\r\n设计项目\r\n\r\n第16章 图和图算法\r\n\r\n16.1 基础知道\r\n16.1.1 图的表示法\r\n16.2 图的实现\r\n16.2.1 顶点的实现\r\n16.2.3 抽象图和有向图\r\n16.2.4 无向图的实现\r\n16.2.5 边带权图和顶点带权图\r\n16.2.6 图表示法的比较\r\n16.3 图的遍历\r\n16.3.1 深度优先遍历\r\n16.3.2 广度优先遍历\r\n16.3.3 拓扑排序\r\n16.3.4 图遍历的应用：检查图的回路及连通性\r\n16.4 最短路径算法\r\n16.4.1 单源最短路径\r\n16.4.2 每对顶点间的最短路径\r\n16.5 最小支撑树\r\n16.5.1 Prim算法\r\n16.5.2 Kruskal算法\r\n16.6 应用：关键路径分析\r\n习题\r\n设计项目\r\n\r\n附录A C＋＋与面向对象编程\r\n附录B 类层次图\r\n附录C 字符码\r\n参考答案