数据结构与算法

本章知识要点：

算法的基本概念；

数据结构的定义；

线性表的定义和存储；

树、二叉树的定义和存储；

查找与排序算法。

算法（algorithm）是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方****与完整的描述。

算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：

一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。

1．算法的基本特征。

作为一个算法，一般应具有以下几个基本特性。

1）确定性。

算法的每一种运算必须有确定的意义，该种运算执行某种动作应无二义性，目的明确；这一性质反映了算法与数学公式的明显差别。在解决实际问题时，可能会出现这样的情况：针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从，这是因为根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，此计算过程就不能适应了。

2）可行性。

要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成；针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。

3）输入。一个算法有0个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合。

4）输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量。

5）有穷性。

一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有穷的。因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。

算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，显然失去了实用价值。

满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，在一个算法中，有些指令可能是重复执行的，因此指令的执行次数可能远远大于算法中的指令条数。由有穷性可知，对于任何输入，一个算法在执行了有限类指令后一定要终止并且必须在有限的时间内完成，因此，一个程序如果对任何输入都不会陷入无限循环时，即是有穷的，则它就是一个算法。操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。

2．算法的描述。

算法的描述方法可以归纳为以下几种：

1）自然语言。

2）图形，如n-s图、流程图，图的描述与算法语言的描述对应。

3）算法语言，即计算机语言、程序设计语言、伪**。

4）形式语言。用数学的方法，可以避免自然语言的二义性。

用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。

人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如，人们要购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的***如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。图1-1所示的是用流程图描述算法的例子，其函数为：

图1-1 流程图。

3．算法设计基本方法。

计算机解题的过程实际上是在实施某种算法，这些算法可称为计算机算法。计算机算法不同于人工处理的方法。在实际应用时，各种方法之间往往存在着一定的联系。

1）列举法。

列举法的基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。

列举法的特点是算法比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出一些有用的信息，是可以大大减少列举量的。

列举原理是计算机应用领域中十分重要的原理。许多实际问题，若采用人工列举是不可想象的，但由于计算机的运算速度快，擅长重复操作，可以很方便地进行大量列举。列举算法虽然是一种比较笨拙而原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、查找、搜索等问题），局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。

2）归纳法。

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。显然，归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。

从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。

3）递推法。

所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。

递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。

4）递归法。

人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。

在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法设计中占有很重要的地位。

递归分为直接递归与间接递归两种。如果一个算法p显式地调用自己则称为直接递归。如果算法p调用另一个算法q，而算法q又调用算法p，则称为间接递归调用。

递归是很重要的算法设计方法之一。实际上，递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。

有些实际问题，既可以归纳为递推算法，又可以归纳为递归算法。但递推与递归的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。

通常，递归算法要比递推算法清晰易读，其结构比较简练。特别是在许多比较复杂的问题中，很难找到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算法容易得多。但递归算法的执行效率比较低。

5）减半递推技术。

实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。

所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

6）回溯法。

前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果，而减半递推技术也是归纳法的一个分支。在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。

算法的复杂度主要包括时间复杂度和空间复杂度。

1．时间复杂度。

一个算法的时间复杂度是该算法的时间耗费，它是该算法所求解问题规模n的函数，当问题的规模n无穷大时，我们把时间复杂度t（n）的数量级称为算法的渐进时间复杂度。

为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。

例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。又如，当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。

数据结构与算法

算法与数据结构

算法与数据结构

算法与数据结构

其他用户还读了