第1章 基础知识 1
1.1 数据结构的基本概念 1
1.2 抽象数据类型 5
1.3 问题、算法和程序 6
1.4 算法分析概述 7
1.5 时间复杂度 10
1.6 渐近分析 12
1.6.1 上限表示法 12
1.6.2 下限表示法 13
1.6.3 Θ表示法 14
1.6.4 化简法则 14
1.7 空间复杂度 17
1.8 C＋＋语言基础 18
1.8.1 面向对象的概念 19
1.8.2 数据声明和作用域 20
1.8.3 输入／输出 21
1.8.4 函数 23
1.8.5 参数传递 24
1.8.6 函数重载 26
1.8.7 动态内存分配 26
1.8.8 C＋＋的模板 27
本章小结 28
习题 28
第2章 线性表 31
2.1 线性表的定义 31
2.2 线性表的顺序存储结构 32
2.2.1 顺序存储结构 32
2.2.2 顺序存储结构的实现 34
2.3 线性表的链式存储结构 37
2.3.1 单链表 37
2.3.2 双向链表 43
2.3.3 循环链表 46
2.4 线性表应用举例 48
2.4.1 一元多项式的表示 48
2.4.2 商品链更新 50
本章小结 51
习题 51
第3章 受限线性表——栈、队列及串 55
3.1 操作受限线性表——栈 55
3.2 栈的存储结构 56
3.2.1 顺序栈的定义及实现 57
3.2.2 链栈的定义及实现 60
3.3 栈的应用 63
3.3.1 括号匹配检验 63
3.3.2 栈与递归 65
3.4 操作受限线性表——队列 69
3.5 队列的存储结构及实现 70
3.5.1 顺序队列的定义及实现 70
3.5.2 队列的链式存储结构及实现 74
3.6 队列的应用 78
3.6.1 杨辉三角形 78
3.6.2 火车车厢重排 79
3.7 类型受限线性表——字符串 82
3.7.1 串的定义 83
3.7.2 串的操作 83
3.7.3 串的存储结构 84
3.7.4 串类及其实现 85
3.7.5 串的模式匹配 88
本章小结 92
习题 92
第4章 扩展线性表——数组与广义表 96
4.1 扩展线性表——数组 96
4.1.1 数组的定义 96
4.1.2 数组的基本操作 97
4.1.3 数组的存储结构 97
4.1.4 矩阵的压缩存储 98
4.2 扩展线性表——广义表 104
4.2.1 广义表的定义及性质 104
4.2.2 广义表的存储表示 105
4.2.3 广义表的递归操作 110
本章小结 113
习题 114
第5章 树和二叉树 115
5.1 树的定义与基本术语 115
5.1.1 树的定义 115
5.1.2 相关的基本术语 116
5.2 二叉树的定义、性质和存储结构 117
5.2.1 二叉树的定义 117
5.2.2 二叉树的主要性质 118
5.2.3 二叉树的存储结构 122
5.3 二叉树的遍历 125
5.3.1 二叉树的先序遍历 126
5.3.2 二叉树的中序遍历 127
5.3.3 二叉树的后序遍历 129
5.4 二叉树应用1：哈夫曼树 133
5.4.1 哈夫曼树的构造 133
5.4.2 哈夫曼编码 137
5.5 二叉树应用2：二叉查找树 140
5.5.1 二叉查找树的定义 140
5.5.2 二叉查找树的查找 141
5.5.3 二叉查找树的插入 143
5.5.4 二叉查找树的删除 145
5.6 二叉树应用3：平衡二叉查找树 148
5.6.1 平衡二叉树的定义 148
5.6.2 平衡化旋转 149
5.6.3 平衡二叉查找树的插入 154
5.6.4 平衡二叉查找树的删除 155
5.7 二叉树应用4：堆与优先队列 158
5.7.1 堆与优先队列的定义与实现 158
5.7.2 堆的插入和堆顶删除 160
5.8 树与森林 164
5.8.1 树的存储结构 164
5.8.2 树、森林与二叉树的转换 167
5.8.3 树与森林的遍历 169
本章小结 170
习题 170
第6章 图 177
6.1 图的定义和术语 177
6.2 图的存储结构 181
6.2.1 邻接矩阵存储方法 182
6.2.2 邻接表存储方法 185
6.3 图的遍历 190
6.3.1 深度优先搜索 191
6.3.2 广度优先搜索 194
6.4 图的应用1：拓扑排序 196
6.5 图的应用2：关键路径 200
6.6 图的应用3：最短路径 205
6.6.1 单源点最短路径问题 205
6.6.2 任意对顶点之间的最短路径 210
6.7 图的应用4：图的最小生成树 213
6.7.1 Prim算法 214
6.7.2 Kruskal算法 217
本章小结 220
习题 220
第7章 排序算法 224
7.1 排序的基本概念 224
7.2 简单排序 226
7.2.1 简单插入排序 226
7.2.2 冒泡排序 229
7.2.3 简单选择排序 232
7.3 高级排序 234
7.3.1 希尔排序 234
7.3.2 快速排序 236
7.3.3 归并排序 241
7.3.4 树形选择排序1：锦标赛排序 243
7.3.5 树形选择排序2：堆排序 245
7.4 关键字比较排序下界问题 249
7.5 非关键字比较的排序 250
7.5.1 基数排序 250
7.5.2 多关键字排序 253
7.6 各种排序算法的比较 254
本章小结 255
习题 255
第8章 查找算法 258
8.1 查找的基本概念 258
8.2 静态查找表 259
8.2.1 顺序表的查找 260
8.2.2 折半查找 261
8.3 散列表 263
8.3.1 哈希函数的常用构建方法 264
8.3.2 解决冲突的办法 266
8.3.3 哈希表的实现 270
8.3.4 哈希表的分析 273
8.4 线性索引 274
8.5 树形索引 275
8.5.1 2-3树 276
8.5.2 B树 278
8.5.3 B+树 286
本章小结 288
习题 288
第9章 算法设计常用方法 289
9.1 贪心算法 289
9.1.1 活动安排问题 289
9.1.2 贪心算法的设计思想 291
9.1.3 贪心算法的应用 294
9.2 分治算法 302
9.2.1 分治算法的基本思想 302
9.2.2 分治算法复杂度分析 304
9.2.3 大整数相乘 307
9.2.4 矩阵乘法 309
9.2.5 快速排序算法的改进 312
9.3 动态规划 317
9.3.1 动态规划原理 317
9.3.2 最优二叉查找树 321
9.3.3 最长公共子序列 325
9.4 回溯算法 327
9.4.1 回溯算法的思想 328
9.4.2 N皇后问题 331
9.4.3 迷宫问题 332
本章小结 336
习题 337
第10章 计算复杂性简介 340
10.1 基本概念 340
10.1.1 非确定性算法 340
10.1.2 P类与NP类问题 342
10.2 NP难与NP完全问题 343
10.2.1 问题变换与计算复杂度归约 343
10.2.2 NP完全性 344
10.3 NP完全问题的例子 346
10.3.1 CNF-SAT问题 346
10.3.2 3-SAT问题 348
10.3.3 团问题 349
10.3.4 顶点覆盖问题 350
10.3.5 其他一些NP完全问题 351
本章小结 351
习题 352
附录 353
附录A “数据结构与算法”课内实验设计 353
附录B “数据结构与算法”专题实验设计 354
参考文献 362