第一部分 概论 3
第1章 数据结构 3
1.1 什么是数据 3
1.2 什么是数据结构 3
1.2.1 数据的逻辑结构 3
1.2.2 数据的存储结构 4
1.2.3 数据的运算 5
1.3 什么是数据类型 5
1.4 知识点小结 6
习题 6
第2章 算法 7
2.1 什么是算法 7
2.2 算法的描述 7
2.3 算法分析 8
2.3.1 时间复杂度 8
2.3.2 渐近符号 9
2.3.3 空间复杂度 10
2.3.4 复杂度分析举例 10
2.4 知识点小结 13
习题 13
第二部分 预备知识第3章 C语言、递归及存储分配方式 16
3.1 C语言的相关内容 16
3.1.1 函数的参数传递与结果返回 16
3.1.2 结构体类型 17
3.1.3 指针 18
3.2 递归 18
3.3 存储分配方式 19
3.4 知识点小结 20
习题 20
第三部分 线性结构第4章 线性表 22
4.1 线性表的类型定义 22
4.1.1 线性表的逻辑结构 22
4.1.2 线性表的基本运算 22
4.2 线性表的顺序存储表示 23
4.2.1 顺序表 23
4.2.2 顺序表中基本运算的实现 24
4.3 线性表的链式存储表示 30
4.3.1 单链表 30
4.3.2 单链表中基本运算的实现 31
4.4 线性表的其他链式存储表示 38
4.4.1 静态单链表 38
4.4.2 双（向）链表 41
4.4.3 循环单（向）链表 43
4.4.4 循环双（向）链表 46
4.5 线性表的应用举例 47
4.6 顺序表和链表的比较 48
4.7 知识点小结 49
习题 49
第5章 栈 51
5.1 栈的类型定义 51
5.1.1 栈的逻辑结构 51
5.1.2 栈的基本运算 52
5.2 栈的顺序存储表示 52
5.2.1 顺序栈 52
5.2.2 顺序栈中基本运算的实现 53
5.3 栈的链式存储表示 55
5.3.1 链栈 55
5.3.2 链栈中基本运算的实现 55
5.4 两个方向生长的栈 56
5.5 栈的应用举例 57
5.6 知识点小结 61
习题 61
第6章 队列 63
6.1 队列的类型定义 63
6.1.1 队列的逻辑结构 63
6.1.2 队列的基本运算 63
6.2 队列的链式存储表示 64
6.2.1 链队列 64
6.2.2 链队列中基本运算的实现 65
6.3 队列的顺序存储表示 66
6.3.1 顺序队列 66
6.3.2 循环队列 69
6.3.3 循环队列中基本运算的实现 71
6.4 双端队列 74
6.5 队列的应用举例 74
6.6 知识点小结 75
习题 76
第7章 串 77
7.1 串的类型定义 77
7.1.1 串的逻辑结构 77
7.1.2 串的基本运算 77
7.2 串的顺序存储表示 78
7.3 串的堆分配存储表示 80
7.4 串的块链存储表示 81
7.5 串的模式匹配 82
7.6 知识点小结 88
习题 88
第8章 数组及广义表 89
8.1 数组的类型定义 89
8.1.1 数组的定义 89
8.1.2 数组的性质 89
8.1.3 数组的基本运算 89
8.2 数组的顺序存储表示 90
8.3 特殊矩阵的压缩存储 92
8.3.1 特殊形状矩阵的压缩存储 93
8.3.2 随机稀疏矩阵的压缩存储及其运算 95
8.4 广义表 104
8.4.1 广义表的基本概念 104
8.4.2 广义表的基本运算 105
8.4.3 广义表的存储结构 106
8.5 知识点小结 108
习题 108
第四部分 非线性结构第9章 树 110
9.1 概述 110
9.1.1 树的定义及基本术语 110
9.1.2 树的存储结构 112
9.2 二叉树 123
9.2.1 二叉树的定义 123
9.2.2 二叉树的性质 123
9.2.3 二叉树的存储结构 128
9.3 二叉树的遍历 132
9.3.1 遍历操作 132
9.3.2 先序遍历 132
9.3.3 中序遍历 133
9.3.4 后序遍历 134
9.3.5 层次遍历 135
9.3.6 二叉树遍历的应用举例 136
9.4 线索二叉树 144
9.4.1 二叉树的线索化 145
9.4.2 线索二叉树上的运算 149
9.5 二叉树的应用 156
9.5.1 哈夫曼树及其应用 156
9.5.2 二叉排序树 161
9.5.3 平衡二叉树 163
9.6 树、森林与二叉树的相互转换 166
9.6.1 树与二叉树的相互转换 166
9.6.2 森林与二叉树的相互转换 168
9.7 树、森林的遍历 169
9.7.1 树的遍历 169
9.7.2 森林的遍历 169
9.8 树的应用举例 170
9.9 知识点小结 171
习题 172
第10章 图 173
10.1 概述 173
10.1.1 图的定义及基本术语 173
10.1.2 图的存储结构 179
10.1.3 图的创建 184
10.2 图的遍历 187
10.2.1 深度优先搜索遍历 187
10.2.2 广度优先搜索遍历 191
10.2.3 图遍历的应用举例 193
10.3 生成树 194
10.3.1 连通图的生成树 194
10.3.2 连通网的最小生成树 195
10.4 最短路径 197
10.4.1 单源最短路径 197
10.4.2 每对顶点间的最短路径 201
10.5 有向无环图及其应用 205
10.5.1 AOV网与拓扑排序 205
10.5.2 AOE网与关键路径 207
10.6 知识点小结 209
习题 209
第五部分 两种重要运算第11章 查找 212
11.1 查找的基本概念 212
11.2 主要查找方法简介 213
11.3 静态查找 213
11.3.1 顺序查找 213
11.3.2 二分查找 215
11.3.3 分块查找 219
11.4 动态查找 220
11.5 散列查找 227
11.5.1 散列表的概念 228
11.5.2 散列函数的构造方法 228
11.5.3 处理冲突的方法 229
11.5.4 散列表的查找 232
11.6 知识点小结 234
习题 235
第12章 内排序 236
12.1 排序的基本概念 236
12.2 插入排序 237
12.2.1 直接插入排序 237
12.2.2 希尔排序 241
12.3 交换排序 242
12.3.1 冒泡排序 242
12.3.2 快速排序 244
12.4 选择排序 247
12.4.1 直接选择排序 247
12.4.2 树形选择排序 248
12.4.3 堆排序 249
12.5 归并排序 254
12.6 分配排序 255
12.6.1 箱排序 255
12.6.2 基数排序 255
12.7 各种内排序法的比较 257
12.8 知识点小结 257
习题 258
第六部分 文件的组织结构及排序第13章 文件 260
13.1 文件的基本概念 260
13.2 顺序文件 260
13.3 索引文件 261
13.4 索引顺序文件 262
13.5 散列文件 267
13.6 多关键字文件 268
13.7 知识点小结 268
习题 268
第14章 外排序 269
14.1 多路平衡归并 269
14.2 置换选择排序 272
14.3 归并树及最佳归并树 274
14.4 知识点小结 275
习题 275
参考文献 276