计算机数据结构和实用算法大全PDF电子书下载

第一章 引言 1

1.1算法 1

插入排序 1

伪代码的使用约定 3

练习 4

1.2分析算法 4

插入排序算法的分析 5

最坏情况和平均情况分析 6

增长的量级 7

练习 7

1.3设计算法 8

1.3.1分治法 8

1.3.2分治算法分析 10

合并排序算法的分析 10

练习 10

1.4小结 11

练习 12

问题 12

1-1运行时间的比较 12

1-2合并排序中插入排序在短数组上的应用 12

1-3逆序对 13

第一部分 数学基础 14

引言 14

第二章 函数的增长 15

2.1渐近记号 15

Θ-记号 15

O-记号 17

Ω-记号 18

方程中的渐近记号 18

o-记号 19

ω-记号 19

不同函数间的比较 20

练习 21

2.2标准记号体系和通用函数 21

单调性 21

底（Floor）和顶（Ceiling） 21

多项式 22

指数式 22

对数式 23

阶乘 24

多重对数函数 24

斐波那契数 24

练习 25

问题 26

2-1多项式的渐近性态 26

2-2相对渐近增长 26

2-3根据渐近增长率排序 26

2-4渐近记号的性质 27

2-5 O和Ω的一些变形 27

2-6多重函数 27

第三章 求和运算 29

3.1求和公式和性质 29

线性性质 29

算术级数 30

几何级数 30

调和级数 30

积分级数与微分级数 30

套迭级数 31

积 31

练习 31

3.2和式的界 32

数学归纳法 32

对项的限界 33

分解和式 34

积分近似公式 35

练习 36

问题 37

3-1和式的界 37

第四章 递归式 38

4.1替换方法 39

作一个好的猜测 39

一些细微问题 40

避免陷井 40

改变变量 41

练习 41

4.2迭代方法 41

递归树 42

练习 44

4.3主方法 44

主定理 44

主方法的应用 45

练习 45

4.4主定理的证明 46

4.4.1取整数幂时的证明 46

递归树 47

4.4.2底函数和顶函数 50

练习 52

问题 52

4-1递归式的例子 52

4-2找出所缺的整数 53

4-3参数传递的代价 53

4-4进一步的递归式的例子 53

4-5 Sloppincss条件 54

4-6斐波拉契数 54

4-7 VLSI芯片测试 55

第五章 集合、关系、函数、图和树 56

5.1集合 56

练习 59

5.2关系 59

练习 61

5.3函数 61

练习 63

5.4图 63

练习 66

5.5树 67

5.5.1自由树 67

5.5.2有根树和有序树 69

5.5.3二叉树和位置树 69

练习 71

问题 72

5-1图的着色问题 72

5-2友好图 72

5-3二分树 72

第六章 计数和概率 73

6.1计数 73

和规则与积规则 73

串 73

排列 74

组合 74

二项系数 74

二项界 75

练习 76

6.2概率 77

概率公理 77

离散概率分布 78

连续一致概率分布 78

条件概率和独立性 79

贝叶斯定理 80

练习 81

6.3离散随机变量 82

随机变量的期望值 83

方差和标准差 84

练习 84

6.4几何分布与二项分布 85

几何分布 85

二项分布 86

练习 89

6.5二项分布的尾 90

练习 94

6.6概率分析 95

6.6.1生日悖论 95

另一种分析方法 96

6.6.2球与盒子 97

6.6.3序列 98

练习 99

问题 99

6-1球和盒子 99

6-2 max程序的分析 100

6-3雇用问题 100

6-4概率计数 101

第二部分 排序和顺序统计学 102

引言 102

输入数据的结构 102

排序算法 102

顺序统计学 103

第七章堆排序 104

7.1堆 104

练习 105

7.2保持堆的性质 105

练习 106

7.3建堆 106

练习 109

7.4堆排序算法 109

练习 110

7.5优先级队列 111

练习 112

问题 113

7-1由插入而建堆 113

7-2对d叉堆的分析 113

