程序设计的基本方法

第2章 程序设计的基本方法

对于初学者来说，写出一个满足题目要求的程序并不是一件简单的事情。明明已经了解和

掌握了C语言中各种语句的语法和语义以及C程序的基本结构，对题目的要求似乎也都清楚，但

就是不知道怎样写出一个满足题目要求的程序：或者是程序运行所产生的结果不对，或者是程

序一运行就崩溃，或者有时感觉根本就无从下手。

出现这种情况是很正常的。编程是用程序设计语言描述一种可以让计算机准确执行的计算

过程，以期完成所需的计算。这里涉及内容和表达两个方面。所谓内容就是要有明确的解决问

题的思路和方案，所谓表达就是使用程序设计语言对问题的解决方案，包括计算的过程和步骤、

所采用的算法和数据结构等，进行准确的描述。大部分初学者在程序设计的学习过程中首先把

注意力集中在对程序设计语言本身的学习上，需要了解和掌握程序设计语言的基本要素、熟记

各种关键字和各种语句的语法、含意和基本使用方法，因此还没有足够的时间和精力去学习和

掌握使用这些语句去编写程序的方法和技巧，更难以关注如何从任务的要求入手，构思一个合

理的解决方案，以及如何准确有效地实现这一方案，保证所完成的程序正确可靠地运行。这是

学习过程中的一个必然阶段，就好像人们首先要学习和掌握写字和造句，然后才能练习写文章

一样。但是，如果注意掌握正确的学习方法，在学习程序设计语言的同时注意学习程序设计的

方法和对程序设计语言的运用，则可以收到事半功倍的效果。

和学习写作需要掌握遣词造句、布局谋篇、起承转合相类似，学习程序设计也要掌握一些

专门的方法。与使用自然语言写作相比，程序设计语言的词汇和语法都要简单得多，写程序的

方法和步骤也更加规范和易于掌握。因此，经过一定的学习和练习，编写符合题目要求的程序

将不再是一件很困难的事情。

2.1 程序设计的基本过程

和解决任何其他问题一样，在进行程序设计时，需要首先明确的是需要解决的问题和已知

的条件。只有在这两者都明确的情况下，才有可能找到从出发点通向目标的正确道路。在程序

设计中，需要首先考虑的问题是，程序需要完成的任务是什么，已知的条件和数据有哪些，从

哪里获得这些数据、在计算过程中有哪些限制。在明确了这些基本要素之后，才能开始寻找实

现目标的方法，选择和确定适当的算法和数据结构，并且考虑如何检验和证明所实现的程序是

否符合设计目标的各项要求。在这些问题都弄清之后，才能进一步考虑使用什么样的语句进行

编码，把上述思想转化为程序。根据这些要点，程序设计的基本过程可以分为问题分析、设计、

编码、调试和测试等几个阶段。

问题分析阶段的主要工作是明确程序所要完成的任务目标及其工作环境和限制。设计阶段

主要是明确问题求解的基本思路和步骤，将任务目标进一步细化成为对于程序的具体要求，并

在此基础上确定实现技术的基本要素，如数据结构、算法、程序结构等。编码过程是程序的具

体实现，是将问题求解过程和步骤的描述由自然语言或其他不能由计算机执行的表达方式转换

为计算机所能理解的形式，将由形式化或非形式化方式完成的设计转换成用编程语言完成的对

计算过程的步骤和细节进行具体描述的代码。调试阶段的任务主要是发现和改正编码过程中的

错误，保证编码过程，也就是从设计到程序的转换工作的正确性，保证程序能够正常运行。测

试阶段的工作目的是检查程序的功能和性能是否符合目标的要求，能否满足所规定的各项指标。

尽管所有的程序设计工作基本上都要经过这几个阶段，但不同规模的程序在每一个阶段所

需完成的任务的复杂程度是有很大差别的。例如在大型的软件中，与问题分析工作相对应的工

作被称为需求分析，在需求分析结束后需要产生一份详细的需求分析报告。对于更复杂的系统

的需求分析已经创造出了一个新的术语：需求工程。在大型软件中，设计工作被进一步细化分

解为概要设计和详细设计，测试也被划分为单元测试、模块测试、功能测试、性能测试、回归

测试等很多种。这些在软件工程领域都有专门的论著和教科书，进行深入的讨论和分析。对于

几十行、上百行或是再稍大一些的程序来说，事情远不需要这么复杂，各个阶段的工作都要简

单得多。很多时候，这些阶段之间的分界并不是非常明确的，很多工作有可能是交叉进行的。

但是，即使对于一个不大的程序来说，也仍然有许多问题需要仔细地考虑，分阶段地处理。因

此，把程序设计的过程分成上述这些阶段是很必要的。对于初学者来说，这有利于掌握有条有

理、按部就班地分析和解决问题的方法，养成良好的习惯。

在程序设计前期的分析和设计阶段，特别需要注意的是阶段性的工作结果一定要完整、细

致、具体。所谓完整、细致和具体，主要的判断标准有三项：第一是工作的结果能够满足其前

导阶段的要求。例如，对功能和性能的分析结果应当能够与题目的各项要求一一对应，设计方

案应当能够实现分析结果中对功能和性能的要求。第二是工作结果能够为后续阶段工作提供具

体的指导。例如，分析结果应当明确地列举所有需要实现的功能和性能指标，以便在方案设计

时有所依据；方案设计应当清晰完整，对程序的结构以及算法和数据结构的描述应当准确、完

整，以便编码时可以一一对照，而不需要在这些方面再重新构思。第三是工作结果能够为后续

阶段工作提供具体的检验标准，也就是说，我们可以根据前期工作的结果，逐项检查后续阶段

的工作是否满足要求、是否合格。例如，我们可以根据设计方案中关于解题思路、计算步骤、

算法以及数据结构的描述来检查编码的内容是否符合要求，是否完整地实现了设计方案所规定

的各项任务，也可以根据分析结果来检查设计方案是否完整地体现了对功能和性能的各项要求。

我们还应该可以根据分析结果来确定测试数据的构造原则，并据此来构造相应的测试数据，检

验整个程序的功能和性能，并能确保在通过了这些测试后，程序就可以满足题目所规定的各项

任务和要求。所有上述各项，都是概念含混、用词模糊、叙述笼统的分析和设计结果所无法实

现的。

有些人编程时往往不对问题进行认真的分析，不对解题思路进行认真的思考，也没有仔细

的方案设计，而是直接使用编程语言思考如何进行编码。他们首先考虑的往往不是程序的第一

步应该做什么，第二步应该做什么，而是第一个语句应该怎么写，第二个语句应该怎么写。这

种缺少对于问题宏观把握的做法混淆了不同阶段的任务，不仅使得编程人员需要同时面对很多

不同性质的问题，而且需要使用他们还不很熟悉的编程语言来进行思考和做出决策。这种做法

对于简单的小问题还可以应付，对于稍微复杂一点的问题就会很难把握，往往事倍功半。为避

免出现此类情况，应该在开始学习程序设计时就重视编程工作的阶段性，养成踏踏实实、循序

渐进的工作习惯。在编码之前的各个阶段，应当使用中文这种我们最熟悉的自然语言思考，以

保证对问题理解准确、描述清楚，为后续阶段的工作打下坚实的基础。

2.2 问题分析

问题分析是程序设计的第一步，其目的是理解题目的要求，明确程序的运行环境和方式，

以及相关的限制条件。问题分析的基本内容包括确定程序的功能和性能、程序的输入输出数据

的来源、去向、内容、范围及其格式，程序的使用者、调用方式、人机交互要求，与其他程序

的关系和交互方式，对通用性的要求和扩展的可能，以及性能和其他对程序的特殊要求和限制，

如程序所占用系统资源的数量、对输入命令的响应速度等。在进行问题分析时需要注意的是，

不但要理解题目字面的意思，更要深入分析题目字面中隐含的内容，要准确、完整、全面地理

解题目的要求。

2.2.1 对程序功能的要求

对于一般的程序，特别是对于练习题一类的小程序来说，程序的功能要求会在程序的任务

说明中很明确地给出。对于为解决某项实际任务而设计的程序，其主要功能可能会明确地给出，

也可能会隐含地给出，但辅助功能以及具体要求的细节往往需要通过对实际问题的具体分析才

能获得。有时程序的主要功能比较复杂，只凭文字的描述还不足以准确地界定，这就需要通过

一些示例来进一步阐述。这时，编程人员就需要通过对问题的描述以及相关的示例分析来明确

任务对程序主要功能的要求。对程序主要功能的理解是否全面、准确、具体，是后续工作是否

正确和顺利的关键。所谓全面，就是要尽量考虑到问题涉及到的所有方面，以及所有可能出现

的情况。在对主要功能进行描述时，要尽量避免使用“主要是”、“基本上”、“等等”这样一些不精

确的词句，而要将程序所应具备的所有功能，无论大小，一律一一列出，勿使遗漏。此外，还

应考虑到对程序隐含的和潜在的要求。例如，在实际问题中，除了要考虑到任务本身直接的要

求外，还应该考虑到程序在使用过程中可能出现的各种要求以及可能遇到的情况，包括用户的

使用方式、可能的运行环境、潜在的对程序升级和扩展的要求等。对于练习题，则除了认真考

虑题目中给出的每一个条件字面上的意思之外，还需要考虑其中隐含的内容。所谓理解准确，

就是要避免理解上的误差。这其中特别要注意的是一些需求的细节和边界条件。例如取值的范

围是开区间还是闭区间、所要求的解是否是唯一的、对于多解的问题，需要只生成一个任意的

解还是生成全部的解、以及输入/输出数据的准确格式和要求等。所谓具体，就是要尽量避免过

于笼统含混的说法，尽量将程序的主要功能用具有一定限制和可操作性的方式进行描述，以便

于后续的工作。例如，―获取系统运行状态‖就是过于笼统的说法，而―获取当前CPU的使用率和

内存的占用率‖就是更加具体的描述。除了定性的要求之外，应当尽量使用定量的要求。例如，

给出参数的取值范围以及对计算结果的精度要求就比仅仅说明参数和结果的数据类型要更加明

确，说明―数据吞吐量不低于2MB/s‖要比―要有很高的数据吞吐量‖更加具体。

2.2.2 对程序性能的要求

对于程序性能的要求，可以用对系统资源的占用来衡量。程序运行所需要的最基本的系统

资源是CPU时间和存储空间。有一些任务对于程序性能有着明确的要求，例如，要求程序运行

的时间不超过1秒钟，占用内存空间不超过32MB。而多数小型编程任务，特别是练习题一类的

程序，因为程序任务简单，运行时所占用的资源微不足道，一般都没有给出对程序性能的明确

要求。当然，有时一些看似很简单的问题，有可能需要占用很多的系统资源。也有些问题在使

用一些效率不高的算法时，所需要占用的系统资源明显超过了合理的范围，使得程序或者无法

运行，或者在有限的时间内无法得出计算结果。面对这类问题时，对程序性能的考虑就成为对

问题分析的一项重要工作了。

对系统资源的占用，受两方面因素的影响。一个因素是问题的规模，另一个是程序设计和

实现时所选择的算法、数据结构以及代码的结构。一般而言，一个程序对系统资源的占用随问

题规模的增大而增加。例如，对一个大的图像进行压缩所需要的计算时间和存储空间一般都要

大于较小的图象。而对系统资源占用随问题规模增加的速度，取决于所选择的算法和数据结构。

用算法分析的术语来讲，就是说不同的算法具有不同的计算时间复杂度和存储空间复杂度。例

如，如果一个算法具有O(n)的时间复杂度，也就是说其计算所需的时间与问题规模n成正比，当

问题的规模增加到原来的10倍时，它所需要的计算时间约等于原来的10倍。而如果一个算法具

n

有O(2

)的时间复杂度，当问题的规模增加到原来的10倍时，它所需要的计算时间约为原来的

1024倍以上。我们无法改变需要求解的问题的规模，但是有可能设计和选择合适的、具有更高

效率的算法，使程序满足题目的要求。因此，对程序性能的要求实际上是对所选择的算法提出

了要求和限制。

2.2.3 程序的使用方式和环境

使用方式是问题分析的一项重要内容，涉及人机界面、输入/输出数据及格式、与其他系统

的交互、以及使用环境和人员等方面。在问题分析阶段，需要明确程序的基本使用方式，例如

程序是在字符终端上通过字符界面的命令方式被使用，通过图形界面的方式被使用，还是作为

后台服务程序被使用；输入数据是通过命令行参数传递，还是由程序通过文件或图形界面上的

控件读入，抑或是使用给定的库函数获取；输出数据是写到标准输出上，还是写到指定的文件

中；输入/输出数据的编码是二进制方式的还是正文的，数据的类型是整型数还是浮点数；以及

数据的组织方式，数据之间的分隔符等。程序的使用者以及程序的生命周期对于程序的分析和

设计，以及其他阶段的工作也有很大的影响。程序的生命周期是指从任务的提出到程序不再被

使用和维护的全部时间。不同程序的生命周期是不同的。例如，课程作业习题的生命周期到程

序提交并评测完毕，取得了分数就结束了；一个自己常用的工具程序可能会跟随自己几周、几

个月、或者几年的时间；而一个商业性的程序，其生命周期可能会持续更长的时间。程序生命

周期的长短直接关系到设计者需要对它在测试和优化上所花费的资源和精力。为大量非专业的

使用者设计的、具有很长的生命周期、需要经常维护和升级的程序，在功能、性能、程序的可

靠性、可扩展性、对错误的处理等工作的复杂和细致程度方面都会与由设计者本人或者少数专

业人员使用的程序、或者只是作为练习题的答案或者临时使用的工具的程序有很大的不同。此

外，还需要考虑程序运行所在的计算平台，包括硬件系统和操作系统，以及它们所能提供的系

统支持。尽管一般的应用程序基本上不与操作系统直接打交道，但是至少一些基本数据类型的

实际长度会受CPU结构的影响，数据的输入/输出会涉及到操作系统所提供的文件格式、以及对

文件的基本访问和控制功能。当需要使用一些比较复杂的系统功能，例如多进程/多线程的创建、

进程间的通信、内存的管理和设备的控制等等时，就更是需要直接和操作系统进行交互。从功

能方面看，不同操作系统所提供的对一些常用功能，例如对文件的打开和关闭、对数据的读写

等的支持比较类似，有些已经被封装在C语言的库函数中。但是即使是对这些功能的支持，不

同的系统在实现的细节上仍然可能有一些差别，并且这些差别有可能影响到程序执行的正确性。

例如，对于ASCII文件中的换行符，在Unix/Linux上的表示方法就与Windows/Dos不同。对更复

杂的功能来说，差异可能就更大了。因此，当程序有可能在不同的平台上运行时，必须要考虑

不同系统的这些差异，并采取相应的处理方法。

尽管使用方式和环境不是对程序功能要求的主要部分，但在程序的实现中，有时其所占的

比重会大于程序的主要功能本身。这一点在一些通用的实用程序中表现得特别明显。有些时候，

实现程序的主要功能的代码所占的比重远远小于为适应不同的使用环境和使用方式而产生的代

码所占的比重。例如，一个最简单的可以完成基本功能的Web服务器，在仅使用标准库函数的情

况下，其所需要的代码量不过几百行。然而，一个功能完善，可以适用于多种使用环境、满足

不同要求、具有灵活的可配置功能的Web服务器的代码量会远远超过这一规模。广泛应用的开源

Web服务器Apache，其2.0版的源代码包括.c和.h文件共670个，总共约有260000行代码，这其中

有相当一部分是用于处理不同应用环境和使用方式的需求以及各种辅助功能及其配置的。

2.2.4 程序的错误处理

错误处理是指程序在运行时遇到各种不正常的情况时所应做出的反应。程序运行时常见的

错误包含下面三大类：一是用户在使用中造成的错误，二是程序运行环境中出现的错误，三是

程序设计或实现中的漏洞所导致的程序运行错误。我们不能假设程序始终运行在正确的环境下，

不能假设使用者在使用程序时会不犯错误，也不能假设我们的程序自身没有一点错误。例如，

网络连接可能由于网络设备的故障而无法建立，用户可能会在调用程序时给出错误的参数，指

定的输入文件可能不存在或者打不开，输入文件中数据的类型或数值可能是错误的，程序在输

出数据时可能会由于权限问题或存储空间问题而无法打开指定的文件或无法写入数据，程序在

运行时可能会由于地址越界问题而访问了不存在的存储空间，等等。所有设计规范的软件都会

对已知的或未知的错误做出适当的处理和防范。例如，当用户试图使用编辑工具打开一个不存

在的文件时，程序会报告该文件不存在，并允许用户重新输入文件名。这就是对已知类型的使

用错误的一种处理方式。著名的Windows系统的蓝屏问题则是对系统自身产生的未知类型、且

无法正常恢复的运行错误的一种处理方法。错误处理所需要做的就是在出现错误的情况下做出

恰当的反应。完善的错误处理机制是一个相当复杂的问题，有时甚至连一些比较成熟的软件在

这方面也未必做得很完美。例如，很多编译系统对于用户程序中一般的语法错误可以给出比较

准确的定位，但是对于象括号不匹配这样的错误就往往给出不正确的错误信息，有些甚至会停

止运行。

对错误处理的复杂和完善程度取决于程序的性质、规模、重要性、及其用户群。对于初学

者来说，重要的首先是要有对程序在运行时有可能出现错误的预期和防范意识，其次需要知道

什么是对于不同性质的错误的恰当处理，然后，需要根据任务的要求和程序的重要性，在一些

关键的地方进行错误的检测和响应。对于比较简单的程序，包括练习题和在小范围内使用的简

单工具等，首先需要对使用中最容易出现的错误，特别是程序的被调用方式和输入的数据的正

