目    录 

第1章  绪论 1

1.1  数据结构的发展 1

1.2  数据结构的概念 2

1.2.1  数据结构研究的领域 3

1.2.2  数据结构研究的内容 5

1.2.3  数据 5

1.2.4  数据结构 6

1.2.5  数据类型 8

1.3  算法和算法分析 9

1.3.1  算法的概念 10

1.3.2  算法的复杂性分析 10

1.4  习题 13

第2章  线性表 16

2.1  线性表的类型定义 16

2.2  线性表的顺序映像 19

2.2.1  线性表的顺序存储结构 20

2.2.2  顺序存储结构的特点 20

2.2.3  典型操作的算法实现 21

2.2.4  主要操作的算法分析 24

2.3  线性表的链式映像 25

2.3.1  线性链表的定义 25

2.3.2  线性链表的类型定义及典型操作 26

2.3.3  其他形式的链表 30

2.4  线性表实现方法的比较 37

2.4.1  顺序表和链表的比较 37

2.4.2  线性链表定义的改进 38

2.5  一元多项式的表示及相加 40

2.6  习题 44

第3章  栈 49

3.1  栈的定义 49

3.1.1  栈的特点及定义 49

3.1.2  栈的抽象数据类型定义 50

3.2  栈的存储表示及实现 51

3.2.1  栈的顺序存储表示 51

3.2.2  栈的链式存储表示 52

3.3  栈的应用 53

3.3.1  数制转换 53

3.3.2  括号匹配的检验 54

3.3.3  行编辑程序问题 55

3.3.4  迷宫求解问题 56

3.3.5  表达式求值 57

3.3.6  递归的实现 60

3.4  习题 63

第4章  队列 65

4.1  队列的定义 65

4.2  队列类型的实现 66

4.2.1  队列的顺序存储——循环队列 67

4.2.2  队列的链式存储——链队列 69

4.3  队列的应用——离散事件模拟 70

4.4  习题 74

第5章  串 76

5.1  串类型的定义 76

5.1.1  串的基本概念 76

5.1.2  串的抽象数据类型定义 77

5.1.3  串与线性表的区别 79

5.2  串的表示和实现 80

5.2.1  串的定长顺序存储表示 80

5.2.2  串的堆分配存储表示 81

5.2.3  串的块链存储表示 82

5.3  串的模式匹配算法 83

5.3.1  简单匹配算法 83

5.3.2  KMP算法 86

5.4  串应用举例 ——文本编辑 92

5.4.1  文本编辑概述 93

5.4.2  文本编辑程序 94

5.5  习题 94

第6章  数组 95

6.1  数组的基本概念 95

6.2  数组的顺序存储及实现 97

6.2.1  数组的存储方式 97

6.2.2  数组的顺序存储表示和实现 98

6.3  矩阵的压缩存储 100

6.3.1  对称矩阵的压缩存储 100

6.3.2  三角矩阵的压缩存储 101

6.3.3  对角矩阵的压缩存储 102

6.4  稀疏矩阵 103

6.4.1  稀疏矩阵的定义 103

6.4.2  稀疏矩阵的抽象数据类型定义 103

6.4.3  稀疏矩阵的压缩存储 104

6.5  习题 113

第7章  广义表 115

7.1  广义表的定义 115

7.2  广义表的存储结构 117

7.2.1  广义表的头尾链表存储表示 117

7.2.2  广义表的元素存储表示 118

7.3  广义表操作的实现 118

7.3.1  创建广义表 118

7.3.2  求表的深度 120

7.3.3  广义表的结点操作 121

7.3.4  删除广义表 122

7.3.5  求广义表的长度 123

7.3.6  广义表的复制 123

7.4  习题 125

第8章  树 127

8.1  树的类型定义和基本术语 127

8.1.1  树的定义 127

8.1.2  树的常用术语 130

8.1.3  线性结构与树形结构的比较 131

8.2  树和森林的存储结构 131

8.2.1  树的存储结构 131

8.2.2  树和森林的遍历 134

