数据结构与算法PDF电子书下载

编者的话 1

前言 1

第1章　数据结构和算法概述 1

1.1　数据结构 1

1.1.1　数据结构的逻辑结构 1

目录 1

1.1.2　数据结构的物理结构 3

1.1.3　抽象数据类型 4

1.2.1　算法的概念 5

1.2　算法 5

1.2.2　算法的评价 6

1.3　算法的时间复杂性和空间复杂性分析 7

1.3.1　时间复杂性分析概述 8

1.3.2　关键操作计数和执行步数计数 8

1.3.3　最好、最坏和平均情况 10

1.3.4　渐近分析 11

1.3.5　空间复杂性分析 16

1.4　习题 18

2.1　线性表的基本概念 20

第2章　线性表 20

2.2　顺序表 22

2.2.1　线性表的顺序存储 22

2.2.2　顺序表的操作算法 22

2.3　链表 26

2.3.1　线性表的链接存储 26

2.3.2　链表的操作算法 27

2.3.3　链表的变形 30

2.3.4　线性表实现方法的比较 34

2.4.1　一元多项式的表示和相加算法 35

2.4　线性表的应用 35

2.4.2　归并排序算法 39

2.5　广义表 41

2.5.1　广义表的概念 41

2.5.2　广义表的存储结构 42

2.5.3　广义表的递归算法 43

2.6　习题 43

第3章　栈和队列 45

3.1　栈 45

3.1.1　栈的概念 45

3.1.2　顺序栈 46

3.1.3　链接栈 48

3.2　栈的应用 49

3.2.1　数制转换 49

3.2.2　算术表达式求值 50

3.3　队列 56

3.3.1　队列的概念 56

3.3.2　链接队列 57

3.3.3　顺序（循环）队列 58

3.4.1　桶排序 63

3.4　队列的应用 63

3.4.2　多关键字排序 65

3.4.3　基数排序 66

3.5　双向队列 68

3.6　习题 69

第4章　数组、矩阵和串 71

4.1　数组的顺序存储 71

4.1.1　二维数组的顺序存储结构 72

4.1.2　n维数组的顺序存储结构 73

4.2.1　特殊矩阵的压缩存储 74

4.2　矩阵的压缩存储 74

4.2.2　稀疏矩阵的压缩存储和操作 76

4.3 串 80

4.3.1　串的基本概念 81

4.3.2　串的存储结构 81

4.3.3　顺序串的基本操作算法 82

4.3.4　模式匹配 84

4.4　习题 88

第5章　树 89

5.1.1　树和森林的概念和术语 90

5.1　树和森林 90

5.1.2　树的存储结构 93

5.1.3　树和森林的遍历 95

5.2　二叉树 98

5.2.1　二叉树的概念 98

5.2.2　二叉树的抽象数据类型 99

5.2.3　二叉树的基本性质 100

5.2.4　几种特殊的二叉树 101

5.2.5　二叉树的存储结构 103

5.3　二叉树的遍历 105

5.4　树、森林与二叉树的转换 108

5.4.1　树、森林转换为二叉树 109

5.4.2　二叉树还原为树、森林 111

5.5　线索二叉树 112

5.5.1　线索二叉树的概念 112

5.5.2　二叉树的线索化 113

5.5.3　线索二叉树的操作 114

5.6　二叉树的应用 115

5.6.1　表达式树及其求值 115

5.6.2　堆和堆排序 117

5.6.3　哈夫曼树及其应用 121

5.7　习题 128

第6章　图 131

6.1　图的数学基础 131

6.1.1　图的基本概念和术语 131

6.1.2　图的抽象数据类型 135

6.2　图的存储结构 136

6.2.1　邻接矩阵 136

6.2.2　邻接表 138

6.3　图的遍历 140

6.3.1　深度优先搜索法 140

6.3.2　广度优先搜索法 142

6.3.3　遍历的简单应用 144

6.4　最短路径问题 148

6.5　最小生成树 152

6.6　习题 156

第7章　查找 160

7.1　线性表的查找 161

7.1.1　顺序查找 161

7.1.2　二分查找 162

7.1.3　分块查找 164

7.2.1　查找树的概念 165

7.2　查找树 165

7.2.2　查找树的查找 166

7.2.3　查找树的插入和生成 168

7.2.4　查找树的删除 169

7.3　平衡查找树 171

7.4 B-树 178

7.4.1 B-树的查找 179

7.4.2 B-树的插入 180

7.4.3 B-树的删除 182

7.4.4 B＋树 183

7.5　散列表 185

7.5.1　散列函数 186

7.5.2　冲突处理 188

7.5.3　散列方法的性能分析 194

7.6　习题 194

第8章　算法设计方法 196

8.1　贪婪算法 196

8.1.1　直接选择排序和冒泡排序 196

8.1.2 AOV-网络和拓扑排序 200

8.1.3 0/1背包问题 202

8.2.1　快速排序 204

8.2　分而治之算法 204

8.2.2　排序算法综述 206

8.3　动态规划 207

8.3.1　斐波那契数 208

8.3.2　顶点对的最短路径 209

8.3.3　关键路径 211

8.4 回溯 215

8.4.1　皇后问题 216

8.4.2　迷宫问题 219

8.5　分枝定界 221

8.5.1　再论0/1背包问题 222

8.5.2　旅行商问题 225

8.6　随机算法 227

8.6.1　随机数的产生 228

8.6.2　蒙特卡罗积分 228

8.7　习题 229

第9章　算法的限制 232

9.1　更快的计算机与更快的算法 233

9.2　归约 234

9.3　排序问题的时间复杂性下限 235

9.4　难解问题 237

9.4.1　NP完全性理论 237

9.4.2　非确定性计算机 238

9.4.3　NP完全问题的归约证明 239

9.4.4　处理NP难的问题 239

9.5　不可解问题 240

9.5.1　不可解问题的存在性 240

9.5.2　停机问题的不可解性 241

9.6　习题 242

参考文献 243