算法基础：Python和C#语言实现（原书第2版）

图书标准信息

• 作者 罗德·斯蒂芬斯（Rod Stephens）
• 出版社 机械工业出版社
• 出版时间 2021-01
• 版次 1
• ISBN 9787111671855
• 定价 119.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 424页
• 字数 390千字

【内容简介】

本书第2版进行了全面修订与更新，更加易于学习。书中描述了那些重要且经典的算法，并且说明了不同算法的适用情境。跟随作者的讲解，读者将学会分析既有算法，进而理解算法背后的原理。同时，读者也将学习创建新的算法，以适应未来的新需求。这些有用的算法包括：操作常用数据结构的方法，高级数据结构，网络算法，以及数值算法。此外，书中还包含通用的问题求解技巧。除了描述算法，作者还详细介绍了如何分析算法的性能。书中提供大量练习，读者可以自己探索修改算法的方法，以便将其应用于新的情境。

【作者简介】

---作者简介---

罗德·斯蒂芬斯（Rod Stephens） 连续15年被评为Microsoft Visual Basic最有价值专家（MVP），长期在ITT Technical Institute教授编程入门课程。他已经撰写了超过30本技术书籍，这些书被翻译成多种语言在世界范围内出版。他还撰写了超过250篇杂志文章，内容涵盖C#、Visual Basic、Delphi和Java等。

---译者简介---

余青松 华东师范大学高级工程师。1990年毕业于华东师范大学并留校任教。编著计算机相关教材30余本，在国内外学术期刊和学术会议上发表科技论文近百篇。

江红 华东师范大学副教授，博士。1994年毕业于复旦大学计算机系。曾荣获上海市教学成果一等奖、华东师范大学教学成果一等奖、华东师范大学优秀任课教师奖等荣誉。

【目录】

出版者的话

译者序

前言

作者简介

第1章　算法基础  1

1.1　方法  1

1.2　算法和数据结构  2

1.3　伪代码  2

1.4　算法的特点  4

1.4.1　大O符号  5

1.4.2　常用的运行时间函数  7

1.4.3　运行时间函数的可视化比较  11

1.5　实际考虑  12

1.6　本章小结  13

1.7　练习题  14

第2章　数值算法  16

2.1　数据随机化  16

2.1.1　随机数生成器  16

2.1.2　随机化数组  20

2.1.3　生成非均匀分布  21

2.1.4　随机行走  22

2.2　查找最大公约数  25

2.2.1　计算最大公约数  25

2.2.2　最大公约数算法的扩展应用  27

2.3　计算乘幂  28

2.4　处理素数  29

2.4.1　查找素数因子  29

2.4.2　查找素数  31

2.4.3　素性检验  32

2.5　计算数值积分  33

2.5.1　矩形法则  34

2.5.2　梯形法则  34

2.5.3　自适应积分算法  35

2.5.4　蒙特卡罗积分法  37

2.6　方程求解  38

2.7　高斯消元法  40

2.7.1　前向消元  40

2.7.2　后向代换  41

2.7.3　算法实现  42

2.8　最小二乘法拟合  42

2.8.1　线性最小二乘法  43

2.8.2　多项式最小二乘法  44

2.9　本章小结  45

2.10　练习题  46

第3章　链表  48

3.1　基本概念  48

3.2　单向链表  49

3.2.1　遍历链表  49

3.2.2　查找节点  49

3.2.3　使用哨兵  50

3.2.4　在顶部添加节点  51

3.2.5　在尾部添加节点  51

3.2.6　在指定节点后插入节点  52

3.2.7　删除节点  52

3.3　双向链表  53

3.4　有序链表  54

3.5　自组织链表  55

3.5.1　前移方法  56

3.5.2　交换方法  56

3.5.3　计数方法  56

3.5.4　混合方法  56

3.5.5　伪代码  57

3.6　链表算法  57

3.6.1　复制链表  58

3.6.2　插入排序  58

3.6.3　选择排序  60

3.7　多线链表  61

3.8　循环链表  61

3.8.1　标记节点  62

3.8.2　使用哈希表  63

3.8.3　链表回溯  64

3.8.4　链表反转  65

3.8.5　龟兔赛跑算法  66

