程序员实用算法[试读]

数据结构与算法是计算机专业的核心课程，是计算机软件开发和应用人员必备的专业基础。今天的大多数关于算法的图书都是大学教科书，或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书，这些算法对于开发人员在其日常工作中是有用的。 本书介绍了关于算法的基础知识、基本数据结构、散列、查找、排序、树、日期和时间、任意精度的算术运算、数据压缩以及数据完整性和验证等内容。本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是，本书不是一本教材：书中没有提供实现细节，把它作为练习留给读者完成;也没有利用较小的代码段对算法进行高度理论化的讨论，以说... 查看全部[ 译者序 ]

本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是，本书不是一本教材。你将不会发现实现细节(我们把它作为练习留给读者完成);也不会发现利用较小的代码段对算法进行高度理论化的讨论，以说明如何进行实现。相反，与我们的信念(即最佳的解释是实用的程序)保持一致，你将发现完全用C实现的算法的广泛选择，以及关于如何在各种应用程序中最佳地使用它们的真正实用的讨论。本书中介绍的理论材料只用于支持程序员更改实现，以满足特定的需要或者更明智地为特定的应用选择算法。在这些情况下，本书将以一种平易的方式介绍理论。在每一章末尾提供了更抽象材料的参考文献。 关于代码 虽然C++日益普及... 查看全部[ 前言 ]

这本书最初的想法是由Phil Pistone于1991年夏天提出的，感谢他提供给我们这个为期三年的任务。AddisonWesley的许多优秀成员是这次延误的主要“受害者”，非常感谢他们耐心和友善。尤其是Keith Woilman，他领导着计算机普通版图书部门并使之成为AddisonWesley的御宝之一。从这个项目一开始，Claire Horne也参与进来了;她体现了我们所联系的公司的所有和蔼以及恩典。Sarah Weaver引导我们顺利通过了生产计划，在失败面前，她表现得比其他许多人都要优秀。还要感谢Steve Vinoski所做的优秀技术编辑工作和Barbara Milligan所做的... 查看全部[ 致谢 ]

译者序 前言 致谢 第1章绪论 11评估算法 12修改算法 121主要的优化：I/O 122主要的优化：函数调用 13资源和参考资料 第2章基本数据结构 21链表 211双向链表 212链表的其他特征 22栈和队列 221栈的特征 222队列的特征 第3章散列 31散列的概念 32散列函数 33冲突解决方法 331线性再散列法 332非线性再散列法 333外部拉链法 34性能问题 35资源和参考资料 第4章查找 41查找的特征 411准备时间 412运行时间 413回溯的需要 42蛮力查找 43BoyerMoore查找... 查看全部[ 目录 ]

除了最直观的应用之外，算法是所有程序的核心和灵魂。算法一般被设计用于以最小的代价高效地解决特定的问题。算法的价值一般取决于两方面因素：如何恰当地解决问题以及如何高效地实现解决方案。这些是算法分析的定性和定量方面。 对于许多算法，质量不是一个问题。例如，对于排序算法，必须保证每次都对所有元素正确地进行了排序。一旦出错，就必须丢弃它并且严格说来不能将其视为一种算法。在其他领域，不能基于这种简单的通过/失败测试来度量质量。例如，在第4章中介绍的Soundex算法允许检索听起来相同的单词或名字。与排序算法不同，可以调整Soundex算法，以寻找接近的匹配或者相当宽泛的匹配;这取决于实现算法的方式和开发... 查看全部[ 1.1评估算法 ]

在计算机领域，一项正在进行的工作是，通过对算法进行改进以求获得最佳的性能。这种工作通常采用以下两种策略之一：优化现有的算法或者开发新的算法。这些策略具有截然不同的目标，应当加以区别看待。在优化算法的时候，一般不会尝试使其性能方程降级。例如，我们知道冒泡排序的平均性能是O(N2-N)。如果你必须使用冒泡排序，那么将希望确定在冒泡排序中执行的动作所耗费的时间非常短。也就是说，希望它的两个主要操作(比较列表中的元素并交换它们)执行得非常快。在应用程序的上下文中，需要付出相当大的努力来确保算法的实现是经过完全优化的。例如，需要确保在内存中而不是在磁盘上交换元素。通过处理每个数据项的处理所需的时间，可以... 查看全部[ 1.2修改算法 ]

减少I/O和函数调用的开销是如此重要，以至于通过讨论便携式技术以降低其开销被证明具有充分的根据。I/O通常发生在毫秒级时间范围内，而CPU活动一般发生在亚微秒级的范围内。因此，对于算法的性能而言，任何I/O的代价都非常高昂。如果不能消除I/O本身，那么可以通过使用智能缓冲来减小它的影响。许多程序员把它看作创建和控制他们自己的缓冲区的动机，从而花费相当多的努力和代码来管理I/O缓冲区。ANSI C利用setvbuf() 函数提供了一种优雅的替代方案。这个可移植的函数可以让程序员为输入流设置缓冲区的大小。问题是缓冲区应该设置成多大才合适。对此，大多数编译器库倾向于将缓冲区大小设置为一个保守但是可以... 查看全部[ 1.2.1主要的优化：I/O ]

另一个重要的优化是减少函数调用的次数。虽然现在许多编译器已经针对函数调用进行了重大优化，但是对于函数携带的重大开销还是稍存疑虑。为了验证这一点，我们可以编写一个小程序，它把一个只执行返回语句的函数调用了10 000次，你将开始感觉到函数调用的代价，如果函数传递参数或者返回值，那么花费的时间将会更长一些。常见的惯例是使用内联代码或者宏，把函数直接隐藏在算法中。研究编译器的库(如果可用，应该总是能得到源代码)，并且你将会发现许多函数已经被实现为宏。要尽可能使用这些宏，并且要留心观察它们的副作用。如果你仍然必须调用函数并且不能获得所需的性能，可以考虑将供应商的源代码直接复制到你的算法中。这是一种危险... 查看全部[ 1.2.2主要的优化：函数调用 ]

Rex, John“The pascal Keyword”C Gazette, Vol3, No4它很好地分析了使用pascal选项的好处和风险。xml version='1.0' encoding='%SOUP-ENCODING%' Tanenbaum, AndrewOperating Systems: Design and ImplementationEnglewood Cliffs, NJ: Prentice Hall, 1987尽管哲学家进餐问题已被多次介绍，但是这本经典的著作最值得一读。... 查看全部[ 1.3资源和参考资料 ]

算法是指为了达到某种目的而操作数据的方式。算法通常适用于具体的问题，以复杂的方式来处理简单的数据。例如，编译器把简单的字符串和字符翻译成可以在特定机器上执行的二进制代码。编译器的内部工作原理是：通过相互影响的诸多算法按顺序将源代码字符转换为中间表示。这些表示都是通过其他算法将它们自身翻译成目标代码，这些代码与原始的字符和字符串(指源代码)具有极少的相似之处。尽管程序不像编译器那样有雄心壮志，但它们也同样极大地依赖于算法，以一种可预见的方式来处理数据。因此，在不了解操作数据的基本例程的情况下，不可能深入地讨论算法。那些希望通晓如何使用算法的开发人员首先要学习如何操作数据。而后，他们可以根据自己的... 查看全部[ 2.1链表 ]