1.3 算法
1.3.1 算法的基本概念
算法是对特定问题求解步骤的一种描述。它是指令的有限序列，其中每条指令表示一个或多个操作。算法一般应具有以下五种性质：
C0 1-3-1
（1）有穷性：无论在何种情况下，一个算法都必须在执行有限步骤之后结束，而且每一步骤都可以在有穷的时间内完成。
（2）确定性：可以从两个方面来理解算法的确定性，一方面是指算法中每一条指令的确定性，即每一条指令都有确切的含义，不会产生二义性；另一方面是指算法输出结果的确定性，即在任何条件下，只要是相同的一组输入就能得出相同的输出结果。
（3）有效性：算法的有效性是指算法中每一条指令的有效性，即算法中每一条指令的描述都符合语法规则、满足语义要求，都能够被人或机器确切执行，并能通过已经实现的基本运算执行有限次来完成。例如：一个二制数与十制数之间的转换操作，其基本动作（指令）包括数的相除、求余数和商数及判断商是否为零等指令。这些指令不仅能够被准确无误地执行，而且每一步的执行结果都应具有确定的类型。
（4）输入：一个算法具有零个或多个输入，这些输入是某个算法得以实现的初始条件，它取自于某个特定对象的集合，是待处理的信息。
（5）输出：一个算法必须有一个或多个输出，这些输出是与输入有着某些特定关系的量，它是经处理后的信息
由此可见，算法与程序是有区别的，即程序未必能满足动态有穷性。例如，操作系统是一个程序，只要整个系统不遭到破坏，这个程序就永远不会终止，所以它不是一个算法。算法表示的是一个问题的求解步骤，而程序则是算法在计算机上的特定实现。当用高级程序设计语言描述算法时，算法就是程序。
在设计算法时应考虑达到以下目标：
（1）正确性：算法的执行结果应满足具体问题的功能和性能要求。它是算法中最重要的一个属性，不能正确实现其任务的算法是无用的算法。
（2）可读性：在算法正确性得到保证的前提下，算法的描述还要做到便于阅读，以利于后续对算法的理解和修改。可以采用在算法中增加注释的方法，或尽量使算法描述的结构清晰、层次分明，以增强其可读性。
（3）健壮性：算法应具有检查错误和对某些错误进行适当处理的功能。也就是说，算法要具有良好的容错性，要允许用户犯错误，但在错误出现时要具有正确的判断能力和及时的纠错能力。例如，当用户输入了非法数据时，算法要能检查出错误并能将错误信息反映给用户，同时要为用户提供改正错误的机会。
（4）高效率：算法效率的高低是通过算法运行所需资源的多少来反映的，这里的资源包括时间和空间需求量。一个好的算法要做到执行时所需时间尽量短，所需的最大存储空间尽量少。若对同一个问题有多个算法可供选择，则尽可能地选择执行时间短和所需存储空间少的算法。但实际上，时间和空间需求量是矛盾的两个方面，一个算法不可能做到两全其美，往往处理时要根据实际情况来权衡它们的得失。
1.3.2 算法的描述
算法的描述可以采用某种语言，也可以借助数据流程图来表示。描述算法的语言主要有三种形式：自然语言、程序设计语言和伪代码。自然语言用中文或英文文字来描述算法，其优点是算法简单、易懂，但严谨性不够。程序设计语言用某种具体的程序设计语言来描述算法，其优点是算法不用修改就可直接在计算机上执行，但直接使用程序设计语言来描述算法并不容易，也不直观，往往要加入大量注释才能使用户明白。伪代码用一种类似于程序设计语言的语言（由于这种描述不是真正的程序设计语言，所以被称为伪代码）来描述算法，它介于自然语言和程序设计语言之间，既可以忽略程序设计语言中一些严格的语法规则与描述细节，且比程序设计语言更容易描述和被用户理解，相对于自然语言，它能更容易地转换成能够直接在计算机上执行的程序设计语言。为学习者实践的方便，本书全部采用C程序设计语言描述算法。
读者可通过下面两个例子了解用C程序设计语言描述算法的基本方法。
【例1-4】给出求由n个元素所构成的整型数组a中最大值的算法。
int MaxElem（int a[]，int n）{
int max=a[0]；
for（int i=1；i＜n；i++）{
if（max＜a[i]）
max=a[i]；
}
return max；
}
该算法首先将数组中第1个数据元素视为最大者，并将它保存在变量max中；然后从第2个数据元素开始将数组中它后面的所有数据元素依次与max进行值的比较，若遇到比max值更大的数据元素，则将此数据元素值存入max中。当后面的n-1个数据元素都比较完毕后，保存在max中的值就是数组a中的最大值。
【例1-5】给出将整型数组a中n个数据元素实现就地逆置的算法。所谓就地逆置就是要求在逆置过程中利用数组a原有空间来存放数组a中逆序排放后的各个数据元素。
void Reverse（int a[]，int n）{
for（int i=0，j=n-1；i＜j；i++，j==）{
int temp=a[i]；
a[i]=a[j]；
a[j]=temp；
}
}
该算法首先将数组a中第1个与第n个数据元素进行置换，然后将第2个与第n-1个数据元素进行置换，依此类推，直到位于数组a中间的两个数据元素置换完毕为止，如图1-9所示。
图1-9 数组元素逆置方法
1.3.3 相关约定
本书为了算法描述形式上的统一，特约定以下五个方面的内容。
（1）基本操作的算法都用以下形式的函数描述：
函数类型 函数名（形式参数）
//操作算法说明
{
语句序列
}//算法x-x结束
其中x-x是此算法在本章中的编号，前面的x代表这个算法所处的章号，后面的x代表此算法是本章算法中的序号。如：“算法2-3 ”表示此算法是第2章中的第3个算法。
（2）约定Status为函数类型，并预定义为
typedef int Status；
用户在使用时可根据函数返回值的具体类型进行改动。
（3）对函数结果的状态代码约定为如下已经预定义的符号常量。
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE-1
#define OVERFLOW-2
（4）对数据存储结构的表示全部采用typedef类型定义进行描述，同时约定数据元素类型泛指为ElemType，用户在使用该数据类型时再根据具体情况自行定义。如：
typedef int ElemType：
typede struct LNode
{ ElemType data；
struct LNode next；
}LinkList；
这描述了一个链式存储结构，其中存放的是整型数据元素，这个链式存储结构的类型名为LinkList。
（5）本书中所有代表算法的函数名或其他标识符一般都是“按义取名”，并用对应的英语单词或其缩写表示，若名字中含有多个单词则每个单词的首写字母用大写。