C++数据结构与程序设计 (2008 年度畅销榜NO.2450 )

这本精心制作的课本结合面向对象程序设计和C++强有力的特性，构建数据结构的基本思想，设计了程序和有趣的应用。在此过程中，本书探讨了作为软件设计基本工具的问题求解和设计原理、数据抽象、递归和算法的比较分析。本书使用真实的案例研究、可重用的软件开发和程序设计项目来增强理解。
本书内容详尽且配有大量的实例和习题。书中所有算法都做了详细的注解，有利于读者理解算法的实质和编程思想。
本书既可作为高等学校计算机及相关专业学生的教材，亦可供计算机应用领域的工程技术人员参考，尤其适合于应用C++语言编程的科技人员。

第1章 程序设计原理
1.1 简介
1.2 Life游戏
1.3 程序设计风格
1.4 编码、测试和进一步细化
1.5 程序维护
1.6 结论和复习
启示和易犯的错误
复习题
进阶参考书目

第2章 栈
2.1 栈说明
2.2 栈的实现
2.3 应用：桌面计算器
2.4 应用：括号的匹配
2.5 抽象数据类型及其实现
启示和易犯的错误
复习题
进阶参考书目

第3章 队列
3.1 定义
3.2 队列的实现
3.3 C++队列的循环实现
3.4 演示和测试
3.5 队列的应用：模拟
启示和易犯的错误
复习题
进阶参考书目

第4章 链栈和链式队列
4.1 指针和链式结构
4.2 链栈
4.3 带保护的链栈
4.4 链式队列
4.5 应用：多项式运算
4.6 抽象数据类型及其实现
启示和易犯的错误
复习题

第5章 递归
5.1 递归导言
5.2 递归的原理
5.3 回溯法：延缓工作
5.4 树结构的程序：在游戏中预测
启示和易犯的错误
复习题
进阶参考书目

第6章 表和字符串
6.1 表的定义
6.2 表的实现
6.3 字符串
6.4 应用：文本编辑器
6.5 数组链表
6.6 应用：生成排列
启示和易犯的错误
复习题
进阶参考书目

第7章 查找
7.1 查找：引言和符号
7.2 顺序查找
7.3 二分查找
7.4 比较树
7.5 下限
7.6 渐近
启示和易犯的错误
复习题
进阶参考书目

第8章 排序
8.1 引言和符号
8.2 插入排序
8.3 选择排序
8.4 希尔排序
8.5 下限
8.6 分而治之排序
8.7 链表的归并排序
8.8 顺序表的快速排序
8.9 堆和堆排序
8.10 复习：方法比较
启示和易犯的错误
复习题
进阶参考书目

第9章 表格和信息检索
9.1 引言：突破lg n的障碍
9.2 矩形表格
9.3 各种形态的表格
9.4 表格：一种新的抽象数据类型
9.5 应用：基数排序
9.6 哈希法
9.7 关于哈希的分析
9.8 结论：方法的比较
9.9 应用：再访Life游戏
启示和易犯的错误
复习题
进阶参考书目

第10章 二叉树
10.1 二叉树
10.2 二叉查找树
10.3 建立二叉查找树
10.4 高度平衡：AVL树
10.5 伸展树：自我调节的数据结构
启示和易犯的错误
复习题
进阶参考书目

第11章 多路树
11.1 果园.树和二叉树
11.2 词典查找树：trie
11.3 外部查找：B-树
11.4 红-黑树
启示和易犯的错误
复习题
进阶参考书目

第12章 图
12.1 数学背景
12.2 计算机表示
12.3 图的遍历
12.4 拓扑排序
12.5 贪心算法：最短路径
12.6 最小生成树
12.7 图作为数据结构
启示和易犯的错误
复习题
进阶参考书目

第13章 案例研究：波兰表示法
13.1 问题
13.2 思想
13.3 波兰表达式的求值,
13.4 从中缀式到波兰形式的转换
13.5 一个交互式的表达式求值程序
进阶参考书目

附录A 数学方法
A.1 整数幂的和
A.2 对数
A.3 排列.组合和阶乘
A.4 斐波纳契数
A.5 Catalan数
进阶参考书目

附录B 随机数
B.1 介绍
B.2 策略
B.3 程序设计
进阶参考书目

