本书概念清晰、内容新颖、实例详尽，是一本有关设计、实现和有效使用C语言库函数，掌握创建可重用C语言软件模块技术的参考指南。本书倡导基于接口的C语言设计理念及其实现技术，深入详细地描述了24个C语言接口及其实现。
　　本书通过叙述如何用一种与语言无关的方法将接口的设计与实现独立开来，从而形成一种基于接口的设计途径来创建可重用的API，本书是一本针对 C语言程序员的不可多得的好书，也是值得所有希望掌握可重用软件模块技术的读者阅读的参考书籍。
　　关于如何设计、实现和有效使用库函数的指南少之又少(如果说还有的话)。这本力作填补了这 个空白。它可以作为下一代软件的工具书．所有的C语言程序员都应该阅读。
　　——W．Richard Stevens
　　“我向每位专业C语言程序员推荐这本书。C语言程序员们忽视书中所描述的各种技术已经太长时 间了。”
　　 ——Norman Ramsey，贝尔实验室研究员
　　每一位程序员和软件项目经理必须掌握创建可重用软件模块的技术：可重用软件模块是构建大规模、可靠应用的基石。与当前某些面向对象语言不同，C语言为创建可重用应用程 序接口(Application Programming Interface，API)提供的语言和功能支持非常少。尽管大多数C语言程序员在自己所编写的每一个应用程序中都使用API和实现API的库．但只有相当少 的程序员可以创建和发布新的、可广泛使用的API。本书阐述了如何用一种与语言无关的方法将接口的设计与实现独立开来，从而形成一种基于接口的设计途径来创建可重用的API。书中提供大量实例具体说明这种方法。作者详细描述了24个接口和它们的实现细节，有助于读者对这种设计方法的透彻理解。

　　本书具有如下特色：
　　●简洁明了的接口描述。为对接口设计感兴趣的程序员提供了一个参考手册
　　●每一章接口的代码实现分析将帮助读者修改、扩充一个接口,或者设计相关接口
　　●深入探讨了“算法工程”：阐述如何将数据结构以及相关算法打包到可重用模块中
　　●24个API和8个实例程序的源代码都经过测试检查，每个程序都是按照”literate程序”的形 式构成。为源代码提供了全面完整的解释
　　●提供了非常少见的有关C语言编程技巧的文档记录
　　●可以方便地在http://www.cs.princeton.edu/software/cii/访问本书的所有源码

David R.Hanson 普林斯顿大学计算机科学系教授,有着二十多年编程语言研究经验。他曾经同贝尔实验室合作开展研究工作　是适用于UNIX系统上的高质量C编译器——Icc的开发者之一。另与Christopher Fraser合著有《A RetargetableC Complier：Design and lmplementation》一书，对Icc进行了讨论和分析。

