第1章　绪论　1
1.1　数据结构讨论的范畴　1
1.2　与数据结构相关的基本概念　2
1.2.1　基本概念和术语　2
1.2.2　数据结构　3
1.2.3　数据类型和抽象数据类型　6
1.3　算法及其描述和分析　10
1.3.1　算法及其设计原则　10
1.3.2　算法的描述　11
1.3.3　算法效率的衡量方法　11
1.3.4　算法的存储空间需求　14
本章小结　14
第1章习题　15
第2章　线性表　17
2.1　线性表的类型定义　18
2.1.1　抽象数据类型线性表的定义　18
2.1.2　线性表类型的应用　20
2.2　线性表的顺序存储表示和实现　24
2.2.1　顺序表　24
2.2.2　顺序表中基本操作的实现　27
2.2.3　顺序表其他算法举例　31
2.3　线性表的链式存储表示和实现　33
2.3.1　单链表和指针　33
2.3.2　单链表中基本操作的实现　36
2.3.3　单链表其他算法举例　39
2.3.4　循环链表　43
2.3.5　双向链表　44
2.4　有序表的类型定义　45
2.4.1　有序表的定义　45
2.4.2　有序表的基本操作　47
2.5　有序表的应用示例　48
2.5.1　有序链表类型　48
2.5.2　集合运算的实现　51
本章小结　55
第2章习题　55
第3章　栈和队列　59
3.1　栈　60
3.1.1　栈的类型定义　60
3.1.2　栈的存储表示和操作的实现　62
3.2　栈的应用举例　65
3.2.1　数制转换问题　65
3.2.2　括号匹配检验问题　66
3.2.3　迷宫求解问题　67
3.2.4　表达式求值问题　69
3.2.5　递归函数的实现　72
3.3　队列　74
3.3.1　队列的类型定义　74
3.3.2　队列的存储表示和操作的实现　75
3.4　队列应用举例　79
本章小结　84
第3章习题　84
第4章　串　87
4.1　串的类型定义　88
4.2　串的表示和实现　91
4.2.1　串的定长顺序存储表示　91
4.2.2　串的堆分配存储表示　93
4.2.3　串的块链存储表示　94
4.3　正文模式匹配　95
4.3.1　串的模式匹配的简单算法　95
4.3.2　串的模式匹配的改进算法　96
4.4　正文编辑——串操作应用之例　100
本章小结　102
第4章习题　102
第5章　数组　104
5.1　数组类型　105
5.1.1　数组的类型定义　105
5.1.2　数组的顺序存储表示　106
5.2　矩阵的压缩存储　107
5.2.1　特殊矩阵的压缩存储方法　107
5.2.2　稀疏矩阵的压缩存储方法　109
本章小结　119
第5章习题　119
第6章　树和二叉树　121
6.1　树的类型定义　122
6.2　二叉树类型　125
6.2.1　二叉树的类型定义　125
6.2.2　二叉树的几个特性　127
6.3　二叉树的存储表示　129
6.3.1　顺序存储结构　129
6.3.2　链式存储结构　130
6.4　二叉树的遍历　133
6.4.1　先左后右的遍历　133
6.4.2　二叉树其他操作算法举例　135
6.5　线索二叉树　143
6.5.1　二叉树的线索链表　143
6.5.2　以中序线索链表为存储结构的中序遍历　144
6.5.3　线索链表的生成　146
6.6　树和森林的存储表示　148
6.6.1　树的双亲表示法　148
6.6.2　树的孩子表示法　149
6.6.3　树和森林的孩子兄弟表示法　149
6.6.4　森林和二叉树的转换　150
6.7　树和森林的遍历　151
6.7.1　树的遍历　151
6.7.2　森林的遍历　152
6.7.3　森林的其他操作算法举例　153
6.8　最优树和哈夫曼编码　156
6.8.1　最优树的定义　156
6.8.2　最优树的构造方法　157
6.8.3　最优前缀编码　158
本章小结　159
第6章习题　159
第7章　图　163
7.1　图的类型定义　164
7.2　图的存储表示　167
7.2.1　图的数组存储表示　167
7.2.2　图的邻接表存储表示　168
7.2.3　有向图（网）的十字链表存储表示　171
7.2.4　无向图（网）的邻接多重链表存储表示　172
7.3　图的遍历　174
7.3.1　深度优先搜索遍历图　174
7.3.2　广度优先搜索遍历图　176
7.3.3　深度优先生成树和广度优先生成树　178
7.4　连通网的最小生成树　180
7.5　最短路径　184
7.5.1　单源点路径问题　184
7.5.2　各对顶点间的最短路径问题　187
7.6　拓扑排序　188
7.7　关键路径　190
本章小结　191
第7章习题　192
第8章　广义表　193
8.1　广义表的类型定义　194
8.2　广义表的存储表示　196
8.3　广义表操作的实现　197
本章小结　202
第8章习题　202
第9章　查找表　204
9.1　何谓“查找表”？　205
9.2　静态查找表的几种表示方法　206
9.2.1　静态查找表的类型定义　206
9.2.2　顺序表——静态查找表的实现方法之一　207
9.2.3　有序表——静态查找表的实现方法之二　208
9.2.4　索引顺序表——静态查找表的实现方法之三　210
9.2.5　次优查找树——静态查找表的实现方法之四　211
9.3　动态查找树表　215
9.3.1　动态查找表的类型定义　215
9.3.2　二叉查找树　216
9.3.3　平衡二叉（查找）树　221
9.4　哈希表　223
9.4.1　何谓哈希表　223
9.4.2　构造哈希函数的方法　224
9.4.3　处理冲突的方法　226
9.4.4　开放定址的哈希表的查找和插入　228
9.4.5　哈希表的查找性能　229
本章小结　231
第9章习题　231
第10章　内部排序　234
10.1　排序的定义和方法　235
10.2　插入排序　236
10.2.1　直接插入排序　236
10.2.2　折半插入排序　239
10.2.3　表插入排序　240
10.2.4　希尔排序　241
10.3　交换排序法　242
10.3.1　冒泡排序　242
10.3.2　快速排序　245
10.4　选择排序法　247
10.4.1　简单选择排序　247
10.4.2　堆排序　248
10.5　归并排序法　250
10.6　基数排序　252
10.6.1　多关键字的排序　252
10.6.2　基数排序的两种实现方法　253
10.7　各种排序方法的综合比较　257
本章小结　258
第10章习题　259
第11章　文件　261
11.1　基本概念　261
11.1.1　外存储器简介　261
11.1.2　有关文件的基本概念　262
11.2　顺序文件　263
11.2.1　存储在顺序存储器上的顺序文件　263
11.2.2　存储在直接存储器上的顺序文件　264
11.3　索引文件　264
11.3.1　索引文件的组织方法　264
11.3.2　B-树　265
11.4　索引顺序文件　266
11.4.1　索引顺序文件的特点　266
11.4.2　B+树　266
11.4.3　VSAM文件的组织方法　267
11.5　散列文件　268
11.5.1　文件的组织方式　268
11.5.2　文件的操作　268
11.6　多关键码文件　269
本章小结　270
附录1　数据结构知识结构图　271
附录2　词汇表　275