第八章 快速排序 114

8.1对快速排序的描述 114

对数组进行划分 114

练习 116

8.2快速排序的性能 116

最坏情况划分 116

最佳情况划分 117

对称划分 118

关于平均情况的直觉考虑 118

练习 119

8.3快速排序的随机化版本 120

练习 121

8.4快速排序分析 121

8.4.1最坏情况分析 121

8.4.2平均情况分析 122

关于划分过程的分析 122

关于平均情况性态的递归式 123

解递归式 123

上述和式的紧确界 124

练习 124

问题 125

8-1划分的正确性 125

8-2 Lomuto划分算法 125

8-3 Stooge排序 126

8-4快速排序中的堆栈深度 126

8-5“三数取中”划分 127

第九章 线性时间排序 128

9.1排序算法的下界 128

决策树模型 128

最坏情况下界 129

练习 130

9.2计数排序 130

练习 132

9.3基数排序 132

练习 134

9.4桶排序 134

练习 136

问题 136

9-1比较排序的平均情况下界 136

9-2以线性时间做原地置换排序 137

第十章 中位数和顺序统计学 138

10.1最大元素和最小元素 138

同时找最小元素和最大元素 139

练习 139

10.2以线性期望时间做选择 139

练习 141

10.3最坏情况线性时间的选择 141

练习 142

问题 143

10-1已排序的i个最大数 143

10-2带权中位数 143

10-3小型顺序统计 144

第三部分 数据结构 146

引言 146

动态集合的元素 146

动态集合上的操作 146

第三部分纵观 147

第十一章 基本数据结构 148

11.1栈和队列 148

栈 148

队列 149

练习 150

11.2.链表 151

查找链表 152

对链表的插入操作 152

对链表的删除操作 152

哨兵 153

练习 154

11.3指针和对象的实现 155

对象的多重数组表示 155

对象的单数组表示 155

分配和释放对象 156

练习 158

11.4有根树的表示 158

二叉树 158

无界分叉的有根树 159

其他树的表示 160

练习 160

问题 161

11-1表的比较 161

11-2用链表实现可合并性 161

11-3查找一紧凑的排序链表 161

第十二章 杂凑表 163

12.1直接寻址表 163

练习 164

12.2杂凑表 165

通过拉链法来解决碰撞 166

对带拉链杂凑的分析 166

练习 168

12.3杂凑函数 168

好的杂凑函数的特点 169

将关键字解释为实数 169

12.3.1除法杂凑法 169

12.3.2乘法杂凑法 170

12.3.3全域杂凑 171

练习 172

12.4开放地址法 173

线性探查 174

二次探查 175

双重杂凑 176

对开放地址杂凑的分析 176

练习 179

问题 179

12-1最长探查的界 179

12-2查找静态集合 180

12-3拉链法中槽的大小 180

12-4二次探查 180

12-5 K-全域杂凑 181

第十三章 二叉查找树 182

13.1二叉查找树 182

练习 183

13.2查询二叉查找树 184

查找 184

最大元素和最小元素 185

前趋和后继 185

练习 186

13.3插入和删除 187

插入 187

删除 188

练习 189

13.4随机构造的二叉查找树 190

练习 194

问题 194

13-1具有相同关键字的二叉查找树 194

13-2基数树 195

13-3随机构造的二叉查找树中平均节点深度 195

13-4不同的二叉树个数 196

第十四章 红-黑树 197

14.1红-黑树的性质 197

练习 198

14.2旋转 199

练习 200

14.3插入 201

练习 204

14.4删除 204

练习 208

问题 209

14-1持久动态集合 209

14-2红-黑树上的连接操作 210

第十五章 数据结构的扩张 211

15.1动态顺序统计 211

检索具有给定秩的元素 212

确定一个元素的秩 213

对子树规模的维护 213

练习 214

15.2如何扩张数据结构 215

对红-黑树的扩张 216

练习 217

15.3区间树 217

练习 221

问题 222

15-1最大重迭点 222

15-2 Joscphus排列 222

