数据结构有哪些重要的算法（从最早的算法到数据结构）

算法是对解决问题的策略，从广义上说只要问题的解决过程中有逻辑思维的介入，那么就会产生算法。算法的思想自古就有，公认的世界上最早的算法是欧几里得算法，又叫辗转相除法，其作用是计算两个整数的最大公约数（两个整数都能被整除的那个最大的约数）。我国古代算学著作《九章算术》中也有求最大公约数的算法，叫做更相减损术，从本质上说两者是等价的，应用了相同的思想。

欧几里得算法和增相减损术

现今，我们所说的算法专指使用计算机解决特定问题的指令的集合。上世纪四五十年代，最初发明电子计算机的目的是为了科学计算和工程计算，那个时候，计算机处理的数据对象是纯数字的，解决的问题也很单纯，主要为方程求解、微积分计算等。这里，我们举一个例子，使用下图公式来计算π的值，在公式中，正负号隔项改变，通过死板的计算即可得到我们想要的结果。从这个例子就可以发现，数值计算一般都会使用一些数学公式。

计算π的公式

与数值计算相反的就是非数值计算。计算机高速发展到现在，可以输入计算机中的数据已不局限于数字，符号、声音、图像等各种信息都可以经过编码后存储到计算机中，这类数据及数据之间的关系一般无法使用公式或方程来表示，要处理这类非数值计算问题就需要用到算法了。

让我们来看几个例子：

• 从客户信息表中查找客户电话通信公司通过客户登记表记录每个客户的各项信息，要求按照给定的姓名查找客户的电话号码。要解决这个问题，我们需要把客户信息按照顺序依次录入到计算机中，然后遍历查找到我们要查的客户，这里的信息结构的特点是线性的，要使用的结构就是线性表。

线性表表示客户信息

• 计算机的文件系统结构计算机的文件结构是由文件夹组织起来的，这些文件夹的特点是每个文件夹除了根文件夹都最多只有一个父文件夹。这种一对多的关系就不适合使用线性结构来存储，这里使用的结构是树形结构。

计算机文件系统结构

• 社交网络好友问题在社交软件中，两个人可以互相关注，如何用来存储这些好友的关注状况呢？好友的关系互相构成网状，他们是多对多的关系，这里要用到的结构就是图形结构。

社交网络

以上这些非数值问题中的表、树、图模型，无法使用方程或公式来描述，处理此类问题我们需要先找出数据之间的组织方式、表示方式、处理方式等，然后再将其转化为计算机模型，这就是数据结构。

1968年，美国唐纳德·欧·克努特教授开创了数据结构的最初立体，他著作的《计算机程序设计艺术》是第一本系统阐述数据逻辑结构和存储结构的著作。

唐纳德·欧·克努特教授

数据结构是由某一数据对象及该对象中所有数据成员之间的关系组成。数据结构包含三个要素：数据的逻辑结构、数据的存储结构、数据的运算。逻辑结构反映了我们对数据含义的解释，它可以用一组数据及这些数据之间的关系表示。存储结构又称物理结构，是数据及逻辑结构在计算机中的表示方式，实际上是内存单元的分配。数据的运算有两方面的含义，运算的定义和运算的实现。运算的定义取决于数据的逻辑结构，运算的实现则与数据的存储形式密切相关。

数据结构的三要素