本书重点关注的是实用、立即可用的代码，并且广泛讨论了可移植性和特定于实现的细节。本书作者介绍了一些有用但很少被讨论的算法，它们可用于语音查找、日期和时间例程（直到公元1年）、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证，并且还最全面地介绍了查找例程、排序算法和数据结构。

掌握算法的实用精要
写给程序员的算法书


程序员实用算法
（美） Andrew Binstock
John Rex 著


如今大多数关于算法的图书都是大学教科书，或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书，这些算法在开发人员的日常工作中非常有用。
本书重点关注的是实用、立即可用的代码，并且广泛讨论了可移植性和特定于实现的细节。本书作者介绍了一些有用但很少被讨论的算法，它们可用于语音查找、日期和时间例程（直到公元1年）、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证，并且全面地介绍了查找例程、排序算法和数据结构。
本书只要求读者具有C语言的初级知识以及基本代数的相关知识。源代码经过测试符合ANSI标准，可以运行在UNIX下，以及Borland、Microsoft和Watcom的编译器上。

作者简介
Andrew Binstock是《UNIX Review》的主编和《C Gazette》的创刊编辑。他是《HP LaserJet Programming》（Addison-Wesley，1991）的第一作者。
John Rex是一位计算机顾问，专攻C和C++。他是《C Gazette》的前任技术编辑，并且为许多杂志撰写文章。

本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是，本书不是一本教材。你将不会发现实现细节（我们把它作为练习留给读者完成）；也不会发现利用较小的代码段对算法进行高度理论化的讨论，以说明如何进行实现。相反，与我们的信念（即最佳的解释是实用的程序）保持一致，你将发现完全用C实现的算法的广泛选择，以及关于如何在各种应用程序中最佳地使用它们的真正实用的讨论。本书中介绍的理论材料只用于支持程序员更改实现，以满足特定的需要或者更明智地为特定的应用选择算法。在这些情况下，本书将以一种平易的方式介绍理论。在每一章末尾提供了更抽象材料的参考文献。
关于代码
虽然C++日益普及，但是由于以下几个原因我们仍然使用C。首先，C仍是一种被广泛了解和使用的通用程序设计语言。其次，对于C代码，C++编译器的编译结果与C编译器的结果几乎完全一致。最后，从C移植到C++并不困难，但是反过来却很困难。因而，使用C代码可以兼顾尽可能多的读者。
在开发本书中的代码时主要考虑了两个目标：可读性和可移植性。本书中的全部代码都在Borland、Microsoft和Watcom for MSDOS几种编译器下进行了测试，以确保可移植性。我们在扩展DOS下测试了Watcom编译器的编译结果，该扩展DOS使用PharLap或Rational Systems的DOS扩展器（DOS extender）。此外，除了第1章中的一个例外之外，所有的代码在UNIX下都进行了移植和重新编译。确切地讲，将其移植到SVR4的UnixWare实现。对其他UNIX平台和其他操作系统的移植工作也在进行中。
ANSI Extern
在我们的移植工作中，涉及一个很少讨论的移植问题。ANSI C标准提供了几种不同的方式，其中可以将在多个模块中声明为extern的项链接在一起。今天的许多先进编译器不要求将变量的任何局部定义声明为extern：链接器将简单地在连接的程序中定义一个extern变量并将所有的声明指向它。不过，ANSI标准不保证这种行为可以正常工作。
在ANSI下保证行为能正常工作的唯一方法是，将所有的变量声明为extern，使得至少在一个源模块中实际地定义了该变量（也就是说，没有extern指示符）。在实现这种效果时，仍然可以在一个公共的头文件中维持所有的extern变量的声明。这种技术是如下所示在头文件中声明变量，并在所有模块中包括该头文件：
Extern int Globalvariablel;
Extern int Globalvariable2;
然后在某些模块中，比如在一个包含main()函数的模块中，添加下面一行代码：
#define Extern
这具有取消定义Extern并把声明转换为定义的作用。在其他所有的模块中，将具有下面一行代码：
#define Extern extern
这意味着在所有其他的模块头都声明了extern变量。
这种方法具有一定的局限性。主要是，它要求在所有的模块中都适当地定义（#defined）了Extern。一个更简单的方法是：具有一个局部模块，它利用一个明示常量（manifest constant）标识它自身。在我们的示例中，main()模块可以通过以下明示常量通告它自身：
#define　IN_MAIN_MODULE
然后，带有Extern声明的头文件仅需要包含以下代码：
#ifdef　IN_MAIN_MODULE
#define Extern
#else
#define Extern extern
#endif
如果使用这种方法，其中一个模块将会包含extern变量的所有局部定义。这可能不是希望的结果。例如，你可能希望链表的定义出现在与栈不同的模块中。因此在这本书里，不会在所有场合都使用Extern，而是为需要的栈变量使用StkExtern，并为链表使用ListExtern，然后在需要的模块中定义StkExtern。有关这方面的示例出现在第2、3章的代码中。这样，就可以保证ANSI将链接extern变量，并以我们选择的方式把它们与定义精确匹配。
代码风格
最后，在代码可读性方面，我们已竭尽所能。为此目的，我们采用了如下约定：在定义函数和全局变量时，使用MixedCased形式的变量名；在声明局部变量时，使用k_和_r_style风格。此外，为了使代码更可读，我们使用了更多的空白（在水平方向上和垂直方向上）。唯一的例外是第6章（二叉树和B树），该章中的代码很多，因此我们的任务是减少纯粹代码的页数。在该章中，我们采用如下约定：减少代码占据的空间，这也稍微降低了代码的可读性。
我们希望你发现本书可读性很好并且是有用的。它旨在提供立即可用的实用信息和解决方案。