3.8.6　双向链表中的环路  68

3.9　本章小结  68

3.10　练习题  68

第4章　数组  70

4.1　基本概念  70

4.2　一维数组  72

4.2.1　查找数组元素  72

4.2.2　查找最大值、最小值和平均值  72

4.2.3　查找中值  73

4.2.4　查找众数  74

4.2.5　插入数组元素  76

4.2.6　删除数组元素  77

4.3　非零数组下界  77

4.3.1　二维数组  78

4.3.2　高维数组  78

4.4　三角形数组  81

4.5　稀疏数组  83

4.5.1　查找行或列  84

4.5.2　获取元素的值  85

4.5.3　设置元素的值  86

4.5.4　删除数组元素  87

4.6　矩阵  89

4.7　本章小结  91

4.8　练习题  91

第5章　堆栈和队列  93

5.1　堆栈  93

5.1.1　链表堆栈  94

5.1.2　数组堆栈  95

5.1.3　双堆栈  96

5.1.4　堆栈算法  97

5.2　队列  101

5.2.1　链表队列  101

5.2.2　数组队列  102

5.2.3　特殊队列  104

5.3　二项堆  105

5.3.1　二项树的定义  105

5.3.2　二项堆的定义  106

5.3.3　合并树  107

5.3.4　合并堆  108

5.3.5　入队操作  111

5.3.6　出队操作  111

5.3.7　运行时间分析  112

5.4　本章小结  113

5.5　练习题  113

第6章　排序  115

6.1　O(N 2)算法  115

6.1.1　数组的插入排序算法  115

6.1.2　数组的选择排序算法  116

6.1.3　冒泡排序算法  117

6.2　O(NlogN)算法  119

6.2.1　堆排序算法  120

6.2.2　快速排序算法  124

6.2.3　合并排序算法  130

6.3　小于O(NlogN)的算法  132

6.3.1　计数排序算法  132

6.3.2　鸽巢排序算法  133

6.3.3　桶排序算法  135

6.4　本章小结  136

6.5　练习题  137

第7章　查找  139

7.1　线性查找算法  139

7.2　二分查找算法  140

7.3　插值查找算法  141

7.4　多数投票算法  142

7.5　本章小结  143

7.6　练习题  144

第8章　哈希表  145

8.1　哈希表的基本概念  145

8.2　链接哈希表  146

8.3　开放寻址哈希表  147

8.3.1　删除数据项  148

8.3.2　线性探测  149

8.3.3　二次探测  150

8.3.4　伪随机探测  151

8.3.5　双重哈希  151

8.3.6　有序哈希  152

8.4　本章小结  154

8.5　练习题  154

第9章　递归  156

9.1　基本算法  156

9.1.1　阶乘  156

9.1.2　斐波那契数  158

9.1.3　棒料切割问题  159

9.1.4　汉诺塔  161

9.2　图形算法  163

9.2.1　科赫曲线  163

9.2.2　希尔伯特曲线  165

9.2.3　谢尔宾斯基曲线  166

9.2.4　垫圈图案  168

9.2.5　天际线问题  168

9.3　回溯算法  172

9.3.1　八皇后问题  173

9.3.2　骑士巡游问题  175

9.4　组合与排列  177

9.4.1　基于循环的组合  178

9.4.2　允许重复项的组合  179

9.4.3　不允许重复项的组合  180

9.4.4　允许重复项的排列  181

9.4.5　不允许重复项的排列  182

9.4.6　轮询调度算法  183

9.5　递归的删除  188

9.5.1　尾部递归的删除  188

9.5.2　动态规划  189

9.5.3　自底向上编程  190

9.5.4　删除递归的通用方法  191

9.6　本章小结  193

9.7　练习题  194

第10章　树  196

10.1　有关树的术语  196

10.2　二叉树的性质  198

10.3　树的表示  200

10.3.1　构建常规树  200

10.3.2　构建完全树  203

10.4　树的遍历  203

10.4.1　前序遍历  204

10.4.2　中序遍历  206

10.4.3　后序遍历  206

10.4.4　广度优先遍历  207

10.4.5　遍历的应用  207

10.4.6　遍历的运行时间分析  208