现在程序员都面临着大量的关于应用程序接口（Application Programming Interface，API）的信息，大多数人都会使用API和程序库，并在其所写的每一个应用程序中实现它们，但是很少有人会创建或发布新的能广泛应用的API。事实上，程序员似乎倾向于循环使用他们自己的东西，而不愿意查找能满足他们要求的程序库，这或许是因为写特定应用程序的代码要比查找设计好的API容易。
　　我和下一代程序员一样感到心虚：lcc（Chris Fraser 和我给ANSI/ISO C编写的编译器）是建立在一定的背景之上的（在《A Retargetable C Compiler: Design and Implementation》一书中有关于lcc的描述，Addison-Wesley, 1995）。编译器展示了这样一种应用程序，该应用程序可以使用标准接口，并且能够创建在其他地方也可以使用的接口。这类程序的其他例子还有内存管理、字符串和符号表以及链表操作等等。但是lcc仅使用了很少的标准C库函数的例程，并且几乎没有代码能够直接应用到其他应用程序中。
　　本书提倡的是一种基于接口及其实现的设计方法，并且通过对24个接口及其实现的描述详细地演示了这种方法。这些接口涉及到计算机领域的很多知识，其中包括数据结构、算法、字符串处理和并发程序。这些实现并不是简单的玩具—它们是为在产品代码中使用而设计的。
　　C编程语言对基于接口设计方法的支持是极少的。而面向对象的语言，像C++和Modula-3，则鼓励将接口与实现分离。基于接口的设计独立于任何特定的语言，但是它要求程序员对像C一样的语言有更多的驾驭能力和更高的警惕性，因为这类语言很容易破坏带有隐含实现信息的接口，反之亦然。
然而，一旦掌握了基于接口的设计方法，就能够在服务于众多应用程序的通用接口基础上建立应用程序，从而加速开发。在一些C++环境中的基础类库就体现了这种效果。增加对现有软件的重用—接口实现库，能够减少初始开发成本，同时还能减少维护成本，因为应用程序的更多部分都建立在经过良好测试的通用接口的实现之上。
　　本书提供的24个接口来有多种来源，并且针对本书特别做了修正。一些数据结构中的接口—抽象数据类型，源于lcc代码和70年代末80年代初所做的Icon编程语言的实现代码（参见R.E.Griswold and M.T.Griswold, The Icon Programming Language, Prentice Hall, 1990）。其他的接口来自另外一些程序员的著作，我们将会在每一章的“参考书目浅析”部分给出详细信息。
　　书中提供的一些接口是针对数据结构的，但本书不是一本数据结构的书籍，因此，本书侧重点在算法引擎—包装数据结构以供应用程序使用—而不在数据结构算法本身。然而，好的接口设计总是依赖于恰当的数据结构和有效的算法，因此，本书与Robert Sedgewick的《Algorithms in C》（Addison-Wesley, 1990）这样的传统数据结构和算法教材是相得益彰的。
　　大多数章节会描述一个接口及其实现；有少数章节还会描述与其相关的接口。每一章的“接口”部分将会单独给出一个明确且详细的接口描述。对于兴趣仅在于接口的程序员来说，这些节就相当于一本参考手册。少数章节还会包含“示例”部分，该节将会说明在一个简单的应用程序中一个或多个接口的使用。
　　每章的“实现”部分将会详细地介绍本章接口的实现代码。在一些例子中，对一个接口将会给出多种实现方法，以展示基于接口设计的优点。这些节对于修改或扩展一个接口或是设计一个相关的接口将大有裨益。许多练习题将会探究一些设计与实现的其他可行方法。如果仅是为了理解如何使用接口，可以不用阅读“实现”一节。
　　接口、示例和实现都以literate程序的方式给出，换句话说，源代码及其解释是按照最适合理解代码的顺序交织出现的。代码可以自动地从本书的文本文件中抽取，并按C编程语言所规定的顺序组合起来。其他包含C语言literate程序设计例子的书籍有《A Retargetable C Compiler》和D.E.Knuth写的《The Stanford GraphBase: A Platform for Combinatorial Computing》（Addison-Wesley, 1993）。

组织
　　本书材料可分成下面的几大类：
基础 1. 简介
2. 接口与实现
4. 异常与断言
5. 内存管理
6. 进一步内存管理
数据结构 7. 链表
8. 表格
9. 集合
10. 动态数组
11. 序列
12. 环
13. 位向量
字符串 3. 原子
14. 格式化
15. 低级字符串
16. 高级字符串
算法 17. 扩展精度算法
18. 任意精度算法
19. 多精度算法
线程 20. 线程
　　通读第1到4章的内容将使大多数读者有所裨益，因为这几章形成了本书其余部分的框架。剩下的章可以按任何顺序阅读，尽管后面的某些章会参考其前面的内容。
　　第1章涵盖了literate程序设计和编程风格与效率的讨论；第2章提出并描述了基于接口的设计方法，定义了相关的术语，并演示了两个简单的接口及其实现；第3章描述了原子接口的实现原型，这是本书中最简单的具有产品质量的接口；第4章介绍了在每一个接口中都会用到的异常与断言；第5、6章描述了几乎所有的实现都会用到的内存管理；其余的每一章都描述了一个接口及其实现。

