本书是*经典数据结构教材的*新版本,国内外大多数的同类教材都是以本书为蓝本编写而来的。
本书用C++作为描述语言,全面而生动地介绍了数据结构的有关知识,如数组、栈、队列、链表、树和图,以及构成所有软件基础的排序散列技术。此外,本书还介绍了各种**或特殊数据结构,如优先级队列、**二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在*优、*差情形下的复杂度分析。本书的更新版已涵盖了C++语言的*新特性。
本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材,也可以作为研究生**学年的“高等数据结构”课程的教材,同时,本书所介绍的各种算法的C++语言实现,对有关专业人员也具有很好的参考价值。

第1章 基本概念
1.1 概述:系统生命周期
我们假定本书读者已经全面学习了程序设计的基本课程,并具备了扎实的编程基础。程序设计的基本方法通常强调的是掌握一门编程语言的语法(它的语法规则),并且应用这门语言去解决一些相对小的问题。本书将超越基本概念和方法的局限,提供一些对于设计和实现大规模计算机系统所必须的工具和技术。我们相信,在数据抽象和封装、算法规范、性能分析和测量等方面坚实的基础将会为读者提供必要的程序设计方法学。本章将讨论这方面的一些细节。还将简略地讨论递归程序,因为许多读者可能对这种重要的技术仅仅只有粗浅的认识。然而,在开始讨论具体的工具和技术以前,需要强调的是,程序设计不仅仅是编写代码,还包括许多其他的内容。一个好的程序员把大规模计算机程序看成是一个包含了许多复杂交互部分的系统。作为系统,这些程序要经历一个被称为“系统生命周期”的开发过程。这个生命周期由需求、分析、设计、编码和验证等阶段组成。尽管我们将分别讨论这些生命周期阶段,但它们是密切相互关联的,而且对这些生命周期阶段的时间划分也是粗略的。在第1.8节中,列出了一些关于系统生命周期及其各个不同阶段的一些资料,这些资料将给读者提供更详细的补充信息。
(1)需求。所有大型的程序设计项目在开始时,都需要定义一组描述该项目目标的规格说明。这些需求描述了程序所必须得到的信息(输入),以及必然产生的结果(输出)。通常,初始的规格说明都是含糊不清的,必须经过逐步细化,才能够得到严格的包括各种情况的输入和输出描述。
……

第1章 基本概念
1.1 概述:系统生命周期
1.2 面向对象的程序设计
1.3 数据抽象和封装
1.4 C++语言基础
1.5 算法规范
1.6 标准模板库
1.7 性能分析和度量
1.8 参考文献和**读物
第2章 数组
2.1 抽象数据类型和C++类
2.2 将数组作为一种抽象数据类型
2.3 多项式抽象数据类型
2.4 稀疏矩阵
2.5 多维数组的表示
2.6 字符串抽象数据类型
2.7 参考文献和**读物
2.8 附加习题
第3章 栈和队列
3.1 C++模板
3.2 栈的抽象数据类型
3.3 队列抽象数据类型
3.4 C++中的子类型和继承
3.5 一个迷宫问题
3.6 计算表达式
3.7 附加习题
第4章 链表
4.1 单链表和链
4.2 用C++语言表示链表
4.3 链的模板类
4.4 循环链表
4.5 可用空间链表
4.6 链式栈和链式队列
4.7 多项式
4.8 等价类
4.9 稀疏矩阵
4.10 双向链表
4.11 广义表
第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 参考文献和**读物
第6章 图
6.1 图的抽象数据类型
6.2 图的基本操作
6.3 *小代价生成树
6.4 *短路径和传递闭包
6.5 活动网络
6.6 参考文献和**读物
6.7 附加习题
第7章 排序
7.1 目的
7.2 插入排序
7.3 快速排序
7.4 排序算法能够多快
7.5 归并排序
7.6 堆排序
7.7 多关键字排序
7.8 链和列表排序
7.9 内部排序总结
7.10 外部排序
7.11 参考文献和**读物
第8章 散列
第9章 优先队列
第10章 **二叉查找树
第11章 多路查找树
第12章 数字查找结构
术语表