10.5　有序树  208

10.5.1　添加节点  209

10.5.2　查找节点  210

10.5.3　删除节点  211

10.6　最小共同祖先  212

10.6.1　在有序树中查找最小共同祖先  212

10.6.2　使用指向父节点的指针  213

10.6.3　使用指向父节点的指针和深度字段  214

10.6.4　常规树  214

10.6.5　欧拉环游  216

10.6.6　所有节点对的最小共同祖先  217

10.7　线索树  217

10.7.1　构建线索树  218

10.7.2　线索树的应用  220

10.8　特殊的树算法  221

10.8.1　动物游戏  221

10.8.2　表达式求值  223

10.9　区间树  224

10.9.1　构建区间树  225

10.9.2　与点相交  226

10.9.3　与区间相交  226

10.9.4　四叉树  228

10.9.5　字符串树  231

10.10　本章小结  235

10.11　练习题  235

第11章　平衡树  239

11.1　AVL树  239

11.1.1　添加值  239

11.1.2　删除值  240

11.2　2-3树  241

11.2.1　添加值  242

11.2.2　删除值  242

11.3　B树  244

11.3.1　添加值  245

11.3.2　删除值  245

11.4　平衡树的变种  246

11.4.1　自顶向下的B树  246

11.4.2　B+树  247

11.5　本章小结  248

11.6　练习题  248

第12章　决策树  250

12.1　搜索博弈树  250

12.1.1　极小极大算法  251

12.1.2　初始移动和响应  254

12.1.3　博弈树启发式算法  254

12.2　搜索常规决策树  255

12.2.1　优化问题  256

12.2.2　穷举搜索  257

12.2.3　分支定界搜索  258

12.2.4　决策树启发式算法  259

12.2.5　其他决策树问题  264

12.3　群集智能  267

12.3.1　蚁群优化算法  268

12.3.2　蜂群算法  268

12.3.3　群集仿真  269

12.4　本章小结  270

12.5　练习题  271

第13章　基本网络算法  274

13.1　有关网络的术语  274

13.2　网络的表示  276

13.3　遍历  278

13.3.1　深度优先遍历  278

13.3.2　广度优先遍历  280

13.3.3　连通性测试  281

13.3.4　生成树  282

13.3.5　最小生成树  283

13.3.6　欧几里得最小生成树  284

13.3.7　构建迷宫  284

13.4　强连通组件  285

13.4.1　Kosaraju算法  285

13.4.2　关于Kosaraju算法的讨论  286

13.5　查找路径  288

13.5.1　查找任意路径  288

13.5.2　标签设置最短路径  289

13.5.3　标签修正最短路径  291

13.5.4　所有节点对的最短路径  292

13.6　传递性  295

13.6.1　传递闭包  295

13.6.2　传递归约  296

13.7　最短路径算法的改进  298

13.7.1　形状点  298

13.7.2　提前终止  299

13.7.3　双向搜索  299

13.7.4　最佳优先搜索  299

13.7.5　转弯惩罚和禁行  299

13.8　本章小结  302

13.9　练习题  302

第14章　高级网络算法  304

14.1　拓扑排序  304

14.2　回路检测  306

14.3　地图着色  307

14.3.1　双色地图  307

14.3.2　三色地图  308

14.3.3　四色地图  309

14.3.4　五色地图  309

14.3.5　其他地图着色算法  312

14.4　最大流量  312

14.4.1　工作分配  314

14.4.2　最小流量切割  314

14.5　网络克隆  316

14.5.1　字典  316

14.5.2　克隆引用  317

14.6　节点团  318

14.6.1　暴力破解方法  318

14.6.2　Bron-Kerbosch算法  319

14.6.3　查找三角形节点团  323

14.7　社区检测  324

14.7.1　极大节点团  325

14.7.2　Girvan-Newman算法  325

14.7.3　派系过滤法  326

14.8　欧拉路径和欧拉回路  326

14.8.1　暴力破解方法  327

14.8.2　弗莱里算法  327

14.8.3　Hierholzer算法  327

14.9　本章小结  328

14.10　练习题  329

第15章　字符串算法  331

15.1　匹配括号  331

15.1.1　算术表达式求值  332