实用数据结构

第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.3 数据结构的基本概念

1.3.1 两个例子

1.3.2 什么是数据结构

1.3.3 数据结构的图形表示

1.3.4 线性数据结构与非线性数据结构

习题

第2章 线性表及其顺序存储结构

2.1 线性表的基本概念

2.1.1 什么是线性表

2.1.2 线性表的顺序存储结构——顺序表

2.1.3 顺序表的基本运算——插入与删除

2.1.4 顺序表类

2.2 栈及其应用

2.2.1 什么是栈

2.2.2 栈的顺序存储及其运算

2.2.3 顺序栈类

2.2.4 表达式的计算

2.3 队列及其应用

2.3.1 什么是队列

2.3.2 循环队列及其运算

2.3.3 循环队列类

2.3.4 队列的应用

2.4 字符串

2.4.1 字符串的基本概念

2.4.2 字符串匹配

习题

第3章 线性链表

3.1 线性链表的基本概念

3.1.1 线性表顺序存储的问题

3.1.2 线性链表的存储结构

3.2 线性链表的插入与删除

3.2.1 线性链表的插入

3.2.2 线性链表的删除

3.2.3 线性链表类

3.3 带链的栈

3.3.1 带链栈及其基本运算

3.3.2 带链栈类

3.4 带链的队列

3.4.1 带链队列及其基本运算

3.4.2 带链队列类

3.5 循环链表

3.5.1 循环链表及其基本运算

3.5.2 循环链表类

3.6 多项式的表示与运算

习题

第4章 线性表的索引存储结构

4.1 索引存储的概念

4.2 “顺序-索引-顺序”存储方式

4.3 “顺序-索引-链接”存储方式

4.4 多重索引存储结构

习题

第5章 数组

5.1 数组的顺序存储结构

5.2 规则矩阵的压缩

5.3 三列二维数组

5.3.1 稀疏矩阵的三列二维数组表示及其运算

5.3.2 三列二维数组表示的稀疏矩阵类

5.4 三元组链表

5.4.1 稀疏矩阵的三元组链表表示及其运算

5.4.2 三元组链表表示的稀疏矩阵类

5.5 十字链表

5.5.1 稀疏矩阵的十字链表表示

5.5.2 十字链表表示的稀疏矩阵类

习题

第6章 、树与二叉树

6.1 树

6.2 -'叉树及其基本性质

6.2.1 什么是二叉树

6.2.2 叉树的基本性质

6.2.3 满二叉树与完全二叉树

6.3 叉树的存储结构

6.4 叉树的遍历

6.5 二叉链表类

6.6 穿线二叉树

6.6.1 穿线二叉树的概念

6.6.2 中序穿线二叉树

6.6.3 前序穿线二叉树

6.6.4 后序穿线二叉树

6.7 表达式的线性化

6.7.1 有序树的二叉树表示

6.7.2 表达式的线性化

6.8 最优二叉树及其应用

6.8.1 什么是最优二叉树

6.8.2 最优二叉树的构造

6.8.3 最优二叉树类

6.8.4 霍夫曼编码

习题

第7章 图

7.1 图的基本概念

7.2 图的存储结构

7.2.1 关联矩阵

7.2.2 求值矩阵

7.2.3 邻接表

7.2.4 邻接多重表

7.3 图的遍历

7.3.1 纵向优先搜索法

7.3.2 横向优先搜索法

7.4 最短距离问题

7.5 图的邻接表类

习题

第8章 查找技术

8.1 顺序查找

8.2 顺序存储的有序表

8.2.1 顺序有序表的对分查找

8.2.2 顺序有序表类

8.3 分块查找

8.4 二叉排序树

8.4.1 二叉排序树的基本概念

8.4.2 二叉排序树的插入

8.4.3 二叉排序树的删除

8.4.4 二叉排序树的查找

8.4.5 二叉排序树类

8.5 多层索引树查找

8.5.1 b-树

8.5.2 b+树

习题

第9章 hash表技术

9.1 hash表的基本概念

9.1.1 直接查找技术

9.1.2 hash表

9.1.3 hash码的构造

9.2 几种常用的hash表

9.2.1 线性hash表

9.2.2 随机hash表

9.2.3 溢出hash表

9.2.4 拉链hash表

9.2.5 指标hash表

习题

第10章 排序技术

10.1 互换类排序

10.1.1 冒泡排序

10.1.2 快速排序

10.2 插人类排序

10.2.1 简单插入排序

10.2.2 希尔排序

10.3 选择类排序

10.3.1 简单选择排序

10.3.2 堆排序

10.4 拓扑分类

10.5 其他排序方法简介

10.5.1 归并排序

10.5.2 基数排序

习题

参考文献

本书是高等学校学生学习“数据结构”课程而编写的。书中介绍了数据处理领域中常用的数据结构及其主要的运算。主要内容包括： 集合、算法以及数据结构的基本概念，线性表及其顺序存储结构，线性链表及其运算，索引存储结构，数组，树与二叉树，图，查找技术，Hash表技术，排序技术。本书通俗易懂，实例丰富。书中所有的算法均给出了C/C++的描述。本书可作为学习数据结构课程的教材，也可作为自学教材或各类培训班的教材。

《实用数据结构（第3版）》中所有的基本算法均采用C语言描述。考虑到学过C++语言的读者，最后给出了算法的C++语言描述。源代码和电子教案可在清华大学出版社网站下载。