第1章 概论 1
1.1 知识点 1
1.2 内容精要 1
1.2.1 概念和术语 1
1.2.2 数据结构的研究目的和研究内容 1
1.2.3 数据逻辑结构的四种基本形态 2
1.2.4 数据存储结构的基本组织方式 2
1.2.5 数据逻辑结构上定义的基本运算 3
1.2.6 在数据结构中引入抽象数据类型概念的好处 4
1.2.7 什么是算法 4
1.2.8 算法的五个重要特性 4
1.2.9 评价算法优劣的基本标准 4
1.2.10 算法分析的目的 5
1.2.11 算法的时间复杂度的含义 5
1.2.12 算法的空间复杂度的含义 5
1.3 典型例题解析 5
第2章 线性表 11
2.1 知识点 11
2.2 内容精要 11
2.2.1 概念和术语 11
2.2.2 线性表的特点 11
2.2.3 通常在线性表上定义的基本运算 11
2.2.4 线性表的顺序存储结构（顺序表） 12
2.2.5 C语言中线性表顺序存储空间的两种分配方法 12
2.2.6 静态分配空间和动态分配空间时，构造一个顺序表算法之比较 13
2.2.7 线性表的顺序存储结构的优缺点 14
2.2.8 线性表的链式存储结构（链表） 14
2.2.9 几种常用的链式存储结构 14
2.2.10 线性表的链式存储结构的优缺点 15
2.2.11 单链表设置头结点的好处 15
2.2.12 单链表不带头结点和带头结点两种结构下，删除第i个元素的算法之比较 15
2.2.13 循环链表设立尾指针而不设头指针的好处 17
2.2.14 静态链表的用途和构造方法 17
2.2.15 线性表的索引存储结构及其优点 17
2.3 典型例题解析 17
第3章 栈和队列 27
3.1 知识点 27
3.2 内容精要 27
3.2.1 栈的定义和术语 27
3.2.2 栈的特性 27
3.2.3 栈的基本运算定义 27
3.2.4 顺序栈（栈的顺序存储结构） 28
3.2.5 在顺序栈上运算的实现 28
3.2.6 链栈（栈的链式存储结构） 30
3.2.7 栈空间共享问题 30
3.2.8 栈和递归的关系 31
3.2.9 哪些类型的问题适合于用递归方法求解 31
3.2.10 递归模型及递归执行过程 31
3.2.11 递归算法的设计步骤 32
3.2.12 递归过程的实现 32
3.2.13 递归算法的优缺点 33
3.2.14 递归算法转换为非递归算法的方法 33
3.2.15 队列的定义和术语 35
3.2.16 队列的特性 36
3.2.17 队列的基本运算定义 36
3.2.18 顺序队列（队列的顺序存储结构） 36
3.2.19 循环队列的好处 36
3.2.20 在循环队列上运算的实现 37
3.2.21 链队列（队列的链式存储结构） 38
3.2.22 在链队列上运算的实现 38
3.3 典型例题解析 39
第4章 串 54
4.1 知识点 54
4.2 内容精要 54
4.2.1 概念和术语 54
4.2.2 串与线性表的关系 54
4.2.3 两个串相等的充分必要条件 54
4.2.4 通常在串上定义的基本运算 54
4.2.5 顺序串（串的顺序存储结构） 55
4.2.6 链串／块链结构（串的链式存储结构） 56
4.2.7 在块链中结点大小（CHUNKSIZE值）的选择 56
4.2.8 两种典型的串的模式匹配算法 56
4.2.9 求next数组值的方法 58
4.2.10 next数组的缺陷和改进 58
4.3 典型例题解析 58
第5章 多维数组 67
5.1 知识点 67
5.2 内容精要 67
5.2.1 多维数组的定义 67
5.2.2 多维数组和线性表的关系 67
5.2.3 数组的特点 68
5.2.4 数组的基本运算的定义 68
5.2.5 数组的顺序存储结构 68
5.2.6 特殊矩阵压缩存储的意义 69
5.2.7 对称矩阵压缩存储的方法 69
5.2.8 三角矩阵压缩存储的方法 69
5.2.9 对角矩阵压缩存储的方法 70
5.2.10 稀疏矩阵及其压缩存储的特点 70
5.2.11 稀疏矩阵压缩存储的顺序存储方式 70
5.2.12 稀疏矩阵压缩存储的链式存储方式——十字链表（或称正交链表） 72
5.3 典型例题解析 73
第6章 树和二叉树 81
6.1 知识点 81
6.2 内容精要 81
6.2.1 树的概念和定义 81
6.2.2 树的特点 82
6.2.3 树的表示方法 82
6.2.4 树的相关术语 82
6.2.5 二叉树的定义和它的五种形态 83
6.2.6 一棵度为2的有序树与二叉树的区别 83
6.2.7 满二叉树和完全二叉树 83
6.2.8 二叉树的基本运算 84
6.2.9 二叉树的性质 85
6.2.10 二叉树的存储结构 85
6.2.11 遍历二叉树 86
6.2.12 线索二叉树的概念 87
6.2.13 线索二叉树的存储结构 87
6.2.14 二叉树的线索化 87
6.2.15 遍历线索二叉树 88
6.2.16 最优二叉树（也称哈夫曼树）的概念 89
6.2.17 哈夫曼树的构造方法 89
6.2.18 哈夫曼树的应用 89
6.2.19 树的存储结构 90
6.2.20 树与二叉树的转换 91
6.2.21 森林转换为二叉树 92
6.2.22 树和森林的遍历 92
6.3 典型例题解析 93
第7章 图 122
7.1 知识点 122
7.2 内容精要 122
7.2.1 概念和术语 122
7.2.2 图的基本运算的定义 123
7.2.3 图的存储结构 124
7.2.4 邻接矩阵和邻接表两种图的存储结构的比较 125
7.2.5 图的遍历算法 126
7.2.6 图的生成树和最小生成树的概念 126
7.2.7 如何得到图的生成树 126
7.2.8 最小生成树（MST）的性质 129
7.2.9 Prim算法构造最小生成树 129
7.2.10 Kruskal算法构造最小生成树 130
7.2.11 拓扑排序和AOV（Activity on Vertex）网 131
7.2.12 无前趋的顶点优先的拓扑排序算法 131
7.2.13 无后继的顶点优先的拓扑排序算法 133
7.2.14 关键路径问题和AOE（Activity On Edge）网 133
7.2.15 确定关键路径的主要步骤 134
7.2.16 采用邻接表作为图的存储结构时，求事件的最早发生时间和最晚发生时间为何采用不同的策略 134
7.2.17 求关键路径的算法 135
7.2.18 单源最短路径——迪杰斯特拉（Dijkstra）算法 136
7.2.19 每对顶点间的最短路径——弗洛伊德（Floyd）算法 137
7.2.20 Floyd算法使用时的限制 138
7.3 典型例题解析 138
第8章 查找 154
8.1 知识点 154
8.2 内容精要 154
8.2.1 查找在数据处理中的重要性 154
8.2.2 基本概念和术语 154
8.2.3 查找表的典型存储结构 155
8.2.4 静态查找表的顺序表存储结构 155
8.2.5 顺序表上的顺序查找 156
8.2.6 有序顺序表上的折半查找（也称二分查找） 156
8.2.7 索引顺序表的分块查找 158
8.2.8 二叉排序树（也称二叉查找树）的概念和性质 159
8.2.9 二叉排序树的存储结构定义 159
8.2.10 二叉排序树上的查找 160
8.2.11 二叉排序树上结点的插入 161
8.2.12 二叉排序树的生成 162
8.2.13 二叉排序树上结点的删除 162
8.2.14 平衡二叉树（也称AVL树）的概念 163
8.2.15 平衡二叉树上插入结点的操作 163
8.2.16 平衡二叉树的生成 164
8.2.17 平衡二叉树上结点的删除操作 165
8.2.18 平衡二叉树的特点 165
8.2.19 B—树的概念 165
8.2.20 B—树的高度定理 166
8.2.21 B—树的用途 166
8.2.22 B—树的存储结构定义 166
8.2.23 B—树上的查找操作 166
8.2.24 B—树上的插入操作 167
8.2.25 B—树上的删除操作 168
8.2.26 B＋树的概念 168
8.2.27 B—树和B＋树的主要差异 169
8.2.28 B＋树上的基本运算 169
8.2.29 键树（又称数字查找树或字符树）的概念 169
8.2.30 键树的存储结构 170
8.2.31 键树上的运算和性能要点 171
8.2.32 哈希表（也称散列表或杂凑表）的概念和相关术语 171
8.2.33 哈希表的设计过程 171
8.2.34 哈希函数的基本构造方法 172
8.2.35 哈希表中处理冲突的常用方法 172
8.2.36 哈希表的平均查找长度ASL与装填因子α的关系 173
8.3 典型例题解析 173
第9章 排序 187
9.1 知识点 187
9.2 内容精要 187
9.2.1 排序的概念 187
9.2.2 排序的分类 187
9.2.3 评价排序算法的主要标准 188
9.2.4 直接插入排序 188
9.2.5 希尔排序（也称缩小增量排序） 190
9.2.6 冒泡排序 191
9.2.7 快速排序（也称分划交换排序） 192
9.2.8 简单选择排序 193
9.2.9 堆的定义 194
9.2.10 堆与完全二叉树的关系 194
9.2.11 调整堆的操作和建堆的操作 194
9.2.12 堆排序 195
9.2.13 归并排序 196
9.2.14 基数排序与前述排序方法不同的实质是什么 197
9.2.15 多关键字排序的两种方法 197
9.2.16 基数排序 198
9.2.17 各种内部排序方法的比较 200
9.2.18 选择内部排序方法时所应考虑的主要因素 200
9.2.19 外部排序的概念 200
9.2.20 外部排序的基本方法 201
9.2.21 影响外部排序时间开销的因素 201
9.2.22 提高外部排序效率的途径 201
9.2.23 利用败者树实现k路平衡归并的方法 201
9.2.24 胜者树较之败者树的缺陷 202
9.2.25 置换-选择排序生成初始归并段的方法 202
9.2.26 引入最佳归并树的必要性 203
9.2.27 最佳归并树的构造方法 203
9.3 典型例题解析 204
附录A 类C语言说明 220
参考文献 227