第1章 绪论 1
1.1 数据结构的发展及其重要地位 1
1.2 数据结构的基本概念和术语 2
1.3 算法分析概述 5
1.3.1 算法分析评价标准 5
1.3.2 算法的复杂度分析 6
1.3.3 时间复杂度的度量 8
1.3.4 渐进时间复杂度 8
1.3.5 时间复杂度的上界和下界 9
1.3.6 算法的空间复杂度 12
1.3.7 非递归算法分析 13
1.3.8 递归算法的数学分析 15
习题1 16
上篇 数据结构 18
第2章 线性表 18
2.1 线性表的定义及操作 18
2.1.1 线性表的定义 18
2.1.2 线性表的基本操作 19
2.1.3 线性表操作举例 20
2.2 线性表的顺序存储及操作实现 22
2.2.1 线性表的顺序存储结构 22
2.2.2 顺序表的操作实现 23
2.3 线性表的链式存储结构及操作实现 26
2.3.1 单链表 26
2.3.2 单链表上的基本操作 28
2.3.3 循环链表 30
2.3.4 双向链表 31
2.4 顺序表和链表的比较 33
习题2 34
第3章 栈和队列 35
3.1 栈 35
3.1.1 栈的概念及操作 35
3.1.2 栈的存储结构及操作实现 35
3.2 栈的应用举例 40
3.3 队列 45
3.3.1 队列的定义和操作 45
3.3.2 队列的存储结构及操作实现 45
3.4 队列的应用举例 51
习题3 53
第4章 串和数组 55
4.1 串的概念和基本操作 55
4.1.1 串的基本概念 55
4.1.2 串的基本操作 55
4.2 串的存储结构 56
4.2.1 串的顺序存储结构 56
4.2.2 串的链式存储结构 58
4.3 串的操作实现 59
4.4 数组 61
4.4.1 数组的定义 61
4.4.2 数组的顺序存储结构 62
4.5 矩阵的压缩存储 63
4.5.1 特殊矩阵的压缩存储 63
4.5.2 稀疏矩阵的压缩存储 65
习题4 71
第5章 二叉树和树 73
5.1 树和森林 73
5.2 二叉树 74
5.2.1 二叉树的定义和基本术语 74
5.2.2 二叉树的基本性质 76
5.2.3 二叉树的存储结构 77
5.3 二叉树与树、森林之间的转换 79
5.3.1 二叉树与树之间的转换 79
5.3.2 二叉树与森林之间的转换 80
5.4 二叉树遍历 81
5.4.1 二叉树的遍历 81
5.4.2 二叉链表的建立 88
5.5 线索二叉树 90
5.5.1 全线索二叉树 90
5.5.2 线索二叉树 92
5.6 树的应用 96
5.6.1 哈夫曼树及其应用 96
5.6.2 二叉排序树 101
习题5 107
第6章 图和广义表 109
6.1 图的定义和基本术语 109
6.2 图的存储结构 110
6.2.1 邻接矩阵 111
6.2.2 邻接表 112
6.3 图的遍历 115
6.3.1 深度优先搜索遍历 115
6.3.2 图的广度优先搜索遍历 117
6.4 生成树 119
6.4.1 生成树 119
6.4.2 最小生成树 119
6.5 最短路径 124
6.5.1 单源最短路径 124
6.5.2 每一对顶点间的最短路径 128
6.6 拓扑排序 130
6.6.1 AOV网 130
6.6.2 拓扑排序 131
6.7 关键路径 135
6.8 广义表 139
6.8 广义表的定义 139
6.8.2 广义表的存储 139
习题6 140
第7章 排序 142
7.1 排序的基本概念 142
7.2 简单的排序方法 143
7.2.1 气泡排序 143
7.2.2 简单选择排序 144
7.2.3 插入排序 146
7.3 先进的排序方法 148
7.3.1 快速排序 148
7.3.2 归并排序 150
7.3.3 堆排序 152
7.4 基数排序 154
7.5 各种内部排序方法的综合比较 158
习题7 159
第8章 查找 161
8.1 静态查找表 161
8.1.1 顺序查找 161
8.1.2 折半查找 162
8.1.3 分块查找 163
8.2 动态查找表 165
8.2.1 二叉平衡树 165
8.2.2 B_树 167
8.3 哈希表及哈希查找 169
8.3.1 哈希表概念 169
8.3.2 哈希函数 170
8.3.3 处理冲突的方法 172
8.3.4 哈希表的查找 174
8.3.5 哈希表的删除 174
习题8 175
第9章 文件 176
9.1 文件的基本概念 176
9.2 顺序文件 178
9.3 索引文件 179
9.4 索引顺序文件 181
9.4.1 ISAM文件 181
9.4.2 VSAM文件 183
9.5 散列文件 185
9.6 多关键字文件 186
9.6.1 多重表文件 186
9.6.2 倒排文件 187
习题9 188
下篇 算法分析 190
第10章 蛮力法 190
10.1 算法概述 190
10.2 货郎担问题 191
10.2.1 问题陈述 191
10.2.2 问题分析及算法设计分析 191
10.2.3 实例分析 192
10.3 0/1背包问题 193
10.3.1 问题陈述 193
10.3.2 问题分析及算法设计分析 193
10.4 狱吏问题 194
10.4.1 问题陈述 194
10.4.2 问题分析和算法设计分析 195
习题10 195
第11章 贪心法 196
11.1 算法概述 196
11.1.1 贪心选择性质 196
11.1.2 最优子结构性质 197
11.1.3 贪心算法的设计步骤 197
11.2 活动安排问题 198
11.2.1 问题陈述 198
11.2.2 问题分析及算法设计分析 198
11.2.3 实例分析 199
11.2.4 最优性分析 200
11.3 背包问题 200
11.3.1 问题陈述 200
11.3.2 问题分析及算法设计分析 201
11.3.3 实例分析 201
11.3.4 最优性分析 202
11.4 集装箱装载问题 203
11.4.1 问题陈述 203
11.4.2 问题分析及算法设计分析 203
11.4.3 最优性分析 204
习题11 204
第12章 分治法 206
12.1 算法概述 206
12.1.1 分治法的设计步骤 206
12.1.2 分治法的算法分析 207
12.2 大整数乘法 208
12.2.1 问题陈述 208
12.2.2 问题分析及算法设计分析 208
12.3 棋盘问题 211
12.3.1 问题陈述 211
12.3.2 问题分析及算法设计分析 212
12.4 循环赛日程表 214
12.4.1 问题陈述 214
12.4.2 问题分析及算法设计分析 214
习题12 216
第13章 动态规划法 218
13.1 算法概述 218
13.1.1 动态规划法的设计步骤 218
13.1.2 动态规划法与贪心法的比较分析 220
13.2 矩阵连乘问题 221
13.2.1 问题陈述 221
13.2.2 问题分析及算法设计分析 221
13.2.3 实例分析 223
13.3 最长公共子序列问题 224
13.3.1 问题陈述 224
13.3.2 问题分析及算法设计分析 225
13.3.3 实例分析 227
13.4 流水作业调度问题 228
13.4.1 问题陈述 228
13.4.2 问题分析及算法设计分析 228
13.4.3 实例分析 231
习题13 231
第14章 回溯法 234
14.1 算法概述 234
14.1.1 问题的解空间 234
14.1.2 回溯法的设计步骤 235
14.2 n后问题 237
14.2.1 问题陈述 237
14.2.2 问题分析及算法设计分析 237
14.3 图的m—着色问题 239
14.3.1 问题陈述 239
14.3.2 问题分析及算法设计分析 240
习题14 242
第15章 计算复杂性理论 244
15.1 计算复杂性概述 244
15.1.1 易解问题和难解问题 244
15.1.2 不可解问题与停机问题 245
15.2 P类与NP类问题 245
15.2.1 确定性算法和非确定性算法 245
15.2.2 P类问题和NP类问题 246
15.3 NP完全问题 247
15.3.1 多项式归约 247
15.3.2 NP完全性 248
15.3.3 Cook定理 249
15.3.4 NP完全性证明 249
习题15 250
第16章 分布式算法 251
16.1 分布式系统 251
16.1.1 分布式系统概述 251
16.1.2 分布式计算 252
16.1.3 分布式系统特点 252
16.1.4 分布式系统的体系结构 253
16.2 同步技术 255
16.2.1 同步机构 255
16.2.2 物理时钟 255
16.2.3 逻辑时钟 256
16.3 容错技术 258
16.3.1 容错性概述 258
16.3.2 故障检测和诊断 258
16.3.3 故障屏蔽 259
16.3.4 故障恢复 259
16.4 分布式调度 260
16.4.1 调度算法概述 260
16.4.2 静态调度 261
16.4.3 动态调度 262
习题16 263
参考文献 265