数据结构(第2版)

本书面向计算机及相关领域解决复杂工程问题的要求，以问题案例为导向分别讨论线性表、栈、队列、串、哈希表、递归与广义表、二叉树和树、图、排序等数据结构的定义、表示和存储结构的操作与实现。为了强调数据结构在查找问题中的作用，将查找问题融入相应的数据结构中讨论。在多数章节中加入问题案例，介绍运用数据结构和算法解决实际问题的方法，以增强读者对基本知识的理解与掌握，有利于提高分析问题能力和程序设计能力。本书采用类C++语言作为数据结构和算法的描述语言。本书可作为高等院校计算机类和信息类相关专业的本科或专科教材，也可作为相关教师、研究生和工程技术人员的参考书。

第1章绪论
1.1问题的分析
1.1.1系统与结构
1.1.2抽象与模型
1.1.3数据结构与算法
1.2数据结构的相关概念
1.2.1基本概念
1.2.2数据的逻辑结构
1.2.3数据的存储结构
1.3数据类型与抽象数据类型
1.3.1数据类型
1.3.2抽象数据类型
1.3.3抽象数据类型实现
1.4算法和算法分析
1.4.1算法特性
1.4.2算法描述
1.4.3算法性能分析与度量
1.5本章小结
习题
第2章线性表
2.1线性表的定义
2.2线性表的问题案例
2.3线性表的抽象数据类型
2.4顺序表及基本操作
2.4.1线性表的顺序存储
2.4.2顺序表的实现
2.5顺序查找
2.5.1静态查找表
2.5.2顺序查找算法
2.6线性表的链式存储结构及基本操作
2.6.1线性表的链式存储
2.6.2单链表的实现
2.6.3其他形式的链表
2.7线性表的其他存储方法
2.7.1顺序存储与链式存储的比较
2.7.2静态链表
2.7.3间接寻址存储
2.8问题案例分析与实现
2.9本章小结
习题
第3章栈、队列和串
3.1栈
3.1.1栈的逻辑结构
3.1.2栈的问题案例
3.1.3栈的顺序存储结构及基本操作
3.1.4栈的链式存储结构及基本操作
3.1.5顺序栈和链栈的比较
3.1.6案例求解
3.2队列
3.2.1队列的逻辑结构
3.2.2队列的顺序存储结构及实现
3.2.3队列的链式存储结构及实现
3.2.4循环队列和链队的比较
3.2.5队列的应用
3.3串
3.3.1串的逻辑结构
3.3.2串的存储结构
3.3.3模式匹配算法
3.4本章小结80习题
第4章哈希表
4.1哈希表的概念
4.2哈希表的问题案例
4.3哈希表的构建
4.4常用的哈希函数
4.5处理冲突的方法
4.6哈希表的查找分析
4.7问题案例分析与实现944.
本章小结
习题
第5章递归与广义表
5.1递归
5.1.1递归的基本概念
5.1.2递归的问题案例
5.1.3递归函数及其执行过程
5.1.4递归与分治
5.1.5迭代和递归
5.2广义线性表
5.2.1数组的定义
5.2.2数组的顺序存储
5.3矩阵的压缩存储
5.3.1特殊矩阵的压缩存储
5.3.2稀疏矩阵的压缩存储
5.3.3稀疏矩阵的运算
5.4广义表
5.4.1广义表的逻辑结构
5.4.2广义表的问题案例
5.4.3广义表的抽象数据类型
5.4.4广义表的存储
5.4.5广义表的实现
5.5本章小结
习题
第6章二叉树和树
6.1树的定义和基本术语
6.1.1树的定义
6.1.2树的基本术语
6.2二叉树的相关定义
6.2.1二叉树的概念和性质
6.2.2二叉树的问题案例
6.2.3二叉树的抽象数据类型和特殊的二叉树
6.3二叉树的存储结构与实现
6.3.1二叉树的存储结构
6.3.2二叉树的基本操作及实现
6.4二叉树的遍历
6.4.1二叉树的遍历方法及递归实现
6.4.2二叉树遍历的非递归实现
6.4.3由遍历序列恢复二叉树
6.4.4不用栈的二叉树遍历的非递归方法
6.5线索二叉树
6.5.1线索二叉树的定义及其结构
6.5.2线索二叉树的基本操作及实现
6.6二叉树的应用
6.6.1二叉树遍历的应用
6.6.2很优二叉树―哈夫曼树
6.6.3查找与二叉树
6.6.4二叉排序树
6.6.5平衡二叉树
6.7树的操作与存储
6.7.1树的基本操作
6.7.2树的存储结构
6.8树、森林与二叉树的转换
6.8.1树转换为二叉树
6.8.2森林转换为二叉树
6.8.3二叉树转换为树和森林
6.9树和森林的遍历
6.9.1树的遍历
6.9.2森林的遍历
6.10树的应用
6.10.1判定树
6.10.2集合的表示
6.10.3求关系等价类问题
6.11B-树和B+树
6.12本章小结
习题
第7章图
7.1图的基本概念
7.1.1图的定义
7.1.2图的基本术语
7.2图的问题案例
7.3图的抽象数据类型
7.4图的存储结构及操作
7.4.1邻接矩阵
7.4.2邻接表
7.4.3十字链表
7.4.4邻接多重表
7.5图的遍历
7.5.1深度优先搜索
7.5.2广度优先搜索
7.6图的连通性
7.6.1无向图的连通性
7.6.2有向图的连通性
7.6.3生成树和生成森林
7.6.4关结点和重连通分量
7.7最小生成树
7.7.1最小生成树的基本概念
7.7.2构造最小生成树的Prim算法
7.7.3构造最小生成树的Kruskal算法
7.8最短路径
7.8.1从一个源点到其他各点的最短路径
7.8.2每一对顶点之间的最短路径
7.9有向无环图及其应用
……