第1章 绪论 1
1.1 计算机问题求解过程 1
1.2 迷宫问题 2
1.3 数据结构 4
1.3.1 数据结构研究的内容 4
1.3.2 数据结构概念 6
1.4 算法 10
1.4.1 算法概念及特性 10
1.4.2 算法描述 11
1.4.3 算法分析 12
1.5 本章小结 14
1.6 习题 14
第2章 线性表 16
2.1 线性表 16
2.1.1 线性表的定义 16
2.1.2 线性表的顺序存储 20
2.1.3 线性表的链式存储 28
2.1.4 链表的各种变形 37
2.1.5 线性表的应用 40
2.2 栈 45
2.2.1 栈的定义 45
2.2.2 栈的顺序存储 46
2.2.3 栈的链式存储 49
2.2.4 栈的应用 51
2.3 队列 55
2.3.1 队列的定义 55
2.3.2 队列的顺序存储 56
2.3.3 队列的链式存储 59
2.3.4 优先队列 61
2.3.5 队列的应用 62
2.4 数组 65
2.4.1 数组的定义 66
2.4.2 数组的表示和实现 66
2.4.3 数组的应用 77
2.5 本章小结 79
2.6 习题 80
第3章 树 82
3.1 二叉树 83
3.1.1 二叉树的基本概念和性质 83
3.1.2 二叉树的存储结构 86
3.1.3 二叉树的遍历 88
3.2 二叉树的变形 93
3.2.1 线索二叉树 93
3.2.2 二叉排序树 96
3.2.3 平衡二叉树 100
3.2.4 赫夫曼树及赫夫曼编码 105
3.3 树和森林 109
3.3.1 树和森林的定义 109
3.3.2 树和森林的存储结构 110
3.3.3 树和森林的基本操作 112
3.4 树的变形 115
3.4.1 四叉树 115
3.4.2 B树 122
3.4.3 2-3树 127
3.5 树的应用 128
3.5.1 算术表达式 128
3.5.2 堆排序 129
3.5.3 决策分析 131
3.6 本章小结 134
3.7 习题 134
第4章 图和广义表 137
4.1 图简介 137
4.1.1 基本概念和术语 138
4.1.2 图的应用 139
4.2 图的存储结构 140
4.2.1 图的顺序存储结构 140
4.2.2 图的链式存储结构 141
4.3 图的遍历 145
4.3.1 深度优先遍历 145
4.3.2 广度优先遍历 147
4.4 图的应用 148
4.4.1 最小生成树 148
4.4.2 拓扑排序 155
4.4.3 关键路径 158
4.4.4 最短路径 163
4.5 广义表 167
4.5.1 广义表的定义 167
4.5.2 广义表的存储结构 169
4.5.3 广义表的遍历 170
4.5.4 广义表的运算 172
4.6 本章小结 175
4.7 习题 175
第5章 算法设计策略 179
5.1 算法分析技术 179
5.2 直接法 183
5.2.1 穷举法 183
5.2.2 递推法 184
5.2.3 迭代法 185
5.3 分治法 186
5.3.1 分治法的基本思想 187
5.3.2 斯特拉森矩阵乘法 188
5.4 贪心法 190
5.4.1 贪心法的基本思想 190
5.4.2 背包问题 191
5.5 动态规划法 193
5.5.1 动态规划法的基本思想 193
5.5.2 矩阵连乘问题 196
5.6 回溯法 198
5.6.1 回溯法的基本思想 198
5.6.2 回溯法的形式化描述 199
5.6.3 八皇后问题 200
5.7 分支限界法 202
5.7.1 分支限界法的基本思想 202
5.7.2 货郎担问题 203
5.8 本章小结 206
5.9 习题 206
第6章 查找 209
6.1 顺序表的查找 209
6.1.1 顺序查找 209
6.1.2 二分查找 211
6.2 索引表的查找 212
6.2.1 索引表的基本概念 212
6.2.2 索引表的顺序查找 213
6.2.3 索引表的二分查找 215
6.2.4 索引表的树组织查找 216
6.3 散列表的查找 216
6.3.1 基本概念 216
6.3.2 散列函数 217
6.3.3 冲突处理 218
6.3.4 散列查找与性能分析 220
6.4 本章小结 223
6.5 习题 223
第7章 排序 226
7.1 排序的基本概念 226
7.2 插入排序 227
7.2.1 直接插入排序 227
7.2.2 二分插入排序 228
7.2.3 希尔排序 229
7.3 交换排序 230
7.3.1 冒泡排序 230
7.3.2 快速排序 232
7.4 选择排序 234
7.4.1 简单选择排序 234
7.4.2 树形选择排序 235
7.5 2路归并排序 236
7.6 基数排序 237
7.6.1 多关键字排序 237
7.6.2 链式基数排序 238
7.7 各排序方法的比较 241
7.8 本章小结 241
7.9 习题 242
参考文献 245