算法基础pdf

算法基础 内容简介

本书的撰写有机结合了理论与实现，在讲授算法理论的同时也通过C#实例讲授了算法的实现。通过描述并分析一些重要的传统算法，从而理解它们并且了解每一个算法在什么时候使用较为适合，通俗易懂地教授读者创造自己的算法的技巧。这些技巧让读者能从不同的角度看问题，建立有用的方法工具，从而解决实际问题，抑或从容面对面试难题。本书适合当作“算法设计与分析”和“数据结构与算法”两门课程的教材或参考书使用。特别是本书还融入和面试相关的内容，因此适合作为算法相关工作面试的参考资料。

算法基础 目录

出版者的话

译者序

前言

第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 log N）的算法

6.2.1堆排序

6.2.2快速排序

6.2.3归并排序

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

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.4Trie树

10.8总结

练习

第11章平衡树

11.1AVL树

11.1.1添加值

11.1.2删除值

11.22—3树

11.2.1添加值

11.2.2删除值

11.3B树

11.3.1添加值

11.3.2删除值

11.4平衡树变体

11.4.1自上而下的B树

11.4.2B+树

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.3NFA

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.2Feistel密码

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.13SAT

17.3.2二分图匹配

17.4NP难问题

17.5检测、报告和优化问题

17.5.1检测≤p报告

17.5.2报告≤p优化

17.5.3报告≤p检测

17.5.4优化≤p报告

17.6NP完全问题

17.7总结

练习

……

第18章分布式程序设计

第19章面试难题

附录A算法概念综述

附录B练习解答

索引

算法基础 精彩文摘

16.3.3 简单替换密码

在简单替换密码中，每个字母只有一个固定的对应字母。例如，用H代替A，J代替B，C代替X，等等。

在这种密码中，密钥是一组明文字母到密文字母的映射。如果信息中只包含A到Z的字母，一共有4.0*1026种可能的映射。

如果手动加密解密，很好将映射表写下来。

如果使用电脑，就可以使用伪随机数发生器来重置映射。发信者选取一个数字K，并用它初始化伪随机数发生器，然后用这个发生器随机打乱A到Z的字母来生成一组映射。然后值K就成为了密钥，接受者以相同的步骤，用K初始化生成器后，就能生成出发信人使用的映射了。

记住一个数字比记住一整组映射要简单得多。但是大部分随机数生成器中可能的内置状态数远小于4.0*1026。举例来说，如果用一个带符号的整数初始化一个随机数生成器，这个整数最多只可能有约二十亿个不同的值，这个数字依旧很大，但是电脑可以轻易地枚举出所有可能的二十亿个值，看看哪个值产生的映射可以破解出有效的单词。