现代计算机常用数据结构和算法PDF电子书下载

第一篇基本知识 2

第一章算法概念 2

1.1算法 2

目 录 2

插入排序 3

伪代码的使用约定 4

1.2算法分析 4

插入排序算法的分析 5

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

1.3.1分治法 7

增长的量级 7

1.3算法设计 7

1.3.2分治算法分析 9

合并排序算法的分析 9

1.4小结 10

思考题 10

练习一 11

第二章函数的增长 13

2.1渐近记号 13

Θ－记号 13

O－记号 15

方程中的渐近记号 16

Ω－记号 16

O－记号 17

ω－记号 17

不同函数间的比较 18

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

多项式 19

指数式 19

底（Floor）和顶（Ceiling） 19

单调性 19

对数式 20

阶乘 21

多重对数函数 21

斐波那契数 22

思考题 22

练习二 25

第三章求和运算 26

3.1求和公式和性质 26

线性性质 26

套迭级数 27

积分级数与微分级数 27

算术级数 27

几何级数 27

调和级数 27

积 28

3.2和式的界 28

数学归纳法 28

对项的限界 29

分解和式 30

积分近似公式 32

练习三 33

思考题 33

第四章递归式 35

4.1替换方法 35

作一个好的猜测 36

一些细微问题 37

避免陷井 37

改变变量 37

4.2迭代方法 38

递归树 39

主定理 40

4.3主方法 40

主方法的应用 41

* 4.4主定理的证明 42

4.4.1 取整数幂时的证明 42

递归树 43

4.4.2底函数和顶函数 46

思考题 48

练习四 50

5.1集合 52

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

5.2关系 54

5.3函数 56

5.4图 57

5.5树 60

5.5.1 自由树 60

5.5.2有根树和有序树 62

5.5.3二叉树和位置树 63

思考题 64

练习五 65

串 67

和规则与积规则 67

第六章计数和概率 67

6.1计数 67

排列 68

组合 68

二项系数 68

三项界 69

6.2概率 69

概率公理 70

离散概率分布 70

条件概率和独立性 71

连续一致概率分布 71

贝叶斯定理 72

6.3离散随机变量 73

随机变量的期望值 74

方差和标准差 75

6.4几何分布与二项分布 75

几何分布 76

二项分布 77

6.5二项分布的尾 79

6.6.1生日悖论 83

6.6概率分析 83

另一种分析方法 84

6.6.2球与盒子 85

6.6.3序列 85

思考题 87

练习六 88

第二篇排序和顺序统计学 92

输入数据的结构 92

排序算法 92

顺序统计学 93

7.1堆 94

第七章堆排序 94

7.2保持堆的性质 95

7.3建堆 96

7.4堆排序算法 98

7.5优先级队列 99

思考题 101

练习七 102

第八章快速排序 104

8.1对快速排序的描述 104

对数组进行划分 104

最坏情况划分 106

8.2快速排序的性能 106

最佳情况划分 107

对称划分 107

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

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

8.4快速排序分析 110

8.4.1最坏情况分析 110

8.4.2平均情况分析 111

关于划分过程的分析 111

关于平均情况性态的一个递归式 111

解递归式 112

上述和式的紧确界 113

思考题 113

练习八 115

第九章线性时间排序 117

9.1排序算法的下界 117

决策树模型 117

最坏情况下界 118

9.2计数排序 118

9.3基数排序 120

9.4桶排序 121

思考题 123

练习九 124

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

10.1最大元素和最小元素 126

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

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

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

思考题 130

练习十 131

动态集合上的操作 133

动态集合的元素 133

第三篇数据结构 133

内容综述 134

第十一章基本数据结构 135

11.1栈和队列 135

栈 135

队列 136

11.2链表 137

查找链表 138

对链表的插入操作 138

哨兵 139

对链表的删除操作 139

11.3指针和对象的实现 140

对象的多重数组表示 141

对象的单数组表示 141

分配和释放对象 142

11.4有根树的表示 143

二叉树 143

无界分叉的有根树 144

树的其他表示 145

思考题 145

练习十一 146

第十二章杂凑表 149

12.1直接寻址表 149

