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

第1章　绪论 1

1.1　什么是数据结构 1

1.2　基本概念和术语 3

1.3　数据结构的发展及其重要地位 9

1.4　算法的描述和算法分析 10

1.4.1　算法的描述 10

1.4.2　算法设计的要求 12

1.4.3　算法效率的度量 13

1.4.4　算法的存储空间需求 15

1.5　典型例题 15

习题1 18

第2章　线性表 19

2.1　线性表的逻辑结构 19

2.1.1　线性表的定义 19

2.1.2　线性表的基本操作 19

2.2　线性表的顺序存储及运算实现 20

2.2.1　顺序表 20

2.2.2　顺序表上基本运算的实现 21

2.2.3　顺序表应用举例 24

2.3　线性表的链式存储和运算实现 26

2.3.1　单链表 27

2.3.2　单链表上基本运算的实现 28

2.3.3　循环链表 34

2.3.4　双向链表 34

2.3.5　静态链表 36

2.3.6　单链表应用举例 37

2.4　顺序表和链表的比较 39

2.5　典型例题 40

习题2 52

第3章　栈和队列 54

3.1　栈 54

3.1.1　栈的定义及基本运算 54

3.1.2　栈的存储实现和运算实现 54

3.2　栈的应用举例 57

3.3 队列 66

3.3.1 队列的定义及基本运算 66

3.3.2　队列的存储实现及运算实现 66

3.4　队列应用举例 72

3.5　典型例题 74

习题3 81

第4章　串 82

4.1　串的概念和基本运算 82

4.1.1　串的基本概念 82

4.1.2　串的基本运算 82

4.2　串的存储结构 83

4.2.1　串的静态存储结构 83

4.2.2　串的动态存储结构 86

4.3　字符串的模式匹配 91

4.3.1　Brute-Force算法 91

4.3.2　KMP算法 93

4.4　串应用—文本编辑软件 97

4.5　典型例题 103

习题4 109

第5章　递归 110

5.1　递归的概念 110

5.2　用C语言实现递归 112

5.3　递归算法的设计 115

5.4　递归模拟 117

5.4.1　递归的实现机制 117

5.4.2　用非递归算法模拟递归算法 117

习题5 123

第6章　数组、特殊矩阵和广义表 125

6.1　数组的定义及运算 125

6.1.1　数组的定义 125

6.1.2　数组的基本操作 126

6.2　数组的存储结构 126

6.3　矩阵的压缩存储 127

6.3.1　特殊矩阵的压缩存储 127

6.3.2　稀疏矩阵的压缩存储 129

6.4　广义表 134

6.4.1　广义表的定义和基本运算 134

6.4.2　广义表的存储 136

6.5　典型例题 138

习题6 140

第7章　树形结构 142

7.1　树的概念 142

7.1.1　树的定义 142

7.1.2　树的表示方法 143

7.1.3　树的基本术语 144

7.1.4　树的存储结构 144

7.1.5　树的遍历 148

7.2　二叉树 148

7.2.1　二叉树的基本概念 148

7.2.2　二叉树的性质 149

7.3　二叉树的存储结构 151

7.3.1　顺序存储结构 151

7.3.2　链式存储结构 152

7.4　二叉树的遍历 153

7.4.1　二叉树遍历的定义 153

7.4.2　二叉树遍历的递归实现 153

7.4.3　二叉树遍历的非递归实现 155

7.5　二叉树其他运算的实现 158

7.6　线索二叉树 160

7.6.1　线索二叉树的定义 160

7.6.2　中序线索二叉树的存储结构及其实现 161

7.7　树、森林和二叉树的转换 163

7.7.1　树、森林到二叉树的转换 163

7.7.2　二叉树到树、森林的转换 164

7.8　树的应用 165

7.8.1　哈夫曼树及其应用 165

7.8.2　判定树 169

7.9　典型例题 170

习题7 178

第8章　图 180

8.1　图的基本概念 180

8.2　图的存储结构 183

8.2.1　邻接矩阵 183

8.2.2　邻接表 186

8.2.3　十字链表 192

8.2.4　邻接多重表 193

8.3　图的遍历 194

8.3.1　深度优先搜索的遍历方法 194

8.3.2　广度优先搜索的遍历方法 196

8.4　最小生成树 197

8.4.1　最小生成树的基本概念 197

8.4.2　prim算法构造最小生成树 198

8.4.3　Kruskal算法构造最小生成树 200

8.5　最短路径问题 202

8.5.1　单源最短路径 203

8.5.2　每对顶点之间的最短路径 206

8.6　拓扑排序 208

8.7　关键路径问题 211

8.8　典型例题 215

习题8 228

第9章　查找 230

9.1　静态查找表 230

9.1.1　顺序查找 230

9.1.2　二分法查找 231

9.1.3　分块查找 235

9.2　树表的动态查找 236

9.2.1　二叉排序树 236

9.2.2　平衡二叉树 242

9.2.3　B－树 248

9.2.4　B＋树 254

9.3　哈希表与哈希表的查找 254

9.3.1　哈希表的概念 254

9.3.2　构造哈希函数的方法 255

9.3.3　哈希冲突的解决方法 258

9.3.4　哈希表的查找 260

9.3.5　哈希表查找效率分析 261

9.4　典型例题 262

习题9 275

第10章　排序 276

10.1　排序的基本概念 276

10.2　排序方法分类 276

10.3　插入排序 277

10.3.1　直接插入排序 277

10.3.2　Shell排序 279

10.4　选择排序 280

10.4.1　直接选择排序 281

10.4.2　堆排序 282

10.5　交换排序 286

10.5.1　冒泡排序 286

10.5.2　快速排序 287

10.6　归并排序 290

10.7　基数排序 293

10.7.1　多关键字排序 293

10.7.2　链式基数排序 294

10.8　各种内排序算法的比较 297

10.9　外排序 297

10.9.1　外部排序的方法 297

10.9.2　多路平衡归并的实现 299

10.10　典型例题 302

习题10 315

第11章　文件 317

11.1　文件的基本概念 317

11.2　顺序文件 319

11.3　索引文件 320

11.4　索引顺序文件 322

11.4.1　ISAM文件 322

11.4.2　VSAM文件 324

11.5　散列文件 326

11.5.1　多重表文件 327

11.5.2　倒排文件 328

习题11 328

参考文献 330