8.3  习题 138

第9章  二叉树 140

9.1  二叉树的定义和性质 140

9.1.1  二叉树的定义 140

9.1.2  两类特殊的二叉树 143

9.1.3  二叉树的重要特性 143

9.2  二叉树的存储结构 144

9.2.1  二叉树的顺序存储表示 144

9.2.2  二叉树的链式存储表示 145

9.3  二叉树的遍历与应用 146

9.3.1  二叉树的三种遍历算法 147

9.3.2  二叉树遍历算法的非递归描述 150

9.3.3  二叉树遍历算法的应用 153

9.4  线索二叉树 158

9.4.1  线索二叉树的定义 158

9.4.2  线索链表的遍历 159

9.4.3  线索链表的建立 161

9.4.4  中序线索二叉树中插入结点 162

9.4.5  线索二叉树的优缺点 163

9.5  树、森林和二叉树 163

9.5.1  森林与二叉树之间的转换 163

9.5.2  森林与二叉树转换的操作 164

9.5.3  树、森林的遍历和二叉树遍历的对应关系 165

9.6  哈夫曼树及其应用 166

9.6.1  哈夫曼树 166

9.6.2  哈夫曼编码 168

9.7  习题 172

第10章  图 176

10.1  图的基本概念 176

10.1.1  图的定义和术语 176

10.1.2  图的抽象数据类型定义 178

10.2  图的存储结构 180

10.2.1  邻接矩阵(数组)表示法 180

10.2.2  邻接表表示法 183

10.2.3  十字链表表示法 186

10.2.4  邻接多重表表示法 187

10.3  图的遍历 189

10.3.1  深度优先搜索遍历 189

10.3.2  广度优先搜索遍历 190

10.4  图的连通性问题 192

10.4.1  无向图的连通分量和生成树 192

10.4.2  有向图的强连通分量 194

10.4.3  最小生成树 195

10.5  有向无环图及其应用 200

10.5.1  拓扑排序 200

10.5.2  关键路径 203

10.6  最短路径 207

10.6.1  单源最短路径 208

10.6.2  每一对顶点间的最短路径 211

10.7  习题 213

第11章  查找 216

11.1  查找表 216

11.2  静态查找表 218

11.2.1  顺序表的查找 218

11.2.2  有序表的查找 220

11.2.3  索引顺序表的查找 222

11.3  动态查找表 224

11.3.1  二叉排序树 224

11.3.2  平衡二叉树 229

11.3.3  B-树 235

11.3.4  B+树 243

11.4  哈希表 244

11.4.1  什么是哈希表 244

11.4.2  哈希函数的构造方法 246

11.4.3  哈希表处理冲突的方法 248

11.4.4  哈希表的查找及分析 251

11.5  习题 255

第12章  内部排序 258

12.1  排序概述 258

12.1.1  排序的概念 258

12.1.2  排序方法的稳定性 259

12.1.3  内部排序和外部排序 259

12.1.4  内部排序的分类 259

12.2  插入排序 260

12.2.1  直接插入排序 260

12.2.2  折半插入排序 262

12.2.3  2-路插入排序 263

12.2.4  表插入排序 265

12.2.5  希尔排序 268

12.3  交换排序 269

12.3.1  起泡排序 270

12.3.2  快速排序 271

12.4  选择排序 273

12.4.1  简单选择排序 273

12.4.2  堆排序 274

12.5  归并排序 277

12.6  基数排序 279

12.6.1  多关键字排序 279

12.6.2  链式基数排序 281

12.7  各种内部排序方法的比较讨论 283

12.8  习题 284

第13章  外部排序 286

13.1  外部排序的方法 286

13.2  归并排序 287

13.2.1  2-路平衡归并排序 287 

13.2.2  多段2-路归并排序 288

13.2.3  多路平衡归并排序 288

13.3  置换选择排序 290

13.3.1  置换选择排序的处理过程 291

13.3.2  置换选择排序算法 291

13.4  习题 294

参考文献 295