目录

第1章 数据结构概述 1
1.1 什么是数据结构 2
1.2 数据结构有哪些 3
1.3 算法的时间复杂度和空间复杂度 6

第2章 线性表 12
2.1 什么是线性表 13
2.2 顺序表 15
2.2.1 什么是顺序表 15
2.2.2 顺序表的初始化 15
2.2.3 顺序表的基本操作 18
2.3 链表 21
2.3.1 什么是链表 21
2.3.2 链表的节点 22
2.3.3 头节点，头指针和首元节点 23
2.3.4 链表的创建（初始化） 23
2.3.5 链表的基本操作 25
2.4 静态链表 29
2.4.1 什么是静态链表 29
2.4.2 静态链表中的节点 31
2.4.3 备用链表 31
2.4.4 静态链表的实现 32
2.4.5 静态链表的基本操作 35
2.5 双向链表 39
2.5.1 双向链表是什么 39
2.5.2 双向链表的创建 40
2.5.3 双向链表的基本操作 41

第3章 栈与队列 47
3.1 栈 48
3.1.1 什么是栈 48
3.1.2 顺序栈的基本操作 49
3.1.3 链栈的基本操作 52
3.2 案例：进制转换器 54
3.2.1 进制转换器项目要求 54
3.2.2 转换器实例 54
3.2.3 设计思路 55
3.2.4 实现代码 55
3.3 案例：括号匹配 57
3.3.1 括号匹配项目要求 57
3.3.2 设计思路 57
3.3.3 实现代码 57
3.4 队列 59
3.4.1 什么是队列 59
3.4.2 顺序队列的实现 60
3.4.3 链式队列及基本操作 65

第4章 字符串 69
4.1 什么是串 70
4.2 串的存储方式 70
4.2.1 串的定长顺序存储结构 70
4.2.2 串的堆分配存储结构 71
4.2.3 串的块链存储结构 72
4.3 BF算法 75
4.4 KMP算法 78
4.5 案例：字符过滤系统 85
4.5.1 系统简介 85
4.5.2 项目实例 85
4.5.3 设计思路 85
4.5.4 实现代码 86

第5章 数组和广义表 90
5.1 什么是数组 91
5.2 数组的顺序存储 92
5.3 矩阵压缩存储 98
5.3.1 对称矩阵 98
5.3.2 上（下）三角矩阵 99
5.3.3 稀疏矩阵 100
5.3.4 矩阵压缩存储的 3 种方式 100
5.4 广义表的定义和存储结构 109
5.4.1 什么是广义表 110
5.4.2 广义表的表头和表尾 110
5.4.3 广义表的存储结构 111
5.5 广义表的深度和长度 114
5.5.1 广义表的长度 114
5.5.2 广义表的深度 117
5.6 复制广义表 120

第6章 树的介绍 124
6.1 树型存储结构 125
6.1.1 树的结点 125
6.1.2 子树和空树 126
6.1.3 结点的度和层次 126
6.1.4 有序树和无序树 126
6.1.5 森林 127
6.1.6 树的表示方法 127
6.2 二叉树 128
6.2.1 什么是二叉树 128
6.2.2 二叉树的顺序存储结构 130
6.2.3 二叉树的链式存储结构 131
6.3 二叉树的遍历 133
6.3.1 二叉树先序遍历 133
6.3.2 二叉树中序遍历 138
6.3.3 二叉树后序遍历 144
6.3.4 二叉树的层次遍历 149
6.4 线索二叉树 152
6.5 树的三种表达方式 156
6.5.1 树的双亲表示法 156
6.5.2 树的孩子表示法 159
6.5.3 树的孩子兄弟表示法 163

第7章 图的介绍 166
7.1 数据结构中的图 167
7.1.1 什么是图存储结构 167
7.1.2 什么是连通图 169
7.2 图的顺序存储结构 171
7.3 图的3种链式存储 179
7.3.1 邻接表存储法 180
7.3.2 十字链表存储法 182
7.3.3 邻接多重表存储法 185
7.4 普里姆算法 186
7.5 拓扑排序算法 192
7.6 求最短路径 198
7.6.1 迪杰斯特拉（Dijkstra）算法 199
7.6.2 弗洛伊德算法 204
7.7 案例：移动迷宫 210
7.7.1 设计思路 210
7.7.2 二维数组转化成图 210
7.7.3 代码实现 212

第8章 动态内存管理 217
8.1 动态内存管理机制 218
8.2 伙伴系统管理动态内存 221
8.3 系统垃圾回收机制 224
8.4 存储碎片的处理 230

第9章 查找算法 234
9.1 什么是查找表 235
9.2 静态查找之顺序查找算法 235
9.3 二分查找 239
9.4 索引顺序查找 242
9.5 静态树表查找 245
9.6 红黑树算法 249
9.7 B+与B-算法 259
9.7.1 什么是B-树 259
9.7.2 B-树中插入关键字（构建B-树） 261
9.7.3 B-树中删除关键字 264
9.7.4 什么是B+树 266
9.7.5 B+树中插入关键字 267
9.7.6 B+树中删除关键字 268
9.8 哈希表查找算法 271

第10章 排序算法 280
10.1 插入排序算法 281
10.1.1 直接插入排序算法 281
10.1.2 折半插入排序算法 284
10.1.3 2-路插入排序算法 285
10.1.4 表插入排序 289
10.2 希尔排序算法 294
10.3 快速排序算法 297
10.4 选择排序算法 300
10.4.1 简单选择排序 300
10.4.2 树形选择排序 303
10.4.3 堆排序 304

第11章 外部排序算法 311
11.1 什么是外部排序 312
11.2 多路平衡归并排序算法 313
11.3 置换选择排序算法 318
11.4 最佳归并树 327