确性进行检测，在错误出现时进行适当的处理，并且向使用者报告提示信息。这是对任何一个

程序，哪怕仅仅是为自己使用的小型工具程序都应当做的。例如，假设一个程序在运行时需要

从命令行上读入一个给定范围内的整数，程序应该在一开始就检查这个参数是否在命令行上给

出了，这个参数是否是一个整数，以及这个整数的值是否在规定的范围内。如果发现其中有任

何一项错误，则程序需要输出错误提示信息，告诉用户程序的正确调用方式以及参数的类型和

范围，然后结束运行。其次，程序应当对运行中可能出现的错误，如网络连接无法建立、输入

文件无法打开、计算结果溢出、地址越界、除数为0等进行适当的检查和防范，并尽可能地自动

对发现的错误进行处理。在无法自动处理时，也需要向用户报告出错信息，以方便对程序的维

护和修改。应当尽量避免程序在没有任何提示的情况下就停止运行甚至崩溃，并因此导致数据

丢失、服务中断，而且没有为程序的维护和更新留下任何有用的信息。

2.2.5 程序的测试

在对问题的分析完成之后，除了对问题本身的理解之外，还需要考虑对程序的测试。虽然

程序只有在完成后才能进行测试，但关于程序测试的考虑应该在问题分析阶段就开始。对于小

的程序，我们可以只考虑如何对程序的整体进行测试。对于功能和结构较为复杂的程序，则在

整体测试之前还需要考虑如何根据程序的功能和结构，对程序的各个部分进行单独的测试。认

真深入地考虑对程序的测试有助于检验和促进对问题的分析工作。实际上，只有认真思考过如

何对程序进行测试，才能更深刻、更全面地理解题目或任务中各项要求的含义。在问题分析阶

段对测试的考虑主要集中在四个方面，即程序测试的内容、测试的方法、测试所使用的数据、

以及测试所使用的工具和环境。测试内容应当覆盖对程序功能和性能的全部要求。这些内容应

当全面地体现在测试方法和测试数据中。测试的方法取决于程序的类型和规模。对于小型的面

向字符终端的计算和数据处理型程序，在基本测试中多采用“黑盒测试”的模式，不考虑程序的

内部结构和实现方法，只根据对程序功能和性能的要求，设计测试数据和测试方法。测试数据

是测试工作中的重要工具，对测试数据应规定其类型、规模和生成方法，说明预期结果的生成

方法、结果正确性的判断方法、以及测试过程的具体操作流程。测试数据应该完整全面，应该

包括各种典型的正常输入数据、可能出现的极限数据、以及应该处理或做出响应的错误数据。

有些初学者在自己的程序出现问题时往往束手无策，这其中的一个重要原因就是在问题分析阶

段没有仔细地考虑对程序的测试以及测试数据的设计。对一个程序的完整测试往往需要大量的

数据，测试过程也往往需要多次重复性的操作。对于比较复杂的问题，特别是来源于实际应用

领域的程序设计问题，测试是一个相当复杂、耗时而且充满挑战性的工作。设计和使用适当的

测试工具对程序进行完备的测试，应该成为编程人员所需要了解和掌握的重要知识和工作技能。

2.2.6 问题分析的结果

在问题分析工作完成之后，需要对分析结果进行整理，把分析的要点记录下来，以便在程

序完成之后一一对照，检查程序是否完全满足了题目的要求。当然，这些内容在对具体问题进

行分析时，应该根据题目的复杂程度进行适当的取舍和调整。在程序设计课程中遇到的问题多

数比较简单，但对问题的分析也仍需要认真细致，对需求的关键都需要一一列清。下面我们先

来看一个简单的例子：

【例2-1】N！的分解 从标准输入读取一个整数N（2≤N≤60000），将N！分解成质数幂的乘积，

将结果打印到标准输出上。分解式中的质数按从小到大的顺序输出。对重复出现的质因数，用

指数形式表示，各符号间无空白符。例如，当输入数据为5时，程序应输出下列内容：

2^3*3*5

这道题目的要求很明确，基本功能只有一句话，就是将N！分解成质数幂的乘积。辅助功能

分别是读入输入数据和输出计算结果。输入的内容是一个整数，从标准输入上读入，数值的范

围在2到60000之间。输出结果写到标准输出上，稍微复杂一些的是输出数据的格式。为了更清

楚地说明输出的格式，题目中给出了一个输入/输出的样例。因为这道题目很简单，问题分析所

涉及的主要内容在题目中都有直接的描述，所以不需要再写更多文字性的分析要点。需要重点

考虑的是如何保证结果及其输出格式的正确性，再就是考虑程序的测试方法，以及测试数据的

生成。这道题目的程序只有一个输入参数，是取值范围为2~60000的整数，因此生成测试输入

数据很简单。所使用的测试数据应能够覆盖整个区间，其中应该有区间的两个端点2和60000，

以及在这一区间内适当分布的若干数值，包括质数以及分别包含一个和多个质因子的幂组成的

合数。因为这道题的输出结果是一个字符串，所以采用将输出数据直接与预期结果进行比较的

方法是简单可行的。只有预期的输出结果的生成有些问题。对于较小的输入数值，可以直接用

手工的方式生成它们的质因子分解结果。但是对于较大的数值，手工生成它们的质因子分解结

果并不是一件简单的事情，因此需要考虑其他的方法。我们知道，N！和(N-1)!的质因子分解结

果之间相差的是N的质因子。因此对于较大的数值N，可以检查程序对输入数据N和N-1的输出

结果，看看它们之间所相差的质因子的乘积是否等于N。为了使得对程序的测试更加便捷，也

可以设计和实现一个简单的小工具，来检查两个质因子分解结果之间的差别，并生成这一差别

的乘积，看看它是否等于N。这样，我们只需要手工生成一些较小的测试数据，用来对输入数

据区间的低端进行测试，而采用检查两个相邻数据分解结果之差的方法来对输入数据区间的中

间和高端区域进行测试。当然，设计一个测试工具的工作也许对于初学者来说仍然是一个不太

容易的事情。因此对于这个问题，也可以选择更为简单的方法，例如，可以令N为一个质数。

这样，如果程序的计算结果是正确的，那么对于N!和(N-1)!的分解结果之间仅会相差一个质因子

N，而这是很容易检查的。这道题目由于功能要求简单，因此测试也简单，手工方式就可以完

成大部分的测试工作。

有些题目的字面看起来很简单，但是其所包含的意思和要求却远非直觉所能全部理解。特

别是在大量的实际应用问题中，对程序的要求有很多并不是直接表述，而是隐含在文字之中，

或是依托于常规惯例的。为了真正准确地把握题目的要求，就需要进行认真细致的分析，切忌

草率地望文生义，不求甚解。下面我们再看一个稍微复杂一些的例子：

【例2-2】多项式运算 已知一元多项式A = a

n

x

n

+ … + a

1

x + a

0

，B = b

n

x

n

+ … + b

1

x + b

0

，根据运

算符+、-、*，分别计算A + B、A - B、A * B。输入数据从标准输入上读入，由三行组成。第一

行是多项式A，第二行是多项式B，第三行是一个运算符，表示所要进行的运算。多项式中除常

数项外的每一项的形式为a

n

Xn，其中a

n

和n均为正整数，a

n

表示该项的系数，n是该项的次数，X

是一个字母，表示变量名。各单项式与‘+‘之间可以有0个或多个空格符。输入的多项式A和B的

最高次数均不超过50，系数的绝对值不超过100。输出结果写在标准输出上，占一行。结果多项

式按降幂方式排列，各项的表示形式与输入形式相同，按常规的方式显示。各项与运算符之间

空一格。下面是一组输入数据的样例：

3x5 + 5x3 + 6

9x6 + 2x5 + 6x3 + x2 + 6

-

对于这组输入样例，程序应该在标准输出上产生下列输出结果：

-9x6 + x5 - x3 - x2

这道题目的大的计算步骤有三个，即读入数据、完成计算，输出结果。首先，程序应该能

从指定的文件中读入数据，即两个参与运算的多项式以及相应的运算符。然后，程序应能够按

照运算符的要求，完成两个多项式的相加、相减或相乘。最后，程序应能够将计算结果用正确

的格式输出。输入数据的格式很明确，对数据输入的功能要求也很简单：读入三个各占一行的

字符串。至于如何对这三个字符串进行分析和处理，取决于程序所选择的内部表达形式，需要

在数据结构和算法选择的阶段进一步考虑。需要注意的是，输入多项式的各项与运算符之间可

以有数目不确定的空格符，这些空格符需要在读入数据时进行妥善的处理。另外，在题目中给

出了关于输入多项式最高次数和系数最大值的说明。输入多项式的最高次数隐含了输入多项式

和结果多项式的最大长度。输入多项式的最高次数与系数的最大值一起，隐含了结果多项式中

的系数最大值。这两个最大值在进行方案设计阶段，在选择数据结构的存储空间时，都要加以

考虑和满足。

在正确完成了多项式的计算之后，程序需要将计算结果按合适的格式写到标准输出上。在

题目描述中关于输出格式的规定有下列几点明确的要求：

1 输出结果占一行

2 结果多项式按降幂方式排列

3 各项的表示形式与输入形式相同

4 各项与运算符之间空一格

这些都是程序输出时必须满足的要求，但是仅此还不够。程序对于输出的其他要求都隐含

在―按常规的方式显示‖中和输出样例中，而这绝不像初看起来那么简单。例如，对于多项式中

的一个通项aX

b

，程序应该以aXb的格式输出，但是这只有在a和b既不等于0也不等于1时才是如

此。当a等于0时，所对应的项不应输出，而当a等于1时，则不应输出这个系数，而需要直接输

0

出Xb。此外，当b等于0时，这一项就是一个常数项，因此应该只输出系数而不输出X，当b等

于1时，应该只输出X。又例如，对于系数为负数的项需要如何显示，取决于该项是不是结果多

项式的第一项。若该项是整个多项式中的第一项，即幂次最高的项时，则在该项前输出符号"-"，

且不留空格；若该项不是第一项，则不输出符号"-"，但是需要将其前面的运算符显示为减号。

经过对诸如此类的情况进行分析和整理，对于一般项可以得到如下的对于输出格式的要求：

1）输出结果占一行

2）结果多项式按降幂方式排列

3）各项与运算符之间空一格

4) 如果系数为0，则不输出该项

5) 除常数项外，如果系数为正负1，则不显示系数

6) 系数的正负号不单独输出，而是与该项前面的运算符合并在一起

7) 如果指数为1，则不输出指数

8) 如果指数为0，则不输出变量名和指数，而只输出系数。这包括系数为1的情况

对于多项式的第一项，有下面的特殊规则：

1）若第一项系数为正数，则在其前面不输出任何符号

2）若第一项系数为负数，则在其前面输出符号"-"，且"-"与系数之间不留空格

对于整个多项式，还有下面的特殊规则：

3 若多项式中所有项的系数均为0，即整个结果多项式为零，则输出0

4 操作符+、-前后要留有空格

5 末尾要输出换行符‘n‘, 并且‘n‘与前面的可显示字符之间不留空格

此外，如果再仔细看一下题目就会发现，题目描述中只说在多项式中变元的名字是一个字

符，但是并没有规定这个字符一定是x。因此在输出结果中，变元的名字必须与输入多项式中的

变元名字一致，因此变元名需要从输入文件中读出。在这道题目中，没有对于错误处理的特殊

要求。由于这是一道练习题，可以假定所有的输入数据都是符合题目规定的格式的，因此不必

考虑对于输入数据的错误处理步骤。

总结起来，这道题目中关于功能要求的细节共有十几项，远多于我们刚看到题目时的直觉。

从这个例子中可以看出，对题目的分析是一个复杂的过程。要准确全面地理解题目的要求，不

仅需要认真细致，有时还需要多次的反复。有些时候，一些对问题的规模、性能等方面的限制

性条件在题目中没有明确地给出，这时就需要根据已知条件进行分析。在确实缺乏信息，无法

得出确切结论的情况下，可以做些合理的假设，或者采用适当的方案，使得程序可以在计算平

台资源允许的条件下，最大限度地满足各种可能的要求和限制。

根据对题目的分析，可以确定测试数据的范围和要求。一个比较完整的测试中至少要覆盖

所有的极限值测试点，并且包含一些典型的测试点与极限值的多种组合。所有在分析中有明确

要求的数值和数据格式均应有至少一个以上的测试点。下面是对【例2-2】的一些基本考虑要点：

1 输入数据的覆盖：

输入数据覆盖中要考虑的因素有输入数据的长度、多项式各项系数的值以及运算符。

在输入数据的长度方面，应当覆盖下列各点：

1． 两个多项式的长度相等，2． 且小于/等于给定的极限值

3． 多项式A的长度大于多项式B的长度，4． 且A的长度小于/等于给定的极限值

5． 多项式B的长度大于多项式A的长度，6． 且B的长度小于/等于给定的极限值

7． 多项式A和B分别只有一个非0项

8． 多项式A和B分别等于0

在输入数据的系数方面，应当覆盖下列各点：

1

2

3

4

5

6

7

全部系数均为小于给定极限值的正整数

全部系数均为1

常数项为正整数。此外其余所有项的系数均为0

两个多项式均只有偶数次项的系数为正整数，奇数次项的系数为0

两个多项式均只有奇数次项的系数为正整数，偶数次项的系数为0

两个多项式交替只有奇数次项和偶数次项

全部系数均为极限值

运算符：运算符应包含+、-、*。

2 结果数据的覆盖

结果数据覆盖中要考虑的因素有结果多项式的长度、以及多项式各项系数的值，并根

据结果的要求设计相应的输入数据。在结果多项式的长度方面，应当覆盖下列各点：

9． 结果等于0

10． 结果只有一项

11． 结果长度小于可能的最大值

12． 结果长度等于可能的最大值

4 在结果多项式的系数方面，应当覆盖下列各点：

5 所有非常数项的系数等于0

6 常数项的系数等于0

7 全部系数为正整数

8 全部系数为负整数

9 只有偶数次项的系数为正整数/负整数，奇数次项的系数为0

10 只有奇数次项的系数为正整数/负整数，偶数次项的系数为0

11 第一项的系数为正整数/负整数

上面列举了输入数据和输出数据的测试要点以及需要覆盖的内容。这些要点的组合可以生

成一个庞大的测试数据集合，而这些还仅仅是一些基本的验证程序正常功能的覆盖要点，并没

有包含程序可能会遇到的错误输入。对于这道练习题，我们可以暂时忽略程序的错误处理能力。

当然，对于普通的练习题不一定要进行如此完整的测试。但是需要明确的是，即使是简单的程

序和练习题，其测试数据也决不能是随意找几个输入数据简单地试一试就可以的。也许有人会

置疑，对于一个程序是否要进行如此复杂的测试。对于这个问题的回答是肯定的。这里的原因

有以下几点：

17 程序所要解决的是现实世界中的问题。现实世界是复杂的，因此程序所要处理的情况也

很复杂。这导致程序的结构复杂、语句繁多，在程序设计的各个阶段都有可能产生错误。

例如，在对问题的分析阶段有可能对题目的要求理解不准确、不全面，因而忽略了一些

功能要求或特殊限制；在设计阶段有可能忽视了对一些特殊条件的处理，在计算的步骤

或逻辑上引入错误。在编码阶段可能产生的错误就更多了：小到有可能使用了错误的操

作符或者变量名，或者由于手误而将小数点点错了位置；大到漏写了算法中的某些语句，

颠倒了数据处理的顺序，或者向函数传递了错误的参数。对于众多潜在的错误，只有通

过全面的测试才可能发现。

18 在程序设计中，编程人员是程序的第一测试人。对于小规模程序，有时编程人员就是程

序的唯一测试者。当编程人员测试自己的程序时，其潜在的倾向就是证明自己的程序是

正确的，而不是力图发现自己程序中的错误。因此，只有系统规范地规划设计测试数据，

才能尽最大可能保证程序符合题目的各项要求，在各种应用环境和输入数据下正常运

行，产生正确的结果。

19 对于他人设计的程序，完备的测试更是必要的。对同一个问题，不同的人可能有不同的

解题思路。即使是采用同一个解题思路，在程序的具体实现方法上也可能千差万别，代

码的描述质量也会由于编程人员的经验和水平的不同而有很大的差距。我们不能主观地

假定编程人员会采用什么样的解题思路，选择什么样的实现技术，具有什么样的编码质

量。要判断一个程序是否符合要求，只能根据对程序功能和性能上的要求，尽可能全面

地进行测试。

2.3 方案设计

方案设计是根据对问题的分析和理解，确定解决问题的方法和策略，为后续的编码提供依

据。方案设计阶段的工作包括计算过程和步骤的规划、计算模型的选择、以及算法和数据结构

的选择。

2.3.1 解题思路

在明确了对程序的功能、性能等方面的要求之后，接着需要做的是建立解题思路，然后根

据解题思路选择和设计算法，构造相应的数据结构。所谓建立解题思路就是用自然语言描述解

题的计算过程和步骤，而算法则是使用具有可操作性的语言，按照一定的规则，对这些过程和

步骤进一步细化。如果用写文章做比喻的话，可以说解题思路解决的是布局和谋篇的问题，而

算法描述则是关键章节和段落的构思。当然，在程序设计的过程中，这两个层面并不是截然分

开的，它们之间的界线也不是不可逾越的。很多时候，对解题思路的考虑要涉及到所拟采用的

算法的时空效率，而对一些简单的问题，相应的算法就是解题思路的直接延伸，或者说，解题

思路可能直接就导出了相应的算法。有些时候，题目的求解过程很简单，从对问题的分析就直

接可以得到问题的求解思路。例如【例2-2】多项式运算的主要功能只有读入数据、进行多项式

的运算和输出运算结果这三个步骤，而这三个功能从概念上讲，都是比较简单的基本操作步骤。