12.2杂凑表 150

通过拉链法来解决碰撞 151

对带拉链杂凑的分析 152

12.3杂凑函数 153

好的杂凑函数的特点 153

将关键字解释为实数 153

12.3.1除法杂凑法 154

12.3.2乘法杂凑法 154

12 3.3全域杂凑 155

12.4开放地址法 156

线性探查 158

二次探查 158

双重杂凑 158

对开放地址杂凑的分析 159

思考题 161

练习十二 163

第十三章二叉查找树 165

13.1二叉查找树 165

查找 166

13.2查询二叉查找树 166

最大元素和最小元素 167

前趋和后继 168

13.3插入和删除 169

插入 169

删除 170

* 13.4随机构造的二叉查找树 171

思考题 174

练习十三 177

14.1红－黑树的性质 179

第十四章红－黑树 179

14.2旋转 180

14.3插入 182

14.4删除 185

思考题 188

练习十四 190

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

15.1动态顺序统计 192

检索具有给定秩的元素 193

确定一个元素的秩 193

对子树规模的维护 194

15.2如何扩张数据结构 195

对红－黑树的扩张 196

15.3 区间树 197

思考题 200

练习十五 201

第四篇高级设计和分析技术 204

第十六章 动态程序设计 204

16.1 矩阵链乘法 204

计算括号化的重数 205

一个递归解 206

最优括号化的结构 206

计算最优代价 207

构造最优解 209

16.2 动态程序设计基础 209

最优结构 209

重叠子问题 210

记忆化 211

16.3 最长公共子序列 213

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

计算LCS的长度 214

子问题的递归解 214

构造一个LCS 215

对代码的改进 216

16.4最优多边形三角剖分 216

与括号化的对应 217

最优三角剖分的子结构 219

一个递归解 219

思考题 220

练习十六 220

17.1 活动选择问题 223

第十七章贪心算法 223

证明贪心算法的正确性 225

17.2 贪心策略的基本内容 226

贪心选择性质 226

最优子结构 226

贪心法与动态程序设计 226

17.3哈夫曼编码 228

前缀编码 228

构造哈夫曼编码 230

哈夫曼算法的正确性 231

*17.4贪心法的理论基础 232

17.4.1矩阵胚 233

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

17.5一个任务调度问题 236

思考题 238

练习十七 239

第十八章平摊分析 241

18.1聚集方法 241

栈操作 241

二进计数器 243

栈操作 244

18.2会计方法 244

二进计数器的增值 245

18.3势能方法 246

栈操作 246

二进计数器的增值 247

18.4动态表 248

18.4.1表的扩张 248

18.4.2表扩张和收缩 251

思考题 254

练习十八 256

辅存上的数据结构 259

第五篇高级数据结构 259

第十九章B－树 259

19.1 B－树的定义 261

B－树的高度 262

19.2 B－树上的基本操作 263

查找B－树 263

创建一棵空B－树 264

B－树中节点的分裂 264

向B－树中插入一关键字 265

19.3从B－树中删除一个关键字 268

思考题 270

练习十九 271

第二十章 二项堆 273

20.1二项树与二项堆 274

20.1.1 二项树 274

20.1.2 二项堆 275

二项堆的表示 276

创建一个新的二项堆 277

寻找最小关键字 277

20.2 二项堆上的操作 277

合并两个二项堆 278

插入一个节点 282

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

对一个关键字减值 284

删除一个关键字 284

思考题 285

练习二十 287

第二十一章斐波那契堆 288

21.1斐波那契堆的结构 289

21.2可合并堆操作 290

最大度数 290

势函数 290

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

插入一个节点 291

寻找最小节点 292

合并两个斐波那契堆 292

抽取最小节点 292

21.3减小一个关键字与 296

删除一个节点 296

减小一个关键字 297

21.4最大度数的界 299

删除一个节点 299

思考题 301

练习二十一 302

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

22.1分离集合的操作 303

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

22.2分离集合的链表表示 305

UNION的一个简单实现 305

一种加权合并启发式 306

改进运行时间的启发式 307

22.3分离集合森林 307

分离集合森林的伪代码 308

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