使用建议
　　我们假设本书的读者已经了解了在大学介绍性的编程课程中涉及到的关于C语言的内容，并且都实际使用过类似于C算法的以文本形式给出的基本数据结构。在普林斯顿，这本书的内容被用做大学二年级学生到研究生一年级的系统编程课程的教材。许多接口使用的都是高级C语言编程技巧，比如说不透明的指针和指向指针的指针等等，因此这些接口都是非常好的技术实例，且其中的技术在系统编程和数据结构课程中非常实用。
　　这本书可以以多种方式在课堂上使用，最简单的就是用在面向项目的课程中。例如，在编译原理课程中，学生通常需要为一个玩具语言编写一个编译器；在图形学课程中同样也经常有一些实际的项目。许多接口消除了具体项目所需要的一些令人厌烦的编程，这样就使得这类课程中的项目得到简化。这种用法可以帮助学生认识到在项目中重用代码可以节省大量劳动，并且引导学生在其项目中对自己所做的部分尝试使用基于接口的设计。后者在团队项目中特别有用，因为“现实世界”中的项目通常都是团队项目。
　　普林斯顿大学二年级系统编程课程的主要内容是接口与实现，其课外作业要求学生成为接口的用户、实现者和设计者。例如其中的一个作业，我在第8.1节中描述的Table接口、它的实现的目标代码以及第8.2节中描述的单词频率程序wf的说明，让学生只使用我们为Table设计的目标代码来实现wf。在下一个作业中，他们得到了wf的目标代码但必须实现Table。有时，我颠倒这些作业，但是这两种顺序对大部分学生来说都是很不一样的。他们不习惯在他们的大部分程序中只使用目标代码，并且这些作业通常都是他们第一次接触接口和程序说明中使用的半正式表示法。
　　最初布置的作业也介绍了作为接口说明必要组成部分的可检查的运行时错误和断言（assertion）。经过几个这样的作业之后，学生们才开始理解这些概念的意义。我禁止了突发性（unannounced）崩溃，也就是说断言错误的诊断是不会导致崩溃的。运行崩溃的程序将被判为零分，这样做似乎过于苛刻，但是它能够引起学生们的注意；而且也能够理解安全语言的好处，例如ML和Modula-3，在这些语言中，不会出现突发性崩溃（这种分级策略没有它听上去那么苛刻，因为在分成多个部分的作业中，只有产生冲突的那部分作业才会得到惩罚，而且不同的作业将得到不同的分数。我给过许多0分，但是从来没有因此导致任何一个学生的课程成绩很低）。
　　一旦学生们有了属于他们自己的少数几个接口后，接下来就让他们设计新的接口并沿用他们以前的设计选择。例如，Andrew Appel最喜欢的一个作业是一个原始的测试程序。学生们以组为单位设计一个作业需要的任意算术精度的接口，作业的结果类似于第17到19章中描述的接口。不同的组设计的接口不同，完成后对这些接口进行比较，一个组对另一个组设计的接口进行评价，这样做很有启迪作用。Kai Li的需要一个学期来完成的项目也达到了同样的学习实践效果，该项目使用Tcl/Tk系统（J.K. Ousterhout，《Tcl and the TkToolkit》，Addison- Wesley 1994）以及学生们设计和实现的编辑程序专用的接口，构建了一个基于X的编辑程序。Tk本身就提供了另一个很好的基于接口设计的例子。
　　在高级课程中，我通常把作业打包成接口，让学生自由地修改和改进，甚至改变作业的目的。给他们一个出发点可以减少完成作业所需的时间，并允许他们做一些实质性的修改，这样鼓励了有创造性的学生去探索新的解决办法。通常，那些不成功的方法比成功的方法更有教育意义。学生不可避免地会走错路，为此也付出了更多的开发时间。但只有当他们事后再回过头来看，才会了解所犯的错误，也才会知道设计一个好的接口是很困难的，但是值得付出努力，而且到最后，他们几乎都会转到基于接口的设计上来。

如何得到本书的软件
　　本书中的软件已经在以下的平台上通过了测试：
处　 理　 器 操作系统 编　 译　 器
SPARC SunOS 4.1 lcc 3.5
gcc 2.7.2
Alpha OSF/1 3.2A lcc 4.0
gcc 2.6.3
cc
MIPS R3000 IRIX 5.3 lcc 3.5
gcc 2.6.3
cc
MIPS R3000 Ultrix 4.3 lcc 3.5
gcc 2.5.7
Pentium Windows 95 Microsoft Visual C/C++ 4.0
Windows NT 3.51
　　其中少数实现是针对特定机器的；这些实现假设机器使用的是二进制补码表示的整数和IEEE浮点算术，并且无符号的长整数可以用来保存对象指针。
　　本书中所有的源代码在ftp.cs.princeton.edu的目录pub/packages/cii下，用匿名账号就可以得到。使用ftp客户端软件连接到ftp.cs.princeton.edu，转到pub/packages/cii目录，下载README文件，文件中说明了目录的内容以及如何下载出版物。
　　大多数最新的出版物通常都是以ciixy.tar.gz或ciixy.zip的文件名存储的，其中xy是版本号，例如10是指版本1.0。ciixy.tar.gz是用gzip压缩的UNIX tar文件，而ciixy.zip是与PKZIP 2.04g版兼容的ZIP文件。ciixy.zip中的文件都是DOS/Windows下的文本文件，每一行是以回车和换行符结束的。ciixy.zip同时也可以在美国在线、CompuServe以及其他在线服务器上得到。
　　在World Wide Web中的URL地址　http://www.cs.princeton.edu/software/cii/上同样也可以得到相应的信息。该页面还包括了一些错误报告说明。