其中输入数据的读入直接对应了简单的语句，而对多项式的计算和按格式输出计算结果又是和

具体的数据结构的选择以及编码中的一些考虑相关的。因此对这样的问题，就可以省略建立求

解思路的过程而直接进入算法和数据结构的设计以及编码了。

对于复杂一些的问题，解题思路可能涉及多个性质不同的计算步骤和过程，而每一个计算

步骤所涉及的算法和数据结构也各不相同。这样，解题思路就与算法和数据结构的设计有一个

比较明显的划分。例如，不少人都玩过一个叫做―连连看‖的电子游戏。这是一个基于图形界面

的人机交互游戏，用鼠标点击连接盘面上图案相同的两个棋子时，如果这对棋子可以使用不超

过3条线段连接起来，那么这对棋子即可被消除。当盘面上的棋子不能被消除时，游戏程序会对

剩余的棋子重新排列。游戏的目标是尽可能多地连续消除盘面上的棋子，以便在有限的对剩余

棋子的重新排列次数内清除掉所有的棋子。图2-1是游戏的一个初始状态盘面。假设我们希望编

写一个程序来帮助我们对任何一个游戏状态找到最优的操作序列，那么一个自然的想法就是让

程序自动地在游戏的盘面状态上进行搜索。为实现这一目标，我们需要识别盘面中各个棋子的

图案，而要做到这一点，就需要获取计算机终端屏幕上指定区域中的图像，在这个图像中分割

出一个个棋子所对应的区域，然后再对这些区域进行识别和记录。为了便于对盘面状态进行搜

索，需要在识别了棋子的图案后把它们转换为一种内部的表示形式，并存储在程序内部表示游

戏盘面状态的数据结构中。在完成了这些步骤之后，就可以选择最适合的搜索算法来求解最优

的操作顺序。然后，再以合适的方式把这一操作顺序通知用户。这一连串的计算过程分别属于

数据采集、图像处理、图像识别、状态空间搜索、以及人机交互等领域，每一个步骤都是相对

独立的、有其自身的特点和独立的算法的。

图2-1 游戏连连看的一个布局

一般说来，建立解题思路是一个逐步探索、逐步细化的过程，其基本策略是分而治之，也

就是把大的问题逐步分解成小的、更容易把握和解决的问题。对于简单的问题，可能略加思索

就可以明确解题的基本步骤。对于较为复杂的问题，则需要首先明确解题的基本方向和大的步

骤，然后再对每个具体步骤逐步细化，直到每一个步骤都是可以解决的基本问题为止。在这一

过程中，重要的是需要抓住问题的关键，并围绕关键的步骤灵活地思考。在思考的过程中，首

先需要评估一下已知条件和所要求的结果，也就是出发点和目标之间的差距。如果这两者之间

的差距很小，可以用已知的方法实现从出发点到目标的跨越，则说明已经找到了解决这一问题

的方法。否则，就需要考虑如何利用已知的方法，从出发点向着目标前进一步。当然，我们也

可以从目标出发，考虑能否找到利用已知方法达到目标且距离出发点较近的中间结果。不断地

针对新的起点和新的目标重复上述过程，就可以构建一条根据已知条件解决问题的思路。需要

注意的是，在这一过程中，在构建思路中的每一个步骤时，都必须考虑到它的可行性，即这一

步骤应该不仅在理论上是正确的，而且在计算机上是可以实现的，是在计算机所能提供的有限

资源下可以计算的。有些时候，一个解题思路会受到某些因素的制约，因而在实际上是不可行

的。这时就需要另寻其他的思路。至于解题思路中每一步骤的大小，并没有固定的标准。它既

取决于问题的规模，也取决于编程人员的能力和经验。一般来说，规模较大的程序中每一个步

骤的粒度要大于规模较小的程序。有经验的编程人员考虑问题可以粗一些，而经验较少的初学

者就需要把问题分解得更细一些。例如，在做程序练习题时，对于经验较多的人，―根据输入数

据建立一个名字-数值对照表‖可能就是一个很明确的、可以把握的基本操作步骤，而对于初学

者来说，就需要再进一步将其分解为更细的操作步骤。随着经验的积累和能力的提高，对问题

分解的粒度也可以逐渐加大。下面我们以一个具体的题目为例，来讨论解题思路的建立过程。

【例2-1-1】N!的分解-解题思路 在这个例子中，程序的主要功能是将N！进行质因数分解，以

及记录每一个质因数出现次数。最直观的解题方法就是首先计算出N！，然后再对其进行质因数

分解。我们知道如何计算N！，也知道如何对一个数进行质因数分解。因此从理论上讲，我们找

到了一条解决这一问题的思路。但是在实际上，这条路是不可行的，它受到了计算机所能提供

的数值表达能力和计算能力的限制。我们知道，N！随着N的增加呈指数方式迅速增大。对于32

31

位的计算机来说，它所能直接表示的最大有符号整数是2

-1，所能直接表示的最大无符号整数

是2

32

-1。这两个数都介于12！和13！之间，64位整数可以表示到20!。即使使用double类型的浮

点数，也只能表示到1475！的近似值，而这道题目要求准确分解的最大的数是60000！，这远远

超过了计算机基本数据类型所能直接表示的数值范围。即使我们可以用其他方法来表示这么大

的数值，这样的方法在计算效率方面也会很低，在可以接受的时间内无法得出计算结果。因此

必须寻找其他的解决方法。

因为N！是由从1到N的N个正整数的乘积，而N的最大取值60000仍然在计算机可以直接表示

的范围内。所以我们可以考虑逐一地对这N个自然数进行质因数分解，在分解的过程中记录每

一个质因子出现的次数，并把每个自然数中相同的质因子出现的次数累加起来。首先，这一方

法在理论上是正确的：中学的数学教科书中就讲过乘法的交换律和结合律；其次，这一方法是

可以在计算机上计算的：对一个60000以内的自然数进行质因数分解，即使用手工计算也不是非

常困难的问题。使用计算机更是可以轻而易举地完成的。因此我们可以以此作为解决这道题目

的一个思路。

在确定了解题思路之后，剩下的问题就是对其中的关键步骤，也就是一个正整数的质因数

分解、以及对每个质因数出现的次数计数，进行算法和数据结构的设计。这里，我们可以认为

这两个步骤都比较基本，是用已有的知识就可以完成的。如果读者认为这两个步骤依然比较复

杂，对于设计解题的算法和编程来说还嫌过于粗糙，也可以在解题思路的层面上对这两个步骤

进一步细化。

在上面的例子中，解题步骤的实际不可计算性使得初始的解题路线不可行，必须另辟蹊径。

一般来说，对于同一个问题，可能有多个不同的解题思路。不同的解题思路有可能在描述的繁

简、实现的难易、运行的效率、以及对计算资源的要求等方面都不相同，程序的运行环境以及

系统所提供的各种基本支持等其他多种因素也常常对解题步骤产生影响。因此在构思了一个解

题思路之后，需要根据这些指标来衡量一下，看看解题思路是否可行，并在遇到难以克服的困

难时及时转换解题思路。有些时候，对问题的进一步分析，特别是对算法和数据结构的设计和

分析有可能导出新的解题思路。因此，在建立解题思路的过程中，需要保持灵活和开放的态度，

对已有的解题思路进行认真的分析，看看它是否真的可行，是否还有更好的方法。

2.3.2 计算模型

计算模型是对所要求解的问题的一种抽象，它用计算过程中的各种元素，如数据、公式、

操作等来描述需要求解的问题。一些与数值计算和系统软件直接相关的题目，往往直接给出了

题目的计算模型或计算公式。这时编程人员只需要确定适当的计算步骤，选择和设计有效的算

法以及相应的数据结构，就可以着手编码了。另外一类题目，往往是与其他应用领域相关的题

目，则只从相关领域的角度描述了计算的前提条件和对计算的要求。这就像数学习题中求解应

用题一样，需要首先建立起相应的计算模型，然后才能进行后续的工作。

计算模型的建立，是把应用领域中的实体和这些实体之间的关系向抽象的数学模型映射的

过程。在这一过程中，需要首先分析题目中给出的与计算相关的实体，这些实体间的关系，以

及所要求解的内容。然后需要对于这些实体、关系和求解要求逐步细化和抽象，生成一个脱离

具体应用领域的问题描述，建立这一描述中的计算实体与原始题目中计算实体的对应关系。根

据对问题的抽象描述，就可以在已知的各种数学模型中进行检索，找出最为合适或接近的计算

模型，并根据这一模型完成确定计算步骤、算法及数据结构等后续工作。下面我们看一个例子。

【例2-3】 呼叫组(Calling Circles) 这是一道1996 年国际大学生程序设计竞赛(ACM/ICPC)的题

目。题目的大意是，如果A呼叫过B，B又直接或间接地呼叫过A，则A和B同在一个呼叫组中。

给出一组电话呼叫记录，计算出各个呼叫组及其中的人员。

这个问题描述了电话通信中的呼叫关系，实体是通话的各方。问题需要求解的是确定哪些

通话者属于同一个通话组。我们可以很直观地用图来表示这个题目中的实体和关系。通话者可

以用顶点来表示，呼叫关系可以用由呼叫者指向被呼叫者的带箭头的弧来表示，即若A呼叫B，

则从A引一条指向B的弧。通过这样的分析和描述，可以很清楚地看到，这道题目中的实体和关

系构成了一个有向图，题目中给出的数据就是一个对有向图的具体描述，而题目所要求解的就

是根据连通性对有向图中顶点的等价类划分。这样，就可以利用关于有向图连通性的知识来解

决这个问题：首先从输入文件中读入描述用户呼叫过程的数据，按照对有向图的表示方法生成

数据的内部表示形式，并建立用户人名和有向图节点之间的对照表。然后，根据所选择的关于

有向图连通性的计算方法，计算出各个节点之间的连通性，求出节点的分组结果，再参照人名-

节点对照表生成分组名单。最后，根据分组名单，按照规定的格式要求输出分组结果。至于在

计算有向图连通性时采用什么方法，则是在算法设计阶段需要根据题目的要求进一步考虑的。

例如，如果题目中给定的数据规模不大，对计算的时间效率要求不高的话，可以选择邻接矩阵

的方式来表示这个有向图，并用邻接矩阵的幂来计算邻接矩阵的连通性。否则的话，就需要选

择效率更高的算法。在确定了有向图的表示方法之后，数据的读入过程和向内部形式的转换等

步骤就可以进一步细化了。

很多问题的关键计算模型并不唯一。不同模型在模型的直观性、描述的复杂程度、实现的

难易、以及计算复杂性方面都可能有较大的差异。这时就需要根据具体问题来进行分析、比较

和选择。当发现一种计算模型在计算效率或编程复杂度等方面不能满足要求时，可以进一步寻

找其他适当的模型。下面是一个具有不同计算模型的例子：

【例2-4】连词游戏(Play on Words) 这是ACP/ICPC 1999年中欧分区赛中的一道题目。题目大意

是，判断N个由小写字母组成的英文单词是否可以构成这样的序列, 使得相邻的两个单词中前一

个单词的末字母等于后一个单词的首字母。题目的限制条件是，单词长度在2－1000个字母之间，

总的单词数量N小于等于100000。例如，假设给定三个单词：mouse、acm、malform，则可以构

成这样的序列，即acm malform mouse。而对于单词集合：yes、yes、no、ok，则不能构成这样

的序列。

对于这个问题，直观的感觉是可以使用有向图作为计算模型。但是在有向图的顶点和弧与

问题中的实体的对应关系上，却可以有不同的选择。第一种选择是，有向图中的每个顶点对应

一个单词，如果顶点A所对应的单词最后的字母与另一个顶点B所对应的单词的第一个字母相

同，则从顶点A建立一条指向顶点B的弧，也就是说，每条弧都从一个单词出发，指向可以接在

其后的单词。图2-2是在这种对应关系下单词集合mouse、acm、malform所对应的有向图：

malform

acm

mouse

图2-2 连词游戏的一种计算模型

在建立了这样的对应关系之后，问题就转化为判断在有向图中是否存在一条经过所有顶点

一次且仅一次的通路，也就是求解有向图中哈密顿通路是否存在的问题。哈密顿通路是图论中

的一个典型问题。这样看起来，这个问题的计算模型问题似乎就得到了解决。但是判断在一个

图中是否存在哈密顿通路是一个很复杂的计算问题，目前还没有发现求解这一问题的有效算法。

因此，对于100000个顶点的有向图，很难在合理的时间内做出判断。而这也迫使我们考虑其他

的模型。

有向图的顶点和弧与问题中的实体的对应关系的另一种选择是，每个顶点对应26个字母中

的一个，每条弧对应一个单词，从该单词的首字母指向末字母。下面是在这种对应关系下单词

集合mouse、acm、malform所对应的有向图：

a

acm

m

mouse

e

malform

图2-3 连词游戏的另一种计算模型

在建立了这样的对应关系之后，问题就转化为在有向图中求解一条经过所有的弧一次且仅

一次的通路是否存在，也就是判断有向图中欧拉通路的存在性问题。在图论中，对于判断欧拉

通路的存在性是有有效算法的，因此使用图2-3所示的计算模型可以满足求解连词游戏这一问题

的要求。

很多情况下，计算模型的建立不仅取决于待求解问题本身，而且也取决于对问题分析的切

入点和对问题的分解策略。不同的分析方法可能产生完全不同的计算模型。下面我们看一个例

子：

【例2-5】实数格式识别 合法的实数书写格式分普通格式和科学格式。普通格式的描述方法是：

[<符号>]<整数>[.<整数>]

而科学格式的描述方法是：

[<符号>]<整数>[.<整数>]E[<符号>]<整数>

其中由[]括起的内容为可选项，符号包括'+'和'-'。例如，+1.23是一个普通格式的实数， -5.1E-2

是一个科学格式的实数，而9.1.1不是任何格式的实数。写一个程序，分析一个给定的字符串是

哪种格式的实数。

学过形式语言和自动机的读者可能会敏锐地发现，这两种数据格式都是正则表达式，因此

可以使用有限自动机来分析和识别给定的字符串，并可以根据自动机模型写出相应的代码。但

是如果从模式识别的角度来观察，可以发现普通格式与科学格式的显著区别并建立另外一种计

算模型：科学格式中包含有字母E而普通格式中没有。这样，根据字符串中是否包含字母E，就

可以将其划入不同的格式类别，然后再根据该格式的描述对字符串进行检验：对于科学格式，

E的前面是一个可能带有符号的表示普通格式实数的子串，其后面是一个可能带有符号的表示

整数的子串。对于普通格式的实数，可以根据其中是否包含小数点而进一步分解：包含小数点

的实数在小数点前是一个可能带有符号的整数，在小数点后是一个不带符号的整数，而不包含

小数点的实数则只有一个可能带有符号的整数。对这些由E和小数点分隔的子串的检验是很基

本的操作。所有的子串均符合要求即可断定该字符串属于相应的格式类别，任何一个子串不符

合规定的格式即可判断该字符串为非法格式。依据这样模型写出的程序完全不同于依据自动机

模型写出的程序。

计算模型的建立是一个涉及面很广的问题，它不仅要求对问题所涉及的应用领域有深入的

了解，而且还需要有对各种数学模型的熟练掌握，以及高度的抽象思维能力。深入讨论计算模

型的建立远远超出了本书的范围。本书中所涉及的领域都是常识所易于理解的，所使用的模型

也多是常用的。对这类问题建立计算模型，一般来说是比较容易的。有些时候，问题的计算模

型并不是很明显的，有些问题可能有多个可选的模型。如何找到一个最适合的模型是需要认真

思考和仔细权衡的事情。这里更需要的是分析问题的方法和抽象思维的能力，以及勤于实践的

习惯和经验。

2.3.3 算法分类

在确定了解题思路之后，需要对解题过程中的各个步骤进一步细化和精确描述，确定关键

步骤的算法以及所使用的数据结构。在程序设计中，数据结构与算法是密不可分的。程序就是

使用编程语言在数据的某种特定表示方法和结构的基础上对抽象算法的具体描述。一方面，不

了解施加于数据上的算法，就无法决定如何构造数据。另一方面，算法的构造和选择也常常在

很大程度上依赖于作为算法基础的数据结构。因此有些人甚至认为数据结构更为基础，也更为

重要，因为只有先有了计算对象才有计算的算法。在实际工作中，数据结构的选择与算法的设

计是相辅相成、互相协调的。数据结构被用来组织和保存数据，而算法描述对这些数据的操作，

因此这两者应该放在一起来考虑。

与解题思路相似，算法同样是描述计算的过程。所不同的是，算法是对具体而且较为复杂

的计算步骤的精确描述，是用具有可操作性的方式描述一个解题步骤的具体执行过程。至于一

个计算步骤是否复杂，则需要根据问题的性质、规模、编程人员的经验以及所使用的编程工具

等而定。例如，对于一般计算问题的描述而言，浮点数的四则运算属于基本的操作步骤。但是

当进行计算机运算部件的设计和模拟时，一个浮点数的四则运算就是一个复杂的计算过程。在

学习数据结构课程时，快速排序是一个需要认真分析和讨论的复杂算法，但在C程序设计中，

快速排序只是一个对标准库函数的调用。Hash表的构造和操作对于初学者来说可能是一个复杂

的任务，但是对于从事大型系统编程的高级程序员来说，这可能只是对数据处理算法中的一个

简单步骤。

算法根据其复杂程度和应用领域，可以分为简单算法、专用算法和策略算法。无论哪类算

法，作为算法都应该满足下面的几个条件：

1．算法的每一步都应是含意确定、可以计算的

2．算法应该在有限的步骤之内产生所需要的计算结果

3．算法应该在有限的步骤内停止

简单算法

对于简单的问题，一些直观的思路、常规的方法和步骤就可以解决问题。所谓简单算法就