*22.4 关于带路径压缩的 309

按秩合并的分析 309

Ackerman函数与其逆函数 309

秩的性质 311

时间界的证明 312

思考题 315

练习二十二 317

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

第六篇图的算法 319

23.1 图的表示 320

23.2宽度优先搜索 322

分析 324

最短路径 324

宽度优先树 326

23.3深度优先搜索 327

深度优先搜索的性质 330

边的分类 331

23.4拓扑排序 332

23.5强连通支 333

思考题 337

练习二十三 339

第二十四章最小生成树 342

24.1最小生成树的形成 343

24.2 Kruskal算法和Prim算法 345

Kruskal算法 345

Prim算法 347

思考题 349

练习二十四 351

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

单源最短路径问题的变形 352

负权边 353

最短路径的表示方法 353

本章概述 354

25.1最短路径和松弛技术 355

最短路径的理想基础 355

松弛技术 356

松弛的性质 357

最短路径树 358

25.2 Dijkstra算法 360

分析 362

25.3 Bellman-Ford算法 363

25.4有向无回路图中的 366

单源最短路径 366

25.5差分约束与最短路径 367

线性程序设计 367

差分约束系统 368

约束图 369

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

思考题 371

练习二十五 373

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

26.1最短路径与矩阵乘法 378

最短路径的结构 379

解决每对结点间的最短路径问题的 379

一种递归方法 379

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

算法运行时间的改进 381

26.2 Floyd-Warshall算法 382

最短路径的结构 382

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

解决每对结点间最短路径问题的 383

一种递归方案 383

建立最短路径 385

有向图的传递闭包 385

26.3关于稀疏图的Johnson算法 387

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

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

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

的一般性框架 390

闭半环的定义 390

*26.4解决有向图中路径问题 390

有向图中路径的计算 391

闭半环的实例 393

关于有向图标示的一个 394

动态程序设计算法 394

思考题 395

练习二十六 396

第二十七章最大流 399

27.1 流网络 399

流网络与流 399

网络流的一个实例 401

多个源和多个汇的网络 402

对流的处理 403

27.2 Ford-Fulkerson方法 404

残留网络 404

增广路径 406

流网络的割 406

基本的Ford-Fulkerson算法 408

Ford-Fulkerson算法的分析 409

最大二分匹配问题 412

27.3最大二分匹配 412

寻求最大二分匹配 413

27.4先流推进算法 415

直觉知识 415

基本的操作 416

一般性算法 417

先流推进方法的正确性 418

先流推进方法的分析 419

*27.5向前提升算法 421

容许边和容许网络 421

相邻表 422

溢出结点的释放 423

向前提升算法 425

算法分析 427

思考题 428

练习二十七 431

第七篇论题选编 436

第二十八章排序网络 436

28.1比较网络 436

28.2 0-1原则 438

半清洁器 440

28.3双调排序网络 440

双调排序程序 442

28.4合并网络 442

28.5排序网络 444

思考题 445

练习二十八 447

第二十九章算术电路 449

29.1 组合电路 449

组合元件 449

组合电路 450

全加器 451

电路规模 452

电路深度 452

29.2加法电路 453

29.2.1行波进位加法 453

29.2.2先行进位加法器 454

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

29.2.3保留进位加法 459

29.3乘法电路 460

29.3.1阵列乘法器 460

29.3.2华莱士树乘法器 463

分析 463

分析 464

29.4时钟电路 464

29.4.1位串行加法 465

分析 466

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

29.4.2线性阵列乘法器 466

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

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

思考题 469

练习二十九 470

PRAM模型 473

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

并发存储器存取方式与 474

互斥存储器存取方式 474

同步与控制 475

本章概述 475

30.1指针转移 475

30.1.1表排序 476

正确性 477

30.1.2列表的并行前缀 478

分析 478

30.1.3欧拉回路技术 480

30.2 CRCW算法与EREW算法 482

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

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

用EREW算法来模拟CRCW算法 486

30.3 Brent定理与工作效率 488

*30.4高效的并行前缀计算 490

递归的并行前缀计算 490

选择要消除的对象 492

分析 493

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

着色与最大独立集 495

计算6－着色问题 495

