C++数据结构与算法（第4版）

　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》全面系统地介绍了数据结构，并以C++语言实现相关的算法。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》中主要强调了数据结构和算法之间的联系，使用面向对象的方法介绍数据结构，其内容包括算法的复杂度分析、链表、栈、队列、递归、二叉树、图、排序和散列。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》中还清晰地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配等主题。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》中包含大量的示例分析和图形，便于读者进一步理解和巩固所学的知识。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》的示例分析贯穿全书，便于学生在真实的环境下了解数据结构的概念。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》每章最后都提供了编程练习，给学生提供额外的实践机会，巩固所学内容。
　　《C++数据结构与算法（第4版）/国外计算机科学经典教材》配以大量的图形，使学生对数据结构有直观的理解。

第1章 C++面向对象程序设计
1．1 抽象数据类型
1．2 封装
1．3 继承
1．4 指针
1．4．1 指针与数组
1．4．2 指针与复制构造函数
1．4．3 指针与析构函数
1．4．4 指针和引用变量
1．4．5 函数指针
1．5 多态性
1．6 C++和面向对象程序设计
1．7 标准模板库
1．7．1 容器
1．7．2 迭代器
1．7．3 算法
1．7．4 函数对象
1．8 标准模板库中的向量
1．9 数据结构与面向对象编程
1．10 案例分析：随机访问文件
1．11 习题
1．12 编程练习
参考书目

第2章 复杂度分析
2．1 计算复杂度以及渐近复杂度
2．2 大O表示法
2．3 大O表示法的性质
2．4 Q表示法与@表示法
2．5 可能存在的问题
2．6 复杂度示例
2．7 确定渐近复杂度示例
2．8 最好、平均和最坏情况
2．9 摊销复杂度（amortized complexity）
2．10 NP完整性
2．11 习题
参考书目

第3章 链表
3．1 单向链表
3．1．1 插入
3．1．2 删除
3．1．3 查找
3．2 双向链表
3．3 循环链表
3．4 跳跃链表（skip list）
3．5 自组织链表
3．6 稀疏表
3．7 标准模板库中的链表
3．8 小结
3．9 案例分析：图书馆
3．10 习题
3．11 编程练习
参考书目

第4章 栈与队列
4．1 栈
4．2 队列
4．3 优先队列
4．4 标准模板库中的栈
4．5 标准模板库中的队列
4．6 标准模板库中的优先队列
4．7 标准模版库中的双端队列
4．8 案例分析：迷宫问题
4．9 习题
4．10 编程练习
参考书目

第5章 递归
5．1 递归定义
5．2 函数调用与递归实现
5．3 分析递归调用
5．4 尾递归
5．5 非尾递归
5．6 间接递归
5．7 嵌套递归
5．8 不合理递归
5．9 回溯
5．10 小结
5．11 案例分析：递归下降解释器
5．12 习题
5．13 编程练习
参考书目

第6章 二叉树
6．1 树、二叉树和二叉查找树
6．2 二叉树的实现
6．3 二叉查找树的查找
6．4 树的遍历
6．4．1 广度优先遍历
6．4．2 深度优先遍历
……

第7章 多叉树
第8章 图
第9章 排序
第10章 散列
第11章 数据压缩
第12章 内存管理
第13章 字符串匹配

附录A 计算大O
附录B 标准模板库中的算法
附录C NP完整性

　　数据结构是计算机科学教育的基本组成部分之一，计算机科学的许多其他领域都是在此基础上建立的。对于希望从事软件系统的设计、实现、测试或者维护的读者而言，数据结构的知识是必不可少的。本书向读者提供了从事这类工作所必须具备的知识。
　　本书主要讲述数据结构的三个重要特性。首先，着重强调了数据结构与其算法之间的联系，包括算法的复杂度分析。其次，数据结构是以面向对象的方式呈现的，以与当前的设计以及实现范式一致。为了加强封装以及分解，特别强调了信息隐藏原则。最后，本书的重要组成部分之一是数据结构的实现，在此选择C++作为编程语言。
　　C++语言是由C语言演化而来的面向对象语言，是一种广泛应用于产业界以及学术界的优秀编程语言。用该语言来介绍数据结构非常有效，并且很自然。由于C++在编程中的广泛应用以及语言本身的面向对象特性，使用该语言讲述数据结构以及算法课程是非常合适的，即使是入门级课程也是如此。
　　本书可作为入门级数据结构课程以及高级数据结构和算法课程的教材。同时还符合2008计算机科学课程中指定的以下单元的要求：DS/GraphsAndTrees、PF/DataStructures、PF/Recursion、PF/ObjectOriented、AL/BasicAnalysis、AL/AlgorithmicStrategies、AL/FundamentaIAlgorithms、AL/PvesusNP、PL/DeclarationsAndTypes、PL/AbsrractionMechanisms、PL/ObjectOrientedProgramming.
　　多数章节都包含了案例分析，演示可以应用某些算法以及数据结构的情况。这些案例分析选自不同的计算机科学领域（例如解释程序、符号计算以及文件处理），以说明正在讨论的话题可以应用的范围。
　　简要的CH代码示例贯穿本书，以说明数据结构的实际重要性。当然，理论分析同样重要，因此也提供了算法以及效率分析。
　　在介绍递归时费了很多笔墨，因为即使是高年级学生对此也存在疑问。经验表明，考虑运行时栈可以更好地解释递归。不仅在递归章节跟踪递归函数的时候显示栈中的变化，在其他章节也是如此。例如，如果在解释树遍历函数的时候不显示系统在运行时栈中所做的工作，这个短小的函数就会显得很神秘。当讨论数据结构和算法的时候，如果只是单纯地从理论上描述而脱离系统，这种做法就没有太大用处。
　　本书的核心是数据结构，其他话题的引入只是为了更好地理解数据结构。算法是从数据结构的观点来讨论的，因此读者不会看到各种算法的全面讨论，也没有列出介绍一个算法所需要的全部内容。当然，如前所述，本书将深入讨论递归。此外还会深入探讨算法的复杂度分析。
　　第1章以及第3～第8章介绍一些不同的数据结构以及相应的算法。分析了所有算法的效率，并给出了算法的改进建议。