第1章 算法基础知识

1.1方法

1.2算法和数据结构

1.3伪代码

1.4算法的特点

1.4.1大O符号

1.4.2常见的运行时间函数

1.4.3可视化函数

1.5实际因素

1.6总结

练习

第2章 数值算法

2.1随机化数据

2.1.1随机数生成

2.1.2随机化数组

2.1.3生成不均匀分布

2.2寻找最大公约数

2.3求幂运算

2.4有关素数的运算

2.4.1寻找素数因子

2.4.2寻找素数

2.4.3素性测试

2.5进行数值积分

2.5.1矩形规则

2.5.2梯形规则

2.5.3自适应求积

2.5.4蒙特卡罗积分

2.6查找零

2.7总结

练习

第3章 链表

3.1基本概念

3.2单链表

3.2.1遍历链表

3.2.2查找单元格

3.2.3使用哨兵

3.2.4在开头添加单元格

3.2.5在结尾添加单元格

3.2.6在某个单元格后插入单元格

3.2.7删除单元格

3.3双向链表

3.4有序链表

3.5链表算法

3.5.1复制链表

3.5.2链表的插入排序

3.6链表的选择排序

3.7多线程链表

3.8循环链表

3.8.1标记单元格

3.8.2使用散列表

3.8.3链表回溯

3.8.4反转链表

3.8.5乌龟和兔子

3.8.6双向链表中的循环问题

3.9总结

练习

第4章 数组

4.1基本概念

4.2一维数组

4.2.1查找元素

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

4.2.3插入元素

4.2.4移除元素

4.3非零下界

4.3.1二维数组

4.3.2多维数组

4.4三角形数组

4.5稀疏数组

4.5.1找到行或列

4.5.2获取值

4.5.3设置值

4.5.4删除值

4.6矩阵

4.7总结

练习

第5章 栈和队列

5.1栈

5.1.1栈的链表实现

5.1.2栈的数组实现

5.1.3双向栈

5.1.4栈的算法

5.2队列

5.2.1队列的链表实现

5.2.2队列的数组实现

5.2.3专用队列

5.3总结

练习

第6章 排序

6.1时间复杂度为O（N2）的算法

6.1.1数组中的插入排序

6.1.2数组中的选择排序

6.1.3冒泡排序

6.2时间复杂度为O（N logN）的算法

6.2.1堆排序

6.2.2快速排序

6.2.3归并排序

6.3时间复杂度为亚O（N logN）的算法

6.3.1计数排序

6.3.2桶排序

6.4总结

练习

第7章 搜索

7.1线性搜索

7.2二分搜索

7.3插值搜索

7.4总结

练习

第8章 散列表

8.1散列表的基础知识

8.2链

8.3开放寻址

8.3.1删除记录

8.3.2线性探测

8.3.3二次探测

8.3.4伪随机探测

8.3.5双散列

8.3.6有序散列

8.4总结

练习

第9章 递归

9.1基础算法

9.1.1阶乘

9.1.2斐波那契数

9.1.3汉诺塔

9.2图算法

9.2.1科赫曲线

9.2.2希尔伯特曲线

9.2.3谢尔宾斯基曲线

9.2.4垫片

9.3回溯算法

9.3.1八皇后问题

9.3.2骑士巡游

9.4选择与排列

9.4.1循环选择

9.4.2重复选择

9.4.3不重复选择

9.4.4元素可重复的排列

9.4.5元素不重复的排列

9.5消去递归

9.5.1尾递归的消除

9.5.2存储中间值

9.5.3一般递归的消除

9.6总结

练习

第10章树

10.1树的术语

10.2二叉树属性

10.3树的表示

10.3.1建立树的通用方法

10.3.2构造完全树

10.4树的遍历

10.4.1前序遍历

10.4.2中序遍历

10.4.3后序遍历

10.4.4深度优先遍历

10.4.5遍历的运行时间

10.5排序树

10.5.1添加结点

10.5.2查找结点

10.5.3删除结点

10.6线索树

10.6.1建立线索树

10.6.2使用线索树

10.7特化树算法

10.7.1动物游戏

10.7.2表达式求值

10.7.3四叉树

10.7.4 Trie树

10.8总结

练习

第11章 平衡树

11.1 AVL树

11.1.1添加值

11.1.2删除值

11.2 2-3树

11.2.1添加值

11.2.2删除值

11.3 B树

11.3.1添加值

11.3.2删除值

11.4平衡树变体

11.4.1自上而下的B树

11.4.2 B＋树

11.5总结

练习

第12章 决策树

12.1游戏搜索树

12.1.1极小化极大值算法

12.1.2初始步骤和反应

12.1.3启发式游戏树

12.2搜索通用决策树

12.2.1优化问题

12.2.2穷举搜索

12.2.3分支界限

12.2.4决策树的启发式搜索

12.2.5其他决策树问题

12.3总结

练习

第13章 基本网络算法

13.1网络术语

13.2网络的表示方法

13.3网络的遍历

13.3.1深度优先遍历

13.3.2广度优先遍历

13.3.3连通性测试

13.3.4生成树

13.3.5最小生成树

13.4寻找路径

13.4.1寻找任一路径

13.4.2标签设置最短路径

13.4.3标签校正最短路径

13.4.4任意两点间最短路径

13.5总结

练习

第14章 更多的网络算法

14.1拓扑排序

14.2回路检测

14.3地图着色

14.3.1两色着色

14.3.2三色着色

14.3.3四色着色

14.3.4五色着色

14.3.5其他地图着色算法

14.4最大流

14.4.1工作分配

14.4.2最小割

14.5总结

练习

第15章 字符串算法

15.1括号匹配

15.1.1求算术表达式

15.1.2构建解析树

15.2模式匹配

15.2.1DFA

15.2.2为正则表达式建立DFA

15.2.3 NFA

15.3字符串搜索

15.4计算编辑距离

15.5总结

练习

第16章 密码学

16.1术语

16.2换位密码

16.2.1行/列换位

16.2.2列换位

16.2.3路由加密算法

16.3替换密码

16.3.1凯撒替换

16.3.2维吉尼亚密码

16.3.3简单替换密码

16.3.4一次性密码本

16.4分组密码

16.4.1代换-置换网络

16.4.2 Feistel密码

16.5公钥加密和RSA

16.5.1欧拉函数

16.5.2在取模运算下的乘法逆元素

16.5.3一个RSA的例子

16.5.4现实思考

16.6加密技术的其他用途

16.7总结

练习

第17章 复杂性理论

17.1符号

17.2复杂性分类

17.3归约

17.3.1 3SAT

17.3.2二分图匹配

17.4 NP难问题

17.5检测、报告和优化问题

17.5.1检测≤p报告

17.5.2报告≤p优化

17.5.3报告≤p检测

17.5.4优化≤p报告

17.6 NP完全问题

17.7总结

练习

第18章 分布式程序设计

18.1并行的种类

18.1.1脉动阵列

18.1.2分布式计算

18.1.3多CPU的处理

18.1.4竞争条件

18.1.5死锁

18.1.6量子计算

18.2分布式算法

18.2.1调试分布式算法

18.2.2高度并行算法

18.2.3归并排序

18.2.4哲学家进餐

18.2.5两个将军问题

18.2.6拜占庭将军

18.2.7一致性

18.2.8领导人选举

18.2.9快照

18.2.10时钟同步

18.3总结

练习

第19章 面试难题

19.1面试难题提问

19.2面试难题回答

19.3总结

练习

附录A算法概念综述

附录B练习解答

索引