C++数据结构与算法(第4版) 9787302376682

数据结构是计算机科学教育的基本组成部分之一，计算机科学的许多其他领域都是在此基础上建立的。对于希望从事软件系统的设计、实现、测试或者维护的读者而言，数据结构的知识是必不可少的。本书向读者提供了从事这类工作所必须具备的知识。
本书主要讲述数据结构的三个重要特性。首先，着重强调了数据结构与其算法之间的联系，包括算法的复杂度分析。其次，数据结构是以面向对象的方式呈现的，以与当前的设计以及实现范式一致。为了加强封装以及分解，特别强调了信息隐藏原则。后，本书的重要组成部分之一是数据结构的实现，在此选择C  作为编程语言。
C  语言是由C语言演化而来的面向对象语言，是一种广泛应用于产业界以及学术界的优秀编程语言。用该语言来介绍数据结构非常有效，并且很自然。由于C  在编程中的广泛应用以及语言本身的面向对象特性，使用该语言讲述数据结构以及算法课程是非常合适的，即使是入门级课程也是如此。
本书可作为入门级数据结构课程以及高级数据结构和算法课程的教材。同时还符合2008计算机科学课程中指定的以下单元的要求：DS/GraphsAndTrees、PF/DataStructures、PF/Recursion、PF/ObjectOriented、AL/BasicAnalysis、AL/AlgorithmicStrategies、AL/FundamentalAlgorithms、AL/PversusNP、PL/DeclarationsAndTypes、PL/AbstractionMechanisms、PL/ObjectOrientedProgramming。
多数章节都包含了案例分析，演示可以应用某些算法以及数据结构的情况。这些案例分析选自不同的计算机科学领域(例如解释程序、符号计算以及文件处理)，以说明正在讨论的话题可以应用的范围。
简要的C  代码示例贯穿本书，以说明数据结构的实际重要性。当然，理论分析同样重要，因此也提供了算法以及效率分析。
在介绍递归时费了很多笔墨，因为即使是高年级学生对此也存在疑问。经验表明，考虑运行时栈可以更好地解释递归。不仅在递归章节跟踪递归函数的时候显示栈中的变化，在其他章节也是如此。例如，如果在解释树遍历函数的时候不显示系统在运行时栈中所做的工作，这个短小的函数就会显得很神秘。当讨论数据结构和算法的时候，如果只是单纯地从理论上描述而脱离系统，这种做法就没有太大用处。
本书的核心是数据结构，其他话题的引入只是为了更好地理解数据结构。算法是从数据结构的观点来讨论的，因此读者不会看到各种算法的全面讨论，也没有列出介绍一个算法所需要的全部内容。当然，如前所述，本书将深入讨论递归。此外还会深入探讨算法的复杂度分析。
第1章以及第3～第8章介绍一些不同的数据结构以及相应的算法。分析了所有算法的效率，并给出了算法的改进建议。
● 第1章介绍面向对象编程的基本原则，介绍动态内存分配以及指针的应用，并初步讲述标准模版库(STL)。
● 第2章讲述一些评估算法效率的方法。
● 第3章介绍不同类型的链表，并强调使用指针实现链表。
● 第4章介绍栈和队列及其应用。
● 第5章详细讨论递归，在此讨论不同类型的递归，并剖析了递归调用。
● 第6章讨论二叉树，包括二叉树的实现、遍历以及查找。该章还讲述平衡二叉树。
● 第7章讲述更为一般的树，例如trie树、2-4树以及B树。
● 第8章介绍图。
第9～第13章讲述前面章节中数据结构的不同应用。在此强调这些应用的数据结构特性。
● 第9章详细分析排序，介绍了一些基本方法以及一些高级方法。
● 第10章讨论查找领域中非常重要的一种算法——散列算法，在此给出了多种技术，以强调数据结构的应用。
● 第11章讨论数据压缩算法和数据结构。
● 第12章介绍内存管理的各种技术以及数据结构。
● 第13章介绍字符串准确匹配和近似匹配的很多算法。
● 附录A详细介绍大O表示法，该内容在第2章提到过。
● 附录B介绍标准模版库中的标准算法。
● 附录C证明了Cook定理，并给出了大量示例进行演示。
每一章都包含了演示材料的讨论，并配以恰当的图表。除第2章外，每一章都包含了案例分析，这是适用相应章节讨论特性的扩展示例。所有的案例分析都在PC上用Visual C  编译器测试通过，并且在Unix下用g  编译器测试通过，von Koch snowflake是个例外，它只在PC上用Visual C  测试过。每一章的后都有一组不同难度的练习题。除第2章外，所有章节都安排了编程练习，以及与之相关的参考书目。
第1～第6章(不包括2.9节、2.10节、3.4节、6.4.3小节、6.7节、6.8节、6.10节和6.11节)包含的核心材料是任何数据结构课程的基础。这几章应该按顺序阅读，其余几章可以按任何顺序阅读。一学期的课程可以包括第1～第6章、第9章、10.1节和10.2节。整本书也可以作为两学期课程的一部分。
学习资料
可以从http://www.tupwk.com.cn/downpage下载示例程序源代码。
第4版的改动
新版本主要包含一些旧版本中没有讲述的内容，包括：
● 讲述treap(6.10节)以及k-d树(6.11节)的章节
● 讲述k-d B树(7.1.5小节)的章节
● 关于另外两种排序方法的讨论(9.1.4小节和9.3.6小节)
● 新的散列技术(10.5.1小节)
● 关于通用垃圾回收的章节(12.3.4小节)
整本书中还有一些小的改动以及添加。

乔兹德克编著的《C  数据结构与算法（第4版）》全面系统地介绍了数据结构，并以C  语言实现相关的算法。书中主要强调了数据结构和算法之间的联系，使用面向对象的方法介绍数据结构，其内容包括算法的复杂度分析、链表、栈、队列、递归、二叉树、图、排序和散列。本书还清晰地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配等主题。书中包含大量的示例分析和图形，便于读者进一步理解和巩固所学的知识。

乔兹德克编著的《C 数据结构与算法（第4版）》全面系统地介绍了数据结构，并以C 语言实现相关的算法。书中主要强调了数据结构和算法之间的联系，使用面向对象的方法介绍数据结构，其内容包括算法的复杂度分析、链表、栈、队列、递归、二叉树、图、排序和散列。本书还清晰地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配等主题。书中包含大量的示例分析和图形，便于读者进一步理解和巩固所学的知识。

AdamDrozdek毕业于美国莱特州立大学，现任迪尤肯大学计算机科学系副教授，出版过多部数据结构和算法方面的专业书籍，包括本书和DataStructuresandAlgorithmsinJava等。

第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 Ω表示法与Θ表示法
　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章 递归
第6章 二叉树
第7章 多叉树
第8章 图
第9章 排序
第10章 散列
第11章 数据压缩
第12章 内存管理
第13章 字符串匹配
附录A 计算大O
附录B 标准模板库中的算法
附录C NP完整性

乔兹德克编著的《C  数据结构与算法（第4版）》全面系统地介绍了数据结构，并以C  语言实现相关的算法。书中主要强调了数据结构和算法之间的联系，使用面向对象的方法介绍数据结构，其内容包括算法的复杂度分析、链表、栈、队列、递归、二叉树、图、排序和散列。本书还清晰地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配等主题。书中包含大量的示例分析和图形，便于读者进一步理解和巩固所学的知识。

AdamDrozdek毕业于美国莱特州立大学，现任迪尤肯大学计算机科学系副教授，出版过多部数据结构和算法方面的专业书籍，包括本书和DataStructuresandAlgorithmsinJava等。