致谢
　　自1970年末以来，在我自己的研究项目以及亚利桑那州大学和普林斯顿大学的课程中，我就已经使用过本书中的一些接口。选这些课程的学生成为了我设计的这些接口的初稿的试用者。这些年来他们的反馈是本书中代码与说明的重要来源。我要特别感谢的是普林斯顿大学的学生对COS 217和COS 596课程的参与，正是他们在不知不觉中参与了本书中大多数接口的初步设计。
　　利用接口开发是DEC公司（已与Compaq合并）的系统研究中心（System Research Center，SRC）的主要工作方式，而且1992年和1993年暑假我在SRC的工作经历—从事Modula-3项目的开发—消除了我对这种方法有效性的怀疑。我非常感谢SRC对我工作的支持，以及Bill Kalsow、Eric Muller和Greg Nelson提供的许多有意义的讨论。
　　我还要感谢IDA在普林斯顿的通信研究中心（Center for Communications Research，CCR）和La Jolla，感谢他们在1994年暑假和1995-1996休假年对我的支持。还要感谢CCR提供了一个理想的地方让我从容规划并完成了本书。
　　与同事和学生的技术交流也在许多方面对本书提供了帮助。一些即使看上去不相关的讨论也促使我对代码及其说明进行改进。感谢Andrew Appel、Greg Astfalk、Jack Davidson、John Ellis、Mary Fern噉dez、Chris Fraser、Alex Gounares、Kai Li、Jacob Navia、Maylee Noah、Rob Pike、Bill Plauger、John Reppy、Anne Rogers和Richard Stevens。感谢Rex Jaeschke、Brian Kernighan、Taj Khattra、Richard O’Keefe、Norman Ramsey和David Spuler，他们仔细阅读了本书的代码和内容，对确保代码和内容的质量都给予了重要的帮助。

David R.Hanson

傅蓉 周鹏 张昆琪 权威：暂无简介

可重用软件模块是构建大规模、可靠应用的基石，每一位程序员和软件项目经理必须掌握创建可重用软件模块的技术。literate程序设计是一种将编程代码实现与文档描述语言结合起来的编程方法，一个literate程序包含程序代码和文档，它关注文档描述，编写的代码针对于人而不是编译器。本书即使用这种激动人心的编程方式，通过叙述如何用一种与语言无关的方法将接口的设计与实现独立开来，从而设计、实现和有效使用C语言库函数，掌握创建可重用C语言软件模块技术。
　　本书倡导基于接口的C语言设计理念及其实现，深入详细地描述了24个C语言接口及其实现，内容包括：异常和断言、内存管理、链表、表格、集合、动态数组、序列、环、位向量、原子、格式化、低级字符串、高级字符串、扩展精度算法、任意和多精度算法以及线程等，是一本为C语言编程人员排忧解难的参考书。
　　C语言对于创建可重用API只提供了非常少的语言和功能支持。尽管大多数C语言程序员在自己所编写的每一个应用程序中都使用API和实现API的库，但只有相当少的程序员可以创建和发布新的、可广泛使用的API。
　　本书具有简洁明了的接口描述，为对接口设计感兴趣的程序员提供了一个参考手册。每一章接口的代码实现分析将帮助读者修改、扩充一个接口，或者设计相关接口。深入探讨了将数据结构以及相关算法打包到可重用模块中的技术和实现技巧。24个API和8个实例程序的源代码都经过测试检查，每个程序都是按照“literate程序”的形式构成，为源代码提供了全面完整的解释。本书还提供了非常有用但却很少见的有关C语言编程技巧的文档记录，另外读者还可以方便地在http://www.cs.princeton.edu/software/cii/访问本书的所有源码。
　　本书的最大特点是理论与实践相结合。书中从讲述相关的C语言基本知识和概念分析的方法入手，在此基础上结合作者的实践经验讲述如何实现基本数据结构和算法、字符串处理和并行编程接口方法。本书的作者是普林斯顿大学计算机科学系教授，有着二十多年编程语言研究经验。他曾经同贝尔实验室合作开展研究工作，是流行于Unix系统的用于C语言的高质量编译器lcc的合作开发者。书中的讲述思路清晰，语言表达明确，并且还具有丰富的示例，安排具有条理性，易于理解和掌握。使人读完有豁然开朗的感觉。
全书由傅蓉、周鹏、张昆琪、权威等进行翻译，参与翻译工作的还有刘建伟、张小辉、王秀英、周鹏、李家峻、成丽杰、吴文英、方舒凯、文静等。本书的出版是集体劳动的结晶，前导工作室全体工作人员共同完成了本书的录排、校对等工作。由于时间仓促，且译者的水平有限，在翻译过程中难免会出现一些错误，请读者批评指正。

译　 者
2003年7月