根据6－着色计算出 MIS 498

思考题 498

练习三十 501

第三十一章矩阵操作 503

31.1矩阵的性质 503

矩阵和向量 503

关于矩阵的操作 506

逆矩阵，秩和行列式 507

正定矩阵 508

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

算法概述 509

确定子矩阵的乘积 510

讨论 513

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

拟环 513

环 514

域 515

布尔矩阵的乘法 515

31.4求解线性方程组 516

LUP分解总述 517

正向替换与逆向替换 518

关于LU分解的计算 520

LUP分解的计算 523

31.5逆矩阵 526

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

矩阵乘法与逆矩阵 526

矩阵乘法问题 527

把求逆矩阵问题转化为 527

31.6对称正定矩阵与 529

最小二乘逼近 529

最小二乘逼近 530

思考题 533

练习三十一 535

第三十二章多项式与快速傅里叶变换 539

多项式 539

32.1多项式的表示 540

系数表示法 540

本章概述 540

点值表示法 541

关于系数形式表示的多项式 543

的快速乘法 543

32.2 DFT与FFT 544

单位元素的复根 544

DFT 546

FFT 546

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

FFT的一种迭代实现 549

32.3有效的FFT实现方法 549

并行FFT电路 552

思考题 553

练习三十二 556

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

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

33.1基本的数论概念 559

可除性与约数 559

素数与合数 559

除法定理，余数和同模 559

公约数与最大公约数 560

互质数 561

唯一的因子分解 561

33.2最大公约数 562

欧几里德算法 563

EUCLID算法的运行时间 563

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

33.3模运算 565

有限群 565

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

子群 568

由一个元素生成的子群 569

33.4求解模线性方程 570

33.5中国余数定理 572

33.6元素的幂 574

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

33.7 RSA公开密钥加密系统 577

公开密钥加密系统 577

RSA加密系统 579

33.8素数的测试 581

素数的密度 581

伪素数测试过程 582

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

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

*33.9整数的因子分解 587

POLLARD的rho启发性方法 587

思考题 590

练习三十三 592

第三十四章串匹配 595

记号与术语 595

34.1朴素的串匹配算法 596

34.2 Rabin-Karp算法 597

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

有限自动机 601

串匹配自动机 601

计算变迁函数 604

34.4 Knuth-Morris-Pratt算法 605

关于模式的前缀函数 605

运行时间分析 607

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

KMP算法的正确性 609

34.5 Boyer-Moore算法 610

坏字符启发性方法 611

好后缀启发性方法 613

思考题 614

练习三十四 616

第三十五章计算几何学 618

35.1线段的性质 618

叉积 619

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

确定两条线段是否相交 620

叉积的其他应用 621

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

扫除线的移动 622

排序线段 622

求线段交点的伪代码 623

正确性 624

运行时间 625

35.3寻找凸包 625

Graham扫描法 626

Jarvis步进法 631

35.4寻找最近点对 632

分治算法 632

正确性 633

算法实现与运行时间 634

思考题 635

练习三十五 636

第三十六章NP－完全性 639

36.1多项式时间 640

抽象问题 640

编码 641

形式语言体系 642

36.2多项式时间的验证 644

汉密尔顿回路 644

复杂类NP 645

验证算法 645

36.3 NP－完全性与可化简性 646

可化简性 647

NP－完全性 648

电路可满足性 649

36.4 NP－完全性的证明 653

公式可满足性 653

3－CNF可满足性 655

36.5一些NP－完全的问题 658

36.5.1集团问题 658

36.5.2顶点覆盖问题 660

36.5.3子集和问题 661

36.5.4汉密尔顿回路问题 663

36.5.5货郎担问题 668

思考题 669

练习三十六 670

第三十七章近似算法 673

近似算法的性能界 673

本章内容的安排 674

37.1 顶点覆盖问题 674

37.2.1 满足三角不等式的货郎担问题 676

37.2货郎担问题 676

37.2.2一般货郎担问题 678

37.3集合覆盖问题 679

一个贪心近似算法 680

分析 680

37.4子集和问题 682

一个指数时间算法 682

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

思考题 686

练习三十七 686