第四部分 高级设计和分析技术 223

引言 223

第十六章 动态程序设计 224

16.1矩阵链乘法 224

计算括号化的重数 225

最优括号化的结构 226

一个递归解 226

计算最优代价 227

构造一个最优解 229

练习 229

16.2动态程序设计基础 230

最优结构 230

重迭子问题 231

记忆化 232

练习 234

16.3最长公共子序列 234

对最长公共子序列进行刻划 234

子问题的递归解 235

计算LCS的长度 236

构造一个LCS 237

对代码的改进 237

练习 238

16.4最优多边形三角剖分 238

与括号化的对应 239

最优三角剖分的子结构 241

一个递归解 241

练习 241

问题 242

16-1 Bitonic欧几里德货郎担问题 242

16-2优美打印 243

16-3编辑距E离 243

16-4 Vitcrbi算法 244

第十七章 贪心算法 245

17.1活动选择问题 245

证明贪心算法的正确性 247

练习 248

17.2贪心策略的基本内容 248

贪心选择性质 249

最优子结构 249

贪心法与动态程序设计 249

练习 250

17.3哈夫曼编码 251

前缀编码 252

构造哈夫曼编码 253

哈夫曼算法的正确性 254

练习 256

17.4贪心法的理论基础 257

17.4.1矩阵胚 257

17.4.2关于加权矩阵胚的贪心算法 258

练习 261

17.5一个任务调度问题 262

练习 264

问题 264

17-1找换硬币 264

17-2无环子图 264

17-3调度问题的变形 265

第十八章 平摊分析 266

18.1聚集方法 266

栈操作 267

二进计数器 268

练习 269

18.2会计方法 270

栈操作 270

二进计数器的增值 271

练习 271

18.3势能方法 271

栈操作 272

二进计数器的增值 273

练习 274

18.4动态表 274

18.4.1表的扩张 275

18.4.2表扩张和收缩 276

练习 281

问题 281

18-1按位反序二进计数器 281

18-2使二叉查找动态化 282

18-3平摊权平衡树 282

第五部分 高级数据结构 284

引言 284

第十九章 B-树 286

辅存上的数据结构 286

19.1 B-树的定义 288

B-树的高度 289

练习 290

19.2 B-树上的基本操作 290

查找B-树 290

创建一棵空B-树 291

B-树中节点的分裂 292

向B-树中插入一关键字 293

练习 296

问题 299

19-1辅存中的栈 299

19-2联结与分裂2-3-4树 299

第二十章 二项堆 301

20.1二项树与二项堆 302

20.1.1二项树 303

20.1.2二项堆 304

二项堆的表示 305

练习 305

20.2二项堆上的操作 306

创建一个新的二项堆 306

寻找最小关键字 306

合并两个二项堆 306

插入一个节点 311

抽取具有最小关键字的节点 312

对一个关键字减值 313

删除一个关键字 313

练习 314

问题 315

20-1 2-3-4堆 315

20-2 采用可合并堆的最小生成树算法 316

第二十一章 斐波那契堆 317

21.1斐波那契堆的结构 318

势函数 319

最大度数 319

21.2可合并堆操作 319

创建一个新的斐波那契堆 320

插入一个节点 320

寻找最小节点 321

合并两个斐波那契堆 321

抽取最小节点 322

练习 326

21.3减小一个关键字与删除一个节点 326

减小一个关键字 326

删除一个节点 329

练习 329

21.4最大度数的界 329

练习 332

问题 332

21-1删除的另一种实现 332

21-2另一些斐波那契堆操作 332

第二十二章 用于分离集合的数据结构 334

22.1分离集合的操作 334

分离集合数据结构的一个应用 335

练习 336

22.2分离集合的链表表示 337

UNION的一个简单实现 337

一种加权合并启发式 337

练习 338

22.3分离集合森林 339

改进运行时间的启发式 339

分离集合森林的伪代码 340

启发式知识对运行时间的影响 341

练习 341

22.4关于带路径压缩的按秩合并的分析 342

