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

第1章 数据结构概论 1

1.1数据与结构 1

1.1.1数据的演进 1

1.1.2数据与结构 2

1.2数据结构及算法 3

1.2.1数据结构 3

1.2.2算法 4

【重点整理】 5

【学习自测】 6

第2章 数组 7

2.1什么是数组 7

2.1.1数组概论 7

2.1.2数组结构 8

2.2数组类型和计量 10

2.2.1一维数组 10

2.2.2 二维数组 12

2.2.3三维数组 15

2.2.4对角线数组 16

2.2.5上下三角形数组 17

2.2.6三对角线数组 18

2.2.7方形带状数组 19

2.3数组的遍历 20

2.3.1一维数组遍历 20

2.3.2二维数组的遍历 25

2.4矩阵运算 30

2.4.1概述 30

2.4.2矩阵的加减法 30

2.4.3矩阵乘法 32

2.4.4矩阵的转置 34

【重点整理】 36

【学习自测】 36

3.1.1概述 39

3.1 算法概述 39

第3章 算法 39

3.1.2算法的描述方法 40

3.2算法的效率分析 42

3.2.1概述 42

3.2.2统计分析执行次数 43

3.3渐进式表示法 44

3.3.1时间复杂度等级分类 44

3.3.2 O表示法 50

3.3.3 Ω表示法 51

3.4.4 Θ表示法 52

【重点整理】 53

【学习自测】 54

第4章 数组结构的算法应用 57

4.1 多项式的运算 57

4.1.1基本数组表示法 57

4.1.2推演关系式 58

4.1.3压缩数组表示法 60

4.1.4两个变量的多项式 62

4.1.5多项式相加 64

4.2捉大头抽签游戏 70

4.2.1概述 70

4.2.2对应原理和结构设计 71

4.2.3算法和程序设计 74

4.3魔术方块 76

4.3.1概述和方法 76

4.3.2算法和程序 78

4.4对奖算法与数据结构 80

4.4.1概述和结构设计 80

4.4.2第2个算法 82

4.4.3第3个算法 83

4.4.4第4个算法 85

4.4.5问卷调查与计算机阅卷 86

【重点整理】 87

【学习自测】 88

5.1查找算法概述 91

5.1.1定义和分类 91

5.1.2查找算法比较 91

第5章 查找算法 91

5.2线性查找法 92

5.2.1想法和结构 92

5.2.2算法和程序 93

5.3二分查找法 95

5.3.1想法和结构 95

5.3.2算法和程序 96

5.4插补查找法 98

5.4.1方法 98

5.4.2插补查找法算法 100

【重点整理】 103

【学习自测】 103

6.1.1定义和分类 105

第6章 排序算法 105

6.1排序算法概述 105

6.1.2排序算法比较 106

6.2冒泡排序法 107

6.2.1想法和结构 107

6.2.2算法和程序设计 108

6.3交换排序法 111

6.3.1想法和结构 111

6.3.2算法 112

6.4选择排序法 114

6.4.1想法和结构 114

6.4.2算法 115

6.5插入排序法 117

6.5.1想法和结构 117

6.5.2算法 118

6.6.1想法和结构 120

6.6谢尔排序法 120

6.6.2算法 122

6.7基数排序法 125

6.7.1想法和结构 125

6.7.2算法 126

6.8快速排序法 131

6.8.1想法和结构 131

6.8.2算法 134

6.9归并排序法 137

6.9.1想法和结构 137

6.9.2算法 139

【重点整理】 142

【学习自测】 143

第7章 堆栈 147

7.1堆栈概述 147

7.1.1堆栈的意义 147

7.1.2堆栈的应用 148

7.2堆栈的数据结构和操作 150

7.2.1数据结构 150

7.2.2操作堆栈 151

7.3表达式的应用 153

7.3.1算术表达式和中序表示法 153

7.3.2后缀表示法 155

7.3.3前缀表示法 162

7.4.1后缀表示法求值 167

7.4后缀表示法求值或转换机器码 167

7.4.2后缀表示法转换机器码 171

【重点整理】 172

【学习自测】 173

第8章 队列 176

8.1 队列概述 176

8.1.1队列的定义 176

8.1.2队列的应用 177

8.2.2操作队列 178

8.2.1数据结构 178

8.2队列的数据结构和操作 178

8.3循环队列 183

8.3.1循环队列结构 183

8.3.2循环队列算法 184

