1.3　算法描述

著名计算机科学家N.Wirth曾给出过如下公式

程序＝算法＋数据结构

这个公式表明,数据结构和算法是程序的两大要素,二者相辅相成,缺一不可。

对于任何一种运算,如果数据的存储结构不同,则其算法描述一般是不同的,即使在存储结构相同的前提下,由于可以采用不同的求解策略,往往也可以有很多不同的算法。那么,如何选择一个好算法呢？首先,需要理解算法。

1.3.1　基本概念

1.算法的定义

算法（algorithm）是规则的有限集合,是为了解决特定问题而规定的一系列操作。

2.算法的特性

（1）有限性　算法在有限步骤之内应正常结束,不能形成无穷循环。

（2）确定性　算法中的每一个步骤必须有确定含义,使得无二义性得以实现。

（3）输入性　有多个或0个输入。

（4）输出性　至少有一个或多个输出。

（5）可行性　原则上能精确进行,操作上可通过已实现的基本运算执行有限次而完成。在算法的五大特性中,最基本的是有限性、确定性和可行性。

3.算法设计的要求

算法设计一般应该具有以下几个基本特征。

1）算法的正确性

算法的正确性是指算法应该满足具体问题的需求,其中“正确”的含义包括以下三个方面。

（1）算法对几组不同的输入数据能够得出满足要求的结构。

（2）算法对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足要求的结果。

（3）算法对于一切合法的输入数据都产生满足要求的结果。

2）可读性

算法主要是为了方便程序员的阅读与交流,其次才是便于机器执行。可读性好有利于程序员对算法的理解；晦涩难懂的程序易隐藏较多错误,难以调试和修改。

3）健壮性

健壮性即指算法对于非法输入的抵抗能力,它强调了即使输入了非法数据,算法应能够识别并做出正确处理,而不是产生莫名其妙的输出结果。例如,一个求凸多边形面积的算法是采用求各三角形面积之和的策略来解决问题,当输入的坐标值集合表示的是一个凹多边形时,则不应继续计算,而应报告输入出错。并且,处理错误的方法是返回一个表示错误或错误性质的值,而不是打印错误信息或异常,并同时终止程序的执行,以便在更高的抽象层次上进行处理。

4）高效率和低存储量

算法的效率通常是指算法的执行时间。对于一个具体的问题,通常有多个算法可以解决,执行时间短的算法其效率就高。所谓存储量,是指算法在执行过程中所需要的最大存储空间。效率与低存储量需求这两者与问题的规模有关。

1.3.2　算法描述的工具

1.流程图

用流程图描述算法符合人们的思维习惯,直观形象,并且易于理解。

2.自然语言

用自然语言描述算法通俗易懂,特别适用于对顺序程序结构算法的描述。在使用时,要特别注意算法逻辑的正确性。

3.其他方法

还可以用数学语言或约定的符号语言来描述算法。

4.计算机语言

由于是使用计算机实现算法,因此,可以使用计算机语言来表示算法,使用计算机语言描述算法时必须严格遵循所用语言的语法规则。本书中采用的是C语言描述算法。

1.3.3　C语言的语法结构简介

C语言的语法结构主要有以下几个部分。

（1）预定义常量和类型。

本书中将用到的常量符号有TRUE、FALSE、MAXSIZE等,约定用如下的宏定义预先定义。

（2）本书中所有的算法都以如下的函数形式加以表示,其中的结构类型使用前面已有的定义。

[数据类型]　函数名（[形式参数及说明]）

{

内部数据说明；

执行语句组；

}　/＊函数名＊/

函数的定义主要由函数名和函数体组成,函数体用花括号“{”和“}”括起来。函数中用方括号括起来的部分,如“[形式参数]”为可选项,函数名之后的圆括号不可省略。

（3）赋值语句。

①简单赋值语句。

●〈变量名〉＝〈表达式〉,它表示将表达式的值赋给左边的变量。

●〈变量〉＋＋,它表示变量加1后赋值给变量。

●〈变量〉－－,它表示变量减1后赋值给变量。

②串联赋值语句。

〈变量1〉＝〈变量2〉＝〈变量3〉＝…＝〈变量k〉＝〈表达式〉；

③成组赋值语句。

（〈变量1〉,〈变量2〉,〈变量3〉,…,〈变量k〉）＝（〈表达式1〉,〈表达式2〉,〈表达式3〉,…,〈表达式k〉）；

〈数组名1〉[下标1][下标2]＝〈数组名2〉[下标1][下标2]；

④条件赋值语句。

〈变量名〉＝〈条件表达式〉？〈表达式1〉:〈表达式2〉；

（4）条件选择语句,有以下几种形式。

（5）循环语句,主要有以下几种形式。

①for语句。

for语句首先计算表达式1的值,然后求表达式2的值,若结果为非零（即为真）则执行循环体语句,最后计算表达式3的值,如此循环,直到表达式2的值为零（即不成立为假）时为止。

②while语句。

while循环语句首先计算条件表达式的值,若条件表达式的值为非零（即条件成立）,则执行循环体语句,然后再次计算条件表达式的值,如此重复执行,直到条件表达式的值为零（即为假）时退出循环,执行该循环之后的语句。

③do…while语句。

do…while循环语句首先执行循环体语句,然后计算条件表达式的值,若条件表达式成立,则再次执行循环体,再计算条件表达式的值,直到条件表达式的值为零（即条件不成立）时结束循环。

（6）输入/输出语句。

①输入语句用scanf函数实现。特别当输入数据为单个字符时,则用getchar函数来实现。当输入数据为字符串时,用gets函数来实现。

②输出语句用printf函数实现。当输出为单个字符时,用putchar函数实现。当输出数据为字符串时,用puts函数实现。

其中,输入/输出函数中的类型部分不做严格要求,淡化表述。

（7）其他一些语句。

①return＜表达式＞或return:该语句用于函数结束。

②break语句:可使用该语句在循环语句或case语句中,从而结束循环过程或跳出情况语句。

③continue语句:该语句可用在循环语句中,从而结束本次循环过程,进入下一次循环过程。

④exit语句:在出现异常情况时,使用该语句控制退出函数。

（8）处理动态链表所需的常用函数。链表结构是动态地分配存储空间的,即在需要时才开辟一个结点的存储单元。C语言编译系统的库函数提供了以下函数来完成对应的功能。

①malloc函数,其函数原型如下。

void *malloc(unsignedintsize);

其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即“返回值”）是一个指向分配域起始地址的指针（类型为void）。如果此函数未能成功执行（如内存空间不足）,则返回空指针（NULL）。

②free函数,其函数原型如下。

voidfree(void*p)

其作用是由p指向的内存区,使这部分内存区能被其他变量使用。该函数无返回值。