Ackerman 数与其逆函数 342

秩的性质 344

时间界的证明 345

练习 348

问题 348

22-1脱机最小值 348

22-2深度确定 349

22-3 Tarjan的脱机最小公共祖先算法 350

第六部分 图的算法 351

引言 351

第二十三章 图的基本算法 352

23.1图的表示 352

练习 354

23.2宽度优先搜索 354

分析 357

最短路径 357

宽度优先树 359

练习 360

23.3深度优先搜索 361

深度优先搜索的性质 363

边的分类 365

练习 366

23.4拓扑排序 367

练习 368

23.5强连通支 369

练习 373

问题 374

23-1通过宽度优先搜索对边进行分类 374

23-2挂接点、桥以及双连通子图 374

23-3欧拉回路 375

第二十四章 最小生成树 376

24.1最小生成树的形成 377

练习 379

24.2Kruskal算法和Prim算法 380

Kruskal算法 381

Prim算法 382

练习 384

问题 385

24-1次最小生成树 385

24-2稀疏图的最小生成树 385

第二十五章 单源最短路径 387

变体 387

负权边 388

最短路径的表示方法 389

本章概述 389

25.1最短路径和松弛技术 390

最短路径的理想基础 390

松弛 391

松弛的性质 392

最短路径树 394

练习 396

25.2 Dijkstra算法 397

分析 399

练习 400

25.3 Bcllman-Ford算法 400

练习 403

25.4有向无回路图中的单源最短路径 403

练习 405

25.5差分约束与最短路径 405

线性规划 406

差分约束系统 406

约束图 407

差分约束系统问题的求解 409

练习 409

问题 410

25-1对Bcllman-Ford算法的Yen氏改进 410

25-2嵌套框 411

25-3套汇问题 411

25-4关于单源最短路径的Gabow定标算法 411

25-5Karp最小平均权回路算法 412

第二十六章 每对结点间的最短路径 414

本章概述 415

26.1最短路径与矩阵乘法 415

最短路径的结构 416

解决每对结点间的最短路径问题的一种递归方法 416

自底向上计算最短路径的权 416

算法运行时间的改进 419

练习 419

26.2 Floyd-Warshall算法 420

最短路径的结构 421

解决每对结点间最短路径问题的一种递归方案 421

自底向上计算最短路径的权 423

建立最短路径 423

有向图的传递闭包 424

练习 425

26.3关于稀疏图的Johnson算法 426

通过重赋权保持最短路径 427

通过重赋权产生非负的权 429

计算每对结点间的最短路径 429

练习 430

26.4解决有向图中路径问题的一般性框架 430

闭半环的定义 430

有向图中路径的计算 431

闭半环的实例 433

关于有向图标示的一个动态规划算法 433

练习 435

问题 435

26-1动态图的传递闭包 435

26-2ε-稠密图中的最短路径 436

26-3作为一个闭半环的最小生成树 436

第二十七章 最大流 437

27.1流网络 437

流网络与流 438

网络流的一个实例 439

多个源和多个汇的网络 441

对流的处理 441

练习 442

27.2 Ford-Fulkcrson方法 443

残留网络 443

增广路径 445

流网络的割 446

基本的Ford-Fulkcrson算法 448

Ford-Fulkcrson算法的分析 449

练习 452

27.3最大偶匹配 452

最大偶匹配问题 453

寻求最大偶匹配 453

练习 455

27.4先流推进算法 455

直觉知识 456

基本的操作 457

一般性算法 458

先流推进方法的正确性 459

先流推进方法的分析 460

练习 463

27.5向前提升算法 463

容许边和容许网络 464

相邻表 465

溢出结点的释放 465

向前提升算法 458

算法分析 470

练习 471

问题 471

27-1逃脱问题 471

27-2最小路径覆盖 472

27-3航天飞机进行的实验 472

27-4最大流的更新 473

27-5用定标法计算最大流 473

27-6具有容量上限和下限的最大流 473

第七部分 论题选编 475

引言 475

第二十八章 排序网络 477

