第1章 基础知识 1
1.1 数据结构研究什么 1
1.2 基本概念和有关术语 3
1.3 数据类型与抽象数据类型 4
1.3.1 数据类型 4
1.3.2 抽象数据类型 4
1.4 算法描述与算法分析 6
1.4.1 算法的描述 6
1.4.2 算法的时间复杂度分析 7
1.4.3 算法的空间复杂度分析 8
1.5 小结 8
1.6 经典题库 9
1.6.1 要点提醒 9
1.6.2 经典剖析 9
1.7 练习 11
第2章 线性存储结构 13
2.1 线性表的定义及基本操作 13
2.1.1 线性表的基本概念 13
2.1.2 线性表的抽象数据类型 14
2.2 线性表顺序存储结构的定义 15
2.2.1 线性表顺序存储结构的定义 15
2.2.2 顺序表的基本操作及实现 16
2.2.3 顺序表的应用 18
2.3 线性表链式存储结构与实现 20
2.3.1 线性表链式存储结构 21
2.3.2 单链表及其基本操作 21
2.3.3 循环链表的基本操作及实现 29
2.3.4 双链表的基本操作及实现 33
2.3.5 循环双链表 37
2.4 实验 38
实验一：顺序表的操作 38
实验二：单链表连接 40
实验三：循环链表连接 43
实验四：循环双链表操作 47
2.5 小结 52
2.6 经典题库 52
2.6.1 要点提醒 52
2.6.2 经典剖析 53
2.7 练习 61
第3章 栈 65
3.1 栈 65
3.1.1 栈的基本概念 65
3.1.2 栈的抽象数据类型 65
3.1.3 栈的顺序存储结构及实现 66
3.1.4 栈的链式存储结构与实现 70
3.2 栈的应用 74
3.2.1 表达式求值 74
3.2.2 数制转换 76
3.2.3 括号匹配检验 77
3.2.4 栈与递归的实现 78
3.3 实验 79
实验：利用栈寻找迷宫路径 79
3.4 小结 82
3.5 经典题库 82
3.5.1 要点提醒 82
3.5.2 经典剖析 83
3.6 练习 86
第4章 队列 90
4.1 队列 90
4.1.1 什么是队列 90
4.1.2 队列的抽象数据类型 90
4.1.3 队列的顺序存储结构与实现 91
4.1.4 队列的链式存储结构与实现 97
4.2 队列的应用 101
4.3 实验 105
实验：利用队列模拟病人看病 105
4.4 小结 109
4.5 经典题库 109
4.5.1 要点提醒 109
4.5.2 经典剖析 109
4.6 练习 112
第5章 串 116
5.1 串的定义 116
5.1.1 串的定义 116
5.1.2 串的抽象数据类型 116
5.2 串的存储结构与实现 118
5.2.1 串的顺序存储结构与实现 118
5.2.2 串的堆存储结构与实现 121
5.2.3 串的块链存储结构与实现 122
5.3 串的模式匹配算法 123
5.3.1 简单的模式匹配算法——BF算法 123
5.3.2 改进的模式匹配算法——KMP算法 125
5.4 串的应用 127
5.5 实验 128
实验一：显示多位数数字字符 128
实验二：块链的基本操作 130
实验三：统计串中最长的重复子串 135
5.6 小结 137
5.7 经典题库 138
5.7.1 要点提醒 138
5.7.2 经典剖析 138
5.8 练习 140
第6章 数组与广义表 142
6.1 数组的定义 142
6.1.1 数组的概念与性质 142
6.1.2 抽象数据类型 143
6.2 数组相关结构的实现 143
6.2.1 数组的顺序存储 143
6.2.2 数组的基本操作实现 144
6.3 矩阵的压缩存储探究 147
6.3.1 特殊矩阵 147
6.3.2 稀疏矩阵 149
6.4 广义表 153
6.4.1 广义表相关概念 153
6.4.2 抽象数据类型 154
6.4.3 广义表存储结构详解 155
6.4.4 广义表的相关应用 156
6.5 实验 157
实验一：矩阵乘法 157
实验二：三元组实现两个矩阵的乘法 160
实验三：广义表的基本运算 163
6.6 小结 168
6.7 经典题库 169
6.7.1 要点提醒 169
6.7.2 经典剖析 169
6.8 练习 172
第7章 树型结构 175
7.1 树的基本概念和术语 175
7.1.1 树的基本概念 175
7.1.2 基本术语 175
7.2 二叉树 176
7.2.1 二叉树的基本概念 176
7.2.2 二叉树性质的探究 178
7.2.3 抽象数据类型 179
7.2.4 存储结构 181
7.3 遍历二叉树的方法 185
7.3.1 遍历的定义 185
7.3.2 遍历算法探究 186
7.4 线索二叉树 189
7.5 树和森林 192
7.5.1 树的存储结构 192
7.5.2 二叉树与森林 194
7.5.3 树和森林的遍历探究 195
7.6 哈夫曼树 196
7.6.1 哈夫曼树的基本概念 196
7.6.2 哈夫曼树的构造算法 197
7.6.3 哈夫曼树和哈夫曼编码 199
7.7 实验 201
实验一：运算二叉树 201
实验二：统计二叉树结点的个数 203
实验三：统计二叉树的宽度 205
实验四：按层遍历二叉树 207
7.8 小结 210
7.9 经典题库 210
7.9.1 要点提醒 210
7.9.2 经典剖析 210
7.10 练习 217
第8章 图状结构 220
8.1 图的相关定义和术语 220
8.1.1 图的基本概念 220
8.1.2 图的基本术语 220
8.1.3 抽象数据类型 222
8.2 图的存储结构探究 223
8.2.1 邻接矩阵 223
8.2.2 邻接表 225
8.2.3 十字链表 227
8.2.4 多重邻接表 228
8.3 图的遍历 229
8.3.1 深度优先遍历 229
8.3.2 广度优先遍历 230
8.4 最小生成树 231
8.4.1 生成树的概念 231
8.4.2 最小生成树 231
8.4.3 Prim算法 235
8.5 最短路径探究 238
8.5.1 单源点最短路径问题分析 238
8.5.2 所有顶点对应最短路径问题分析 240
8.6 拓扑排序探究 241
8.7 关键路径 244
8.8 实验 244
实验一：遍历算法 244
实验二：Prim算法 248
8.9 小结 253
8.10 经典题库 253
8.10.1 要点提醒 253
8.10.2 经典剖析 253
8.11 练习 264
第9章 查找 269
9.1 查找的基本概念 269
9.2 静态查找表 269
9.2.1 顺序表的查找 269
9.2.2 有序表的查找 270
9.2.3 索引顺序表的查找 271
9.2.4 静态树表的查找 273
9.3 动态查找表 274
9.3.1 二叉排序树 274
9.3.2 平衡二叉树 276
9.3.3 B－和B＋树 280
9.3.4 键树 288
9.4 哈希表 289
9.4.1 哈希表的概念 289
9.4.2 哈希表的构造方法 289
9.4.3 处理冲突的方法 290
9.4.4 哈希表的查找及分析 293
9.5 实验 294
实验一：二叉排序树的查找 294
实验二：哈希查找 298
9.6 小结 300
9.7 经典题库 301
9.7.1 要点提醒 301
9.7.2 经典剖析 301
9.8 练习 308
第10章 内部排序 310
10.1 插入排序 310
10.1.1 直接插入排序 310
10.1.2 希尔排序 311
10.2 交换排序 313
10.2.1 冒泡排序 313
10.2.2 快速排序 315
10.3 选择排序 316
10.3.1 简单选择排序 316
10.3.2 堆排序 317
10.4 归并排序 320
10.5 基数排序 321
10.6 各种内排序方法的比较 324
10.7 实验 325
实验一：双向冒泡排序 325
实验二：数组归并排序 328
实验三：计数排序 331
实验四：字符串排序 332
实验五：最高位关键字排序MSD 335
10.8 小结 338
10.9 经典题库 338
10.9.1 要点提醒 338
10.9.2 经典剖析 339
10.10 练习 343
第11章 经典算法 345
11.1 基础算法 345
11.1.1 河内之塔 345
11.1.2 八皇后 346
11.1.3 背包问题 348
11.2 数、运算 352
11.2.1 筛选求质数 352
11.2.2 最大公因数、最小公倍数、因式分解 353
11.2.3 最大访客数 356
11.3 关于博弈 358
11.3.1 洗扑克牌（乱数排列） 358
11.3.2 Craps赌博游戏 360
11.4 集合问题 362
11.4.1 格雷码（Gray Code） 362
11.4.2 m元素集合的n元子集 364
11.5 矩阵 365
11.5.1 稀疏矩阵存储 365
11.5.2 上三角、下三角、对称矩阵存储 367
11.5.3 奇数魔方阵 369
第12章 数据分析与挖掘 371
12.1 大数据时代的挖掘 371
12.1.1 数据挖掘 371
12.1.2 从数据挖掘应用的角度看大数据 372
12.2 挖掘技术发展和历史 373
12.3 十大挖掘算法简介 374
参考文献 378