是对这些解决问题的直观思路和常规方法的精确描述。枚举、递推、以及模拟算法等也可以归

入这一类。简单算法一般不涉及复杂的数据结构和计算过程。例如，【例1-4】获奖人员就可以

使用嵌套的循环语句对A~F获奖的各种可能性进行枚举，从中选出符合条件的组合。设计简单

算法时更多需要的是对问题的准确理解和把握，以及对相关领域的基本常识。下面我们看一个

简单算法的例子。

【例2-6】求倒数 给出整数a（2 <= a <= 10000），求 1/a。输入文件有一行，包含两个正整数，

分别代表正整数a和所要保留的小数位数N(N <= 500)。输出所求的小数部分，不输出尾部的0。

题目的计算结果要求保存最多500位有效数字，远远超过了C语言中任何基本数据类型的表

示范围。因此这道题的程序需要使用超长有效数字计算方法。超长有效数字计算也称为高精度

计算。在高精度计算中，可以使用一维数组来表示一个数值，其中每一个数组元素表示该数值

的一个十进制位。有了这样的数据表示方法，我们就可以采用在小学算术中学过的除法竖式计

算的方法，逐位计算出1/a的值：

2 将1放入余数存储单元r中，将数组元素全部清零。

3 根据给定的所要保留的小数位数N，循环执行下列操作序列N次：

2.1. r的内容乘以10。

2.2. r的内容除以a，2.3. 将结果保存在数组的当前位中。

2.4. 从r中减去数组的当前位中的值与a的乘积。

2.5. 如果r等于0，2.6. 则停止循环；否则转回2.1。

在计算结束后，从1/a的末尾，也就是数组中第N个元素开始向前检查，记住第一个不等于0

的数组元素的位置，然后从数组中第1个元素开始向后顺序输出数组中的各个元素的值。根据算

术教科书可以知道这个算法是正确的。根据上述算法，也可以很容易地推知对相关数据结构的

要求：保存计算结果的一维数组的长度只要大于500即可。因为数组中只保存1/a的各位有效数

字，所以各元素的最大值不超过9。因为a <= 10000，所以余数的最大值不会超过9999。这样，a

和r都可以使用普通的整型变量。

专用算法

专用算法是对特定领域中的问题进行计算的算法。依据问题的领域和应用类型，常见的专

用算法可以分为数值算法和非数值算法两大类。初等数学中求最大公约数的辗转相除法、线性

代数中的高斯消元法、信号处理中的快速傅立叶变换(FFT)、插值算法、微分方程求解的龙格-

库塔法等都是数值算法的例子；而图像处理算法、代码优化算法、语音识别算法、内存垃圾收

集算法等则是非数值算法的例子。每种专用算法都与一个或几个特定应用领域中的问题密切相

关，是相关领域的研究对象。

策略算法

策略算法是一类应用广泛的算法。策略算法并不局限于具体的问题和应用领域。各种搜索

算法、动态规划算法、贪心算法等都是策略算法的例子。在策略算法中，重点描述的是问题求

解的策略和步骤，算法中的控制机制以及对抽象运算对象的操作。例如，在搜索算法中会描述

在抽象的搜索空间中按照什么样的次序生成节点、如何对搜索空间中的节点进行遍历，等等。

但是，一个节点代表什么对象、具有哪些属性、如何生成新的节点等具体问题都是和具体的实

际问题密切相关的，是策略算法所不关心的。因此，在选择策略算法时首先应将具体问题抽象

为策略算法描述中所使用的概念和模型。在选定了策略算法之后，还必须根据具体的问题，确

定对具体对象描述和操作的细节。熟练地掌握一些常用的策略算法，对于提高通过程序设计解

决实际问题的能力是很有帮助的。

2.3.4 算法和数据结构的选择

与问题的计算模型相类似，一般来说，对于一个确定的问题，可选的数据结构和算法并不

唯一，当问题比较复杂时更是如此。数据结构和算法，由于其更加接近于程序的实现，因此更

需要从实现的角度来观察和考虑各种不同方案的优缺点。程序的运行时间和所需要的存储空间、

算法的思路是否直观和易于理解、算法描述和表达的复杂程度、使用特定语言和在特定环境下

实现的难易程度等等，都是算法选择时需要关注的。在很多情况下，尽管不同的方案都可以完

成所给定的任务，但是它们在不同的度量指标上的表现各不相同。只有根据程序在实现和使用

过程中的具体要求和限制条件进行权衡，才能在诸多方案中选择出最合适的方案。数据结构的

设计和选择既与算法的选择密切相关，又有其需要独立考虑的内容。有一些算法隐含了对数据

结构的要求和限制，因此在确定了算法后，就基本上确定了所要采用的数据结构。这时需要重

点考虑的是数据结构与问题规模的关系，以及程序将要运行的计算平台能否满足问题规模对存

储空间的要求。如果在给定的问题规模下计算平台不能满足算法所需要的存储空间，就需要选

择其他可能较为复杂或计算效率较低但是对内存需要较少的算法。有些算法可以运行在几种不

同的数据结构上。这时对数据结构的选择就取决于问题的规模以及算法实现的复杂程度。当问

题规模较小时，我们不妨采用空间效率略低但是算法实现较为简洁的数据结构。当问题规模较

大，以至于对内存的需求有可能超过计算平台的限制时，对空间效率的考虑就是第一位的了。

算法的设计是一个自顶向下、逐步求精的过程。其详细程度应能使描述中的每一步都对应一个

或一组明确的对数据结构的操作，因此可以直接指导对程序的编码。下面我们通过一个实际的

例子来看看算法和数据结构的选择过程。

【例 2-1-2】 N！的分解-算法和数据结构

根据对这个题目的解题思路，需要对从2开始的自然数逐一地进行质因子分解，并将每一个

质因子出现的次数分别累加。这很自然地使我们想到，需要建立一个质数表，以及一个与之相

对应的质数出现次数表，来分别保存所用到的质数以及每个质数在N！中出现的次数。这样，

我们就可以依次检查质数表中的质数在N！中出现的次数，并将它们记录下来。质数表是一个

大小固定的线性表，在计算过程中不需要增加和删除其中的表项，因此可以选择最方便的线性

表的实现方式，即一维数组。相应地，质数出现次数表也采用相同的数据结构。这样，两个表

的对应关系就可以通过数组下标来建立：质数出现次数表中每个表项所记录的是下标与之相同

的质数表项中所保存的质数在N！中出现的次数。当然，我们也可以选择使用组合结构的方式，

把一个质数与其在N！中出现的次数作为两个不同的成员保存在同一个组合结构(记录)中，使用

一个一维的结构数组来同时保存质数表和质数出现次数表。一般来说，使用组合结构的方式可

以使数据组织更加清晰，更便于维护。在本题目中，由于问题简单，使用两个分开的数组与使

用一个结构数组对于程序中计算过程的描述以及程序的可读性和可维护性影响不大。而当选择

使用事先计算好的静态质数表时，使用分开的数组在对质数表的初始化描述上更加方便，因此

我们选择使用两个分开的一维数组作为程序的存储结构。有兴趣的读者可以自己试一试使用组

合结构的方式。使用这样两个表对各个自然数进行质因子的分解和结果累加的算法可以具体地

描述如下：

【算法2-1-1】N！的质因子分解-方法1

1. 建立按升序排列的自然数N以下的质数表

2. 将所有的质数出现次数表项清零

3. 对于从2到N的自然数进行遍历，并且对每一个数n

i

进行下列操作：

3.1 对n

i

进行质因数分解并将n

i

所包含的各个质因子的个数分别累加到相应的质数出现

表项中

在这个描述中，建立质数表是一个相对独立的步骤。既可以直接使用已知的质数表对程序

中的质数表进行初始化，也可以用各种质数表生成算法计算出所需的质数表。因此我们暂时可

以认为建立质数表是一个可以直接编码的基本操作步骤。质数出现次数表项清零也是可以直接

编码实现的，因此不需要进一步地细化描述。对于从2到N的自然数的遍历，在编码中对应着循

环语句，也是可以直接实现的。而对于每一个自然数进行质因数分解，以及将分解的结果累加

到相应的质数出现表项中，则稍微复杂一些，我们一时无法看到它与编码的直接对应关系，因

此需要进一步细化。

对于一个自然数的质因子分解，可以用可能的质数去除该自然数。如果一个质数可以整除

这个自然数，则说明在它的质因子中包含这个质数，这时，我们需要将这个质数所对应的质因

子出现表项的值加1，同时将该自然数除以这个质数，以便将这个质因子从原来的自然数中剔除，

然后再继续重复上述过程，直到它不能再被该质数整除为止。这样就完成了从该自然数中提取

完这一质因子出现次数的工作。如果一个数不能被某一个质数整除，则说明在它的因子中不包

含该质数，因此需要跳过这一质数，继续使用后面的质数进行试探，直到该自然数在历次整除

后所得的商等于1为止。根据这一过程，可以对上面算法的第3.1步进一步具体描述如下：

3.1对每一个大于1的自然数n

i

进行的质因子提取操作如下：

3.1.1 将n

i

保存在存储单元A中，将第一个质数的序号保存在存储单元B中

3.1.2检查A中的数值是否等于1。如果A中的数值等于1，则结束3.1的操作

3.1.3 根据B中的序号从质数表中取出质数，并检查该数能否整除A中的数值

3.1.4如果该质数可以整除A中的数值，则将A被该质数整除所得的商保存到A中，并根据

B中的下标将质数出现表项的值加1，然后转回3.1.3

3.1.5 如果该质数不能整除A中的数值，则将B中的序号加1，转回3.1.2

这些描述已经比前面的描述更加具体，其中的每一步都具有可以直接编码的可操作性。第

3.1.2规定了算法结束的条件。第3.1.3步和第3.1.4步不断地从n

i

中按照从小到大的顺序提取质因

子，而n

i

中的质因子数量是有限的，因此算法总能在有限的步骤之内结束运行并产生运算结果。

具有一定经验的读者已经可以据此写出相应的代码。从计算速度上看，这一算法并不是最优的。

例如，如果一个正整数不能被任何小于等于其平方根的质数整除，则该数就是一个质数。因此

算法可以在试探完所有小于等于该数平方根的质数时停止，而不必等到3.1.2的条件得到满足。

上述算法可以根据这一思路做进一步的改进，以提高运行效率。

在上面这段算法的描述中，质数表可以通过单独的程序段来建立。但是，对上述改进后的

算法再仔细地研究就可以发现，建立质数表的基本操作已经包含在算法的各个步骤之中了。只

要对算法进行一些不大的调整和改动，就可以在质数表初始只包含一个质数2的条件下，在对自

然数序列进行质因子提取的同时，不断地生成新的质数并添加到质数表中。我们把这一算法的

设计留给读者作为练习。

在确定了算法之后，需要进一步考虑数据空间的大小，也就是质数表以及质数出现次数表

中所应包含表项的数量。为此，需要估计质数表中所需要的所有质数的数量。尽管N！是一个

非常巨大的数，但它是N-1个因子的乘积，因此其最大的质因子不应该超过N。题目中N的上限

是60000，因此质数表中最大的质数小于60000。对质数数量及其分布的估计是一个复杂的数学

问题，有各种各样或粗略或精确的数学公式。在这道题目中，我们并不需要精确地知道60000

以下质数的数量，而只需要用粗略估计的方法来确定质数数量一个比较接近的上限即可，因此

完全不需要了解和使用这些公式。对一些辅助性参数的范围进行粗略的估计，是程序设计中常

用的一种技术。我们知道，质数的分布随着数值区间向上增长而趋于稀疏。例如，10以内有4

个质数，100以内有25个质数，200以内有46个质数，500以内有95个质数，1000以内有168个质

数，5000以内有669个质数。依此类推，我们可以保守地估计，在60000以内，质数不超过1/8。

因此，质数表和质数出现次数表只要有7500项就足够了。实际上，在60000以内共有6057个质数，

略多于60000的1/10，因此7500个表项绰绰有余。

除了表项的数量之外，需要确定的还有每项数据存储的类型。我们已经知道，质数表中最

大的质数不超过60000，因此完全可以用16位二进制位的无符号整数来表示。但是，作为良好的

程序设计习惯，一般情况下应该避免使用无符号整数来表示需要进行运算的数据。关于这一点，

在第三章中将有更详细的讨论。16位有符号整数所能表示的最大数值只有32767，小于质数表中

最大的质数，因此质数表项的数据类型需要使用32位的有符号整数。在确定质数出现次数表项

的数据类型时，需要估计在所有质因子中出现次数最多的质因子的最大出现次数是多少。我们

知道，2是最小的质数，在自然数中，每隔一个数就是偶数，包含有2的因子。因此在N！的各

个质因子中，2出现的次数最多。为了便于分析，我们将N！按定义展开成为从1到N的连乘，并

1

对这一由自然数构成的因子序列进行考察。可以看出，从1到N的自然数中，每2

=2个数中就有

一个数包含有一个2，每2

2

=4个就有一个数包含有两个2，每2

3

=8个就有一个数包含有三个2。依

此类推，N！中所包含的2的个数为N/2

1

+ N/2

2

+ N/2

3

+…+N/2

t

，其中t为满足2

t

<= N的最大值，

而除法(/)是整除，即商的小数部分被抛弃。为方便计算起见，我们假设N的最大值为2

16

= 65536，

则这时N！中所包含的2的个数为2

16

-1=65535。这是16位无符号整数表示数值的上限。出于与质

数表项数据类型同样的考虑，我们选择32位的有符号整数作为质数出现次数表项的数据类型。

上面的分析可以推广到其他任意的质数。可以看出，对N以下的每一个质数，我们都可以直

接计算出它在N！中出现的次数，而这正是我们的程序所要解决的问题。这个方法看起来要比

对N以下的各个正整数进行质因子分解更简单一些。这就启发我们考虑另外一条解题思路：用N

以下质数的各次幂分别整除N，并将结果累加，直接得到对N！的质因子分解结果。与这个思路

相对应的算法可以描述如下：

【算法2-1-2】N！的质因子分解-方法2

1．建立按从小到大排序的N以下的质数表

2．将所有的质数出现次数表项清零

3．对从2到N之间所有的质数进行遍历，并对每一个质数Pi进行下列操作：

3.1 将质数Pi放入存储单元A中

3.2 用A中的数整除N，并将结果累加到相应的质数出现表项中

3.3 将A中的数乘以质数Pi并保存到A中，比较A中的数是否大于N

3.4 如果A中的数大于N，结束对质数Pi的处理

3.5如果A中的数不大于N，则转到3.2

这个算法描述比上一个算法要简单很多，实现起来也更方便，而且算法的运算效率也更高。

首先，这一算法是对N以下的所有质数进行遍历，而不是对N以下的所有自然数进行遍历，而N

以下的质数的数量远远小于N以下的自然数的数量。其次，对于每一个质数，所需要进行的除

法的次数也很少，约为log

Pi

N次。【算法2-1-2】唯一的缺点是在计算各个质因子的个数的过程中

无法同时生成质数表，因此质数表需要事先提供或另行计算。从这个例子中可以看到，在相同

的数据结构上可以采用不同的算法，并产生不同的效果。

有时，算法的改进是伴随着数据结构的改变，或者说数据结构的改变直接影响到算法的改

进。下面我们看另外一个例子。

【例2-2-2】多项式的计算-算法和数据结构

这道题目的核心功能是计算两个多项式的和、差和乘积。多项式的运算规则很简单，但是

具体的操作步骤取决于多项式的内部表示方法。因此在这道题目中首先需要确定的是数据结构。

多项式是单项式的代数和，在程序内部的数据结构中需要能表示多项式中所有的单项式以

及它们之间的关系。每一个单项式都有自己的次数和系数，需要有相应的数据结构来存储。各

单项式的代数和是一个一维线性结构，而能够表示这样一种一维线性结构的数据结构不只一种。

常见的选择有单向链表和一维数组。

采用单向链表的基本方法是，以链表中的一个元素代表一个系数不为0的单项式。每一个链

表元素是一个复合结构(struct)。其中的一个成员表示单项式的次数，另一个成员表示单项式的

系数。链表中的各个元素按照降幂的顺序链接起来。下面是使用链表方式表示一个多项式的例

子：



2 6 0 /

52

7x+3x+6

图2-4

采用一维数组的基本方法是，数组中的一个元素只表示一个单项式的系数，单项式的次数

用单项式在数组中的序号，也就是数组的下标来表示。数组的长度应能够分别保存两个最大长

度的输入多项式以及其乘积所产生的结果多项式。下图是用定长一维数组表示一个与图1-1相同

7 5 3

的多项式的例子。在这个例子中，数组的长度假设为16，即假设多项式的最高次数为15。

0 0 0 0 7 0 0 3 0 6

8 0

52

7x+3x+6

图2-5

采用单向链表方式的优点是，存储空间只用于存储系数不为0的单项式。因此当一个多项式

中只有少量的系数不为0的单项式时，它的存储空间的利用率比较高。例如，假设一个多项式只

包含了一个单项式，采用单向链表的方式只需要分配一个元素的存储空间即可。假设次数、系

数和指向下一个元素的指针都各占4个字节，则保存这一多项式所需要的全部存储空间只有12

个字节。同时，由于采用单向链表的方式时往往通过向系统动态申请内存分配来为新节点申请

存储空间，因此无需事先设定对多项式长度的限制。对多项式的长度限制只取决于系统的内存

资源。而采用长度固定的一维数组的方式，则所需要的存储空间取决于题目所允许的多项式次

数的最大值，与正在处理的多项式的项数无关。即使一个多项式中只包含了一个单项式，采用

一维数组的方式仍然需要为(次数最大极限值+1)个单项式分配存储空间。如果每一个系数占4个

