数据结构（C++语言描述） (2008 年度畅销榜NO.9161 )

本书是一部关于数据结构(C++语言描述)的全新的教材。内容新颖全面，讲解通俗易懂，结构清晰合理。编写时通过贴近实际的事例和清晰的图示表现数据结构课程的内容及相关的算法思想，以求激发学生掌握专业基础理论的兴趣和满足学生实际应用的需要。
全书共8章，包括绪论、线性表、栈和队列、数组和广义表、树和二叉树、图、查找、排序等内容。各章根据不同的教学目标，恰当合理地安排了内容层次及应用实例和相应的习题。
本书总结了作者一线教学20余年的经验，注重研究教与学的特点，充分考虑学生的需求。通过阅读本书，可对数据结构有全面的了解，并为进一步深入学习和研究计算机科学技术奠定基础。本书可作为普通高校、高等职业技术学校计算机类各专业、信息类及相关专业本、专科学生的教材或教学参考书，也可供非计算机专业学生选用，同时希望对自学计算机软件开发的人员也有所帮助。

第1章 绪论
1.1 程序二算法+数据结构
1.1.1 程序的产生及对程序的分析
1.1.2 算法的概念及对算法的要求
1.1.3 算法与程序的关系及算法的描述方法
1.1.4 数据结构简介
1.2 数据结构的基本内涵
1.2.1 数据结构研究的内容
1.2.2 基本概念和术语
1.2.3 数据的存储结构
1.2.4 数据结构的表示
1.3 时间复杂度和空间复杂度
1.3.1 时间复杂度
1.3.2 空间复杂度
1.4数据结构与面向对象编程
习题1
第2章 线性表
2.1 线性表的逻辑特点
2.2 线性表的顺序存储结构顺序表
2.2.1 顺序表定义
2.2.2 顺序表基本操作的实现
2.2.3 典型应用多项式求值
2.3 线性表的链式存储结构链表
2.3.1 单向链表的类定义
2.3.2 基本运算的实现
2.3.3 基本操作的实现
2.3.4 循环链表与双向链表
2.3.5 典型应用多项式表示及相加
习题2
第3章 栈和队列
3.1 栈的概念
3.1.1 栈的定义和特征
3.1.2 栈的基本操作
3.2 顺序栈栈的顺序存储表示
3.2.1 顺序栈的类定义
3.2.2 其他基本操作的实现
3.2.3 多栈共享空间
3.2.4 栈的应用
3.3 栈的链式存储结构链栈
3.3.1 链栈的类定义
3.3.2 部分操作的实现
3.4 队列的基本概念
3.5 队列的链式存储结构链队列
3.5.1 链队列的的概念和特征
3.5.2 链队列的表示与实现
3.6 队列的J1顷序存储结构
3.6.1 JI顷序存储的队列
3.6.2 以数组表示的循环队列
3.6.3 应用举例
3.7 优先级队列
3.7.1 优先级队列的基本概念
3.7.2 优先级队列的类定义
3.7.3 优先级队列的存储表示和实现
3.7.4 优先级队列的应用实例
习题3
第4章 数组和广义表
4.1 数组的逻辑特点
4.2 数组的存储结构
4.2.1 一维数组
4.2.2 维数组
4.2.3 多维数组
4.3 特殊矩阵的压缩存储
4.3.1 对称矩阵
4.3.2 三角矩阵
4 带状矩阵
4.4 稀疏矩阵的压缩存储
4.5 稀疏矩阵运算的实现
4.5.1 稀疏矩阵转置的实现
4.5.2 矩阵相乘
4.6 广义表
46.1 广义表的概念
4.6.2 广义表的存储结构
4.6.3 广义表的类定义
4.6.4 广义表的递归算法
4.7 递归
4.7.1 递归的概念
4.7.2 函数调用与递归实现
4.7.3 回溯
4.7.4 递归问题的非递归算法
习题4
第5章 树和二叉树.
5.1 树的逻辑结构
5.1.1 树的递归定义
5.1.2树的基本术语
5.1.3 树的表示
5. 2 二叉树
5.2.1 叉树的基本概念
5.2.2 叉树的性质
5.2.3 叉树的抽象数据类型
5.2.4 叉树的存储结构
5.2.5 叉树的基本操作及实现
5. 3 二叉树遍历
5.3.1 叉树遍历的定义
5.3.2 先序遍历算法描述
5.3.3 中序遍历算法描述
5.3.4 后序遍历算法描述
5.3.5 叉树遍历的非递归实现
5.3.6 层次遍历算法描述
5.3.7 叉树遍历算法的应用
5. 4 线索二叉树
5.4.1 叉树的线索化
5.4.2 线索二叉树的中序遍历
5.5 堆
5.5.1 堆的定义
5.5.2 最小堆的类声明
5.5.3 堆的建立
5.5.4 堆的插入与删除
5.5.5 堆的应用
5.6 树和森林
5.6.1 树的存储结构
5.62 树、森林与二叉树的转换
5.6.3 树和森林的遍历
5.7 哈夫曼树及其应用
5.7.1 基本术语
5.7.2 构造哈夫曼树
5.7.3 哈夫曼树的应用
习题5
第6章 图
6.1 图的定义和术语
6.1.1 图的定义
6.1.2 基本术语
6.1.3 图的应用领域
6.2 图的存储结构
6.2.1 邻接矩阵
6.2.2 邻接表
6.2.3 十字链表
6.2.4 邻接多重表
6.3 图的遍历
6.3.1 深度优先搜索
6.3.2 广度优先搜索
6.4 图的应用
6.4.1 图的连通性
6.4.2 最小生成树
6.4.3 最短路径
6.4.4 拓扑排序
6.4.5 关键路径
习题6
第7章 查找
7.1 查找的基本概念
7.2线性表查找
7.2.1 顺序查找
7.2.2 折半查找
7.3 索引表查找
7.3.1 索引查找
7.3.2 分块查找
7.4 树表查找
7.4.1 '叉排序树查找
7.4.2平衡二叉树
7.4.3 B树
7.5 散列表查找
7.5.1 散列表与散列函数
7.5.2 处理冲突的办法
7.5.3 散列表的查找算法
7.5.4 散列查找性能分析
习题7
第8章 排序
8.1 排序的基本概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希尔排序
8.3 交换排序
8.3.1 冒泡排序
8.3.2快速排序
8.4 选择排序
8.4.1 直接选择排序
8.4.2堆排序
8.5 归并排序
8.5.1 路归并排序
8.5.2 多路归并排序
8.5.3 两个有序文件的归并
8.6 基数排序
8.7 各种排序方法的比较
8.7.1 时间性能
8. 7.2 空间性能
8.7.3 排序方法的稳定性能
8.7.4 排序方法的时间复杂度下限
8.7.5 一般选择规则
习题8
参考文献

