目录

第1章程序设计: 综述1

1.1本书讨论的内容1

1.2复习数学知识2

1.2.1指数2

1.2.2对数2

1.2.3级数3

1.2.4模运算4

1.2.5证明方法4

1.3递归简论6

1.4C++类8

1.4.1类的基本语法8

1.4.2构造函数的其他语法和访问函数9

1.4.3接口与实现分离11

1.4.4vector类和string类13

1.5C++细节15

1.5.1指针15

1.5.2左值、右值和引用16

1.5.3参数传递18

1.5.4传递返回值20

1.5.5std:swap和std::move21

1.5.6五大函数21

1.5.7C风格的数组和字符串25

1.6模板26

1.6.1函数模板26

1.6.2类模板27

1.6.3Object、Comparable和例子28

1.6.4函数对象29

1.6.5类模板的分离式编译31

1.7使用矩阵32

1.7.1数据成员、构造函数和基本访问函数33

1.7.2operator［ ］33

1.7.3五大函数33

小结33

练习34

参考文献35

第2章算法分析36

2.1数学基础36

2.2模型38

2.3要分析的问题38

2.4估算运行时间40

2.4.1简单的例子40

2.4.2一般法则41

2.4.3求解最大子序列和问题42

2.4.4对数运行时间46

2.4.5分析最坏情况的局限性49

小结49

练习49

参考文献53

第3章表、栈和队列54

3.1抽象数据类型54

3.2表ADT54

3.2.1表的简单数组实现55

3.2.2简单链表55

3.3STL中的容器vector和list56

3.3.1迭代器57

3.3.2例子: 对表使用erase函数58

3.3.3const_iterators59

3.4vector的实现61

3.5list的实现64

3.6栈ADT72

3.6.1栈模型72

3.6.2栈的实现73

3.6.3栈的应用73

3.7队列ADT79

3.7.1队列模型79

3.7.2队列的数组实现79

3.7.3队列的应用80

小结81

练习81

第4章树85

4.1预备知识85

4.1.1树的实现86

4.1.2树的遍历与应用86

4.2二叉树89

4.2.1实现89

4.2.2例子: 表达式树89

4.3查找树ADT——二叉查找树91

4.3.1contains函数93

4.3.2findMin函数和findMax函数94

4.3.3insert函数95

4.3.4remove函数96

4.3.5析构函数和拷贝构造函数98

4.3.6平均情况分析98

4.4AVL树100

4.4.1单旋转102

4.4.2双旋转104

4.5伸展树109

4.5.1一种简单的想法（不可行）110

4.5.2伸展111

4.6树的遍历（回顾）116

4.7B树117

4.8STL中的容器set和map121

4.8.1集合容器set121

4.8.2映射容器map122

4.8.3set和map的实现123

4.8.4例子: 使用多个map123

小结127

练习127

参考文献132

第5章散列表133

5.1基本思想133

5.2散列函数134

5.3分离链接法135

5.4不用链表的散列表138

5.4.1线性探测法139

5.4.2平方探测法140

5.4.3双散列143

5.5再散列144

5.6标准库中的散列表146

5.7最坏情况下O(1)访问时间的散列表146

5.7.1完美散列147

5.7.2杜鹃散列148

5.7.3跳房子散列155

5.8通用散列158

5.9可扩散列160

小结162

练习163

参考文献166

第6章优先队列（堆）168

6.1模型168

6.2几种简单的实现169

6.3二叉堆169

6.3.1结构性质169

6.3.2堆序性质170

6.3.3堆的基本操作171

6.3.4堆的其他操作174

6.4优先队列的应用176

6.4.1选择问题177

6.4.2事件模拟178

6.5d-堆179

6.6左式堆179

6.6.1左式堆的性质179

6.6.2左式堆的操作180

6.7斜堆185

6.8二项队列186

6.8.1二项队列的结构186

6.8.2二项队列的操作187

6.8.3二项队列的实现189

6.9标准库的优先队列193

小结194

练习194

参考文献198

