《现代计算机常用数据结构和算法》求取 ⇩

第一篇基本知识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

构造一个LCS215

对代码的改进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－着色计算出 MIS498

思考题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与FFT544

单位元素的复根544

DFT546

FFT546

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

复杂类NP645

验证算法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