本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是,本书不是一本教材。你将不会发现实现细节(我们把它作为练习留给读者完成);也不会发现利用较小的代码段对算法进行高度理论化的讨论,以说明如何进行实现。相反,与我们的信念(即最佳的解释是实用的程序)保持一致,你将发现完全用C实现的算法的广泛选择,以及关于如何在各种应用程序中最佳地使用它们的真正实用的讨论。本书中介绍的理论材料只用于支持程序员更改实现,以满足特定的需要或者更明智地为特定的应用选择算法。在这些情况下,本书将以一种平易的方式介绍理论。在每一章末尾提供了更抽象材料的参考文献。 关于代码 虽然C++日益普及,但是由于以下几个原因我们仍然使用C。首先,C仍是一种被广泛了解和使用的通用程序设计语言。其次,对于C代码,C++编译器的编译结果与C编译器的结果几乎完全一致。最后,从C移植到C++并不困难,但是反过来却很困难。因而,使用C代码可以兼顾尽可能多的读者。 在开发本书中的代码时主要考虑了两个目标:可读性和可移植性。本书中的全部代码都在Borland、Microsoft和Watcom for MSDOS几种编译器下进行了测试,以确保可移植性。我们在扩展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树),该章中的代码很多,因此我们的任务是减少纯粹代码的页数。在该章中,我们采用如下约定:减少代码占据的空间,这也稍微降低了代码的可读性。 我们希望你发现本书可读性很好并且是有用的。它旨在提供立即可用的实用信息和解决方案。