第1章 绪论 1
1.1 数据结构的概念 1
1.1.1 辑结构 2
1.1.2 抽象数据类型 4
1.1.3 物理结构 5
1.2 算法的概念和描述 6
1.2.1 算法的概念 6
1.2.2 算法的描述——C语言回顾 7
1.3 算法的时间复杂性和空间复杂性 13
1.3.1 算法的评价 13
1 3.2 算法的时间复杂性 14
1 3.3 分析算法的时间复杂性 15
1 3.4 时间复杂性的大O记法 17
1 3.5 时间复杂性比较 18
1.3.6 算法的空间复杂性 20
1.4 算法设计方法 20
1.4.1 贪婪算法 20
1.4.2 分而治之算法 21
1.4.3 动态规划 24
1.4.4 回溯 26
1.5 小结 31
习题 31
第2章 线性表 34
2.1 线性表的基本概念 34
2.2 顺序表 35
2.2.1 顺序表 35
2.2.2 顺序表的操作 36
2.3 链表 42
2.3.1 单链表 42
2.3.2 单链表的操作 43
2.3.3 链表的变形 49
2.3.4 线性表存储方法的比较 54
2.4 广义表 55
2.4.1 广义表的概念 55
2.4.2 广义表的存储结构 56
2.4.3 广义表的递归算法 56
2.5 小结 58
习题 58
第3章 栈和队列 60
3.1 栈 60
3.1.1 栈的概念 60
3.1.2 顺序栈 61
3.1.3 链接栈 65
3.2 队列 67
3.2.1 队列的概念 67
3.2.2 顺序队列 68
3.2.3 链接队列 71
3.2.4 循环队列 74
3.3 小结 77
习题 78
第4章 数组、矩阵和串 80
4.1 数组的顺序存储 80
4.1.1 一维数组的顺序存储 80
4.1.2 二维数组的顺序存储 81
4.1.3 n维数组的顺序存储 82
4.2 矩阵的压缩存储 83
4.2.1 特殊矩阵的压缩存储 84
4.2.2 稀疏矩阵的压缩存储 85
4.3 串 88
4.3.1 串的基本概念 88
4.3.2 串的存储结构 88
4.3.3 顺序串的基本操作 90
4.3.4 模式匹配 93
4.4 小结 95
习题 95
第5章 树 97
5.1 树和森林 98
5.1.1 树和森林的概念及术语 98
5.1.2 树的存储 101
5.1.3 树的遍历 104
5.2 二叉树 105
5.2.1 二叉树的概念 105
5.2.2 二叉树的基本性质 106
5.2.3 几种特殊的二叉树 108
5.2.4 二叉树的存储方式 110
5.3 二叉树的遍历 113
5.4 树、森林与二叉树的转换 117
5.4.1 树、森林转换为二叉树 117
5.4.2 二叉树还原为树、森林 119
5.5 线索二叉树 120
5.5.1 线索二叉树的概念 120
5.5.2 二叉树的线索化 122
5.5.3 线索二叉树的操作算法 123
5.6 二叉树的应用举例 125
5.6.1 表达式树及其求值 125
5.6.2 哈夫曼树及其应用 126
5.7 小结 134
习题 134
第6章 图 137
6.1 图的基本概念与术语 137
6.1.1 图的概念 137
6.1.2 图的连通性 140
6.1.3 树与生成子树 141
6.1.4 带权图 142
6.2 图的存储结构 143
6.2.1 邻接矩阵 143
6.2.2 邻接表 145
6.3 图的遍历 150
6.3.1 深度优先搜索法 150
6.3.2 广度优先搜索法 152
6.3.3 遍历的简单应用 154
6.4 最短路径问题 159
6.4.1 求一个顶点到其他各顶点的最短路径 160
6.4.2 求每一对顶点之间的最短路径 163
6.5 最小生成树 166
6.5.1 Prim算法 167
6.5.2 Kruskal算法 170
6.6 拓扑排序 170
6.7 小结 174
习题 174
第7章 查找 177
7.1 线性表的查找 178
7.1.1 顺序查找 178
7.1.2 二分查找 179
7.1.3 分块查找 181
7.2 查找树 182
7.2.1 查找树的概念 183
7.2.2 查找树的查找 185
7.2.3 查找树的插入和生成 187
7.2.4 查找树的删除 188
7.3 平衡查找树 192
7.4 B-树 196
7.5 散列表 199
7.5.1 散列函数 200
7.5.2 冲突处理 202
7.5.3 散列表的操作 204
7.5.4 散列方法的性能分析 210
7.6 小结 210
习题 211
第8章 排序 213
8.1 插入排序 214
8.1.1 直接插入排序 214
8.1.2 希尔排序 216
8.2 交换排序 218
8.2.1 冒泡排序 218
8.2.2 快速排序 221
8.3 选择排序 223
8.3.1 直接选择排序 223
8.3.2 堆排序 224
8.4 合并排序 229
8.5 基数排序 233
8.5.1 桶排序 233
8.5.2 多关键字排序 234
8.5.3 基数排序 236
8.6 内排序算法综述 238
8.7 外部排序简介 239
8.8 小结 239
习题 240
模拟试题1 241
模拟试题2 245
模拟试题1参考答案 250
模拟试题2参考答案 253
参考文献 257