1.5　算法

在定义了数据类型之后，就要在此基础上设计实现算法，即程序。本节将介绍数据结构与算法的关系、算法的定义、算法的特性、算法的描述方式。

1.5.1　数据结构与算法的关系

算法与数据结构关系密切。两者既有联系，又有区别。数据结构与算法的联系可用如下公式描述：

程序=算法+数据结构

数据结构是算法实现的基础，算法依赖于某种数据结构才能实现。算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构，只有确定了数据的存储方式和描述方式，即确定了数据结构之后，才能确定算法。例如，在数组和链表中查找元素值的具体算法实现是不同的。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法。

数据结构是算法设计的基础。比如你要装修房子，装修房子的设计就相当于算法设计，而如何装修房子要看房子的结构设计。不同的房间结构，其装修设计是不同的，只有确定了房间结构，我们才能进行房间的装修设计。房间的结构就像数据结构。算法设计必须考虑到数据结构的构造，算法设计是不可能独立于数据结构而存在的。数据结构的设计和选择需要为算法服务，根据数据结构及其特点才能设计出好的算法。

数据结构与算法相辅相成，不是相互孤立存在的。数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上设计解决实际问题的方法。算法是编程思想，数据结构则是为了算法实现方便而提供的存储结构及基本操作，是算法设计的基础。

1.5.2　什么是算法

算法（Algorithm）是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。操作序列包括一组操作，每一个操作都能完成特定的功能。例如，求n个数中最大者的问题，其算法描述如下。

（1）定义一个数组对象a并赋值，用数组中第一个元素初始化max，即初始时假定第一个数最大。

     int a[]={60,36,12,31,78,93,82,26};
     max=a[0];

（2）依次把数组a[]中其余的n-1个数与max进行比较，遇到较大的数时，将其赋值给max。

最后，max中的数就是n个数中的最大者。

1.5.3　算法的5个特性

算法具有以下5个特性。

（1）有穷性（Finiteness）。有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

（2）确定性（Definiteness）。算法的每个步骤都具有确定的含义，不会出现二义性。算法在一定条件下只有一条执行路径，也就是相同的输入只能有一个唯一的输出结果。

（3）可行性（Feasibility）。算法的每个操作都能够通过执行有限次基本运算完成。

（4）输入（Input）。算法具有零个或多个输入。

（5）输出（Output）。算法至少有一个或多个输出。输出的形式可以是打印输出，也可以是返回一个或多个值。

1.5.4　算法的描述

算法的描述方式有多种，如自然语言、类语言（或称为伪代码）、程序流程图及程序设计语言（如Java、Python、C、C++）等。其中，自然语言描述可以是汉语或英语等文字描述；类语言类似于程序设计语言形式，但是不能直接运行；程序流程图的优点是直观，但是不易直接转化为可运行的程序；采用程序设计语言描述算法，就是直接利用像Java、Python、C、C++等语言来表述，其优点是可以直接在计算机上运行。

例如，判断正整数m是否为质数，算法可用以下几种方式描述。

1．自然语言

利用自然语言描述“判断m是否为质数”的算法如下：

（1）输入正整数m，令i=2。

（2）若，则令m对i求余，将余数送入中间变量r；否则输出“m是质数”，算法结束。

（3）判断r是否为零。若为零，则输出“m不是质数”，算法结束；若r不为零，则令i增加1，转到步骤（2）执行。

2．程序流程图

判断m是否为质数的程序流程图如图1-11所示。不难看出，采用自然语言描述算法直观性和可读性不强；采用程序流程图描述算法比较直观，可读性强，缺点是不能直接转换为计算机程序，移植性不好。

3．类语言

类Java语言描述如下：

4．程序设计语言

Java语言描述如下：

可以看出，类语言的描述除了没有变量的定义、输入和输出的写法外，与程序设计语言的描述差别不大，类语言的描述可以转换为直接运行的计算机程序。

本书所有算法均采用Java语言描述，所有程序均可直接上机运行。