字节，则保存这一多项式所需要的全部存储空间为 (次数最大极限值+1) * 4。

数组元素

数组下标



0 0

15

0

0

0

0

尽管采用单向链表的方式可以节省存储空间，但是却增加了算法的复杂程度和编码的难度。

首先，把输入数据保存到链表中的过程就比较复杂。单向链表的元素是动态分配，并逐一链接

到链表上去的。因此，对多项式中的每一个项，都需要申请存储空间，填写相应的次数和系数，

然后再把它链接到链表的尾部。相比之下，一维数组的存储空间是一次性分配的。当采用按允

许次数的极限值预先分配时，只需要一个数组定义语句。对于读入的多项式中的每一个项，采

用一维数组时所需要做的只是根据单项式的次数确定数组元素的下标，然后再将系数填写进去。

其次，在进行多项式的运算时，采用单向链表的方式就显得更为复杂。在进行多项式的加减运

算时，需要同时在两个输入多项式所对应的链表中查找，以便根据各个项的次数来决定它们之

间是否可以运算，然后对次数相同的项的系数进行运算，再将运算结果以及没有对应运算对象

的输入项按降幂的次序链接到保存结果多项式的链表中。对于乘法运算，则需要不断地在保存

结果多项式的链表中查找，以确定其中是否已经存在与两个单项式乘积的次数相同的项。如果

这样的项已经存在，则需要将乘积的系数与之相加，否则，就需要按降幂的方式在结果多项式

链表中的适当位置上插入新的项。而采用一维数组的表示方式，多项式之间的运算就要简单得

多。在进行多项式的加减运算时，只需要对输入多项式所对应的数组中下标相同的元素进行加

减运算，并将结果保存到结果多项式所对应数组中下标相同的元素中即可。在乘法运算中，任

意两个单项式的乘积的次数就是两个单项式次数之和，在使用数组下标表示单项式的次数时，

它就是两个因子元素的下标之和，其系数的乘积可以直接据此保存到结果多项式所对应数组元

素中。当然，对于一维数组的表示方式来说，进行多项式的运算时，需要对数组中所有的元素

进行遍历，而无论其系数是否为0。这在输入多项式中仅有少量的非零项时，也会造成一些无效

计算。

对于数据结构的选择是一个多种因素互相权衡的过程。在这个多项式运算的例子中，单向

链表的存储方式在一些特殊的情况下，在存储空间的效率方面比定长一维数组具有优势。但是

这种优势是有限的。当在最高次数项与常数项之间的非0系数项的数量占到所有项数的1/3时，

两种方案所占用的存储空间就相等了。当非0系数项的数量超过最高允许项数的1/3时，一维数

组所需的存储空间反而小于单向链表。而且根据这道题目的规模，使用一维数组所需的存储空

间不过区区812个字节，与当前计算机系统的内存空间动辄上百兆字节相比，是微不足道的。而

从编程的难度来说，采用单向链表方式则是明显地高于定长一维数组。根据这些因素，可以确

认一维数组是一个更为可取的方案。

在确定了使用一维数组作为程序中的数据存储结构之后，需要进一步确定数组的大小和元

素的类型。对于最高次数为N的输入多项式A和B，其数组的长度应大于等于N+1。对于结果多

项式，其数组长度应大于等于2*N+1，以便保存两个极限长度输入多项式的乘积。数组元素的

类型取决于其所要保存的最大值，而这一最大值出现在两个极限状态下的多项式相乘时。对于

两个系数最大绝对值为M、最高次数为N的多项式，其乘积中单项式系数的最大绝对值为N*M

2

。

根据题目给定的限制，这一最大绝对值为5*10

5

，因此可以使用4字节的int类型来表示。这样，

这一程序所使用的数据结构可以定义如下：

#define N 50

int a[N + 1], b[N + 1], c[2 * N + 1];

很多时候，算法和数据结构的选择不仅取决于任务的内容和性质，而且取决于任务的规模。

同一个问题，如果所要处理的数据的规模较小，则可以采用比较简单的算法和数据结构。但是

当所要处理的数据的规模较大时，则需要采用比较复杂的算法和数据结构，以便降低程序的时

空复杂度，提高计算效率。例如，假设在程序中需要进行数据的记录和查找。当所要处理的数

据项在百十项左右时，可以使用简单的线性表和线性查找算法。但是当所要记录和处理的数据

项有成千上万，甚至更多时，就需要采用排序表、二叉树、Hash表等更便于数据记录和查找的

数据结构和相应的算法了。下面我们看两个例子：

【例2-7】最大的N个数 从文件中读入M个整数，在标准输出上输出其中最大的N(M >= N)个数

对于这道题，很多人最容易想到的是可以把M个整数读入一个数组中，对其按降序排序，再

输出前N个数。当M不是太大时，比如当M在10

6

以下时，这无疑是一种可行的方法。但是如果

M大于计算平台对内存使用的限制时，这种方法就不可行了。这时如果N不太大的话，我们可以

建立一个能保存N个数据的存储结构，暂存读入数据中N个最大的数。每当读入一个新的数据时，

就和这个存储结构中的数进行比较，当新读入的数据大于程序中暂存的数据时，就剔除暂存记

录中最小的数，而将新读入的数据放入暂存记录。暂存记录的存储结构及其内容的更新方法也

与N的大小相关。当N是很小的一位数时，可以使用排序的链表结构。当N为两位数或更大的数

值时，更好的方法可能是使用数组，并辅以适当的索引结构进行排序。如果N的大小也超过了

计算平台对内存使用的限制，那就只能选择外排序算法了。

【例2-8】队列 这是CEOI2006中的一道题，题目的大意是，M(1 ≤ M ≤ 10

9

)个人排队，并根

据每个人的初始位置从1到M顺序编号，然后进行N(2 ≤ N ≤ 50 000)轮的位置变动，使编号

为A

i

的人站到编号为B

i

的人前面(1 ≤ i ≤ N; 1 ≤A

i

, B

i

≤ 10

9

)。问N轮过后，编号为X

j

(1 ≤ j

≤ L)的人站的位置是多少，站在位置P

k j

(1 ≤ k ≤ P)的人的编号是多少(1 ≤ L + P ≤ 50

000)。对程序的内存限制为32MB，运行时限3秒。

对于这道题，可以使用模拟操作的方式来求解：使用一个数据结构表示队列，结构中的元

素表示队列中的每个人，每次位置变动可以直接转换成对结构中元素位置的操作。如果问题的

规模很小，例如M、N、L、P等都在100以内，那么这道题的数据结构很容易选择。例如我们可

以使用由一维数组来表示这一队列，队列中的每一个人对应着数组中的一个元素，这样程序也

很容易写。但是这道题目的规模很大，人员数量的上限是10

9

，数组元素使用4个字节的int型整

数，需要约4GB的内存。这超过了32位计算平台所能提供的资源容量，更远远超过了题目给定

的内存限制。因此在程序中需要使用更有效的数据结构，以减少对内存空间的需求。

因为在题目中人员位置交换的次数远远少于人员的总数，人员位置顺序被打乱的情况也就

不多，所以我们可以设计一种结构，通过记录队列中按顺序连续排列人员的首尾编号来表示这

一组人员，并把整个队列表示为由这种结构节点组成的链表。例如在初始状态下，整个队列只

9

使用一个首尾编号分别是1和10的记录就可以表示。当把编号为A

i

的人移到编号为B

i

的人前面

时，只需要分别找到A

i

和B

i

所在的节点，对它们进行分裂操作，并插入新的节点即可。图2-6是

在初始状态下把编号5的人移到编号为10

8

的人前面时的数据结构的变化：

1

10

9

1

4

->

6

10

8

-1

->

5

5

->

10

8

9

10

(a) 初始状态 (b) 人员移动后的状态

图2-6 【例2-8】队列 中5号人员移到10

8

号人员前面时数据结构的变化

分析各种不同的情况可以看出，对于每一次的位置变动，表示连续排列人员的结构节点最

多增加3个。因为人员位置变动的次数不超过5*10

4

，所以所有节点的总数不超过1.5*10

5

个。设

每个节点占16字节，所有节点共占2.4*10

6

字节，远远小于题目中给定的对内存使用的限制。但

是这一数据结构并不能满足问题对计算速度的要求。在题目中，对于人员移动和位置查询都可

4

能高达5*10，因此对这一结构的搜索操作耗时巨大。例如，每次人员位置移动都需要对这一数

据结构进行两次搜索，一次是查找被移动人员所在的节点，另一次是查找其所要移入位置所在

的节点。在不采取任何优化措施的情况下，当进行节点搜索时需要从头到尾地对结构链表进行

扫描，而每次扫描所需要的时间正比于人员位置的移动次数，因此处理人员位置移动所需要的

总的节点搜索时间正比于人员位置移动次数的平方。同理，人员位置查询所需要的节点搜索时

间正比于人员位置变动次数与查询次数的乘积。无论是人员位置变动次数还是查询次数，其上

限都是5*10

4

，这样线性扫描的结果必定使得程序的运行时间远远超出题目规定的时限。

为避免节点搜索时对结构链表的线性扫描，需要采用数据索引结构以加速对链表节点的搜

索。因为在程序运行时节点的数量是在不断变化的，所以排序二叉树是一种比较好的选择。如

果可以保证二叉树的结构基本平衡，则一次搜索所需访问的节点数量正比于节点总数的对数。

对于这道题目的规模，这样做对程序的性能最大可望有上千倍的改进。

2.3.5 算法的检验

在实际编程中，只有很少的任务可以直接采用已有的成熟算法。在大多数情况下，或者需

要对已有的算法进行一定的改动，以满足所要求解问题的特殊要求；或者很难找到接近任务要

求的现成算法，因此需要从头设计。无论是新设计的算法，还是对已有算法的改动，在付诸编

码前都需要对其进行检验，以尽量保证算法在与实现无关的描述层面上的正确性。

对算法的检验既不是对算法的再次推导，也不是对算法的证明。对算法的检验是在对算法

的理论分析和理解的基础上，通过实例对算法的执行过程进行模拟，以便了解算法在处理不同

的数据时所执行的步骤以及内部数据结构的变化，并且检查算法描述中是否有疏漏或错误。为

此需要使用测试数据或专门为检验算法而准备的数据作为算法运行的输入数据，一步步地根据

算法中的步骤，手工计算出算法所涉及的数据结构和中间结果的变化，直至产生出最终结果，

并将这一结果与预期的结果进行比较，看看是否一致。例如，对于在排序线性表中进行二分查

找算法，我们可以分别使用具有一个、两个、三个以至更多元素的排序数据作为该算法的输入

数据，并分别以存在于这些数据之中和不在这些数据之中的数据作为查找目标，看看在不同的

输入数据下查找究竟是如何进行的，各种中间结果是如何变化的，不同的查找目标对查找过程

和中间结果有何影响，等等。当算法的执行结果与预期不一致时，需要进一步分析问题出在哪

里：是算法描述有误还是我们对算法的理解不准确？抑或是模拟执行的过程有疏漏？通过这样

的检验，不仅可以加深对算法的理解，有助于编码和对代码的调试，也有可能发现算法中潜藏

的错误。

2.4 编码：从算法到代码

在完成了包括算法和数据结构在内的方案设计并经过认真的检查之后，就可以进入编码阶

段，把设计方案付诸实施了。编码是使用编程语言对程序的解题步骤、算法和数据结构进行操

作性描述的过程。编码工作依据程序的设计方案，但并不仅仅是对解题步骤和算法的简单翻译。

在编码过程中，有其特别需要注意的要点和方法，以保证编码的结果既能完整正确地体现设计

方案的思想，又能充分利用编程语言的描述能力，简洁有效地实现程序。

2.4.1 代码的结构

在编码过程中首先需要关注的是程序的结构。编码是一个自顶向下的过程，保持良好的程

序结构所需要注意的要点就是对计算过程描述的层次性。所谓层次性就是对程序的描述要自顶

向下，逐步细化，在每一个层面上只描述本层面直接使用到的计算步骤和控制机制。至于各个

计算步骤的细节，则在下一层面再进行细化的描述。这样逐级细化的过程，一直要进行到所有

的操作都转化为基本的C语言计算/控制语句为止。

描述过程自顶向下的层次性是通过函数的调用和定义来实现的。在对每一层的各个计算步

骤进行描述时，如果一个计算步骤由于过于复杂而不能使用简单的C语句直接描述它的全部细

节，我们就可以使用一种抽象的方式来描述它：用一个函数来表示这个计算步骤，然后在对这

个函数具体定义时再详细描述计算步骤的操作细节。在使用函数来表示一个计算步骤时，需要

给它起一个名字来说明这个函数所要完成的任务，把这一计算步骤所需要的原始数据做为参数

传递给这一函数，同时说明这一函数的返回值或者以其他方式返回的计算结果和对外部环境的

影响。

在C语言中，一个程序的顶层函数是main()。在main()函数内的语句层面上，应该只描述计

算的基本步骤，包括对程序调用参数的检查和错误处理，以及对大的计算过程的控制。至于各

个计算步骤的细节，则需要留待下面的层次去逐步展开。这样既可以清晰准确地使用程序设计

语言描述计算的过程，也可以避免同时被过多的编码细节所困扰。下面我们看几个例子。

【例 2-1-3】 N！的分解-程序编码

根据对问题的分析和方案设计，我们可以写出相应的数据结构定义和顶层代码：

#define MAX_N 60000 // N的最大值

#define MAX_ITEM MAX_N / 8 //表项的最大值

int primes[MAX_ITEM], f_num_tab[MAX_ITEM]; // 质数表和质数出现次数表，均初始化

为0

int gen_primes(int n, int *prime); // 生成质数表

void gen_factors(int n, int m, int *prime_tab, int *num_tab);

// 分解质因数，填入质数出现次数表

void print(int m, int *num_tab, int *prime_tab); // 打印结果

int main(int c, char **v)

{

int m, n;

if (c < 2) { // 检查命令行参数的个数

fprintf(stderr, "Usage: %s Nn", v[0]);

return 1;

}

n = atoi(v[1]);

if (n < 2 || n > MAX_N) { // 检查命令行参数的值

fprintf(stderr, "N must be between 2 and %dn", MAX_N);

return 2;

}

m = gen_primes(n, primes); // 生成质数表

gen_factors(n, m, primes, f_num_tab); // 分解质因数，填入质数出现次数表

print(m, f_num_tab, primes); // 打印结果

return 0;

}

在这段main()函数的代码中，第3行到第6行检查本程序被调用时是否带有所需要的参数。如

果用户在调用本程序时没有给出必要的参数，则程序向用户提出警示，说明程序的调用格式，

然后结束运行，并返回1说明程序非正常结束。代码的第7行把用户所提供的参数n转换为内部的

表示形式，然后再进一步检查这一参数的值是否在规定的范围内。上述这些步骤的每一个都是

基本的操作，只涉及一两条基本的C语句。其中fprintf()和atoi()是在和中说明、

在标准函数库中提供的标准库函数，分别完成向指定文件输出信息和将由数字字符组成的字符

串转换为整型数的工作。

这段main()函数代码的第12行到第14行是程序功能的主体部分。这部分描述了完成程序功能

的3个步骤，即生成质数表，对N！进行质因数分解并记录各个质因数出现的次数，以及打印输

出结果。这3个步骤都是比较复杂的步骤，因此在顶层描述中只使用函数对它们进行抽象的描述。

生成质数表时需要知道所要生成的最大质数的大小以及质数表的存储位置。因此质数表生

成函数gen_primes()需要两个参数，一个是n，说明所要求的是小于等于n的最大质数，另一个是

整型数组prime[]，用来保存所生成的质数表。函数gen_primes()返回一个整型数，表示所生成的

质数表中表项的个数。

在对N！进行质因数分解并记录各个质因数出现的次数时，需要知道N的大小、所要使用的

质数表的大小、以及质数表和质因数出现次数表的存储位置。因此函数gen_factors ()需要4个参

数，第1个是n，表示N的大小；第2个是m，说明所要使用的质数的个数；第3个是质数表prime[]，

按照递增的顺序保存所需要用到的质数；第4个是质因数出现次数表f_num_tab[]，用来保存对n!

的分解结果。函数gen_factors ()只填写质因数出现次数表f_num_tab[]，因此没有返回值。

输出结果的工作是由函数print()完成的。这个函数在工作时需要知道质数表、质因数出现次

数表以及表中需要输出的有效表项，因此需要三个参数。

对照一下【算法2-1-2】，可以看到关于质因数出现次数表的初始化，也就是算法中的步骤2，

没有对应的描述语句。实际上，对于质因数出现次数表的初始化是由编译系统隐含实现的。质

因数出现次数表f_num_tab[]被定义为一个全局变量，因此其初始值被编译系统自动设置为全0。

这样，在程序的代码中就不需要显式地描述对该数组的初始化。

在完成了第一层次的编码工作之后，产生了三个新的、等待实现的函数gen_primes()、

gen_factors ()和print()。这几个函数的定义都很简单。下面是函数gen_factors ()的定义：

void gen_factors(int max, int p_no, int prime[], int f_tab[])

{

int i, n;

for (i = 0; i < p_no; i++) {

for (n = prime[i]; n <= max; n *= prime[i]) {

f_tab[i] += max / n;

}

}

}

这段函数就是【算法2-1-2】中步骤3的直接翻译。一些初学编程的人往往会觉得，这么短的

程序段是否有必要单独提出来组成一个独立的函数。实际上，这个程序的全部代码加在一起的

长度也不过几十行。如果单纯从代码的长度来看，整个程序的全部代码完全可以放在一个main()

函数中。这也是很多初学编程的人常常选择的方法，然而却是一种不好的方法。把全部或大量

的代码放在一个函数中，会把大量不分层次、不分步骤的细节同时展现出来。这样做的最大问

