数据结构 第3版PDF电子书下载

第1章 数学准备 1

1.1 数学归纳法 1

1.2 数、幂与对数 2

1.3 和与积 4

1.4 整数函数和初等数论 7

1.5 排列和阶乘 8

1.6 二项式系数 10

1.7 调和数 13

1.8 斐波那契数 17

小结 21

推荐读物与参考文献 22

习题 22

第2章 绪论 27

2.1 为什么要学习数据结构 27

2.2 数据结构概念 27

2.2.1 数据的逻辑结构 29

2.2.2 数据的存储结构 30

2.2.3 对数据结构的操作 31

2.2.4 数据结构示例 32

2.3 算法 32

2.3.1 算法及其特性 32

2.3.2 算法的描述 33

2.3.3 算法的评价准则 36

2.4 算法的正确性证明 37

2.5 算法分析基础 39

2.5.1 算法时间复杂性的分析方法 39

2.5.2 复杂性函数的渐近表示 42

2.5.3 算法时间与空间分析 44

2.5.4 计算复杂性和算法的效率 45

小结 45

推荐读物与参考文献 47

习题 48

第3章 线性表、堆栈和队列 49

3.1 线性表的定义和基本操作 49

3.2 线性表的顺序存储结构 50

3.3 线性表的链接存储结构 52

3.3.1 单链表 52

3.3.2 循环链表 56

3.3.3 双向链表 57

3.4 复杂性分析 59

3.5 堆栈 59

3.5.1 堆栈的定义和基本操作 60

3.5.2 顺序栈 60

3.5.3 链式栈 61

3.5.4 顺序栈与链式栈的比较 63

3.5.5 堆栈应用——括号匹配 63

3.5.6 堆栈应用——递归 64

3.6 队列 66

3.6.1 队列的定义和基本操作 66

3.6.2 顺序队列 67

3.6.3 链式队列 69

小结 70

推荐读物与参考文献 71

习题 72

第4章 数组和字符串 75

4.1 数组 75

4.1.1 数组的存储和寻址 75

4.1.2 一维数组的基本操作 77

4.2 矩阵 77

4.2.1 矩阵的数组表示 77

4.2.2 特殊矩阵的压缩存储 79

4.2.3 三元组表 80

4.2.4 十字链表 81

4.3 字符串 85

4.3.1 字符串的定义与存储 85

4.3.2 模式匹配算法 86

小结 91

推荐读物与参考文献 91

习题 92

第5章 树与二叉树 94

5.1 树的基本概念 94

5.1.1 树的定义 94

5.1.2 树的相关术语 96

5.1.3 树的表示 98

5.2 二叉树 99

5.2.1 二叉树定义和主要性质 99

5.2.2 二叉树顺序存储 102

5.2.3 二叉树链接存储 103

5.2.4 二叉树遍历 104

5.2.5 二叉树的其他操作 111

5.2.6 表达式树 115

5.3 线索二叉树 118

5.3.1 线索二叉树的概念 118

5.3.2 线索二叉树的操作 120

5.3.3 线索二叉树的进一步说明 127

5.4 压缩与哈夫曼树 131

5.4.1 文件编码 131

5.4.2 扩充二叉树 132

5.4.3 哈夫曼树和哈夫曼编码 133

5.5 树的存储和操作 137

5.5.1 树与二叉树的转换 137

5.5.2 树的存储结构 140

5.5.3 树和森林的遍历 144

5.5.4 树的顺序表示 149

5.6 等价类与并查集 150

5.6.1 等价类 150

5.6.2 并查集的实现 152

5.7 分类与决策树 156

小结 160

推荐读物与参考文献 161

习题 162

第6章 图 164

6.1 图的基本概念 164

6.2 图的存储结构 168

6.2.1 邻接矩阵 168

6.2.2 邻接表 169

6.3 图的遍历算法 170

6.3.1 深度优先遍历 171

6.3.2 广度优先遍历 173

6.4 拓扑排序 175

6.5 关键路径 178

6.6 最短路径问题 183

6.6.1 无权最短路径问题 184

6.6.2 正权最短路径问题 186

6.6.3 每对顶点之间的最短路径 189

6.6.4 满足约束的最短路径 191

6.7 最小支撑树 194

6.7.1 普里姆算法 195

6.7.2 克鲁斯卡尔算法 198

6.8 图的应用 203

6.8.1 可及性及传递闭包算法 203

6.8.2 连通分量 206

6.8.3 图在网络分析和信息检索中的应用 207

小结 210

推荐读物与参考文献 212

习题 213

第7章 排序 217

7.1 排序问题的基本概念 217

7.2 插入排序 219

7.2.1 直接插入排序 219

7.2.2 Shell排序 222

7.3 交换排序 223

7.3.1 冒泡排序 223

7.3.2 快速排序 227

7.4 选择排序 234

7.4.1 直接选择排序 234

7.4.2 堆排序 234

7.5 合并排序 240

7.6 基于关键词比较的排序算法分析 242

7.6.1 平方阶排序算法及改进算法 242

7.6.2 线性对数阶排序算法 243

7.6.3 分治排序的一般方法 244

7.6.4 基于关键词比较的排序算法下界 245

7.7 分布排序 247

7.8 外排序 250

7.8.1 外存储器 250

7.8.2 磁带排序 251

7.8.3 磁盘排序 261

小结 265

推荐读物与参考文献 265

习题 266

第8章 查找 271

8.1 顺序查找 272

8.1.1 无序表的顺序查找 272

8.1.2 有序表的顺序查找 274

8.2 基于关键词比较的查找 274

8.2.1 对半查找 275

8.2.2 一致对半查找 279

8.2.3 斐波那契查找 281

8.2.4 插值查找 285

8.3 二叉查找树 286

8.3.1 基本概念和性质 286

8.3.2 查找、插入和删除 287

8.3.3 平均情况时间分析 291

8.4 最优二叉查找树 292

8.4.1 访问频率 292

8.4.2 最优二叉查找树 292

8.4.3 近似最优树的构造 298

8.5 高度平衡树 301

8.5.1 基本概念和性质 301

8.5.2 查找和插入操作 303

8.5.3 线性表的平衡树表示 307

8.5.4 删除操作 309

8.6 B树 310

8.6.1 多叉树 310

8.6.2 B树 311

8.7 数字查找 315

8.7.1 检索结构查找 315

8.7.2 数字树查找 319

8.8 散列 323

8.8.1 散列函数 324

8.8.2 冲突调节 329

8.8.3 删除 337

小结 338

推荐读物与参考文献 339

习题 340