附录C 软件包和实用函数
C.1 软件包和C++转换单元
C.2 课文中的软件包
C.3 实用程序软件包
C.4 计时方法

附录D 程序设计规则.启示和易犯的错误
D.1 数据结构和算法的选择
D.2 递归
D.3 数据结构的设计
D.4 算法设计和分析
D.5 程序设计
D.6 用指针对象进行程序设计
D.7 调试和测试
D.8 维护

术语表

木匠学徒可能仅仅需要一把斧头和一把锯子, 而建筑师却使用许多精密的工具. 计算机程序设计同样需要完善的工具来应对实际应用的复杂性, 而只有不断使用这些工具进行实践, 才能积累使用技能. 本书将结构化问题求解. 面向对象的程序设计. 数据抽象以及算法的比较分析看作程序设计的基本工具. 书中详细设计了几个相当规模的案例研究, 以此说明如何同时使用所有这些工具来建立完整的程序. 我们所研究的许多算法和数据结构拥有内在的简洁性, 这是一种掩盖了它们的应用范围和能力的简洁性. 用不了多长时间, 学生即发现在预备课程中经常使用的一些天真的方法得到了巨大的改进. 然而方法的这种简洁性却被不确定性淡化了. 学生很快又发现, 几种方法中的哪一种在特定应用中能证明是最佳的, 其答案远非显而易见. 因此我们利用这个机会, 及早地介绍那些既具有内在趣味性, 又具有实际重要性的真正复杂的问题, 并展示数学方法在算法验证和分析中的应用. 许多学生感到很难将抽象的概念转化为实践. 因此, 本书特别关注了将概念表达成算法和将算法细化成能运用于实际问题的具体程序. 类似地, 本书将数据说明和抽象的过程放在数据结构选择及其实现之前. 精心设计启发性的例子, 继之以更通用的形式来表达这个概念, 我们认为这是一个从具体到抽象的发展过程. 大多数学生在其学业的早期, 需要通过目睹所学概念的直接应用来加以巩固, 他们需要编写并且运行程序, 以阐明自己所学的每个重要概念. 因此本书包含许多例子程序, 有较短的函数, 也有相当长的完整程序. 另外, 习题和程序设计项目构成了本书不可缺少的部分. 其中许多习题和项目是所学主题的直接应用, 经常要求编写和运行程序, 以此可以测试和比较算法. 有些是比较大的项目, 并且有一些项目适合学生小组共同设计完成. 本书中的程序采用流行的面向对象语言C++编写. 我们认为许多面向对象的技术为数据结构设计的基本原理提供了自然的实现. 这样, C++允许我们构造安全. 有效和简单的数据结构实现. 我们承认C++很复杂, 学生们需要通过学习一门数据结构课程来深化和提炼他们对这门语言的理解. 在编写本书的过程中, 我们尽量通过仔细介绍和解释C++各种面向对象的特征来支持这种深化. 因此, 我们在第1章开始时假设读者能自如地使用C++的基本部分(实质上是C的子集), 并逐步地加入C++的面向对象的元素, 如类. 方法. 构造函数. 继承. 动态内存管理. 析构函数. 拷贝构造函数. 重载函数和运算符. 模板. 虚函数和STL. 当然, 本书重点讲述的是数据结构, 因此对不太了解C++的学生来说, 阅读本书前需要先学习一本C++程序设计的课本. 大纲 程序设计原理 第1章通过完成首个大型项目(Conway的Life游戏), 详细说明面向对象的程序设计自顶向下的细化. 复查和测试的原理, 向学生展示这些原理, 并且希望他们从头到尾都遵循这些原理. 同时, 这个项目为学生提供了一个机会来复习C++基本特征的语法, C++是本书通篇使用的程序设计语言. 栈 第2章介绍我们要学习的第一种数据结构——栈. 本章将栈应用到反转输入. 模拟桌面计算器和检查括弧嵌套等程序设计中. 开始时利用STL栈实现, 随后设计和使用我们自己的栈实现. 第2章的一个主要目的是使学生理解信息隐藏. 封装和数据抽象这些概念后面的思想, 并将自顶向下的设计方法应用于数据和算法. 本章最后对抽象数据类型进行了介绍. 队列 队列是第3章的中心论点. 本章详细说明抽象数据类型的几种不同实现, 并设计一个大型的应用程序来说明不同实现的相对优点. 本章介绍了继承这一重要的面向对象技术. 链栈和队列 第4章提供栈和队列的链式实现. 本章首先对C++中的指针和动态内存管理做一个全面的介绍. 在展示一种简单的链栈实现后, 我们讨论析构函数. 拷贝构造函数和重载赋值运算符, 它们都是链式结构的安全的C++实现中所需要的. 递归 第5章通过研究栈与递归问题的求解和程序设计之间的关系来继续阐明栈. 本书通过研究几个实质性的递归应用来巩固这些概念, 这些应用包括回溯和树结构的程序. 如果需要的话, 本章可以安排在此处之前. 第2章结束后的任何时候学习. 表和字符串 第6章的主题是以链式和邻接实现的更通用的表. 本章也包含封装, 的字符串的实现. C++模板介绍和对算法分析的非形式化的介绍. 查找 排序 表和信息检索 第7章. 第8章和第9章分别介绍查找. 排序和表格访问(包含散列)的算法. 这些章节阐述算法和相关抽象数据类型. 数据结构及实现之间的相互关系. 课本中为初步的算法分析引入“大—O”和相关符号, 并强调在空间. 时间和程序设计强度的最佳利用方面作出关键的选择. 这些选择要求我们找到分析方法来评价算法, 而进行这些分析犹如一场战斗, 需要利用组合数学这样的武器. 在初级水平, 我们既不期望学生全面掌握, 也不期望他们拥有完备的数学知识而使自己的技能变得完美. 因此, 我们的目的是帮助学生认识到这些技能的重要性, 期待以后有机会再学习数学. 二叉树 二叉树肯定是数据结构中最精致和有用的数据结构之一. 第10章将对它进行研究, 并将它与表. 查找. 排序中的概念相结合. 作为递归定义的数据结构, 二叉树为学生灵活地在数据结构和算法中应用递归提供了条件. 本章以基本主题开始, 并进展到诸如伸展树和平摊算法分析这样的高深的主题. 多路树 第11章继续学习更复杂的数据结构, 包括Trie树. B—树和红—黑树. 图 第12章介绍图, 将它作为对问题求解有用的更通用的结构, 并介绍图中最短路径和最小生成树的一些经典算法. 案例研究：波兰表示法 第13章中的案例研究相当详细地分析了波兰表示法, 以此研究递归. 树和栈作为问题求解和算法设计工具的相互关系. 所涉及的一些问题能充当编译器设计的一个非形式化的介绍. 我们照例将这个算法完全设计成一个能运行的C++程序, 此程序接受输入普通(中缀)形式的表达式, 将它翻译成后缀形式, 并用指定的变量值评估此表达式. 第13章可安排在10. 1节完成后的任何时候学习. 附录中的几个论题并非切合于本书主题, 但学生在课程准备过程中经常遗漏它们. 数学方法 附录A介绍了离散数学中的一些论题. 它的最后两节是斐波纳契数(Fibonacci number)和卡塔兰数(Catalan number), 这两节更为复杂, 并且并非课本中任何重要论题所必需的, 但附录中将它们包含进来是鼓励更偏向数学的综合兴趣. 随机数 附录B讨论伪随机数. 生成器和应用, 这是许多学生感兴趣的论题, 但它不适合放在本课程的正文中. 软件包和实用函数 附录C对本书中设计和多次使用的各种实用程序和数据结构软件包进行分类. 附录C中讨论了声明和定义文件. 变换单位. 本书中通篇所用的实用程序包和一个计算CPU时间的软件包. 程序设计技术规则. 启示和易犯的错误 最后, 附录D收集了所有的程序设计技术规则及分散在本书中的所有启示和易犯的错误, 并将它们按主题组织以方便参考. 课程结构 必备条件 学习本书的必备条件是学习过一门基本的程序设计课程, 具有使用C++基本特征的经验. 然而, 因为我们仅仅是逐步谨慎地引入复杂的C++技术, 我们相信, 结合使用一本补充的C++课本和关于C++语言问题的更多的用法说明和重点, 加之本书提供了C++版的数据结构教程, 即使对于程序设计背景是另一门语言(如C, Pascal或Java)的学生, 这本书仍然适用. 中学数学的良好知识能满足几乎所有的算法分析的需要, 但进一步的(可能是同步的)离散数学的知识准备将颇有价值. 附录A中复习了所有要求的数学知识. 内容 本书供诸如ACM Course CS2(程序设计和实现). ACM Course CS7(数据结构和算法分析)或结合了这些课程的某门课程使用. 本书完全覆盖了ACM/IEEE关于数据结构和算法的大多数知识单元①, 它们包括： AL1基本数据结构, 如数组. 表. 栈. 队列. 树和图, AL2抽象数据类型, AL3递归和递归算法, AL4使用大Oh符号的复杂性分析, AL6排序和查找, AL8带有大型案例研究的实际问题求解策略. 本书不论述3个最高级的知识单元：AL5(复杂性类, NP—完全问题). AL7(可计算性和不可判定性)和AL9(并行和分布式算法). 本书中大多数章节都是首先介绍核心主题, 然后给出例子. 应用和更大的案例研究. 因此, 如果时间仅允许简要学习某个主题, 则可以在不失连续性的情况下, 仅学习核心主题, 快速地从一章跳到另一章. 然而当时间允许时, 学习那些附加的主题和完成的项目都将使学生和教师从中获益. 两学期课程 基本上可以用两学期的时间学完本书, 学完本书后您就可以了解问题求解. 数据结构. 程序开发和算法分析等领域的许多论题. 学生需要时间和实践来理解通用方法. 通过将数据抽象. 数据结构和算法的学习同它们在现实规模的项目中的实现相结合, 一门综合的课程可以奠定一个坚实的基础, 此后可以基于它学习更多的理论课程. 即使本书没有完全覆盖它们, 但也提供了足够的深度, 使得感兴趣的学生在以后的工作中可以继续用它作为参考书目. 无论如何, 分配主要的程序设计项目并给予足够的时间来完成它们, 这一点是重要的. 补充材料 除本书全部内容以外, 还有一些补充材料, 包括： ·来自课本的所有的软件包. 程序和其他C++代码段, 其格式便于按需并人其他程序, ·课本中一些示例程序和几乎所有程序设计项目的可执行的版本(DOS或Windows平台), ·课本中每节的提要或总结, 适于用作学习指南. 这些材料可通过ftp方式获取：以anonymous用户登录进站点ftp.prenhall. com, 并转到目录pub/esm/computer_science. s-041/kruse/cpp. 致谢 这些年来, 本书的Pascal版和C语言版得到许多人的帮助, 他们是家人. 朋友. 同事和学生, 在以前的书中曾特别提到过其中一些人. 其他的许多人在学习这些书或是其各种语言的译本的同时, 友好地将他们的意见和建议转发给我们, 所有这些都有助于我们将这本书做得更好. 感谢下列审阅者的建议, 他们在许多方面帮助我们改进本书. 他们是：Vander Linden(加尔文学院). Jens Gregor(田纳西州大学). Victor Berry(波土顿大学). Jeffery Leon(伊利诺伊大学芝加哥分校). Susan Hutt(密苏里—哥伦比亚大学). Fred Harris(内华达大学). Zhi—Li Zhang(明尼苏达大学)和Andrew Sung(新墨西哥技术学院). Alex Ryba特别感谢Marquette大学的Wim Ruitenburg和John Simms, 近年来从他们那里获得了富有成效的建议和鼓励, 还要感谢以前的学生Rick Vogel和Jun Wang提出的意见. Robert Kruse特别感谢PreTEX公司Paul Mailhot不断提出忠告并给予帮助, 他最初是一名出色的学生, 后来作为一名可靠的研究助手, 现在已成为一名得力的同事. 他在书籍制作的软件开发, 项目管理, 对出版商. 印刷工和作者的问题解答, 以及为这项工作的各方面提出忠告和鼓励等方面都做出了重要的贡献. 没有Prentice Hall的编辑人员, 特别是出版商Alan Apt. 采编Laura Steele和主编Marcia Horton热心的支持. 真诚的鼓励和极大的耐心, 这个项目不会开始, 当然也不会完成. 他们和其他制作人员的帮助是无价的.