28.1 比较网络 477

练习 480

28.2 0-1原则 480

练习 482

28.3 双调排序网络 483

半清洁器 483

双调排序程序 484

练习 485

28.4 合并网络 485

练习 487

28.5 排序网络 487

练习 488

问题 489

28-1 转置顺序网络 489

28-2 Batcher奇偶合并网络 489

28-3 排列网络 490

第二十九章 运算电路 491

29.1 组合电路 491

组合电路 492

全加器 493

电路深度 494

电路规模 494

练习 495

29.2加法电路 495

29.2.1行波进位加法 495

29.2.2先行进位加法器 496

完成先行进位加法器的构造 496

29.2.3保留进位加法 501

练习 502

29.3乘法电路 504

29.3.1阵列乘法器 504

分析 507

29.3.2华莱士树型乘法器 507

分析 508

练习 509

29.4时钟电路 509

29.4.1位串行加法 509

分析 511

行波进位加法与位串行加法 511

29.4.2线性阵列乘法器 511

一种慢速线性阵列实现方法 513

一种快速的线性阵列实现方法 513

练习 514

问题 515

29-1除法电路 515

29-2关于对称函数的布尔公式 515

第三十章 关于并行计算机的算法 517

PRAM模型 517

并发存储器存取方式与互斥存储器存取方式 518

同步与控制 519

本章概述 519

30.1指针转移 520

30.1.1表排序 520

正确性 521

分析 522

30.1.2列表的并行前缀 522

30.1.3欧拉回路技术 524

练习 526

30.2 CRCW算法与EREW算法 527

并发操作发挥作用的有关问题 527

并发写操作发挥作用的一个问题 529

用EREW算法来模拟CRCW算法 531

练习 533

30.3 Brent定理与工作效率 533

练习 536

30.4工作效率高的并行前缀计算 537

递归的并行前缀计算 537

选择要消除的对象 539

分析 539

练习 541

30.5确定的打破对称性问题 541

着色与最大独立集 542

计算6-着色问题 542

根据6-着色计算出MIS 545

练习 545

问题 546

30-1分段的并行前缀 546

30-2处理器效率的最大值算法 546

30-3连通子图 547

30-4对光栅像进行转置处理 548

第三十一章 关于矩阵的操作 549

31.1矩阵的性质 549

矩阵和向量 549

关于矩阵的操作 552

矩阵的逆矩阵,秩和行列式 553

正定矩阵 555

练习 555

31.2关于矩阵乘法的Strassen算法 556

算法总论 556

确定子矩阵的乘积 557

讨论 560

练习 561

31.3代数系统与布尔矩阵乘法 561

拟环 561

环 562

布尔矩阵的乘法 563

域 564

练习 564

31.4求解线性方程组 565

LUP分解总述 566

正向替换与逆向替换 566

关于LU分解的计算 569

LUP分解的计算 572

练习 575

31.5逆矩阵 575

根据LUP分解来计算逆矩阵 576

矩阵乘法与逆矩阵 576

把求逆矩阵问题转化为矩阵乘法问题 577

练习 578

31.6对称正定矩阵与最小二乘逼近 579

最小二乘逼近 581

练习 584

问题 584

31-1 Shamir布尔矩阵乘法算法 584

31-2三对角线性方程组 585

31-3.样条 585

第三十二章 多项式与快速付里叶变换 587

多项式 587

本章概述 588

32.1多项式的表示 588

系数表示法 589

点值表示法 589

关于系数形式表示的多项式的快速乘法 591

练习 592

32.2 DFT与FFT 593

单位元素的复根 593

DFT 595

FFT 595

对单位元素的复根进行插值 598

练习 599

32.3有效的FFT实现方法 599

FFT的一种迭代实现 600

并行FFT电路 603

练习 604

问题 604

32-1分治乘法 604

32-2Tocplitz矩阵 604

32-3求多项式在某一点的所有阶导数的值 604

32-4多项式在多个点的求值 605

32-5运用模运算的FFT 606

第三十三章 有关数论的算法 607

