目录 1
第1章 初识数据结构 1
1.1 数据结构回顾 1
1.1.1 数据结构的概念 1
1.1.2 系统的生命周期 2
1.2 算法的定义 3
1.3 算法性能分析和度量 7
1.3.1 算法评价的标准 7
1.3.2 算法复杂度的度量 7
1.4 数据抽象 12
1.5 常用教材习题解答 13
1.6 巩固练习 15
第2章 重要的C语言概念 17
2.1 基本数据类型回顾 17
2.1.1 整型数据 17
2.1.2 实型数据 17
2.1.3 字符型数据 18
2.2 基本控制语句 19
2.2.1 条件语句 19
2.2.2 循环语句 20
2.2.3 开关语句 27
2.3 结构和联合 30
2.3.1 结构 30
2.3.2 联合 35
第3章 数组 37
3.1 顺序数组 37
3.1.1 概念回顾 37
3.1.2 数据结构实现 37
3.2 实例—多项式的数组表示 38
3.3 实例—稀疏矩阵 39
3.3.1 概念回顾 39
3.3.2 矩阵置换 40
3.3.3 矩阵乘法 42
3.3.4 对角矩阵建立 44
3.3.5 三对角矩阵建立 45
3.3.6 三角矩阵建立 46
3.3.7 对称矩阵建立 47
3.4 字符串数组 48
3.4.1 基本操作实现 48
3.4.2 实例—串插入、串匹配及改进、串合并 49
3.5 常用教材习题解答 51
第4章 栈和队列 57
4.1 栈 57
4.1.1 概念回顾 57
4.1.2 数据结构实现 57
4.1.3 基本操作实现 58
4.1.4 实例—进制转换问题 62
4.2.2 数据结构实现 64
4.2 队列 64
4.2.1 概念回顾 64
4.2.3 基本操作实现 65
4.2.4 实例—舞伴问题 71
4.3 经典应用 74
4.3.1 迷宫问题 74
4.3.2 图元识别 76
4.3.3 括号匹配 79
4.3.4 火车车厢重排 81
4.3.5 开关盒布线 85
4.3.6 离线等价类 88
4.4 常用教材习题解答 91
第5章 链表 97
5.1 单链表 97
5.1.1 概念回顾 97
5.1.2 数据结构实现 97
5.1.3 基本操作实现 98
5.1.4 实例—动态堆栈、动态队列 108
5.2 双向链表 113
5.2.1 概念回顾 113
5.2.2 数据结构实现 113
5.2.3 基本操作实现 113
5.3.3 基本操作实现 116
5.3.2 数据结构实现 116
5.3.1 概念回顾 116
5.3 循环链表 116
5.4 实例—循环链表的多项式求解 117
5.5 实例—稀疏矩阵 121
5.5.1 稀疏矩阵的建立 123
5.5.2 稀疏矩阵的删除 125
5.6 经典应用—箱子排序 128
5.7 常用教材习题解答 130
第6章 递归 139
6.1 概念回顾 139
6.2.1 算法实现 140
6.2 实例—汉诺塔 140
6.2.2 递归过程分析 141
6.3 经典应用—八皇后问题 145
6.4 常用教材习题解答 147
第7章 树和森林 150
7.1 树和森林 150
7.1.1 概念回顾 150
7.1.2 数据结构实现 151
7.2 二叉树 154
7.2.1 概念回顾 154
7.2.2 数据结构实现 156
7.3 二叉树的遍历 159
7.3.1 中序遍历 159
7.3.2 前序遍历 160
7.3.3 后序遍历 161
7.3.4 应用实例 162
7.4 线索化二叉树 162
7.5 树与森林的转换 165
7.5.1 森林与二叉树的转换 165
7.5.2 森林的遍历 166
7.6 经典应用 168
7.6.1 信号放大器 168
7.6.2 在线等价类 171
7.7 常用教材习题解答 173
8.1.1 概念回顾 190
8.1 静态搜索 190
第8章 搜索 190
8.1.2 实例—顺序搜索 191
8.1.3 实例—基于有序表的折半搜索 192
8.2 二叉搜索树 194
8.2.1 概念回顾 194
8.2.2 基本操作实现 196
8.3 AVL树 201
8.3.1 概念回顾 201
8.3.2 基本操作实现 202
8.4 经典应用 205
8.4.1 直方图 205
8.4.2 箱子装载问题 206
8.4.3 交叉分布 208
8.5 常用教材习题解答 212
第9章 图 218
9.1 概念回顾 218
9.2 数据结构实现 218
9.2.1 图的邻接矩阵表示法 218
9.2.2 图的邻接表表示法 220
9.3 基本操作实现 223
9.3.1 深度优先搜索 223
9.3.2 广度优先搜索 225
9.3.3 连通分量 228
9.3.4 生成树 230
9.3.5 重连通分量 231
9.4 图的最小生成树 234
9.4.1 Kruskal算法 235
9.4.2 Prim算法 238
9.5 求解最短路径 240
9.5.1 单源全目的地的最短路径 241
9.5.2 所有对的最短路径 243
9.6 实例—活动网络（AOV） 244
9.7 经典应用 246
9.7.1 寻找路径 246
9.7.2 连通图 247
9.8 常用教材习题解答 249
10.1.2 基本操作实现 257
10.1.1 概念回顾 257
第10章 堆和哈希表 257
10.1 堆 257
10.2 哈希表 262
10.2.1 概念回顾 262
10.2.2 基本操作实现 263
10.2.3 静态哈希 267
10.2.4 动态哈希 270
10.3 经典应用 270
10.3.1 机器调度 270
10.3.2 霍夫曼编码 272
10.4 常用教材习题解答 274
11.2 插入排序 276
第11章 排序问题 276
11.1 概念回顾 276
11.3 交换排序 280
11.3.1 冒泡排序 280
11.3.2 快速排序 283
11.4 归并排序 285
11.4.1 概念回顾 285
11.4.2 自底向上的实现 285
11.4.3 自顶向下的实现 287
11.5.1 概念回顾 289
11.5.2 数据结构实现 289
11.5 堆排序 289
11.6 基数排序 290
11.6.1 概念回顾 290
11.6.2 链式排序实现 293
11.7 外排序 295
11.7.1 概念回顾 295
11.7.2 K路平衡归并 295
11.8 常用教材习题解答 297
第12章 经典算法设计 307
12.1 贪心算法 307
12.1.1 算法思想及描述 307
12.1.2 经典应用 309
12.2 分治算法 315
12.2.1 算法思想及描述 315
12.2.2 经典应用 316
12.3 动态规划 322
12.3.1 算法思想及描述 322
12.3.2 经典应用 322
12.4 回溯算法 326
12.4.1 算法思想及描述 326
12.4.2 经典应用 328
12.5 分枝定界算法 336
12.5.1 算法思想及描述 336
12.5.2 经典应用 337