算法与数据结构(C语言版)第2版[图书]

2.3 线性表的链式表示和实现 25
2.3.1 单链表的表示 25
2.3.2 单链表操作的实现 27
2.4 线性表实现方法的比较 33
2.5 循环链表 34
2.6 双链表 35
*2.7 静态链表 36
*2.8 算法设计举例 38
习题 42
第3章 栈和队列 44
3.1 栈 44
3.1.1 栈的类型定义 44
3.1.2 栈的表示和实现 45
3.2 栈的应用举例 49
3.3 栈与递归 51
3.3.1 如何实现递归 52
3.3.2 采用递归算法解决的问题 52
3.3.3 将递归转换为非递归 54
3.4 队列 56
3.4.1 队列的类型定义 56
3.4.2 循环队列—队列的顺序存储结构 57
3.4.3 链队列—队列的链式表示和实现 60
*3.5 算法设计举例 62
习题 64
第4章 串 67
4.1 串的类型定义 67
4.2 串的表示和实现 68
4.2.1 串的顺序存储结构 69
4.2.2 串的链式存储结构 70
4.3 串的模式匹配 71
4.3.1 朴素的模式匹配算法 71
4.3.2 KMP算法 72
4.4 串的应用举例 74
*4.5 算法设计举例 75
习题 77
第5章 数组和广义表 79
5.1 数组的概念及其基本操作 79
5.2 数组的顺序存储 80
5.3 矩阵的压缩存储 81
5.3.1 特殊矩阵 81
5.3.2 稀疏矩阵 83
5.4 广义表 91
5.4.1 广义表的定义 91
5.4.2 广义表的存储结构 92
*5.5 算法设计举例 94
习题 96
第6章 树 98
6.1 树的概念及操作 98
6.2 二叉树 100
6.2.1 二叉树的概念及操作 100
6.2.2 二叉树的性质 102
6.2.3 二叉树的存储结构 104
6.3 二叉树的遍历 105
*6.4 线索二叉树 108
6.4.1 线索二叉树的概念 108
6.4.2 遍历线索二叉树 110
6.5 树和森林 112
6.5.1 树的存储结构 112
6.5.2 森林、树、二叉树的相互转换 114
6.5.3 树和森林的遍历 116
6.6 哈夫曼树及其应用 117
6.6.1 最优二叉树（哈夫曼树） 117
6.6.2 哈夫曼编码 119
*6.7 算法设计举例 121
习题.. 124
第7章 图 128
7.1 图的定义和术语 128
7.2 图的存储结构 131
7.2.1 邻接矩阵表示法（数组表示法） 131
7.2.2 邻接表 132
7.2.3 十字链表 134
7.2.4 邻接多重表 135
7.3 图的遍历 136
7.3.1 深度优先遍历 136
7.3.2 广度优先遍历 138
7.4 图的连通性问题 139
7.4.1 图的连通分量和生成树 139
7.4.2 最小生成树 140
7.5 有向无环图及其应用 144
7.5.1 拓扑排序 144
7.5.2 关键路径 146
7.6 最短路径 150
7.6.1 从某个源点到其他各顶点的最短
路径 150
7.6.2 每一对顶点之间的最短路径 152
*7.7 算法设计举例 154
习题 157
第 8章 动态存储管理 160
8.1 概述 160
8.1.1 问题的提出 160
8.1.2 内存分配处理 161
8.2 可利用空间表及分配办法 161
8.2.1 可利用空间表的三种不同的结构
形式 162
8.2.2 可利用空间表的三种分配策略 163
8.3 边界标识法 164
8.3.1 可利用空间表的结构 164
8.3.2 分配算法 165
8.3.3 回收算法 167
8.4 伙伴系统 169
8.4.1 可利用空间表的结构 169
8.4.2 分配算法 170
8.4.3 回收算法 171
习题 171
第9章 查找 173
9.1 静态查找表上的查找 174
9.1.1 顺序表的查找 174
9.1.2 折半查找 175
9.1.3 斐波那契查找 178
9.1.4 插值查找 179
9.1.5 分块查找 180
9.2 动态查找表上的查找 182
9.2.1 二叉排序树 182
9.2.2 平衡二叉树 186
*9.2.3 B-树 194
*9.2.4 键树 199
9.3 散列表上的查找 199
9.3.1 散列表的概念 199
9.3.2 构造散列函数的方法 200
9.3.3 解决冲突的方法 202
9.3.4 散列表的查找性能分析 206
9.3.5 闭散列法与开散列法的比较 207
*9.4 算法设计举例 207
习题 210
第10章 排序 213
10.1 概述 213
10.2 插入排序 214
10.2.1 直接插入排序 214
10.2.2 折半插入排序 216
10.2.3 二路插入排序 216
*10.2.4 表插入排序 218
10.2.5 希尔排序 220
10.3 交换排序 221
10.3.1 起泡排序 221
10.3.2 快速排序 222
10.4 选择排序 224
10.4.1 直接选择排序 225
10.4.2 树形选择排序 226
10.4.3 堆排序 226
10.5 归并排序 229
10.6 分配排序 230
10.7 各种内部排序方法的比较 234
10.8 外部排序 235
10.8.1 文件管理 235
10.8.2 外部排序的方法 236
10.8.3 多路平衡归并排序 237
10.8.4 置换选择排序 239
10.8.5 最佳归并树 242
*10.8.6 磁带排序 243
*10.9 算法设计举例 244
习题 246
第11章 文件 249
11.1 基本概念 249
11.2 顺序文件 251
11.3 索引文件 253
11.4 索引顺序文件 254
11.4.1 ISAM文件 254
11.4.2 VSAM文件 257
11.5 散列文件 259
11.6 多关键字文件 259
11.6.1 多重表文件 260
11.6.2 倒排文件 260
习题 261
附录 上机实验题目 262
参考文献 ...264