算法与数据结构

出版时间：2013-4  出版社：清华大学出版社  

内容概要

算法是每个计算机应用程序的核心。算法学是计算机科学的一个崭新、活跃的领域。每位计算机科学家和专业程序员都应该熟悉算法的基本工具包；即有效组织和检索数据的结构。常用的算法；用于建模、理解并求解算法问题的基本技术。
    梅霍内、桑德斯编著的《算法与数据结构》内容精炼，强调了学生和专业人员必须熟悉的编程和基本数学语言，包括了数组与链表、散列表与关联数组、排序与选择、优先队列、有序序列、图的表示、图的遍历、最短路径、最小生成树和优化等章节。本书首先提出问题，然后进行分析说明，最后给出问题的解决方案，在讲解过程中，不仅给出清晰的定义，丰富的示例和练习，而且还采用插图和伪代码来解释算法，再用真正的编程语言(如C++和Java)高效实现算法。
    《算法与数据结构》是作者多年的本科生和研究生算法课程的经验荟萃，非常适合作为算法与数据结构课程的教材。

作者简介

作者:(德)梅霍内、桑德斯 译者:葛秀慧、田浩

书籍目录

第1章 开胃菜： 整数运算1  1.1 加法2  1.2 乘法： 学校方法2  1.3 结果检查5  1.4 递归版的学校方法6  1.5 Karatsuba乘法7  1.6 算法工程9  1.7 程序10  1.8 引理1.5和定理1.7的证明13  1.9 实现提示14  1.9.1 C++14  1.9.2 Java14  1.10 历史注释与进一步的读物15第2章 概述16  2.1 渐近表示法16  2.2 机器模型19  2.2.1 外部存储器20  2.2.2 并行处理21  2.3 伪代码21  2.3.1 变量和基本数据类型21  2.3.2 语句23  2.3.3 过程与函数23  2.3.4 面向对象25  2.4 设计正确的算法和程序25  2.4.1 断言和不变量26  2.4.2 循环不变量26  2.4.3 数据结构不变量27  2.4.4 验证算法27  2.5 一个示例： 二分查找27  2.6 基本算法分析29  2.6.1 求和29  2.6.2 递推30  2.6.3 全局参数33  2.7 平均情况分析33  2.7.1 递增计数器33  2.7.2 从左到右的最大值34  2.7.3 线性搜索35  2.8 随机算法36  2.8.1 形式模型37  2.8.2 Las Vegas和Monte Carlo算法38  2.9 图39  2.9.1 第一个图算法41  2.9.2 树41  2.9.3 有序树42  2.10 P与NP43  2.11 实现提示45  2.11.1 C++45  2.11.2 Java46  2.12 历史注释与进一步的读物46第3章 用数组与链表表示序列47  3.1 链表48  3.1.1 双链表48  3.1.2 单链表51  3.2 无界数组52  3.2.1 无界数组的平摊分析： 全局参数53  3.2.2 无界数组的平摊分析： 局部参数55  3.2.3 二进制计数器的平摊分析55  3.3* 平摊分析56  3.3.1 平摊分析： 势能方法或银行账户方法57  3.3.2 势能方法的普遍性58  3.4 栈与队列58  3.5 链表与数组60  3.6 实现提示61  3.6.1 C++61  3.6.2 Java62  3.7 历史注释与进一步的读物62第4章 散列表与关联数组64  4.1 链接法散列66  4.2 通用散列67  4.3 线性探测散列71  4.4 链接法与线性探测法72  4.5 *完全散列73  4.6 实现提示75  4.6.1 C++76  4.6.2 Java76  4.7 历史注释与进一步的读物76第5章 排序与选择78  5.1 简单排序80  5.2 归并排序--O(nlogn)的排序算法81  5.3 下界83  5.4 快速排序85  5.4.1 分析85  5.4.2 细化87  5.5 选择89  5.6 打破下界91  5.7 外部排序93  5.7.1 多路归并94  5.7.2 采样排序94  5.8 实现提示96  5.8.1 C/C++97  5.8.2 Java97  5.9 历史注释与进一步的读物97第6章 优先级队列99  6.1 二叉堆100  6.2 可寻址的优先级队列104  6.2.1 配对堆104  6.2.2 斐波那契堆106  6.3 外部存储器109  6.4 实现提示110  6.4.1 C++110  6.4.2 Java110  6.5 历史注释与进一步的读物111第7章 有序序列112  7.1 二叉搜索树113  7.2 (a,b)-树与红黑树115  7.3 更多的操作121  7.3.1 连接121  7.3.2 拆分122  7.4 更新操作的平摊分析123  7.5 增强搜索树124  7.5.1 父指针125  7.5.2 子树大小125  7.6 实现提示126  7.6.1 C++127  7.6.2 Java127  7.7 历史注释与进一步的读物128第8章 图的表示130  8.1 无序的边序列131  8.2 邻接数组--静态图132  8.3 邻接表--动态图132  8.4 邻接矩阵表示133  8.5 隐式表示134  8.6 实现提示134  8.6.1 C++135  8.6.2 Java135  8.7 历史注释与进一步的读物135第9章 图的遍历137  9.1 广度优先搜索137  9.2 深度优先搜索139  9.2.1 DFS编号、完成时间和拓扑排序140  9.2.2 强连通分量142  9.3 实现提示147  9.3.1 C++147  9.3.2 Java148  9.4 历史注释与进一步的读物148第10章 最短路径149  10.1 从基本概念到遗传算法150  10.2 有向无环图153  10.3 非负边代价(Dijkstra算法)153  10.4 *Dijkstra算法的平均情况分析156  10.5 单调整数优先级队列157  10.5.1 桶队列157  10.5.2 *基数堆158  10.6 任意边代价(Bellman-Ford算法)161  10.7 所有点对最短路径和节点的势162  10.8 最短路径查询163  10.8.1 目标定向搜索164  10.8.2 等级166  10.8.3 中转节点路线166  10.9 实现提示167  10.9.1 C++167  10.9.2 Java167  10.10 历史注释与进一步的读物168第11章 最小生成树169  11.1 割和环的性质170  11.2 Jarník-Prim算法171  11.3 Kruskal算法172  11.4 并-查数据结构173  11.5 *外部存储器176  11.5.1 Semiexternal的Kruskal算法176  11.5.2 边收缩176  11.5.3 Sibeyn算法176  11.6 应用程序178  11.6.1 Steiner树问题178  11.6.2 旅行推销员之旅179  11.7 实现提示180  11.7.1 C++180  11.7.2 Java180  11.8 历史注释与进一步的读物180第12章 遗传方法优化182  12.1 线性规划： 黑盒求解器183  12.1.1 整数线性规划185  12.2 贪婪算法： 永不回头186  12.3 动态规划： 子问题的构建189  12.4 系统搜索： 有疑问，用蛮力192  12.4.1 求解整数线性规划194  12.5 局部搜索： 全局思考，局部行动194  12.5.1 爬山195  12.5.2 模拟退火： 从自然中学习196  12.5.3 局部搜索的优化201  12.6 进化算法201  12.7 实现提示203  12.8 历史注释与进一步的读物204附录A205  A.1 数学符号205  A.2 数学概念206  A.3 概率论基础207  A.4 有用的公式210  A.4.1 证明211参考文献21

编辑推荐

梅霍内、桑德斯编著的《算法与数据结构》共分12章，涵盖了数据结构的数组与链表、散列表与关联数组、排序与选择、优先队列、有序序列、图的表示、图的遍历、最短路径、最小生成树与优化。第1章作为一个引子，作者以读者熟悉的整数乘法为核心，介绍了大数乘法算法，以此激发读者对算法的兴趣。第2章介绍了本书算法所需的基础知识--渐近表示法、术语、机器模型、高级伪代码表、复杂度、平均情况分析、随机算法、图的基础、复杂性类P和NP，同时还给出了本书的第一个综合性示例--有序数组的二分查找。第3～11章是数据结构课程必须学习的内容，其与其他教科书的不同之处在于：作者独具匠心的从问题域到解域的思考方法，这种学习思想是非常棒的。在第12章中，以背包问题为主线，介绍了7种遗传方法：黑盒求解器、贪婪算法、线性规划、动态规划、系统搜索、局部搜索和进化算法。特别是局部搜索算法中的爬山、模拟退火和图着色使人印象深刻。