Andrew Binstock和John Rex

封底文字：
针对程序员的实用算法
今天的大多数关于算法的图书都是大学教科书，或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书，这些算法对于开发人员在其日常工作中是有用的。
本书重点关注的是实用、立即可用的代码，并且广泛讨论了可移植性和特定于实现的细节。本书作者介绍了一些有用但很少被讨论的算法，它们可用于语音查找、日期和时间例程（直到公元1年）、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证，并且还最全面地介绍了查找例程、排序算法和数据结构。
本书只要求读者具有C语言的初级知识以及不超出基本代数之外的数学知识。源代码是符合ANSI标准的，并且对它们进行了测试，它们都可以运行在UNIX下以及Borland、Microsoft和Watcom的编译器上。
Andrew Binstock是UNIX Review的主编和C Gazette的创刊编辑。他是HP LaserJet Programming（Addison-Wesley，1991）的第一作者。
John Rex是一位计算机顾问，专攻C和C++。他是C Gazette的前任技术编辑，并且为许多杂志撰写文章。

Andrew Binstock; John Rex：暂无简介

马丽华：暂无简介

数据结构与算法是计算机专业的核心课程，是计算机软件开发和应用人员必备的专业基础。今天的大多数关于算法的图书都是大学教科书，或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书，这些算法对于开发人员在其日常工作中是有用的。
本书介绍了关于算法的基础知识、基本数据结构、散列、查找、排序、树、日期和时间、任意精度的算术运算、数据压缩以及数据完整性和验证等内容。本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是，本书不是一本教材：书中没有提供实现细节，把它作为练习留给读者完成；也没有利用较小的代码段对算法进行高度理论化的讨论，以说明如何进行实现。相反，本书完全用C语言实现了各种算法，并且讨论了如何在各种应用程序中最佳地使用它们。
本书只要求读者具有C语言的初级知识以及不超出基本代数之外的数学知识。源代码是符合ANSI标准的，并且对它们进行了测试，它们都可以运行在UNIX下以及Borland、Microsoft和Watcom的编译器上。
本书非常适合于高等院校计算机专业的学生阅读，对于从事计算机软件开发的人员，也将从本书中受益匪浅。
参加本书翻译的人员有：陈宗斌、张景友、易小丽、陈婷、管学岗、王新彦、金惠敏、张海峰、徐晔、戴锋。
由于时间紧迫，加之译者水平有限，错误在所难免，恳请广大读者批评指正。译者
2009年6月

译者序
前言
致谢


第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31启发式方法#1：跳过字符
432启发式方法#2：重复模式
44多字符串查找
45用于正则表达式的字符串
查找：grep
46近似字符串匹配技术
47语音比较：Soundex算法
48Metaphone：现代的Soundex
49选择技术
410资源和参考资料
4101通用参考资料
4102BoyerMoore
4103多字符串查找
4104正则表达式查找
4105近似字符串匹配
4106Soundex算法和Metaphone
算法
第5章排序
51排序的基本特征
511稳定性
512对哨兵的需求
513对链表进行排序的能力
514输入的阶的相关性
515对额外存储空间的需求
516内部排序技术与外部排序
技术
52排序模型
521冒泡排序
522插入排序
523希尔排序
524快速排序
525堆排序
53对链表进行插入排序
54对链表进行快速排序
55对多个键进行排序——不稳定
排序的修正方法
56网络排序
57小结：选择一种排序算法
58资源和参考资料
第6章树
61二叉树
611树查找
612节点插入
613节点删除
614二叉查找树的性能
615AVL树
62红黑树
63伸展树
64B树
641保持B树平衡
642实现B树算法
643B树实现的代码
65可以看见森林吗
66资源和参考资料
第7章日期和时间
71日期例程的库
72时间例程
73用于日期和时间数据的格式
74最后的提醒
75资源和参考资料
第8章任意精度的算术
81构建计算器82表示数字
83计算
84加法
85减法
86乘法
87除法
88关于计算器要注意的最后几点
89用于计算平方根的牛顿算法
810分期付款表
811资源和参考资料
第9章数据压缩
91行程编码
92霍夫曼压缩
921代码
922其他问题
93滑动窗口压缩
94基于字典的压缩（LZW）
941LZW算法的伪代码
942LZW压缩的实现
943填满字典
95使用哪种压缩方法
96资源和参考资料
第10章数据完整性和验证
101简单的校验和
102加权校验和
103循环冗余校验
1031CRCCCITT
1032CRC16
1033CRC32
104资源和参考资料