第1章 绪论 1
1.1 数据结构与算法的重要性 1
1.2 数据结构的基本概念 3
1.3 算法和算法分析 6
1.3.1 算法描述 6
1.3.2 算法分析 8
1.3.3 NP问题 11
1.4 STL与数据结构 12
1.4.1 STL简介 12
1.4.2 STL与数据结构的关系 13
1.5 工程实践和思考 14
习题1 18
第2章 线性表 20
2.1 线性表概述 20
2.1.1 线性表的定义 20
2.1.2 线性表的运算 21
2.1.3 各种常用存储结构 21
2.2 顺序表的实现 24
2.2.1 顺序表的存储结构 24
2.2.2 顺序表的基本运算 25
2.2.3 顺序表的应用——通信录 29
2.2.4 STL中的顺序表——vector 31
2.3 单链表的实现 33
2.3.1 单链表的存储结构 34
2.3.2 单链表的基本运算 35
2.3.3 单链表的应用——通信录 42
2.4 循环链表的实现 43
2.5 双链表的实现 44
2.5.1 双链表的基本结构 44
2.5.2 双链表的基本运算 45
2.5.3 STL中的双链表——list 46
2.6 顺序表与链表的比较 47
2.6.1 时间性能比较 47
2.6.2 空间性能比较 47
2.7 工程实践和思考 48
问题1：不支持指针的高级语言，如何实现链表？ 48
问题2：如何实现一元多项式的求和？ 52
问题3：操作系统的内存如何管理？ 57
问题4：荷兰国旗问题 61
习题2 63
第3章 线性表的扩展 68
3.1 各种扩展线性表 68
3.1.1 栈 68
3.1.2 队列 69
3.1.3 串 69
3.1.4 多维数组 71
3.2 栈的实现 72
3.2.1 顺序栈 72
3.2.2 链式栈 74
3.2.3 STL中的栈——stack 76
3.3 队列的实现 77
3.3.1 循环队列 77
3.3.2 链队列 80
3.3.3 STL中的队列 83
3.4 串的实现 85
3.4.1 串的存储结构 85
3.4.2 串的模式匹配 86
3.4.3 KMP算法 89
3.4.4 STL中的串——string 93
3.5 多维数组 94
3.5.1 多维数组的存储 94
3.5.2 稀疏矩阵 95
3.6 基于栈的经典算法 100
3.6.1 递归——斐波那契数列 100
3.6.2 分治法——汉诺塔游戏 101
3.6.3 回溯法——迷宫问题 104
3.6.4 动态规划——背包问题 107
3.7 工程实践和思考 109
问题1：优先级队列的调度 109
问题2：图像识别领域的基本问题——手写数字识别 111
问题3：贪心算法和动态规划的区别 114
问题4：穷举法和动态规划的区别 115
习题3 115
第4章 树 119
4.1 基本概念 119
4.1.1 树 119
4.1.2 二叉树 120
4.1.3 森林 123
4.2 基本操作 124
4.2.1 树的遍历 124
4.2.2 二叉树的遍历 125
4.2.3 森林的遍历 126
4.2.4 树、森林与二叉树的转换 127
4.3 存储结构 128
4.3.1 树的存储结构 128
4.3.2 二叉树的存储结构 132
4.4 二叉树的实现 134
4.4.1 二叉树的声明 134
4.4.2 二叉树的关键算法 134
4.4.3 递归算法的规律 138
4.5 哈夫曼树的应用 143
4.5.1 哈夫曼树的定义与存储结构 144
4.5.2 哈夫曼树的构造 146
4.5.3 哈夫曼编码表的构建 148
4.5.4 哈夫曼编、解码的实现 148
4.6 工程实践和思考 149
问题1：构建算术表达式二叉树 149
问题2：通信系统中如何使用哈夫曼树压缩信息？ 153
习题4 154
第5章 图 158
5.1 基本概念 158
5.1.1 图的定义 158
5.1.2 图的基本术语 158
5.2 图的存储结构 161
5.2.1 邻接矩阵 161
5.2.2 邻接表 163
5.2.3 十字链表 165
5.2.4 邻接多重表 166
5.2.5 边集数组 166
5.2.6 图的存储结构比较 167
5.3 图的实现 167
5.3.1 图的构建 167
5.3.2 图的遍历 169
5.3.3 图的析构 173
5.4 最小生成树 173
5.4.1 普里姆算法 174
5.4.2 克鲁斯卡尔算法 178
5.5 最短路径 182
5.5.1 Dijkstra算法 183
5.5.2 Floyd算法 186
5.6 工程实践与思考 187
问题1：图着色问题 187
问题2：地铁换乘线路查找问题 191
问题3：教学计划安排问题 192
问题4：关键路径问题 194
习题5 195
第6章 查找 197
6.1 基本概念 197
6.1.1 静态查找和动态查找 197
6.1.2 查找的性能评估 197
6.1.3 查找结构分类 198
6.2 线性表查找 198
6.2.1 顺序查找 198
6.2.2 折半查找 199
6.2.3 索引查找 202
6.3 树表查找 203
6.3.1 二叉排序树 203
6.3.2 平衡二叉树 209
6.3.3 B—树 211
6.3.4 STL中的树表——set和map 217
6.4 散列查找 220
6.4.1 散列技术 220
6.4.2 散列函数设计 221
6.4.3 冲突处理 222
6.4.4 常用的散列函数 225
6.5 工程实践和思考 227
问题1：自然语言处理的基本问题——中文分词 227
问题2：数据库索引结构 231
习题6 235
第7章 排序 237
7.1 基本概念 237
7.1.1 相关概念 237
7.1.2 排序性能评估 238
7.1.3 排序方法分析 238
7.2 简单排序 239
7.2.1 起泡排序 239
7.2.2 直接插入排序 241
7.2.3 简单选择排序 243
7.3 复杂排序 245
7.3.1 希尔排序 245
7.3.2 快速排序 247
7.3.3 堆排序 249
7.3.4 归并排序 253
7.3.5 STL中常用的排序算法 257
7.4 非比较的排序算法 258
7.4.1 计数排序 259
7.4.2 桶排序 260
7.4.3 基数排序 262
7.5 工程实践和思考 264
问题1：电话号码排序 264
问题2：大数据下的排序问题 267
习题7 270
参考文献 272
附录 273
附录1 异常处理 273
附录2 模板 275