输入的规模与算术运算的代价 607

33.1基本的数论概念 608

可除性与约数 608

素数与合数 608

除法定理,余数和同模 608

公约数与最大公约数 609

互质数 610

唯一的因子分解 611

练习 611

33.2最大公约数 612

欧几里德算法 613

EUCLID算法的运行时间 613

欧几里德算法的推广形式 615

练习 616

33.3模运算 616

有限群 617

根据模加法与模乘法所定义的群 617

子群 620

由一个元素生成的子群 620

练习 621

33.4求解模线性方程 622

练习 624

33.5中国余数定理 625

练习 627

33.6元素的幂 627

运用反复平方法求数的幂 630

练习 631

33.7 RSA公开密钥加密系统 631

公开密钥加密系统 631

RSA加密系统 632

练习 635

33.8.素数的测试 636

素数的密度 636

伪素数测试过程 637

Miller-Rabin随机性素数测试方法 638

Miller-Rabin素数测试过程的出错率 639

练习 640

33.9整数的因子分解 641

POLLARD的rho启发性方法 641

练习 644

问题 644

33-1二进制的gcd算法 644

33-2欧几里德算法中对位操作的分析 645

33-3关于Fibonacci数的三个算法 645

33-4二次残数 645

第三十四章 串匹配 647

记号与术语 648

34.1朴素的串匹配算法 649

练习 649

34.2 Rabim-Karp算法 650

练习 653

34.3利用有限自动机进行串匹配 654

有限自动机 654

串匹配自动机 655

计算变迁函数 658

练习 658

34.4 Knuth-Morris-Pratt算法 659

关于模式的前缀函数 659

运行时间分析 662

前缀函数计算过程的正确性 662

KMP算法的正确性 664

练习 664

34.5 Boyer-Moore算法 665

坏字符启发性方法 666

好后缀启发性方法 668

练习 670

问题 670

34-1基于重复因子的串匹配算 670

34-2并行串匹配 671

第三十五章计算几何学 672

35.1线段的性质 672

叉积 673

确定连续线段是向左转还是向右转 674

确定两条线段是否相交 674

叉积的其它应用 675

练习 675

35.2确定任意一对线段是否相交 676

排序线段 676

扫除线的移动 677

求线段交点的伪代码 678

正确性 679

运行时间 680

练习 680

35.3寻找凸包 680

Graham扫描法 682

Jarvis步进法 687

练习 688

35.4寻找最近点对 688

分治算法 689

正确性 690

算法实现与运行时间 691

练习 691

问题 692

35-1凸层 692

35-2最大层 692

35-3巨人和鬼 693

35-4稀疏包分布 693

第三十六章NP-完全性 694

36.1多项式时间 695

抽象问题 695

编码 696

形式语言体系 698

练习 699

36.2多项式时间的验证 700

汉密尔顿回路 700

验证算法 701

复杂类NP 701

练习 702

36.3 NP-完全性与可约简性 703

可化简性 703

NP-完全性 705

电路可满足性 705

练习 710

36.4 NP-完全性的证明 710

公式可满足性 711

3-CNF可满足性 713

练习 715

36.5一些NP-完全的问题 716

36.5.1集团问题 716

36.5.2顶点覆盖问题 718

36.5.3子集和问题 720

36.5.4汉密尔顿回路问题 722

36.5.5货郎担问题 726

练习 727

问题 728

36-1独立集 728

36-2图的着色 728

第三十七章 近似算法 730

近似算法的性能界 730

本章内容的安排 731

37.1顶点覆盖问题 731

练习 733

37.2货郎担问题 733

37.2.1带三角不等式的货郎担问题 734

37.2.2一般货郎担问题 736

练习 737

37.3集合覆盖问题 737

一个贪心近似算法 738

分析 739

练习 740

37.4子集和问题 741

一个指数时间算法 741

一个完全多项式时间近似方案 742

练习 744

问题 744

37-1装箱 744

37-2对最大集团规模的近似 745

37-3加权集合覆盖问题 745