最早的算法

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

数据结构有哪些重要的算法(从最早的算法到数据结构)(1)

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

计算机算法

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

数据结构有哪些重要的算法(从最早的算法到数据结构)(2)

计算π的公式

非数值计算问题

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

让我们来看几个例子:

数据结构有哪些重要的算法(从最早的算法到数据结构)(3)

线性表表示客户信息

数据结构有哪些重要的算法(从最早的算法到数据结构)(4)

计算机文件系统结构

数据结构有哪些重要的算法(从最早的算法到数据结构)(5)

社交网络

数据结构

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

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

数据结构有哪些重要的算法(从最早的算法到数据结构)(6)

唐纳德·欧·克努特教授

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

数据结构有哪些重要的算法(从最早的算法到数据结构)(7)

数据结构的三要素

,