第7章排序200

7.1预备知识200

7.2插入排序201

7.2.1算法201

7.2.2插入排序的STL实现201

7.2.3插入排序的分析202

7.3一些简单排序算法的下界203

7.4希尔排序203

7.4.1算法204

7.4.2希尔排序的最坏情况分析204

7.5堆排序206

7.5.1算法206

7.5.2堆排序的分析207

7.6归并排序209

7.6.1算法209

7.6.2归并排序的分析211

7.7快速排序213

7.7.1选取轴值214

7.7.2划分策略216

7.7.3小数组217

7.7.4实际的快速排序程序217

7.7.5快速排序的分析219

7.7.6选择问题的期望线性时间算法221

7.8排序算法的一般下界222

7.9选择问题的判定树下界224

7.10对手下界225

7.11线性时间排序: 桶式排序和基数排序227

7.12外部排序231

7.12.1为什么需要新算法231

7.12.2外部排序模型231

7.12.3简单算法232

7.12.4多路合并232

7.12.5多相合并233

7.12.6替换选择234

小结235

练习235

参考文献240

第8章不相交集类241

8.1等价关系241

8.2动态等价问题241

8.3基本数据结构243

8.4灵活的union算法245

8.5路径压缩246

8.6按秩合并与路径压缩的最坏情况248

8.6.1缓慢增长的函数248

8.6.2通过递归分解进行分析248

8.6.3O(MlogN)界254

8.6.4O(Mα(M, N))界254

8.7应用255

小结257

练习257

参考文献258

第9章图论算法260

9.1相关定义260

9.2拓扑排序262

9.3最短路径算法264

9.3.1无权最短路径265

9.3.2Dijkstra算法268

9.3.3具有负值边的图272

9.3.4无环图272

9.3.5所有顶点之间的最短路径274

9.3.6最短路径实例275

9.4网络流问题276

9.5最小生成树281

9.5.1Prim算法282

9.5.2Kruskal算法283

9.6深度优先搜索与应用284

9.6.1无向图285

9.6.2双连通性286

9.6.3欧拉回路288

9.6.4有向图291

9.6.5查找强连通分量291

9.7NP完全性简论293

9.7.1难解问题与易解问题293

9.7.2NP问题294

9.7.3NP完全问题294

小结296

练习296

参考文献301

第10章算法设计技术303

10.1贪心算法303

10.1.1简单的调度问题304

10.1.2哈夫曼编码306

10.1.3近似装箱问题309

10.2分治算法315

10.2.1分治算法的运行时间315

10.2.2最近点对问题317

10.2.3选择问题319

10.2.4算术问题的理论改进321

10.3动态规划324

10.3.1用表格代替递归324

10.3.2矩阵乘法的运算顺序326

10.3.3最优二叉查找树328

10.3.4所有顶点之间的最短路径331

10.4随机算法332

10.4.1随机数生成器333

10.4.2跳跃表336

10.4.3素数测试339

10.5回溯算法341

10.5.1收费公路重建问题341

10.5.2博弈344

小结349

练习350

参考文献356

第11章摊还分析358

11.1一个无关的智力问题358

11.2二项队列359

11.3斜堆362

11.4Fibonacci堆364

11.4.1切断左式堆中的节点364

11.4.2二项队列的懒惰合并366

11.4.3Fibonacci堆的基本操作368

11.4.4时间界的证明369

11.5伸展树370

小结373

练习373

参考文献375

第12章高级数据结构与实现376

12.1自顶向下伸展树376

12.2红黑树382

12.2.1自底向上插入382

12.2.2自顶向下红黑树383

12.2.3自顶向下删除388

12.3treap树389

12.4后缀数组和后缀树391

12.4.1后缀数组392

12.4.2后缀树394

12.4.3线性时间构建后缀数组和后缀树395

12.5k-d树404

12.6配对堆406

小结411

练习411

参考文献414

附录A类模板的分离式编译416

A.1全部放入头文件417

A.2显式实例化417

索引419