目录
第 1章 绪论 1
1.1 程序设计的问题背景 1
1.2 程序设计的一般过程 2
1.3 数据结构概述 3
1.4 数据结构基本概念 6
1.5 算法设计的一般步骤 9
1.5.1 算法定义及性质 9
1.5.2 算法设计步骤 12
1.6 算法复杂度分析 12
1.6.1 算法时间复杂度分析 12
1.6.2 算法空间复杂度分析 15
1.7 算法分析实例 17
1.8 本章小结 22
计算机领域名人堂 23
本章习题 23
第 2章 线性表 27
2.1 线性表的基本概念 27
2.1.1 线性表定义 28
2.2.2 抽象数据类型定义 29
2.2 线性表顺序存储结构定义及实现 32
2.2.1 顺序表存储结构定义 32
2.2.2 顺序表的基本操作实现 35
2.3 线性表链式存储结构定义及实现 39
2.3.1 单链表存储结构定义 40
2.3.2 单链表的实现 40
2.3.3 循环单链表 44
2.3.4 双向链表 46
2.4 顺序表与链表的比较 48
2.5 线性表应用实例 49
2.5.1 递增有序单链表生成算法 49
2.5.2 单链表插入删除算法 53
2.5.3 单链表合并算法 55
2.5.4 单链表的逆置 57
2.6 本章小结 60
计算机领域名人堂 61
本章习题 62
第3章 栈与队列 66
3.1 栈 67
3.1.1 栈的基本概念 67
3.1.2 栈的抽象数据类型 68
3.1.3 栈的操作特性 68
3.1.4 栈的顺序存储结构 70
3.1.5 栈的链式存储结构 76
3.1.6 栈的应用 78
3.2 队列 86
3.2.1 队列的基本概念 87
3.2.2 队列的抽象数据类型 87
3.2.3 链式队列的基本运算及实现 88
3.2.4 顺序队列的基本运算及实现 91
3.3 应用实例 96
3.3.1 栈的应用实例 96
3.3.2 队列的应用实例 99
3.4 本章小结 102
计算机领域名人堂 103
本章习题 103
第4章 字符串、多维数组与广义表 108
4.1 字符串 108
4.1.1 字符串的定义 109
4.1.2 字符串的存储结构及其基本运算的实现 111
4.1.3 字符串的模式匹配算法 116
4.2 多维数组 122
4.2.1 多维数组概念的引入 122
4.2.2 多维数组的顺序存储 124
4.2.3 矩阵的压缩存储 128
4.3 广义表 137
4.3.1 广义表的定义 137
4.3.2 广义表的存储 139
4.4 应用实例 143
4.4.1最大匹配分词算法 143
4.4.2正数值三角形的最优路径 147
4.5 本章小结 149
计算机领域名人堂 149
本章习题 150
第5章 树与二叉树 153
5.1 实际应用中的树 153
5.2树的逻辑结构 155
5.2.1 树的定义与基本术语 155
5.2.2 树的抽象数据类型定义 157
5.3 树的存储结构 158
5.3.1 双亲表示法 159
5.3.2 孩子表示法 159
5.3.3 孩子兄弟表示法 161
5.4 二叉树的逻辑结构 162
5.4.1 二叉树的定义 163
5.4.2 二叉树的性质 163
5.4.3 二叉树的操作与抽象数据类型定义 166
5.5 二叉树的存储结构 168
5.5.1 二叉树的顺序存储结构 168
5.5.2 二叉树的链式存储结构 169
5.5.3 基于二叉链表的二叉树遍历 170
5.5.4 线索链表与线索二叉树 179
5.6 树、森林与二叉树的转换 185
5.6.1 树与二叉树的转换 185
5.6.2 森林与二叉树的转换 186
5.6.3 树与森林的遍历 187
5.7 哈夫曼树 189
5.7.1 哈夫曼树与哈夫曼算法 189
5.7.2 哈夫曼编码 192
5.8 应用实例：表达式二叉树 193
5.8.1 表达式二叉树的概念 194
5.8.2 表达式二叉树的实现 194
5.9本章小结 197
计算机领域名人堂 197
本章习题 198
第6章 图 203
6.1 实际应用中的图 203
6.2 图的基本概念 204
6.2.1 图的定义和基本术语 204
6.2.2 图的操作定义 207
6.3 图的存储结构 208
6.3.1 邻接矩阵 208
6.3.2 邻接表 211
6.3.3 十字链表 213
6.3.4 邻接多重表 214
6.4 图的遍历 215
6.4.1 图的深度优先搜索遍历 215
6.4.2 图的广度优先搜索遍历 217
6.4.3 图的连通性 218
6.5 图的生成树问题 219
6.5.1 生成树与最小生成树 219
6.5.2 最小生成树Prim算法 220
6.5.3 最小生成树Kruskal算法 223
6.6 图的最短路径问题 226
6.6.1 单源最短路径Dijkstra算法 226
6.6.2 各顶点间最短路径Floyd算法 230
6.7 有向无环图的应用 233
6.7.1 拓扑排序 233
6.7.2 关键路径 236
6.8 应用实例 241
6.8.1 并查集 241
6.8.2 地铁换乘问题 245
6.9 本章小结 258
计算机领域名人堂 258
本章习题 259
第7章 排序 263
7.1 实际应用中的排序 263
7.2 排序的概述 264
7.2.1 排序算法的稳定性 265
7.2.2 排序算法的分类 266
7.2.3 排序算法的性能 266
7.3 插入排序 266
7.3.1 直接插入排序 266
7.3.2 折半插入排序 269
7.3.3 希尔排序 271
7.4 交换排序 274
7.4.1 冒泡排序 274
7.4.2 快速排序 277
7.5 选择排序 281
7.5.1 简单选择排序 281
7.5.2 树形选择排序 284
7.6 归并排序 291
7.7 分配排序 295
7.7.1 桶排序 295
7.7.2 基数排序 296
7.8 各种排序技术比较 299
7.9 本章小结 300
计算机领域名人堂 301
本章习题 302
第8章 查找 308
8.1 查找概述 308
8.1.1 查找基本概念 308
8.1.2 查找操作性能分析 309
8.2 线性表的查找技术 309
8.2.1 顺序查找 309
8.2.2 折半查找 312
8.2.3 索引查找 315
8.3 树表的查找技术 316
8.3.1 二叉排序树 316
8.3.2 平衡二叉树 325
8.3.3 红黑树 331
8.3.4 B树 346
8.4 散列表的查找技术 350
8.4.1 散列表概述 350
8.4.2 散列函数设计 351
8.4.3 处理冲突的方法 352
8.4.4 散列查找性能分析 355
8.5 本章小结 357
计算机领域名人堂 358
本章习题 359
第9章 大数据存储与检索 364
9.1 大数据的定义与特征 364
9.1.1 大数据定义 365
9.1.2 大数据特征 365
9.1.3 大数据的行业发展趋势 367
9.2 大数据存储 367
9.2.1 数据存储管理 368
9.2.2 分布式文件系统 368
9.2.3 NoSQL数据库 371
9.2.4 HBase数据库 372
9.3 大数据检索 375
9.3.1 大数据索引 375
9.3.2 大数据高效检索 377
9.4 应用实例 378
9.5 本章小结 382
计算机领域名人堂 383
本章习题 383