《计算机数据结构和实用算法大全》求取 ⇩

第一章引言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-5O和Ω的一些变形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-5Sloppincss条件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-2max程序的分析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-2Lomuto划分算法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-5K-全域杂凑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-2Joscphus排列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

构造一个LCS237

对代码的改进237

练习238

16.4最优多边形三角剖分238

与括号化的对应239

最优三角剖分的子结构241

一个递归解241

练习241

问题242

16-1Bitonic欧几里德货郎担问题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.1B-树的定义288

B-树的高度289

练习290

19.2B-树上的基本操作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-12-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-3Tarjan的脱机最小公共祖先算法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.2Dijkstra算法397

分析399

练习400

25.3Bcllman-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.2Floyd-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.2Ford-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.20-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.2CRCW算法与EREW算法527

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

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

用EREW算法来模拟CRCW算法531

练习533

30.3Brent定理与工作效率533

练习536

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

递归的并行前缀计算537

选择要消除的对象539

分析539

练习541

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

着色与最大独立集542

计算6-着色问题542

根据6-着色计算出MIS545

练习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-1Shamir布尔矩阵乘法算法584

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

31-3.样条585

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

多项式587

本章概述588

32.1多项式的表示588

系数表示法589

点值表示法589

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

练习592

32.2DFT与FFT593

单位元素的复根593

DFT595

FFT595

对单位元素的复根进行插值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运用模运算的FFT606

第三十三章有关数论的算法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.7RSA公开密钥加密系统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.2Rabim-Karp算法650

练习653

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

有限自动机654

串匹配自动机655

计算变迁函数658

练习658

34.4Knuth-Morris-Pratt算法659

关于模式的前缀函数659

运行时间分析662

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

KMP算法的正确性664

练习664

34.5Boyer-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

复杂类NP701

练习702

36.3NP-完全性与可约简性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