程序设计实践

第1章 风 格 我们将从一个很平凡的地方入手，首先讨论程序设计的风格问题。风格的作用主要就是 使代码容易读，无论是对程序员本人，还是对其他人。好的风格对于好的程序设计具有关键 性作用。 全局变量使用具有说明性的名字，局部变量用短名字。根据定义，全局变量可以出现在整个 程序中的任何地方，因此它们的名字应该足够长，具有足够的说明性，以便使读者能够记得 它们是干什么用的。给每个全局变量声明附一个简短注释也非常有帮助： 避免函数宏。在C++ 里，在线函数更削减了函数宏的用武之地，在 Java里根本就没有宏这种 东西。即使是在C语言里，它们带来的麻烦也比解决的问题更多。 给神秘的数起个名字。作为一个指导原则，除了0和1之外，程序里出现的任何数大概 都可以算是神秘的数，它们应该有自己的名字。 把数定义为常数，不要定义为宏。C程序员的传统方式是用#define行来对付神秘的数值。C 语言预处理程序是一个强有力的工具，但是它又有些鲁莽。使用宏进行编程是一种很危险的 方式，因为宏会在背地里改变程序的词法结构。我们应该让语言去做正确的工作 。在C和 C++ 里，整数常数可以用枚举语句声明。 否定性的东西很不好理解，应该尽量避免。 使用表达式的自然形式。表达式应该写得你能大声念出来。含有否定运算的条件表达式比较 难理解： 第2章 算法与数据结构 数组是组织数据的最简单方式。所以大部分语言都提供了有效而方便的下标数组，字符 串也用字符的数组表示。数组的使用非常简单，它提供对元素的O(1)访问，又能很好地使用 二分检索和快速排序，空间开销也比较小。对于固定规模的数据集合，数组甚至可以在编译 时建构起来。所以，如果能保证数据不太多，数组就是最佳选择。但事情也有另一方面，在 数组里维护一组不断变化的数据代价很高。所以，如果元素数量无法预计，或者可能会非常 多，选择其他数据结构可能就更合适些。 表特别适合那些需要在中间插入和删除的情况，也适用于管理一批规模经常变动的无顺 序数据，特别是当数据的访问方式接近后进先出 (LIFO)的情况时(类似于栈的情况)。如果程序 里存在多个互相独立地增长和收缩的栈，采用表比用数组能更有效地利用存储。当信息之间 有一种内在顺序，就像一些事先不知道长短的链，例如文本中顺序的一系列单词，用表实现 也非常合适。如果同时还必须对付频繁的更新和随机访问，那么最好就是使用某些非线性的 数据结构，例如树或者散列表等。 在现实中，二分检索树的使用并不很多。另一种 B树有非常多的分支，它常被用在二级存 储的数据组织中。在日常的程序设计里，树的常见用途之一是用于表示语句或表达式结构。 散列表是计算机科学里的一个伟大发明，它是由数组、表和一些数学方法相结合，构造 起来的一种能够有效支持动态数据的存储和提取的结构。 由于散列表是链接表的数组，其基本元素类型与链接表相同： 要实现符号表，采用散列表结构是最好的，因为它对元素访问提供了一个O(1)的期望性 能。散列表也有一些缺点。如果散列函数不好，或者所用的数组太小，其中的链接表就可能 变得很长。由于这些链接表没有排序，得到的将是O(n)操作。即使元素排了序也无法直接访 问它们。但是这后一个问题比较容易对付：可以分配一个数组，在里面存储指向各个元素的 指针，然后对它做排序。总之，散列表如果使用得当，常数时间的检索、插入和删除操作是 任何其他技术都望尘莫及的。 数组支持在常数时间里访问任何元素，但不能方便地增长或缩短。链表对于插 入、删除可以很好地适应，但对它做随机元素访问要求O(n)的时间。树与散列表提供了好的 折衷，既支持对特定元素的快速访问，又支持方便的增长，条件是只要能维持好某种平衡性。 以上从Brooks的经典书中摘录的内容想说的是，数据结构设计是程序构造过程的中心环 。一旦数据结构安排好了，算法就像是瓜熟蒂落，编码也比较容易。 隐藏在设计模式后面的基本思想是：大部分程序所采用的不过是很少几种不同的设计结 构，与此类似，实际上也只有不多的几种基本数据结构。 按照Brooks的建议，我们发现最好是从数据结构开始，在关于可以使用哪些算法的知识 的指导下进行详细设计。当数据结构安置好后，代码就比较容易组织了。 第4章 界 面 设计的真谛，就是在一些互相冲突的需求和约束条件之间寻找平衡点。 要建立一个其他人能用的界面，我们必须考虑在本章开始处列出的那些问题：界面、信 息隐藏、资源管理和错误处理。它们的相互作用对设计有极强的影响。 这里有一个基本原则：在错误发生的时候，库函数绝不能简单地死掉，而是应该把错误 状态返回给调用程序，以便那里能采取适当的措施。另一方面，库函数也不应该输出错误信 息，或者弹出一个会话框，因为这个程序将来可能运行在某种环境里，在那里这种信息可能 干扰其他东西。 一个界面在使用时不应该强求另外的东西，如果这样做仅仅是为了设计者或实现者的某 些方便。相反，我们应该使界面成为自给自足的。 释放资源与分配资源应该在同一个层次进行。控制资源分配和回收有一种基本方式，那就是 令完成资源分配的同一个库、程序包或界面也负责完成它的释放工作。这种处理原则的另一 种说法是：资源的分配状态在跨过界面时不应该改变。 在低层检查错误，在高层处理它们。作为一条具有普遍意义的规则，错误应该在尽可能低的 层次上检测和发现，但应该在某个高一些的层次上处理。一般情况下，应该由调用程序决定 对错误的处理方式，而不该由被调用程序决定。 异常机制常常被人过度使用。由于异常是对控制流的一种旁路，它们可能使结构变得非 常复杂，以至成为错误的根源。文件无法打开很难说是什么异常，在这种情况下产生一个异 常有点过分。异常最好是保留给那些真正无法预期的事件，例如文件系统满或者浮点错误等 等。 错误信息输出应该包含所有可用信息，在可能情况下应给出有意义的上下文信息。 我们把这个库分成两个文件，头文件包含了函数声明，表示的是界面的公共部分；实现文件是程 序代码。使用者应该在他们的代码中包括这里的头文件，并把实现文件编译后的代码连接到他 们的代码上。源代码从来都不必是可见的。 第5章 排 错 键入前仔细读一读。一个有效的但却没有受到足够重视的排错技术，那就是非常仔细地阅读 代码，仔细想一段时间，但是不要急于去做修改。出错时最大的诱惑就是赶快去用键盘，立 刻开始修改程序，看看错误是否马上就能烟消云散。 应该稍微休息一下。有时你看到的代码实际上是你自己的意愿，而不是你实际写出的东 西。离开它一小段时间能够松弛你的误解，帮助代码显出其本来面目。 把你的代码解释给别人。另一种有效技术就是把你的代码解释给其他什么人，这常常会使你 把错误也给自己解释清楚了。某大学的计算中心在咨询台上放了个绒毛玩具熊，出现了奇怪 错误的学生被要求首先给玩具熊做解释，然后再去找做咨询的人。 采用二分检索的方式，丢掉一半输入，看看输出是否还是错的。 代码中的频繁改动是个信号，常常说明对问题的理解不够，或者表示需求发生了变化，这些经 常是潜在错误的根源。 第6章 测 试 测试能够说明程序中有错误，但却不能说明其中没有错误。 在编程的过程中测试，其花费是最小的，而回报却特别优厚。在写程序过程中考虑测试 问题，得到的将是更好的代码，因为在这时你对代码应该做些什么了解得最清楚。如果不这 样做，而是一直等到某种东西崩溃了，到那时你可能已经忘记了代码是怎样工作的。 边界条件检查对发现“超出一个”的错误特别有效。在实践中，做这种检查已经变成了 许多人的习惯。这样，大量的小错误在它们还没有真正发生前就已经被清除了。 检验应保持不变的特征。许多程序将保持它们输入的一些特征。 自动化测试的最基本形式是回归测试，也就是说执行一系列测试，对某些东西的 新版本与以前的版本做一个比较。 如果你发现了一个程序错误，那么又该怎么办？如果这个错误不是通过已有的测试发现 的，那么你就应该建立一个能发现这个问题的新测试，并用那个崩溃的代码版本检验这个测 试。 做测试的原因就是要发现程序里的错误，而不 是为了表明这个程序能够工作。所以，测试应该是恶毒的，如果发现了问题，那是你的方法 有效的证明，根本不应该恐慌。 对于测试，惟一的、最重要的规则就是必须做。 第7章 性 能 优化的第一要义是不做。 测量是改进性能过程中最关键的一环，推断和直觉都很容易受骗，所以在这里必须使用 各种工具。 这些问题都是性能方面出麻烦的常见原因——某个例程或者界面对于各种典型情况都工 作得非常好，但是对某些特殊情况却很糟糕，特别是如果这些情况又恰好出现在程序所处理 工作的中心位置时。 使用轮廓程序。 使用更好的算法或数据结构。 让编译程序做优化。 调整代码。 铺开或者删除代码。 高速缓存频繁使用的值。 第8章 可 移 植 性 请不要使用 C或C + +的位域，它们是高度不可移植的，而且倾向于产生大 量的低效代码。你应该把所需要的操作都封装在函数里面，在这些操作中利用移位和掩码， 取出或者设置字或字的数组里的位。 采用隐含的方式或者一种共同的形式存储公共值，在其他值上花更多的空 间和时间。 位域对机器的依赖太强，无论如何都不应该用它。 不要用c h a r与E O F做比较。总使用s i z e o f计算类型和对象的值。决不右移带符号的值。 达到可移植性的方式，最重要的有两种，我们将把它们称为联合的方式和取交集的方式。 避免条件编译。使用# i f d e f和其他类似预处理指示写的条件编译是很难管理的，因为在这种 情况下有关信息趋向于散布在整个源文件里。 把系统依赖性局限在独立文件里。如果不同系统需要不同的代码，应该使这种差异局限在独 立的文件里，一个文件对应一个系统。 把系统依赖性隐藏在界面后面。 用正文做数据交换。 维护现存程序与数据的相容性。 第9章 记 法 采用正确的语言有可能使某个程序的书写变得容易许多。 如果你发现自己为某些平庸的事情写了太多代码，或者你需要表述某些过程却遇到了很大 麻烦，那么你正在使用的很可能是一种不适当的语言。如果合适的语言不存在，那么这很可 能就是个机会，需要你自己来建立一种。发明语言并不意味着是建立某种像 J a v a那样复杂的东 西，许多棘手的问题常常可以通过改变描述方式的办法来解决。 小语言是指那些针对较窄的领域而使用的特定记法，它们不仅提供了某种好界面，还能 够帮助人组织实现它们的程序。p r i n t f的格式控制序列是一个很好的例子。 正则表达式也是一种语言。 有些程序里综合了转换和执行的功能，它们能读入源代码正文，对其做转换后运行之，这种程序称作“解 释器” 函数g e n e r a t e最值得注意的地方，或许就在于它是一个写程序的程序：它的输出是另 一个(虚拟)机器可以执行的指令序列。编译程序每时每刻都在做这件事。 这里的关键思想还是记法。记法给了我们一种表达问题的一般性方法，而这种记法的编 译程序可以针对特定计算的细节生成专门代码。

1. 风格，比如，括号，空格， 等

2. 选择合适的数据结构。所有的大程序都是由基本的数据结构构成的。如vector，list, tree, map,

hash table等。数据结构与数据库的功能都是提供增删改查。因此，基本的算法，如排序，查找，插入，删除等对算法的影响很明显。

3. 设计合适的界面。界面就是提供一个接口，如函数名，输入输出等。在c++中就是.h文件。实现是.cpp文件。用户直接调用. h 文件。

4. 调试。（1）输出，比单步调试要快。（2）用assert(条件)； （3）用#ifdef DEBUG #endif; (4)前条件，后条件； （5）追踪栈里的值。（6）边界输入输出，和条件。

5.测试。几种测试方法，值得注意：①递增测试；（2）分片测试；（3）独立实现，演算；（4）期望输出；（5）校验不变特征；（6）不要漏试任何一行代码。

6. 性能。（1）能用简单算式，不用函数。（2）不变量放在循环体外。

7. 命名。使用命名空间？

（PS：这两个名字都比较好：第一个是动词get + 名词time；第二个是动词put + 名词char）