出版者的话
专家指导委员会
译者序
前言
第1章　 简介 1
1.1　 literate程序 2
1.2　 编程风格 6
1.3　 效率 7
参考书目浅析 9
练习 9
第2章　 接口与实现 11
2.1　 接口 11
2.2　 实现 13
2.3　 抽象数据类型 15
2.4　 客户调用程序的责任 17
2.5　 效率 21
参考书目浅析 21
练习 22
第3章　 原子 25
3.1　 接口 25
3.2　 实现 26
参考书目浅析 31
练习 31
第4章　 异常与断言 33
4.1　 接口 34
4.2　 实现 38
4.3　 断言 43
参考书目浅析 46
练习 46
第5章　 内存管理 49
5.1　 接口 50
5.2　 产品级实现 53
5.3　 校验实现 55
参考书目浅析 62
练习 62
第6章　 进一步内存管理 65
6.1　 接口 65
6.2　 实现 67
参考书目浅析 72
练习 73
第7章　 链表 75
7.1　 接口 75
7.2　 实现 78
参考书目浅析 83
练习 83
第8章　 表格 85
8.1　 接口 85
8.2　 例子：单词频率 87
8.3　 实现 92
参考书目浅析 98
练习 98
第9章　 集合 101
9.1　 接口 101
9.2　 实例：交叉引用列表 103
9.3　 实现 109
9.3.1　 成员操作 110
9.3.2　 集合操作 113
参考书目浅析 116
练习 116
第10章　 动态数组 119
10.1　 接口 119
10.2　 实现 122
参考书目浅析 124
练习 125
第11章　 序列 127
11.1　 接口 127
11.2　 实现 128
参考书目浅析 133
练习 133
第12章　 环 135
12.1　 接口 135
12.2　 实现 137
参考书目浅析 144
练习 144
第13章　 位向量 147
13.1　 接口 147
13.2　 实现 149
13.2.1　 成员操作 150
13.2.2　 比较 154
13.2.3　 集合操作 155
参考书目浅析 157
练习 157
第14章　 格式化 159
14.1　 接口 159
14.1.1　 格式化函数 160
14.1.2　 转换函数 162
14.2　 实现 165
14.2.1　 格式化函数 165
14.2.2　 转换函数 171
参考书目浅析 175
练习 176
第15章　 低级字符串 177
15.1　 接口 178
15.2　 例子：打印标识符 183
15.3　 实现 183
15.3.1　 字符串操作 185
15.3.2　 分析字符串 189
15.3.3　 转换函数 193
参考书目浅析 193
练习 194
第16章　 高级字符串 197
16.1　 接口 197
16.2　 实现 202
16.2.1　 字符串操作 205
16.2.2　 内存管理 208
16.2.3　 分析字符串 210
16.2.4　 转换函数 214
参考书目浅析 214
练习 215
第17章　 扩展精度算法 217
17.1　 接口 217
17.2　 实现 221
17.2.1　 加法和减法 222
17.2.2　 乘法 224
17.2.3　 除法和比较 225
17.2.4　 移位 230
17.2.5　 字符串转换 232
参考书目浅析 234
练习 234
第18章　 任意精度算法 237
18.1　 接口 237
18.2　 示例：一个计算器 240
18.3　 实现 245
18.3.1　 取反和乘法 247
18.3.2　 加法和减法 248
18.3.3　 除法 250
18.3.4　 求幂 252
18.3.5　 比较 253
18.3.6　 简易函数 254
18.3.7　 移位 255
18.3.8　 字符串和整数转换 256
参考书目浅析 259
练习 259
第19章　 多精度算法 261
19.1　 接口 261
19.2　 示例：另一计算器 266
19.3　 实现 272
19.3.1　 转换 276
19.3.2　 无符号算法 278
19.3.3　 有符号算法 280
19.3.4　 简易函数 283
19.3.5　 比较和逻辑操作 288
19.3.6　 字符串转换 291
参考书目浅析 293
练习 293
第20章　 线程 295
20.1　 接口 297
20.1.1　 Thread 297
20.1.2　 一般信号量 300
20.1.3　 同步通信通道 302
20.2　 示例 303
20.2.1　 并行排序 303
20.2.2　 临界区 307
20.2.3　 生成素数 309
20.3　 实现 312
20.3.1　 同步通信通道 312
20.3.2　 线程 314
20.3.3　 线程创建与上下文转换 322
20.3.4　 抢占 328
20.3.5　 一般信号量 330
20.3.6　 MIPS和ALPHA上的上下文转换 331
参考书目浅析 335
练习 336
附录　 接口概要 339
参考书目 361
索引 367