目录 1
第1章概论 1
1.1数据结构 1
1.1.1数据结构 1
1.1.2数据的逻辑结构 3
1.1.3数据的存储结构 3
1.1.4数据的运算集合 5
1.2数据类型和抽象数据类型 6
1.2.1数据类型 7
1.2.2数据结构 7
1.2.3抽象数据类型 7
1.2.4抽象数据类型的描述和实现 8
1.3算法和算法分析 9
1.3.1 算法 9
1.3.2算法的时间和空间复杂度 9
习题 10
第2章线性表及其顺序存储 12
2.1线性表 12
2.2顺序表 12
2.2.1顺序表 12
2.2.2顺序表的实现 13
2.3栈 18
2.3.1栈 18
2.3.2顺序栈及其实现 19
2.3.3栈的应用之一——括号匹配 21
2.3.4栈的应用之二——算术表达式求值 23
2.4队列 28
2.4.1 队列 28
2.4.2顺序队列及其实现 29
2.4.3顺序循环队列及其实现 32
习题 34
第3章线性表的链式存储 35
3.1链式存储 35
3.2单链表 36
3.2.1单链表 36
3.2.2单链表的实现 37
3.3带头结点的单链表 43
3.3.1带头结点的单链表 43
3.3.2带头结点的单链表的实现 44
3.4循环单链表 48
3.4.1循环单链表 48
3.4.2循环单链表的实现 49
3.5双链表 56
3.5.1双链表 56
3.5.2 双链表的实现 57
3.6链式栈 64
3.6.1链式栈 64
3.6.2链式栈的实现 65
3.7.1链式队列 67
3.7链式队列 67
3.7.2链式队列的实现 68
习题 71
第4章字符串、数组和特殊矩阵 72
4.1字符串 72
4.1.1字符串的基本概念 72
4.1.2字符串类的定义 73
4.1.3字符串的存储及其实现 74
4.2字符串的模式匹配 81
4.2.1朴素的模式匹配算法 81
4.2.2快速模式匹配算法 82
4.3.1数组和数组元素 85
4.3数组 85
4.3.2数组类的定义 86
4.3.3数组的顺序存储及实现 86
4.4特殊矩阵 90
4.4.1对称矩阵的压缩存储 90
4.4.2三角矩阵的压缩存储 92
4.4.3带状矩阵的压缩存储 93
4.5稀疏矩阵 95
4.5.1稀疏矩阵类的定义 95
4.5.2稀疏矩阵的顺序存储及其实现 95
4.5.3稀疏矩阵的链式存储及实现 98
习题 102
5.1递归与递归程序设计 103
第5章递归 103
5.2递归程序执行过程的分析 105
5.3递归程序到非递归程序的转换 108
5.3.1 简单递归程序到非递归程序的转换 109
5.3.2复杂递归程序到非递归程序的转换 112
5.4递归程序设计的应用实例 116
习题 118
第6章树型结构 120
6.1树的基本概念 120
6.2树类的定义 122
6.3树的存储结构 123
6.3.1双亲表示法 123
6.3.2孩子表示法 124
6.3.3孩子兄弟表示法 127
6.4树的遍历 127
6.5树的线性表示 131
6.5.1树的括号表示 131
6.5.2树的层号表示 133
习题 135
第7章二叉树 137
7.1二叉树的基本概念 137
7.2二叉树的基本运算 139
7.3二叉树的存储结构 140
7.3.1顺序存储结构 140
7.3.2链式存储结构 142
7.4.2 二叉树遍历的递归实现 144
7.4二叉树的遍历 144
7.4.1 二叉树遍历的定义 144
7.4.3 二叉树遍历的非递归实现 146
7.5二叉树其他运算的实现 150
7.6穿线二叉树 152
7.6.1穿线二叉树的定义 152
7.6.2中序穿线二叉树的基本运算 153
7.6.3中序穿线二叉树的存储结构及其实现 154
7.7树、森林和叉树的转换 156
7.7.1树、森林到二叉树的转换 156
7.7.2二叉树到树、森林的转换 157
习题 158
8.1图的基本概念 159
第8章图 159
8.2图的基本运算 162
8.3图的基本存储结构 163
8.3.1邻接矩阵及其实现 163
8.3.2邻接表及其实现 166
8.3.3邻接多重表 168
8.4图的遍历 169
8.4.1深度优先遍历 169
8.4.2广度优先遍历 171
8.5生成树与最小生成树 173
8.5.1最小生成树的定义 174
8.5.2最小生成树的普里姆（Prim）算法 175
8.5.3最小生成树的克鲁斯卡尔（Kruskal）算法 178
8.6最短路径 180
8.6.1单源最短路径 180
8.6.2所有顶点对的最短路径 183
8.7拓扑排序 186
8.8关键路径 189
习题 194
第9章检索 196
9.1检索的基本概念 196
9.2线性表的检索 197
9.2.1顺序检索 197
9.2.2二分法检索 199
9.2.3分块检索 201
9.3二叉排序树 203
9.4丰满树和平衡树 210
9.4.1丰满树 211
9.4.2平衡二叉排序树 212
9.5最佳二叉排序树和Huffman树 218
9.5.1扩充二叉树 218
9.5.2最佳二叉排序树 220
9.5.3 Huffman树 225
9.6 B－树 228
9.6.1 B-树的定义 228
9.6.2 B-树的基本操作 229
9.7.1散列存储 234
9.7散列表检索 234
9.7.2散列函数的构造 235
9.7.3 冲突处理 236
习题 240
第10章内排序 242
10.1排序的基本概念 242
10.2插入排序 243
10.2.1直接插入排序 243
10.2.2二分法插入排序 246
10.2.3表插入排序 248
10.2.4 Shell插入排序 249
10.3.1直接选择排序 251
10.3选择排序 251
10.3.2树型选择排序 253
10.3.3堆排序 256
10.4交换排序 259
10.4.1 冒泡排序 259
10.4.2快速排序 261
10.5归并排序 263
10.6基数排序 267
10.6.1多排序码的排序 267
10.6.2静态链式基数排序 267
习题 271
11.1.2磁带存储器 273
11.1.1磁盘存储器 273
11.1外存储器简介 273
第11章外排序 273
11.2文件简介 274
11.2.1文件的逻辑结构 274
11.2.2文件的存储结构 274
11.3外排序——磁盘排序 274
11.3.1磁盘排序 274
11.3.2多路归并 276
11.3.3初始有序串的生成 278
11.4外排序——磁带排序 279
11.4.1磁带排序 279
11.4.2非平衡归并 281
习题 282
第12章动态存储管理 283
12.1概述 283
12.2可利用空间表及分配方法 285
12.3边界标识法 288
12.3.1可利用空间表的结构 288
12.3.2分配算法 289
12.3.3 回收算法 291
12.4无用单元的收集 293
12.5存储压缩 296
习题 298
参考文献 299