1.1.1 算法与数据结构概述

本节的主要考点集中在算法与数据结构的基本概念上，包括算法的基本特征、复杂度，以及数据结构的表示等。

1.算法的概念

算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内得到所要求的输出的步骤。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法完成同样的任务可能有不同的时间、空间或效率。

（1）算法的基本特征

1）有穷性（Finiteness）：算法必须能在执行有限个步骤之后终止。

2）确定性（Definiteness）：算法的每一步骤必须有确切的定义。

3）输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

4）输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

5）可行性（Effectiveness）：也称有效性，算法中执行的任何计算步都可以被分解为基本的、可执行的操作步，即每个计算步都可以在有限时间内完成。

（2）算法的基本要素

算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下4类。

1）算术运算：主要包括加、减、乘、除等运算。

2）逻辑运算：主要包括与、或、非等运算。

3）关系运算：主要包括大于、小于、等于、不等于等运算。

4）数据传输：主要包括赋值、输入、输出等操作。

算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。

（3）算法设计的基本方法

计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计。在实际应用时，各种方法之间往往存在着一定的联系。

1）递推法：递推法是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的。

2）递归法：递归法指的是一个过程。函数不断引用自身，直到引用的对象已知。

3）穷举搜索法：穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

4）贪婪法：贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

5）分治法：分治法是把一个复杂的问题分成两个或更多相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。

6）动态规划法：动态规划法是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

7）迭代法：迭代法是数值分析中通过从一个初始估计解出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。

（4）良好的算法设计的要求

一个良好的算法应达到如下目标。

1）正确性（Correctness）：算法的计算结果必须是正确的。

2）可读性（Readability）：可读性好有助于用户对算法的理解；不易理解的程序容易隐藏较多错误，难以调试和修改。

3）健壮性（Robustness）：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

4）效率与低存储量需求：效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。

2.算法的复杂度

算法复杂度分为空间复杂度和时间复杂度。

（1）算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。

（2）算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的存储空间、输入的初始数据所占的存储空间，以及算法执行中所需要的额外空间。

3.数据结构的定义

数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据元素的集合。

数据（Data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

在一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系（即连续），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。

一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

（1）数据的逻辑结构

数据结构是指反映数据元素之间的关系的数据元素集合的表示。通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。

一个数据结构应包含两方面信息：表示数据元素的信息和表示各数据元素之间的前后件关系的信息。

数据的逻辑结果是对数据元素之间的逻辑关系的描述。它可以用一个数据元素的集合和在此集合中定义的若干关系来表示。用D表示数据元素的集合，用R表示数据元素之间的前后件关系，即一个数据结构可以表示为B=（D, R），这是一个二元关系的表示方式。

（2）数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构（也称为数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

4.数据结构的表示

数据结构的表示除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据节点，简称为节点。为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件节点指向后件节点。

在数据结构中，没有前件的节点称为根节点；没有后件的节点称为终端节点（也称为叶子节点）。

一个数据结构中的节点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新节点（称为插入运算），也可以删除数据结构中的某个节点（称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。

5.线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

线性结构满足以下条件：

1）有且只有一个根节点。

2）每一个节点最多有一个前件，也最多只有一个后件。

如果一个数据结构不是线性结构，则称之为非线性结构。如果在一个数据结构中一个数据元素都没有，则称该数据结构为空。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。