数据结构教程（第二版）

第1章?绪论

1.1?什么是数据结构1

*1.2?数据结构的发展简史及其在计算机科学中的地位5

1.3?算法5

1.3.1?算法及其性质5

1.3.2?基本算法7

1.3.3?算法的描述8

1.4?算法分析12

1.4.1?时间复杂度12

1.4.2?空间复杂度15

1.4.3?其他方面16

习题16

第2章?线性表

2.1?线性表的定义及其基本操作21

2.1.1?线性表的定义21

2.1.2?线性表的基本操作22

2.2?线性表的顺序存储结构23

2.2.1?顺序存储结构的构造23

2.2.2?几种常见操作的实现25

2.2.3?顺序存储结构小结30

2.3?线性链表及其操作31

2.3.1?线性链表的构造31

2.3.2?线性链表的基本算法34

2.4?循环链表及其操作50

2.5?双向链表及其操作53

2.5.1?双向链表的构造53

2.5.2?双向链表的插入与删除算法54

*2.6?链表的应用举例57

2.6.1?链式存储结构下的一元多项式相加57

2.6.2?打印文本文件的最后n行60

习题63

第3章?数组

3.1?数组的概念69

3.2?数组的存储结构69

3.3?矩阵的压缩存储71

3.3.1?对称矩阵的压缩存储72

3.3.2?对角矩阵的压缩存储73

3.4?稀疏矩阵的三元组表表示74

3.4.1?稀疏矩阵的三元组表存储方法74

*3.4.2?稀疏矩阵的转置算法75

*3.4.3?稀疏矩阵的相加算法78

*3.4.4?稀疏矩阵的相乘算法79

*3.5?稀疏矩阵的链表表示81

3.5.1?线性链表存储方法82

3.5.2?带行指针向量的链表存储方法83

3.5.3?十字链表存储方法83

3.6?数组的应用举例88

3.6.1?一元多项式的数组表示88

3.6.2?n阶魔方89

习题91

第4章?堆栈和队列

4.1?堆栈的概念及其操作95

4.1.1?堆栈的定义95

4.1.2?堆栈的基本操作96

4.2?堆栈的顺序存储结构96

4.2.1?顺序堆栈的构造97

4.2.2?顺序堆栈的基本算法97

*4.2.3?多个堆栈共享连续空间99

4.3?堆栈的链式存储结构102

4.3.1?链接堆栈的构造103

4.3.2?链接堆栈的基本算法103

4.4?堆栈的应用举例106

4.4.1?符号匹配检查106

4.4.2?数制转换107

4.4.3?堆栈在递归中的应用108

4.4.4?表达式的计算113

4.4.5?又一个趣味游戏——迷宫117

4.5?队列的概念及其操作120

4.5.1?队列的定义120

4.5.2?队列的基本操作121

4.6?队列的顺序存储结构121

4.6.1?顺序队列的构造121

4.6.2?顺序队列的基本算法123

4.6.3?循环队列124

4.7?队列的链式存储结构127

4.7.1?链接队列的构造127

4.7.2?链接队列的基本算法128

习题131

第5章?广义表

5.1?广义表的基本概念136

5.2?广义表的存储结构137

*5.3?多元多项式的表示141

习题143

第6章?串

6.1?串的基本概念145

6.1.1?串的定义145

6.1.2?串的几个概念146

6.2?串的基本操作146

6.3?串的存储结构148

6.3.1?串的顺序存储结构149

6.3.2?串的链式存储结构150

6.4?串的几个操作151

习题157

第7章?树与二叉树

7.1?树的基本概念158

7.1.1?树的定义158

7.1.2?树的逻辑表示方法160

7.1.3?基本术语161

7.1.4?树的性质163

7.1.5?树的基本操作164

*7.2?树的存储结构164

7.2.1?多重链表表示法165

7.2.2?三重链表表示法166

7.3?二叉树167

7.3.1?二叉树的定义167

7.3.2?二叉树的基本操作168

7.3.3?两种特殊形态的二叉树169

7.3.4?二叉树的性质169

*7.3.5?二叉树与树、树林之间的转换171

7.4?二叉树的存储结构174

7.4.1?二叉树的顺序存储结构174

7.4.2?二叉树的链式存储结构176

7.5?二叉树与树的遍历180

7.5.1?二叉树的遍历181

7.5.2?由遍历序列恢复二叉树189

7.5.3?二叉树的等价性190

*7.5.4?树和树林的遍历191

7.5.5?基于二叉树遍历操作的算法举例192

7.6?线索二叉树199

7.6.1?线索二叉树的构造200

7.6.2?线索二叉树的利用201

*7.6.3?二叉树的线索化204

*7.6.4?线索二叉树的更新205

7.7?二叉排序树206

7.7.1?二叉排序树的定义206

7.7.2?二叉排序树的建立206

*7.7.3?在二叉排序树中删除结点209

7.7.4?二叉排序树的查找212

*7.8?平衡二叉树215

7.9?哈夫曼树及其应用222

7.9.1?哈夫曼树的概念222

*7.9.2?哈夫曼编码223

习题227

第8章?图

8.1?图的基本概念233

8.1.1?图的定义和基本术语233

8.1.2?图的基本操作237

8.2?图的存储方法238

8.2.1?邻接矩阵存储方法238

8.2.2?邻接表存储方法240

*8.2.3?有向图的十字链表存储方法244

*8.2.4?无向图的多重邻接表存储方法245

8.3?图的遍历246

8.3.1?深度优先搜索247

8.3.2?广度优先搜索