题是破坏了描述的层次结构和清晰程度。对于比较小的程序段，因为程序很短，分析和理解起

来可能不会很困难。但是这往往会使初学者养成不良的程序设计习惯，当程序的段落比较大时，

会给准确地把握程序的结构和程序的执行过程带来较大的困难。特别是当程序需要进行后期维

护时，大量不分层次的代码堆积在一起会带来很多不利的影响，有可能使得程序难于理解，难

于调试，而且这种不利的影响会随着程序规模的增大而迅速显现和增强。

从心理学的理论和大量实际的编程经验来看，一般人所能迅速理解和把握的程序段的长度

是有限的，越长的程序段理解起来越困难。当大量的代码不分层次地放在一起时，我们的注意

力往往会不适当地被一些细节所吸引，程序中的关键内容，例如程序的基本解题思路和计算过

程，往往会隐藏在大量无关的细节中，特别是当程序段落中有较多的条件判断和分支时。可以

想象，要在一段长长的代码中理清程序执行过程的基本脉络，分析出程序中存在的问题，所面

临的困难会远远大于分析一段短小得多的代码。

将程序按层次逐级分解，是分治思想在编码过程中的体现。它可以使我们在编码的每一阶

段所需要关注的代码量迅速减少。通过自顶向下的层次描述，可以使我们首先在大的计算步骤

上理解和把握程序的执行过程，保证程序在大的计算步骤上执行正确。在这个基础上，通过逐

层细化的方法，就可以理解和把握程序执行的每一个步骤，保证每一个执行步骤的正确。

把程序逐级分解成为较为短小的函数，不仅有助于对程序的理解，而且对于程序的调试和

维护，以及代码的重用，也都很有帮助。在编写和调试一段代码时，往往需要关注与这段代码

相关的前后文。一般情况下，一个合理定义的函数应该是一个相对独立的程序段，其与外部的

交互只是通过函数的参数和返回值来完成的。因此在编辑和调试一段函数中的代码时，我们所

需要关注的仅仅是这个函数中的代码。较短的函数可以使我们对函数的整体一目了然。在一些

经典的程序，例如Unix操作系统的实现代码中，我们常常可以看到只有两三行代码的函数，有

些函数的函数体甚至只有一行代码。这样做的目的就是为了增加程序的可读性和可维护性。

从实践经验来看，一般函数的长度最好不要超过显示器一屏所能显示的长度，也就是20行

至30行。当函数的长度超过这一长度时，就应该考虑是否进行适当的分段，把一些关系紧密，

可以构成独立功能模块的语句集中在一起，构成新的函数。有些函数，主要是运算过程较为复

杂的数值计算函数，由于计算流程的问题，代码较长，代码内部的耦合比较紧，比较难于分成

较小的独立段落。当拆分成若干个函数时，往往会由于大量的参数传递和频繁的函数调用而显

著地降低程序的效率。对于这类函数，可以作为特例处理。即使如此，也要注意在可能的情况

下尽量控制函数的长度，在代码的效率与可理解和可维护性之间找到适当的平衡点，使一个独

立函数的代码不至于过长。

在对算法进行编码时，不但需要遵循算法的基本原理，也需要关注算法的具体执行过程和

实施细节。有时，一些执行步骤的调整和实施细节的改动对于程序的效率会有较大的影响。下

面我们看一个例子：

【例2-9】硬币兑换 计算出N元人民币兑换成1分、2分和5分的硬币，有多少种可能的组合。

这个问题可以有多种解法，其中最直观的就是枚举法。我们可以把三种硬币各种可能的组

合逐一列出，然后检查其中哪些组合的硬币总值正好符合要求，并将其记录下来。至于如何枚

举，则可以有不同的方法。例如，我们可以按照1分、2分和5分的顺序进行枚举，即把这一枚举

过程写成一个三重循环，对1分硬币的枚举在最外层，对5分硬币的枚举在最内层，在每一种硬

币组合被枚举出来之后，计算其币值，判断其是否符合要求。这样，这一计算过程的计算复杂

3

度应是O(N

)。如果我们调整一下循环的次序，首先对5分和2分进行枚举，只要这两种硬币的组

合币值小于等于N元，总可以找到满足要求的1分硬币的数量，因此就没有必要再对1分硬币进

行枚举了。这样，同样是枚举，这一计算过程的计算复杂度就降到了O(N

2

)，计算效率会有明显

的改进。对于这一问题，计算复杂度为O(N

2

)仍然是较低的效率。仔细分析，可以找到O(N)的枚

举算法和O(1)的非枚举算法。我们把这留做练习。

2.4.2 编码的质量

除了保持良好的程序结构之外，在编码过程中所需要注意的第二个要点就是代码描述的准

确、完整和简洁。这些是代码质量的基本指标。所谓准确，就是说代码应该严格地根据解题步

骤和算法的规定，完整地描述具体的计算过程。解题步骤和算法的每一步是否都在代码中得到

正确的描述、各个计算步骤的前后顺序是否正确、条件判断的内容和位置是否恰当，这些都需

要认真地检查和推敲。例如，在进行条件判断时变量n究竟应该是大于0 (n>0)还是大于等于0

(n>=0)，在for语句中循环继续的条件究竟应该是i < n还是i <= n，抑或i <= n + 1，移位的次数究

竟是p还是p – 1,... ...，这类地方都是容易发生错误、影响程序编码准确性的地方，需要格外加以

注意。在编码的准确性方面，另一个需要特别注意的地方是对程序处理数据的边界和特殊条件

的判断。在这方面稍有不慎就有可能产生错误。下面我们来看一个例子。

【例2-10】质数判断 编写一个判断一个正整数是否是质数的函数，其函数原型如下：

int is_prime(int n);

这个函数的直观算法就是从2开始依次用所有小于等于n的平方根的数来测试，看看是否可

以整除n。如果这其中任何一个数可以整除n，则说明n不是质数，否则n就是一个质数。为了提

高函数的计算速度，我们可以首先判断n是否是偶数，然后再依次使用所有小于等于n的平方根

的奇数来测试，看看是否可以整除n。这样可以写出如下的代码：

int is_prime(int n)

{

int i;

if (n % 2 == 0)

return 0;

for (i = 3; i <= sqrt(n); i += 2) {

if (n % i == 0)

return 0;

}

return 1;

}

这段代码看起来没有什么问题，但是实际上这里面有两个明显的错误：当输入的参数为1或

2时，函数会给出错误的答案。根据定义，1不是质数，但是由于1不能被除其自身之外的任何数

整除，而程序中没有对1的专门判断，因此当参数n等于1时，函数只能返回1，表示函数认为1

是一个质数。2是质数，但是由于2又是偶数，因此在遇到第一个判断语句时就符合条件，因此

函数只能返回0，表示函数认为2是合数。这个例子尽管简单，但是却典型地说明了在程序中关

注边界条件和特例的重要性。

所谓简洁，就是说代码的描述应该避免冗余。对计算过程的描述应该直截了当，避免不必

要的语句。例如，如果一个变量在计算过程中被用来保存中间结果，那么就没有必要对它进行

初始化。又例如，在程序中如果有多处需要用到相同的计算过程，则应该通过使用函数定义的

方式描述这一计算过程，在需要使用这一计算过程的地方对这一函数进行调用，而不应该在多

处分散地重复实现。这样不仅可以使得描述简洁，而且可以增加程序的可维护性。在相关功能

需要进行修改时，可以保持对相关功能描述的一致性，避免引起不必要的混乱，大大减少工作

量，提高工作效率。此外，在编码过程中还需要注意，对语言的使用要准确，避免由于疏忽或

对语言的误解而产生编码错误。

所谓完整，是指算法描述中的所有步骤以及相关的细节都需要在代码中有所体现，不可遗

漏。当利用C语言的默认操作，例如对全局变量的初始化等，来隐含地实现算法中的某些步骤

时，一定要保证C语言中的默认操作与算法中所需要的操作是一致的。对于初学者来说，最容

易忽略的是对变量做必要的初始化。对于默认初始值不确定的局部变量来说，直接使用未经初

始化的局部变量的值会引起程序运行时非确定性的错误。

2.4.3 代码的可维护性

在编码过程中所需要注意的第三个要点是程序代码的可维护性。所谓代码的可维护性是指

代码应该容易阅读、理解和修改，并且在一定的范围内适应合理的需求变动。使用函数和宏，

精心设计合理的程序结构是增加代码可维护性的重要方法。例如，在【例 2-1-3】的代码中，

程序所允许的最大输入参数是由常数宏MAX_N来规定的，质数表和质数出现次数表的大小是由常

数宏MAX_ITEM来规定的，而且常数宏MAX_ITEM是根据MAX_N计算得出的。这样，当需要改变程序

所允许的最大输入参数时，只需要修改常数宏MAX_N的定义就可以了。在这段代码中，质数表的

生成、质数出现次数表的生成以及结果的打印输出都是通过函数的定义来实现的。当需要面对

不同的输出格式的要求，或者发现了更有效的质数表生成算法时，就可以只针对相关函数进行

必要的修改，而不必考虑程序的其他部分。

为增加代码的可维护性，应该使代码易读易懂。这就要求我们尽量使用简单准确的描述方

法，避免为了过度追求程序的简练而使用不易理解的技巧和复杂的表达式、

带有不易发觉的副

作用的语句、

以及容易引起误解的描述方式。一些教科书练习题中的表达式，例如

p=(i++)+(i++)+(i++); x = y+++++z;之类的语句，只有智力测验方面的意义，在编码当中应当

避免。这些语句不但必须仔细思考才能理解其中的含义，而且往往带有歧义性。例如表达

式y+++++z就可以有不同的解释。而且这个表达式在很多编译器上被认为在语法上是错误

的。

代码的可维护性是一个比较复杂的问题，涉及到多种程序设计技术，并且可能影响到程序

的结构和风格。我们在第九章中关于程序设计风格的部分还会进一步讨论。

2.4.4 代码中的注释

在编码过程中所需要注意的第四个要点就是在代码中要加入必要的注释。注释的作用是为

了帮助人们更好地理解程序，不论是对编程者自己还是对其他可能的程序阅读者。程序的编写

是一个复杂的智力活动，程序是用编程语言编写、由计算机执行的运算过程。因此程序所表达

的内容对于人来说并不是很直观的。对程序的理解随着时间的流逝而逐渐淡忘，对程序重新理

解的难度随着程序规模的增加而增加。有些源代码，在经过几个月、几个星期、甚至几天之后，

连它的编写者都很难准确地说出每一个段落和每一个语句的含义，以及一些关键的数据结构和

算法的选择理由，更不必说其他因为维护等目的而第一次接触这些代码的人了。因此，必要的

注释对于理解代码，增加程序的可维护性具有非常重要的作用。

从实际经验来说，一个程序只要生存周期在一天以上，就有必要加以注释。在一个值得注

释的程序中，即使代码再短，至少也应该有一处注释，那就是在代码文件的开头部分应当说明

这个程序的目的和作用，程序编写所依据的文件，例如是哪本书上的哪道题，或者是哪个项目

的需求和设计文档等，以及程序的使用方法，程序对运行环境和输入数据的要求和限制等。当

然，最好再加上作者姓名和编写时间，以备检索。根据题目要求写出程序是一个复杂的过程，

而在没有注释的情况下从程序代码倒推出题目要求则是一个更加困难的任务。除此之外，在程

序中比较复杂、难于直观地理解的地方，也需要加以注释说明，例如程序所采用的算法和数据

结构，以及采用的理由，复杂代码段落的含义等等。在注释中需要注意的是，注释内容应该与

代码含义一致。在代码进行修改时，相应的注释也应该随之更新。否则，大量累积下来的程序

代码就会变成一堆无法理解的天书，无法利用的废物，占用磁盘空间的垃圾。

2.4.5 代码的检查

在编码过程中，在每一个阶段性的编码工作完成后，需要做的第一件事情就是检查代码中

是否有由于疏忽和键入错误引起的语法错误。对代码的语法检查可以借助于编译系统，进行语

法检查的代码段的大小可以根据每个人的经验和习惯。对于初学者，在一个复杂的函数或者一

段较长的、具有相对完整功能的代码完成之后，就应该对代码进行一次编译，看看是否有什么

语法错误。在积累了一定的经验之后，检查性编译的段落规模可以适当地扩大，但至少在一个

独立的源文件阶段性地完成之后，需要对整个文件编译一次，然后再进行后续的工作。较小的

编译段落有助于对错误的定位。大多数编译系统在发现了语法错误之后，都会给出比较详细的

错误信息，例如错误所在的行号、错误的类型、错误的上下文、以及错误的严重程度等。根据

这些信息，往往可以很快地找到和改正产生语法错误的地方。对某些错误，一些编译系统可能

产生不准确的错误信息。例如，当括号或字符串界定符不匹配时，往往会影响编译系统对随后

代码的正确分析。这时编译系统往往会产生一连串不正确的错误信息，报告一些实际上可能不

存在的错误。遇到这种情况时，需要注意的是不要被大量的错误信息所迷惑。这时应该做的是

改正编译系统报出的前几个可以确定的语法错误，然后再调用编译系统重新对代码进行编译，

看看会产生什么结果。很可能在改正了一两处括号不匹配的错误之后，大量的错误信息就一起

消失了。现代计算机的运行速度很快，对一个几百行的程序的编译只不过需要几秒钟的时间。

充分利用计算机系统的功能和性能，对于提高工作效率是很有帮助的。

2.4.6 代码中常见的错误

代码中出现的错误五花八门，难以一一尽述。本节仅列举几个在初学者程序中最常见的错

误及其可能出现的故障现象，供读者举一反三。

在代码中常见错误之一是对变量，特别是局部变量未赋值即引用。C语言对于全局变量的

默认初始值有明确的规定：在未赋值初值的情况下，全局变量的值为0。对于局部变量的缺省初

始值，C语言没有任何的规定。如果由于全局变量未赋正确的初值而引起程序执行的错误，那

么这种错误是固定的，也比较好查找。但如果对于局部变量未赋值即引用，那么最容易引起的

错误现象是程序的运行状态不稳定：可能程序在多次运行中偶尔出错，也可能程序在多次运行

中偶尔正确；如果这一变量被用作数组下标，那就极有可能使程序崩溃。产生这种现象的原因

是由于未被明确赋值的局部变量的初始值是不确定的，在多数情况下取决于这个局部变量所使

用的存储空间在此之前的用途。这样初始值不确定的变量被用在程序中，自然会引起执行过程

或计算结果的不确定。如果被用作数组下标，当其初始值超过了数组的范围，就会造成地址访

问越界，并引起程序的崩溃。不同版本或不同操作系统平台上的编译系统对局部变量的初始值

的处理也不尽相同。在有些编译系统中，当使用某些调试选项时，编译系统可能会给局部变量

自动赋一个确定的数值，而当不使用这些选项时，编译系统就不会处理局部变量的初始值。这

也可以解释为什么有时程序在一种平台（例如Windows）上运行正确，而在另一种平台(例如Linux)

上运行不正确；在一种编译选项（例如-Debug）下运行正确，而在另一种编译选项（例如-Release）

下运行不正确。下面是一个局部变量未初始化引起程序运行不稳定的例子：

for (i = 0; i < M; i++) {

if (a[i] > max) {

max = a[i];

n = i;

}

}

这段代码的功能是在数组a[]的M个元素中找出最大的元素，把它的值保存在变量max中，

下标保存在变量n中。在这段代码中，因为变量max没有赋初值，所以在for语句的第一次循环时，

它的值是一个随机确定的数。如果碰巧这个数小于数组a[]中最大的元素，则程序可以产生正确

的结果；否则，不但变量max中保存的依然是那个随机确定的初始值，变量n中的结果也是一个

没有意义的数。为使这段代码正确地执行，需要对变量max和n都赋初值：

for (i = n = 0, max = a[0]; i < M; i++) {

if (a[i] > max) {

max = a[i];

n = i;

}

}

大多数编译系统都可以对程序源代码中这类语义错误进行检查和报告。因为此类错误并不

是语法错误，不影响目标码的生成，所以编译系统只在使用了必要的编译选项后才对这类错误

产生告警信息，提醒编程人员注意这一程序中潜在的危险。例如，在gcc上，可以使用-Wall选项，

使编译系统对源程序进行严格的检查，报告所有可能引起程序错误的地方。在其他集成化编程

环境，如MS VC++/IDE中，也可以通过配置工具设定输出告警信息的级别。

在程序中另一个容易出现的错误与数组的使用有关。在C语言中，具有n个元素的数组的下

标范围是从0到n-1。超越这一下标范围对数组元素进行访问就会引起地址越界。例如，有人在

对具有n个元素的数组进行遍历时将循环控制语句写为for (i = 0; i <= n; i++) …，并且使用变量i

作为数组元素下标。这样，在循环语句中访问的最后一个数组元素就越出了数组的范围。在向

字符数组中复制字符串时也有类似的问题。当复制字符串时，字符数组必须有足够的空间来保

存被复制的字符串。这不但包括字符串中所有的字符，还必须包括字符串结束符(‗0‘)。因此字

符数组的长度必须大于字符串的长度。有些人忽视了这一点，只按照字符串长度分配了存储空

间而没有给字符串结束符预留位置。例如，下面的代码：

char s[4];

strcpy(s, "test");

将字符串"test"复制到数组s[]中，其中strcpy()是一个字符串复制的标准库函数，其功能是将

第二个参数指定的字符串复制到第一个参数指定的数组中。在这段代码中，字符串的正文部分

已经占据了4个字节，因此字符串结束符只能写到从s的起始地址开始的第五个字节，也就是s[4]

中。这样就越出了字符数组s的存储空间范围。这种地址越界所产生的后果取决于多种因素，因

此是难以预料的。如果幸运的话，程序可能在多次运行中都不出现错误，但在更多的情况下，

