零基础学数据结构第2版（零基础学编程）最新章节_陈锐著

1.5　算法

在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序运行效率的高低。如何建立一个比较好的运算集合就是算法要研究的问题。本节主要介绍算法的定义、算法的特性、算法的描述及算法与数据结构的关系。

1.5.1　数据结构与算法的关系

算法与数据结构关系密切。两者既有联系又有区别。

数据结构与算法的联系可用一个公式描述，即程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构，简单地说，数据结构的设计就是选择存储方式，如确定问题中的信息是用普通变量存储还是用数组存储或其他更加复杂的数据结构存储。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法。

数据结构是算法设计的基础。用一个形象的比喻来解释就是，开采煤矿过程中，煤矿以各种形式深埋于地下，矿体的结构就相当于计算机领域的数据结构，而煤就相当于一个个数据元素；开采煤矿然后运输、加工这些“操作”技术就相当于算法；显然，如何开采、如何运输必须考虑到煤矿的存储（物理）结构，只拥有开采技术而没有煤矿是没有任何意义的。算法设计必须要考虑到数据结构的构造，算法设计是不可能独立于数据结构存在的。另外，数据结构的设计和选择需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的实际意义。知道某种数据结构的典型操作才能设计出好的算法。总之，算法的设计同时伴有数据结构的设计，两者都是为最终解决问题服务的。

数据结构与算法的区别在于数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。

1.5.2　什么是算法

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

（1）定义一个变量max和一个数组a[]，分别用来存放最大数和数组的元素，并假定第一个数最大，赋给max。

max=a[0]
；

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

for(i=1;i<n;i++)
      if(max<a[i])
          max=a[i];

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

1.5.3　算法的五大特性

算法具有以下5个特性。

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

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

（3）可行性。算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

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

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

1.5.4　算法的描述

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

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

1.自然语言描述法

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

①输入正整数m，令i=2。

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

③判断r是否为零。如果为零，输出“m不是质数”，算法结束；如果r不为零，则令i增加1，转到步骤②执行。

因为上述算法采用自然语言描述不具有直观性和良好的可读性，采用程序流程图描述比较直观，可读性好，但是不能直接转化为计算机程序，移植性不好。

2.程序流程图法

判断m是否为质数的程序流程图如图1-9所示。我们采用类C语言描述和C语言描述如下：

图1-9 　判断m是否为质数的程序流程图

3.类语言法

类C语言描述如下。

void IsPrime() 
/*
判断m
是否为质数*/
{
     scanf(m);          /*
输入正整数m*/
     for(i=2;i<=sqrt(m);i++)
     {
          r=m%i;                /*
求余数*/
          if(r==0)              /*
如果m
能被整除*/
          {
                printf("m
不是质数！");
                break;
          }
     }
    printf("m
是质数！");
}

4.程序设计语言法

C语言描述如下。

void IsPrime()
/*
判断m
是否为质数*/
{
     printf("
请输入一个正整数：");
     scanf("%d",&m);                /*
输入正整数m*/
     for(i=2;i<=sqrt(m);i++)
     {
            r=m%i;                      /*
求余数*/
            if(r==0)            /*
如果m
能被整除*/
            {
                  printf("m
不是质数！\n");
                  break;
            }
     }
    printf("m
是质数！\n");
}

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

为了方便读者学习和上机操作，本书所有算法均采用C程序设计语言描述，能直接上机运行。

1.5 算法

1.5.1 数据结构与算法的关系

1.5.2 什么是算法

1.5.3 算法的五大特性

1.5.4 算法的描述