8.4双向队列和特殊队列 188

8.4.1特殊队列 188

8.4.2双向队列 189

【重点整理】 190

【学习自测】 191

第9章 链表 193

9.1链表概述 193

9.1.1列表的定义 193

9.1.2列表的应用 193

9.1.3链表 194

9.1.4链表的应用 196

9.2.2寻找节点 197

9.2单一链表以数组表示 197

9.2.1 结构 197

9.2.3新增节点 198

9.2.4删除节点 201

9.2.5反转 203

9.3 以数组表示双向链表 211

9.3.1双向链表结构 211

9.3.2双向链表寻找节点 212

9.3.3双向链表新增节点 213

9.3.4双向链表删除节点 215

9.4用指针和结构表示链表 222

9.4.1概述 222

9.4.2指针与结构 222

9.5链表应用在其他结构 230

9.5.1链接堆栈 230

9.5.2链接队列 234

【重点整理】 239

【学习自测】 240

第10章 递归 242

10.1递归关系 242

10.1.1递归与循环 242

10.1.2解析程序系统处理递归函数 245

10.1.3为什么使用递归 246

10.2数学问题 246

10.2.1常见的数学递归公式 246

10.2.2费波纳茨数列 247

10.2.3二项式系数 250

10.2.4最小公因子 252

10.3河内塔问题 255

10.3.1问题概述及模拟 255

10.3.2算法分析 258

10.4迷宫问题 258

【重点整理】 266

【学习自测】 267

第11章 树 270

11.1树型结构和特性 270

11.1.1 结构 270

11.1.2特性和计算公式 271

11.2二叉树 273

11.2.1 二叉树的定义和结构 273

11.2.2满二叉树 276

11.2.3完全二叉树 277

11.3二叉树的数据结构 278

11.3.1二叉树的编号系统 278

11.3.2用数组表示二叉树 281

11.3.3以结构数组表示二叉树 284

11.3.4以链表表示二叉树 287

11.4二叉树的遍历 289

11.4.1前序遍历 290

11.4.2 中序遍历 292

11.4.3后序遍历 294

11.4.4按层遍历 296

11.4.5利用中序、前序法或中序、后序法求二叉树 297

11.5二叉运算树 303

11.5.1 结构 303

11.5.2建立二叉运算树 304

11.6堆 308

11.6.1堆的结构 308

11.6.2堆的操作 310

11.6.3堆树的应用——优先队列 313

11.6.4堆排序法 314

11.7二叉查找树 320

11.7.1定义与结构 320

11.7.2二叉查找树的特性 321

11.7.3二叉查找树的查找 322

11.7.4二叉查找树与二叉树、堆、二分查找法的比较 323

11.7.6建立二叉查找树与新增数据 324

11.7.5二叉查找树应用于排序 324

11.7.7删除二叉查找树的节点 328

【重点整理】 331

【学习自测】 332

第12章 图 336

12.1 图型结构 336

12.1.1基本结构 336

12.1.2 延伸结构和特性 337

12.1.3带权图 341

12.2图的数据结构 341

12.2.1邻接矩阵表示法 341

12.2.2邻接表表示法 343

12.3 图的遍历 344

12.3.1深度优先搜索遍历 344

12.3.2 广度优先搜索 345

12.3.3 DFS与BFS的比较与应用 347

12.4.1生成树结构 348

12.4 生成树和最小成本生成树 348

12.4.2最小成本生成树结构 349

12.4.3 Kruskal算法 350

12.4.4 Prim算法 352

12.5最短路径 354

12.5.1 出发点最短路径问题 354

12.5.2每对顶点最短路径问题 358

12.6拓扑排序 360

12.6.1定义与特性 360

12.6.2算法 362

【重点整理】 364

【学习自测】 365

第13章 散列 369

13.1 散列概述 369

13.1.1数学应用 369

13.1.2代数转换 369

13.1.3散列 370

13.2散列应用与散列函数 372

13.2.1 散列应用 372

13.2.2除留余数法 373

13.2.3 平方取中法 374

13.2.4折叠法 375

13.2.5抽取法 375

13.2.6乘法 375

13.2.8数字分析法 376

13.2.7基数法 376

13.3溢出处理 378

13.3.1线性探测法 378

13.3.2平方探测法 379

13.3.3再散列法 380

13.3.4链表法 381

13.4散列查找法 381

【重点整理】 385

【学习自测】 386