程序可能会产生莫名其妙的错误，甚至崩溃。为避免这类错误的出现，可以在编码时为字符数

组多分配几个字节的存储空间，并使用可以指定字符串复制长度的函数来进行字符串的复制。

下面是一段代码样例：

char str[MAXLEN + 1];

… …

strncpy(str, str_src, MAXLEN);

str[MAXLEN] = ‗0‘;

其中函数strncpy()是一个功能与strcpy()相近的标准库函数，其第三个参数是一个整数，表示

允许复制字符串的最大长度。在上面的代码中，当str_src的长度大于MAXLEN时，strncpy()只

复制其前MAXLEN个字符以避免地址越界，并确保在任何情况下str[]中保存的都是一个带有结束

符的完整字符串。

运算符优先级和结合方式错误也是代码中经常出现的，并且不易发觉。例如，表达式 1 <<

a + b等价于1 << (a + b)，但是却经常会被误解为(1 << a) + b。C语言中的运算符很多，优先级和

结合关系也比较复杂，很不容易记忆准确。当出现这类问题时，往往会由于习惯性的错觉而对

代码中的错误视而不见。与前面几种错误不同的是，这类错误是确定性的错误。如果错误存在，

那么在每次测试中、在任何平台上，错误总会以相同的方式重复出现。为避免这类错误的出现，

在表达式中应当避免过分依赖对运算符的优先级和结合方式的记忆，而应该多使用一些括号，

以便准确地表达我们所需要的计算顺序。

2.5 测试和调试

在程序通过了语法检查，生成可执行文件之后，紧接着需要做的工作就是对程序整体或其

中的某些部分进行测试，看看它们是否能正确运行，是否能满足任务对程序功能和性能方面的

要求，并调试和修改测试中发现的错误。在程序设计过程中，测试可以分为两个阶段：第一个

阶段是在部分或全部编码初步完成后，目的是检验程序各个部分的代码是否可以正常运行，并

大致观察程序是否可以输出基本正确的结果。第二阶段是在代码基本调试完毕，程序的各个部

分运行基本正常之后。这时的测试目的是确保程序在设计和实现的各个阶段工作正确，程序的

功能和性能都可以满足题目和任务中提出的各项要求。其中第一阶段的测试与对程序的调试紧

密地耦合在一起，从测试的范围、深度、方法和手段来看也相对简单，因此往往与调试划在一

起。第二阶段的测试在测试的范围、深度、方法和手段方面都和第一阶段有很大的不同，在工

作流程上也是一个相对独立的阶段。测试和调试单元的大小既取决于程序的性质和规模，也取

决于编程人员的经验和工作习惯。一般来说，对于规模较大的程序，应该首先对程序的各个部

分分别进行测试和调试。初学者可以选择小一些的程序单元，例如单个或一组较短的函数开始

测试。对于较短的程序，例如两三百行以内的程序，也可以一次性地对整个程序进行测试和调

试。

对程序的测试可以分为―黑盒测试‖和―白盒测试‖。所谓黑盒测试是假设对程序内部的结构和

执行机制没有任何的了解，只是根据任务对程序的要求生成测试数据，检查程序是否能产生预

期的结果。白盒测试是根据对程序的结构和实现机制的了解，有针对性地生成测试数据，对程

序结构的各个部分进行测试，检查程序各部分代码是否运行正确。在编程人员对程序的测试中，

往往是交替使用这两种方法。在程序完成后，首先根据在问题分析时确定的原则和生成的测试

数据，对程序进行黑盒测试。然后，根据测试中发现的问题以及对程序结构的理解，再有针对

性地对程序中特定的部分进行白盒测试。

2.5.1 调试的基本方法

除了少数极其简单的程序外，几乎没有什么程序可以不经过调试而交付使用的。即使是已

经交付使用的程序，也经常会在使用中发现程序中存在的错误和问题，需要通过调试的手段来

定位故障，改正错误。看看各种软件工具和产品的版本号及其维护说明，就可以明白这一点。

有些人宣称，他们写的程序不需要调试即可正确地运行，并交付使用。这样的人即使有，也是

凤毛麟角，大多数人是很难望其项背的。因此，至少对大多数人来说，调试工作是程序设计中

的一个必不可少的步骤。

程序调试的大致过程是，首先确定故障现象，然后确定程序在产生故障或表现出故障前的

执行路线，以及一些关键变量的值，然后再着手对故障进行分析和定位。在确定了故障的原因

和引起故障的代码后，再着手排除。在故障调试中，重要的是发现和确认引起故障的代码段，

也就是故障点，及其错误的原因。在弄清了这些问题之后，一般情况下对代码错误的修改是比

较容易的。

故障现象是观察程序出错过程的第一个窗口。故障现象包括程序是在什么环境和条件下、

在处理什么样的输入数据或操作命令时产生的错误、是所有的测试数据都出错还是只有部分测

试数据出错、以及程序执行的过程是否正常结束、产生的错误结果的具体内容、产生错误结果

前程序运行的时间、程序输出的提示信息、操作系统输出的错误信息、错误是固定出现还是随

机性地出现、每次出现的错误是否一样、在同样的输入数据和运行条件下程序的错误是否可以

重现、等等。这些故障现象为故障的判断和定位提供了初步的线索。例如，一个无法终止的程

序很可能是由某个循环语句中没有终止条件、或者给定的循环终止条件错误，使得终止条件无

法达到所引起的；错误的输出结果很可能是由相关的计算公式或编码实现的错误引起的；不确

定性的错误以及引起程序崩溃的错误原因很可能是指针使用错误或数组访问时的地址越界、以

及某些变量未初始化所引起的；等等。在对故障现象确认完毕后，应当适当地记录，以备在排

除故障的过程中参考和在排除故障之后复查。必须认识到，准确全面地认定和描述程序运行时

出现的故障现象，是迅速有效地排除故障的最重要的先决条件。

调试的第二步是对已发现的故障进行分析，根据程序的结构和故障现象，判断故障产生的

原因和位置，并对分析的结果进行检验和确认。对故障的分析至少应该包括下列几项：故障的

性质是什么、故障可能发生的位置在哪里、产生故障时程序的执行路线是什么、与故障相关的

变量有哪些、与这些变量相关的操作有哪些、这些相关变量在各个关键点的值应该是什么。在

得到对故障现象的初步分析结论之后，需要对这些结论进行检验和确认，以保证在对故障进行

调试时有一个可靠的基础。

调试工作的第三步是确定程序产生错误时的执行路线，确认错误产生的位置或区间，然后

再在故障产生的区间进行深入的检查和分析。在一个程序中往往有多个分支，一个结果的产生

往往要经过很多的条件判断，在不同的条件下执行不同的语句。在着手改正程序中存在的错误

之前，必须先弄清程序的执行路线，也就是到底是哪一组语句的执行在给定的运行条件下产生

了程序的错误，否则有可能把大量的时间和精力花在检查和分析与错误无关的代码上。

在上面这些工作完成后，我们就会对程序错误的产生原因有一个基本的判断。在此基础上

使用调试工具，或者在程序中插入必要的调试代码，就可以逐步地判断故障产生的位置和原因，

形成对错误进行修改的初步方案，并依据这一判断和方案来修改相应的代码。至于这一判断和

方案是否正确，只能在修改完成之后通过进一步的测试来检验。对于比较复杂的程序，对程序

中错误的彻底改正往往不是一轮调试工作所能完成的。这时需要按部就班地重复上述调试过程，

并将调试过程，包括使用的数据、修改的位置、产生的效果等一一记录下来，进行仔细的分析，

以便一步步地接近产生错误的实际位置，发现产生错误的真正原因。这时切忌无目的的随意修

改代码，以免引入新的错误。

2.5.2 故障的检查、确认和修改

常用的故障检查和确认方法有两种：一种是阅读和检查代码中相关的部分，分析可能产生

错误的原因；另一种是观察程序的执行路径以及相关变量值的变化，并由此推断出错误的原因。

对于规模比较小的简单程序，一般采用第一种方法。例如，如果一个程序在执行过程中进入了

死循环，而这段程序中只有一个循环语句，我们这时首先应该做的就是检查这段代码。假设这

段代码是这样的：

for (i = n; i >= 0; i++) {

... ...

}

仔细阅读，我们会发现，在for语句中，循环控制变量的修改方向错了。一般情况下，循环

变量的值是从0开始向n遍历的。而这段代码由于计算的要求，循环变量的值是从n开始向0遍历

的，因此循环变量i的值应该是递减的。编程者可能由于习惯性的原因把i—顺手写成了i++，并

因此导致了程序长期在这段代码中执行而无法结束。

当然，并不是所有的故障原因都是这么简单，仅仅通过仔细阅读代码就可以很容易地发现

和确认。对于不能通过阅读代码发现和确认的故障，需要进一步观察相关变量的值，并根据这

些值与预期值之间的差异做出进一步的分析和判断。

对变量值的观察可以通过在适当的位置设置临时的打印语句来完成。在使用调试工具时，

特别是在使用具有图形界面的集成调试工具时，也可以在适当的位置设置断点，使程序暂停运

行，以便直接检查相关变量的值。需要注意的是，在观察程序变量的值之前，需要对变量的正

确值有一个准确的估计。这样才能在得到变量的实际值时做出判断和分析。

【例2-11】使用浮点数作为循环控制变量引起的错误 假设在程序中引起死循环的是下面这段循

环语句：

for (i = 0.0; i != 1.0; i += 0.1) {

... ...

}

仔细阅读这段代码，似乎看不出有什么问题：循环变量i从初始值0.0开始，在每次循环之后增加

0.1，在10次循环之后，i就等于1.0，于是循环条件就不满足，循环就应该停止了。为了进一步

考察程序死循环的原因，我们可以检查循环变量i的值在每次循环中的变化。为此，可以在循环

中加上一条打印语句：

for (i = 0.0; i != 1.0; i += 0.1) {

... ...

printf(―i = %fn‖, i);

}

或者使用调试工具在循环语句中设置断点，在每次循环中检查变量i的值。当我们使用打印语句

时，会在屏幕上看到如下的输出结果：

i = 0.0

i = 0.1

i = 0.2

i = 0.3

... ...

i = 0.9

i = 1.0

i = 1.1

... ...

从变量的输出结果看，可以得到两点结论：

3 循环变量i确实是按照我们的设想，以每次0.1的增量从0.0变到1.0，然后再继续增长。

4 当循环变量i等于1.0时，循环依然没有终止。这说明循环条件依然满足，也就是说i != 1.0

这一条件在我们看到i等于1.0时依然成立。可能我们一时还弄不清这其中的原因，但至

少知道程序是在这一点上出了问题。在没有准确地理解产生这一现象的原因之前，我们

至少可以想些办法，试试绕开这一现象。例如，我们可以把循环条件由i != 1.0改为i < 1.0，

看看会产生什么结果。

在检查和确认了产生错误的原因之后，经过分析和思考，找出排除故障的方案，就可以着

手修改代码了。在修改代码时需要注意的有两点：第一，当程序有多处错误时，一般一次只修

改一处错误，除非有其他的错误与这一错误紧密地耦合在一起。第二，在修改代码时，需要保

留原来代码的副本，以备在判断和修改方案不正确时恢复程序的原状。保留代码副本的方法有

多种。对于局部的少量错误，一般不直接在原来的代码行上修改，而是采用对需要修改的代码

用注释或条件编译加以屏蔽的方式，并用修改后的代码取代原有代码的位置。对于一个错误涉

及程序中多处或大段代码的情况，可以采用保留原文件副本的方式。这样，一旦对故障定位不

准，修改发生错误，就可以很方便地恢复程序的原状，并重新开始对故障的定位和修改。在对

故障修改完毕后，首先要针对修改的部分进行测试，以保证已经发现的故障已被正确地修改，

同时还需要重新进行完整的测试，以确认在修改故障的过程中没有引入新的错误。

2.5.3 常见的故障类型和调试方法

程序调试中常见的故障一般可分为三大类。第一类是程序可以正常结束，但是什么结果都

不出，或者产生错误的计算结果。第二类是程序在运行了或长或短的一段时间后发生了崩溃，

引起程序的非正常结束。第三类是程序在运行了很长一段时间后既没有正常结束，也没有崩溃，

同时也不产生任何预期的输出结果。尽管对程序调试的基本策略和步骤是相同的，但是不同故

障类型程序的故障表现形式不同，对它们的调试方法既有相同点，也有不同之处。

正常结束但产生错误结果的程序

对于计算结果的错误，首先需要进行充分的测试，分析和发现错误产生的规律。例如，错

误是固定的还是随机的、是对所有的输入数据都产生的还是只对部分输入数据产生、是在大规

模数据的情况下产生还是在小规模数据的情况下产生等等，以便初步判断错误的性质。例如，

随机产生的错误往往与变量未初始化或数组访问时的地址越界有关，固定的错误往往是由于计

算代码写错引起的；在输入数据空间的边界产生的错误往往是由于对边界条件的判断和处理不

正确引起的；部分结果的固定性错误可能是程序中的某些分支中存在错误，而所有数据都出错

则是与所有数据的计算相关的公共部分出现了错误。有了这些对错误性质的初步判断之后，就

可以进一步分析计算结果的生成过程，以及相关的原始数据、中间变量和最终结果之间的关系。

然后，需要准备一些有针对性的测试数据，按照从原始数据、中间结果到最终结果的顺序，确

定关键变量在一些关键点上预期的值，并在所要检查的关键位置上设置断点或数据打印语句。

在完成了这些工作之后，就可以运行程序来检查这些变量的值，分析它们与预期值之间的差异

以及产生的原因，确定后续调试工作的方向。需要注意的是，对程序故障的定位和修改是一个

渐进的过程，上述操作步骤往往需要经过多次循环，才能最终准确地定位和改正程序中的故障。

无法结束运行的程序

这类程序往往在运行中进入了死循环而无法退出。产生这类错误的原因包括循环控制条件

错误和对循环控制变量的修改错误。对于这类故障，首先需要确定程序在执行过程中经过了哪

条路线，陷在哪个循环中无法退出。判断程序执行路线最基本的方法是在程序可能执行的各条

路径的关键点上设置断点或打印语句。使用程序调试工具设置的断点可以使程序在执行断点所

在的语句时暂停下来，以便于进一步观察程序的内部状态。通过打印语句输出适当的信息，可

以清楚地看到程序运行的轨迹以及一些关键的变量的值。对于规模比较大的复杂程序，由于可

能的路径比较多，往往难以通过一次性的断点设置或信息打印而确定程序执行的确切路线。这

时可以采取自顶向下、分层处理的方式，首先在程序执行的顶层描述中设置断点或信息打印语

句，确定程序执行的基本过程和错误所在的区间；然后再根据需要，在已确定的大的执行步骤

中逐步细化，确定程序的执行路线。在设置断点或打印语句时，要注意位置的合理分布，充分

利用每个断点或打印语句，使之提供尽量多的信息，发挥最大的作用。对代码区间的二分法搜

索是常用的有效方法。例如，在程序的中间点设置一个断点或打印语句，就可以判断问题到底

是出现在程序的前一半还是后一半，从而把问题可能发生的搜索区间缩小了一半。而如果同时

在程序的1/4、1/2和3/4处各设置一个断点或打印语句，则一次运行就可以把需要进一步检查的

区间限定在整个程序的1/4之内。连续运用这种策略，即使是功能较复杂、代码规模较大的程序，

也可以很快地把问题产生的位置限定在一个很小的区间内。如果程序中的循环语句不多，也可

以直接在每个循环语句的前后各设置一条打印语句，检查一下程序在进入哪一条循环语句后不

能正常退出。

运行崩溃的程序

对于引起程序崩溃的错误，查找方法与查找无法结束运行的错误的方法类似，也需要首先

确定程序的执行路线，以判断哪条语句引起了程序的崩溃。这类错误多是由地址越界、数组下

标和指针变量未初始化等地址访问错误引起的。因为这类错误可能会破坏程序的正常工作状态，

并引起操作系统的干预，所以如果使用打印语句来跟踪程序执行的路径，定位出错的语句，则

有可能由于程序的崩溃而使得打印语句的输出信息无法显示在输出设备上。例如，一个简单的

数组下标未初始化的错误就有可能使得放置在程序起始位置的打印语句无法输出信息。此时比

较有效的故障定位方法是使用调试工具或使用排除法。例如，我们可以首先在程序的中间位置

设置断点，或者将程序的后一半注释掉，以判断故障点是在程序的哪一半，然后再对故障区间

依次折半排除。这样，即使对于比较长的程序，也可以很快找到故障点。

2.5.4 调试数据的设计和使用

调试用的数据与测试用的数据是不同的。测试数据一般是根据对任务的需求分析和黑盒测

试方法设计的，目的是全面检查程序是否符合任务在功能和性能方面的要求。而调试数据则是

根据对程序结构的了解，针对所要测试的执行路径和故障点，一般采用白盒测试方法设计。因

此测试数据往往覆盖全面，数据规模较大，所涉及的计算过程也比较复杂。而调试数据往往针

对程序中的某些局部，程序的执行步骤比较简单，以求确认或排除程序中可能引发故障的疑点，

因此数据的规模，至少在调试的开始阶段是比较小的。随着调试工作的进展，调试数据的规模

和复杂程度也有可能逐步增加。例如，假设我们设计和实现了一个走迷宫的程序，但是这个程

序的运行不正确，无法从测试数据中给出的入口位置找到出口。那么，我们可以首先使用调试

数据把搜索的起点放到迷宫的出口，看看程序是否能够正确地判断已经找到了迷宫的出口。如

果程序在这样的数据下执行仍然不正确，那么我们可能需要检查程序启动时的初始化部分，以

及输入数据的读入部分，看看相关的数据结构中是否保存了正确的数据。如果程序的这些部分