数据结构是计算机专业和信息管理专业一门重要的专业基础课，其主要内容是研究和解决非数值计算的问题，讨论如何合理地组织、存储和处理数据的方法与技术；其主要任务是使读者掌握数据组织、存储和处理的常用方法和常用的算法思想及在实际中的应用技巧，为今后学习后续专业课和进行软件开发打下良好的基础。只要涉及程序的地方，均要用到数据结构的知识，许多课程(如操作系统、编译原理、数据库和人工智能等)也要用到数据结构的知识。 已出版的许多有价值的数据结构教材，早期的描述语言主要是采用抽象语言、PASCAL语言、类PASCAL语言或C语言等。随着面向对象技术的不断成熟，C+十已被广泛应用，现在越来越多的学校已把C++作为第一门程序设计课程的语言。由于C／／语言在应用程序设计中的广泛使用，用它来讲授数据结构和算法课程是比较方便的。 本书详细介绍了各种基本的数据结构，包括线性结构、数组和广义表、树(层次)结构和图结构；基本的存储结构，包括顺序(数组)结构、链接结构、索引结构和散列结构，以及其中的一种或多种结构的组合及应用。介绍了各种结构的基本操作，包括插入、删除、查找和排序等操作；还介绍了算法时间复杂度的分析方法、算法空间复杂度的分析方法、递归方法及分而治之方法的应用。 本书力求改变读者对数据结构课程内容抽象的惧怕和认为数据结构课程无用的错误观点，以通俗的语言和实例讲授了数据结构课程的内容。实例丰富，图表清晰，深入浅出，易于学生融会贯通。根据C++的特点设计与实现了各种数据结构的存储结构和算法，有助于读者进一步掌握C什的编程思想、方法和技术内涵。 本书是作者多年教学经验的结晶，与以往教材比较有创新之处。特别是本书得到了北京工商大学刘杰副教授的指点，对各章节提出了大量的修改意见，丰富了教材内容。本书希望能够引起读者对数据结构课程的兴趣，提高对数据结构课程的重要性、必要性的认识，特别希望能够提高数据结构课程的教学实效，让读者满意并有收获。 由于编者水平有限，书中错误和不妥之处在所难免，恳请读者与同行批评指正。