执行正常，那么可能需要进一步检查程序中对当前位置的计算、对结束条件的判断、以及对结

果输出部分的代码了。在程序能够正确地判断其所在的出口位置之后，就可以再设计一些数据，

使得入口的起点与出口只有一步之遥，看看程序能否正确地完成任务。在这些调试数据中，应

该包括不同的迷宫规模、出口位置以及入口与出口的相对位置。如果程序在这一步上执行不正

确，那么错误可能发生在与搜索位置的移动相关的代码上。如果程序可以正确地完成这一步的

任务，那么我们就可以进一步扩大数据的规模和复杂程度，使入口与出口的距离不断增加，行

走的路线逐渐复杂，直至发现一个程序不能正确求解的数据为止。这时，仔细分析这一数据与

此前可以正常求解的数据之间的差异，以及程序在求解不同数据时所执行的代码路径，就可以

大致判断产生故障的代码范围。采用变量跟踪技术，就可以进一步确认故障原因和故障点了。

在设计调试数据时，需要注意数据的针对性、简洁性、以及数据规模增长的循序渐进。所

谓调试数据的针对性是指在设计数据时应当明确地知道每个调试数据的使用前提，以及数据所

检查的是程序代码中的哪一部分，其对应的正确结果是什么，如果程序运行结果正确可以说明

什么，如果程序运行不正确需要进一步检查程序的哪些部分，等等。所谓简洁，是指调试数据

应当尽量简单、明了，其规模应是满足对程序进行分析判断的最小数据。所谓数据规模在增长

时要循序渐进，是指调试数据规模的增加需要建立在前一步调试数据运行正确的基础之上，并

且新的调试数据所引起的程序行为的变化与前一步之间不应有太大的差距。这样，一旦程序运

行中出现了问题，就可以很快地把故障可能发生的位置定位在一个比较小的范围之内。

2.5.5 调试数据和标准输入/输出的重新定向

很多程序不是从指定的文件中直接读入数据，也不是把计算结果写入到指定的文件中，而

是从标准输入中读入数据，把计算结果写入到标准输出上。在默认情况下，标准输入/输出分别

对应着计算机的终端键盘和显示器。这样，在对程序进行调试时，就需要反复地从键盘上输入

数据，并且在显示器的屏幕上仔细捕捉可能一闪而过的错误信息。为了避免这种调试中的困难，

提高对这类程序调试工作的效率，我们可以对标准输入/输出文件重新定向，在不对程序中输入

/输出语句进行任何改动的情况下使程序从指定的文件中读入调试数据，并向指定的文件中写入

计算结果。

标准输入/输出文件的重新定向是操作系统提供的一种基本功能。使用重新定向，可以把通

过这两个标准文件进行读写的数据的实际输入来源和输出目的分别映射到其他设备或磁盘文件

上。但是这种标准文件的重新定向在C程序内部没有任何影响，一个普通的程序也无法得知和

判断标准文件是否被重新定向，以及被定向到了什么文件中。使用标准输入和标准输出的重新

定向功能，在程序中就不必直接打开某个指定的文件，而可以使用标准输入和标准输出进行数

据的输入/输出操作，让操作系统执行打开和读写特定文件的操作。在对使用标准输入/输出进行

数据输入/输出操作的程序进行调试时，我们可以将输入数据预先写入文件中，在程序运行时通

过标准输入的重新定向将其提供给程序。这就避免了重复地在键盘上键入输入数据的麻烦。如

果程序的输出数据过多，不便于在终端屏幕上直接阅读，我们也可以先将其定向到指定的文件

中，然后再使用适当的工具仔细阅读。

在Unix/Linux系统上，标准输入和标准输出的重新定向操作符分别是'<'和'>'。在调用程序可

执行文件的命令以及必要的命令行选项之后使用重新定向操作符，并在其后跟随文件名，就可

以把程序的标准输入和标准输出重新定向到指定的文件中。例如，命令ls -l列出当前目录下的所

有文件的文件名和长度等信息，并将其显示在标准输出上。使用下面的命令：

ls -l > tmp

就可以将这一命令的输出内容直接写入文件tmp中。又例如，假设程序prog_1需要从标准输入上

读入数据。使用下面的命令：

prog_1 <

程序prog_1就可以将中的数据作为从标准输入设备上输入的数据读入。

标准输入/输出文件的重新定向是一种很有用的功能，因此MS Windows也采用了Unix/Linux

系统的规范，以操作符'<'和'>'描述对标准输入和标准输出的重新定向。MS VC++的集成开发环

境(IDE)也支持这种对标准输入和标准输出的重新定向。在MS VC++ IDE上，在Project选单的

Settings项中选择Debug页面，在标签字符串Program arguments下的输入框中可以直接使用操作

符'<'和'>'描述对标准输入/输出的重新定向。例如，在该输入框中键入

< >

就可以使正在被调试运行的程序把作为标准输入文件，把作为标准输出文件。

2.5.6 调试工具

在Unix/Linux操作系统上，常用的源代码级的调试工具有SDB和GDB，在此基础上的具有图

形界面的调试工具有xxgdb、ddd等。大多数集成编程环境，如Linux上的Kdeveloper、Windows

上的VC++等，也都集成了相应的基于图形界面的调试工具。各种调试工具，尽管使用方法和调

试命令不尽相同，但是主要的功能都是一样的。各种调试工具中常用的基本功能可以分为下列

几类：

4. 设置和清除程序运行中的断点：中断程序运行的目的是检查程序在运行过程中的中间状

态，例如函数的嵌套调用关系、函数调用时的参数、函数中局部变量的值和全局变量的值

等。程序的中断是通过在程序的代码中设置断点的方式来实现的，在一个程序中可以设置

多处断点。当程序在运行到断点时会暂停，等待接受其他的调试命令。

5. 显示函数的调用关系及参数：当程序处于暂停状态时，可以显示从函数main()到当前断

点所处的函数的嵌套调用关系，以及在每次调用时所使用的参数。这对于了解程序的执行

过程很有帮助。有时通过函数的嵌套调用关系以及调用时所传递的参数就可能发现程序产

生错误的原因。

6. 显示变量和表达式的值：当程序处于暂停状态时，可以按照指定的格式，例如十进制或

十六进制显示给定变量的值。被显示的变量必须是在程序当前断点上可见的变量。在多数

调试工具上，这类命令也可以被用来显示表达式的值。表达式中不但可以包含变量名，也

可以包含各种合法的运算符。

7. 程序执行过程的控制和跟踪：当程序暂停在某个断点时，可以使用―继续运行‖功能使程

序继续运行，直至程序正常或非正常结束，或者遇到下一个断点时为止。此外，也可以通

过其他命令使程序顺序执行下一条语句；或者进入正要被调用的函数内部，停在该函数中

第一条可执行语句上；或者跳出当前断点所在的函数，停在函数调用语句的后面；或者执

行后续的语句，直至到达某个指定的函数或语句，并暂停在那里。使用这些功能，可以很

方便地跟踪程序运行的轨迹。与显示变量值的命令配合，就可以清楚地了解程序的执行过

程，以及内部数据结构的变化。

8. 其他辅助功能：包括设置和显示调试工具工作状态、设置和显示输出信息的格式、对源

文件进行编辑修改、根据源程序的修改更新可执行文件、打印指定的信息、结束调试工具

的运行等。

对于基于字符终端的调试工具，如sdb、gdb等，上述这些功能都是通过调试命令的方式提供

的。对于基于图形界面的调试系统，各种调试功能是通过命令选单或命令按钮的方式提供的。

对于初学者来说，通过图形界面使用调试工具更加直观和易于操作。关于这些命令的使用，需

要进一步阅读修改的使用手册。在Unix/Linux系统上，有些调试器要求被调试的程序在编译时

使用编译选项-g。在MS VC++环境下，被调试的程序必须被编译为调试(Debug)模式才可以使用

调试工具进行调试。

2.5.7 测试和调试中常见的问题

程序的测试和调试是编程工作的一个重要组成部分，是保证程序运行正常、能够满足任务

规定的各项要求的重要步骤，也是极富挑战性的一项工作。对初学者来说，良好的程序测试和

调试能力需要经验的积累，也需要对一些常见错误的防范意识。

在程序的测试过程中，一个经常容易出现的问题是测试简单。编程人员往往只按自己的设

计思路进行测试。这种测试实际上是重复自己的思路，而不是检查和质疑自己的思路，因此难

以发现程序中的错误。经过这样测试的程序在实际使用中会产生不少编程人员意想不到的错误。

初学者经常会问 ―我的程序没错，为什么结果不对？‖就反映了这种潜意识。从理论上讲，涉及

程序运行的各个环节，从硬件平台、操作系统、编译系统、到用户程序，都有可能出错，并引

起程序运行结果出错。但是与用户程序相比，计算机的硬件平台和各种系统软件经历了更严格

的测试和长时间广泛应用的考验，自然要比刚刚写出来的程序更加可靠。特别是在运行初学者

规模很小的程序时，这些软硬件出错的可能性几乎为零。为了避免在程序测试和调试中这种下

意识地证明自己程序正确的倾向，编程人员必须在对任务分析完毕后，在开始设计和编码之前

就完成测试数据的设计。当在测试阶段发现程序运行结果与预期不符时，可能需要再回过头来

检查一下测试数据，看看它们是否完全符合题目的要求。在排除了测试数据中可能存在的错误

之后，剩下的工作就是对程序本身的分析和调试了。

另一个经常容易出现的问题是对故障现象没有明确的认定、记录和分析。调试者除了知道

程序的运行结果不正确外，往往说不出故障的其他特征。这样很容易导致在调试过程中无的放

矢。其次，有些人在确认了故障现象之后，对问题产生的原因分析不够仔细，急于修改代码，

试图通过近似随机的代码修改来发现和排除程序中的错误。但是，这种修改不是建立在对故障

现象和程序运行过程的分析之上的，往往很难取得预期的效果。而且盲目地修改代码，有时甚

至会把原本正确的部分也改错了，以至引入新的错误。为了避免此类错误，最重要的是养成良

好的思维习惯和工作方法。这其中最重要的一点是，在动手修改代码前对程序的测试一定要充

分，要对程序各个方面的功能和性能进行尽量完整的测试，以便对程序运行的各个侧面都有较

详细的了解。在此基础上再进行由表及里、逐步深入的分析，才有可能对故障产生的原因有一

个基本准确的判断。切忌只看到程序运行中的一两个故障现象就急于修改代码。

第三个容易出现的问题是在代码修改之后没有进行完整的回归测试，而只针对原来发现和

修改的问题进行了测试。这样做的结果很有可能在修改了旧的错误的同时引入新的问题而未能

及时发现。程序所描述的是复杂的计算过程，除了少数情况外，对一处代码的修改往往会影响

到其他相关的计算过程。这些关联有时是在程序中显式地描述的，有时则是通过隐蔽的方式，

例如变量的耦合、函数的副作用等建立的。在修改代码时有可能没有充分注意到这些隐蔽的对

程序其他部分的影响，很难保证所进行的修改只在预期的范围内发生作用。因此在完成了对程

序错误的修改之后，一定要重新对程序进行完整全面的测试，以保证程序修改工作的正确。

此外，一些掌握了调试工具使用的初学者在调试过程中常犯的一个错误是，过早地使用调

试工具跟踪代码的执行过程，检查程序执行的中间结果，但却不知道这些执行过程和中间结果

是否正确。这种漫无目的的跟踪和检查，不仅工作效率很低，而且会使人养成忽视分析和思考、

盲目跟踪代码的运行、过分依赖调试工具的不良习惯，对今后编程和调试水平的提高十分不利。

程序设计是一项复杂的智力活动，程序调试更是其中很具有挑战性的工作。―谋定而后动‖是程

序设计各个阶段都应遵循的指导原则，在调试环节尤为重要。调试工具应该是在对问题分析的

基础上围绕可能的故障点使用的，而跟踪代码的执行过程，特别是步进式的跟踪，应该是在小

范围内进行的，而且是作为最后的手段而采用的。在决定采用步进式跟踪前应该问问自己，这

样步进式跟踪程序的目的是什么，是否还有其他更有效的方法。

2.6 手册的使用

手册是一个软件系统的重要组成部分，是对相关系统最权威、最准确、最全面的描述，具

有任何教科书或其他间接文献资料无法替代的作用。即使是经验丰富的编程人员，在工作中也

经常需要翻阅手册，以详细准确地了解系统各方面的细节。与教科书相比，手册的叙述更加严

格、准确、规范，因此篇幅巨大，对初学者来说可能会显得有些艰涩。不少初学者往往不习惯

查阅手册。而实际上，熟练地掌握手册的使用方法，养成查阅手册的习惯，对于全面准确地了

解编程语言和所使用的编程环境，提高编程能力具有重要的作用。

本书内容所涉及的手册，主要是C语言及其标准库函数的联机使用手册，以及由操作系统和

编程环境提供的相关操作系统命令和编程工具的联机使用手册。手册是一种工具书，与字典相

类似。对手册的主要使用方式是查阅，而不是从头到尾的阅读。为了有效地使用手册，需要首

先概览手册的主要结构和内容，掌握手册的检索和查阅方式。例如，在Unix/Linux系统上，联

机手册的查阅命令是man，手册的内容分为8章，操作系统在字符终端下的交互命令，包括cc/gcc

等，在第一章，系统调用和标准库函数分别在第二章和第三章。对各章内容的概述可以使用命

令man N intro，其中N是章号。关于联机手册本身的解释可以使用命令man man。MS VC++/IDE

的联机手册可以通过命令选单调用，也可以使用相关的按钮启动。联机手册中提供了按目录查

找、按名称索引和按主题搜索三种检索方式。在查阅手册时，除了阅读所要查询条目的内容外，

还需要注意条目中的―参见(see also)‖内容。

因为手册的文字表达比较艰深，而且大多数手册都是以英文编写的，所以对初学者来说理

解起来会有一定的难度。对有些较复杂的条目，手册中会给出一些例子。但是限于篇幅，这些

例子数量有限，而且多数也比较简单。为了正确理解手册的内容，在阅读手册时，对于不太有

把握的地方需要自己编写程序加以试验，以便检验和加深对手册内容的理解。熟练地阅读和使

用手册是计算机专业人员的一项重要的基本功。花一些时间掌握手册的使用方法是很有必要的。

习题

5. 改进【例2-1-1】算法，在初始质数表中只有一个质数2的情况下，在对进行质因子提取的

同时，生成新的质数并添加到质数表中

6. 完成对【例2-1】的编码和调试

7. 完成对【例2-2】的编码和调试

8. 设计对【例2-4】连词游戏的测试数据

9. 完成对【例2-4】连词游戏的编码和调试

10. 根据【例2-5】中的讨论，分别使用自动机模型和模式识别模型完成对实数格式识别的编

码，并比较两个程序在代码量、程序的易读性、以及代码的可重用性等方面的差异

11. 根据【例2-6】中的讨论，实现程序求倒数的编码

12. 分别完成当(m<10

6

, n=10

5

)、(m<10

6

, n < 10)、(m<10

9

, n = 5)、(m<10

9

, n = 100)时对【例2-7】

最大的N个数的设计和编码。运行和比较适用于某种数据规模的程序在其他数据规模条件下

的运行效率。

13. 设计对【例2-8】队列的测试数据

14. 完成对【例2-8】队列的编码和调试

15. 对【例2-9】硬币兑换，分别写出计算复杂度为O(N)、O(N)、O(N)和O(1)的程序代码，

运行并比较它们对不同的N的计算时间

16. 给定一个r位(r<512)正整数N，去掉其中任意s个数字后将剩余的数字按原来的左右顺序组

成一个新的正整数，使得新组成的数的值最小。输出结果时每行50个数字，每10个数字之

间留一空格

17. 已知线性方程组AX=B，求解该方程组。求解方程组的算法有多种，常用的消去法的计算过

程是，将列向量B加到矩阵A的最后一列，构成增广矩阵AB。对AB进行初等变换，使原矩阵

A的部分的主对角线上的元素均为1，其余元素均为0，则原列向量B的部分即为X的值。初

等变换有下列三种：

32

1.

将矩阵的一行乘以一个不为0的数

2. 将矩阵的一行加上另一行的倍数

3. 交换矩阵中两行的位置

输入数据的第一行为整数N (1 <= N <= 50)，以下N行每行有N + 1列。前N列为矩阵A中的

元素a

ij

，第N+1列为列向量B中的元素bi。a

ij

与b

i

均为整数。输出数据占一行，包含N个浮

点数，保留小数点后两位，按x

1

x

2

… …x

N

顺序排列，各数之间以空格分隔。例如，对于下

列输入数据：

2

3 6 51

5 1 31

输出

5.00 6.00

40. 在序列a

1

，a

2

，…，a

n

中，对于i>1，a

i

是满足下面两个性质的最小正整数：

(1) a

i

> a

i-1

；

(2) a

i

的各位数字的和与K×a

i-1

的各位数字的和相等。

例如，当a

1

=1, k=2时，该序列的前6个元素是1，2，4，8，16，23。给定a

1

,k,n，计算该序

列的第n项a

n

的值。程序的输入数据从标准输入中读入，只有一行，包含3个整数a

1

、k、n，

(0 < a

1

,k,n < 100000)，计算结果a

n

≤10

5000

。计算结果a

n

写入标准输出，占一行。例如，当

输入数据为1 2 6时，输出结果为23

50. 统计从标准输入读入的字符中出现次数最多的前10个字母的出现次数，同一字母的大小写

合并计算，按出现次数的降序输出各个字母的排序和出现次数，每个字母一行。出现次数

相同的字母按字母顺序输出。当排序在第10的字母之后的其他字母与其出现次数相同时，

也一并输出。输出格式为c:N，其中c是字母，N是其出现的次数