数据结构为什么如此重要？ _数据结构

哪怕只写过几行代码的人都会发现，编程基本上就是在跟数据打交道。计算机程序总是在接收数据、操作数据或返回数据。不管是求两数之和的小程序，还是管理公司的企业级软件，都运行在数据之上。

文章插图
数据是一个广义的术语，可以指代各种类型的信息，包括最基本的数字和字符串。在经典的“Hello World!”这个简单程序中，字符串"Hello World!"就是一条数据。事实上，无论是多么复杂的数据，我们都可以将其拆成一堆数字和字符串来看待。
数据结构则是指数据的组织形式。看看以下代码。

x = "Hello!"y = "How are you"z = "today?"print x + y + z

这个非常简单的程序把3 条数据串成了一句连贯的话。如果要描述该程序中的数据结构，我们会说，这里有3 个独立的变量，分别引用着3 个独立的字符串。
在这里，你将学到，数据结构不只是用于组织数据，它还极大地影响着代码的运行速度。因为数据结构不同，程序的运行速度可能相差多个数量级。如果你写的程序要处理大量的数据，或者要让数千人同时使用，那么你采用何种数据结构，将决定它是能够运行，还是会因为不堪重负而崩溃。
【数据结构为什么如此重要？】一旦对各种数据结构有了深刻的理解，并明白它们对程序性能方面的影响，你就能写出快速而优雅的代码，从而使软件运行得快速且流畅。当然，你的编程技能也会更上一层楼。
接下来我们将会分析两种比较相似的数据结构：数组和集合。它们从表面上看好像差不多，但通过即将介绍的分析工具，你将会观察到它们在性能上的差异。
基础数据结构：数组数组是计算机科学中最基本的数据结构之一。如果你用过数组，那么应该知道它就是一个含有数据的列表。它有多种用途，适用于各种场景，下面就举个简单的例子。
一个允许用户创建和使用购物清单的食杂店应用软件，其源代码可能会包含以下的片段。

array = ["Apples", "bananas", "cucumbers", "dates", "elderberries"]

这就是一个数组，它刚好包含5 个字符串，每个代表我会从超市买的食物。
此外，我们会用一些名为索引的数字来标识每项数据在数组中的位置。
在大多数的编程语言中，索引是从0 算起的，因此在这个例子中，"apples"的索引为0，"elderberries"的索引为4，如下所示。

文章插图
若想了解某个数据结构（例如数组）的性能，得分析程序怎样操作这一数据结构。
一般数据结构都有以下4 种操作（或者说用法）。

读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。例如，查看索引2 上有什么食品，就是一种读取。
查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，那么还得给出其索引。例如，检查"dates"是否存在于食品清单之中，给出其对应的索引，就是一种查找。
插入：给数据结构增加一个数据值。对于数组来说，这意味着多加一个格子并填入一个值。例如，往购物清单中多加一项"figs"，就是一种插入。
删除：从数据结构中移走一个数据值。对于数组来说，这意味着把数组中的某个数据项移走。例如，把购物清单中的"bananas"移走，就是一种删除。

接下来我们将会研究这些操作在数组上的运行速度。同时，我们也将学到第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。
为什么呢？
因为，你不可能很绝对地说，某项操作要花5 秒。它在某台机器上要跑5 秒，但换到一台旧一点的机器，可能就要多于5 秒，而换到一台未来的超级计算机，运行时间又将显著缩短。所以，受硬件影响的计时方法，非常不可靠。
然而，若按步数来算，则确切得多。如果A 操作要5 步，B 操作要500 步，那么我们可以很肯定地说，无论是在什么样的硬件上对比，A 都快过B 。因此，衡量步数是分析速度的关键。
此外，操作的速度，也常被称为时间复杂度。本文中，我们提到速度、时间复杂度、效率、性能，它们其实指的都是步数。
事不宜迟，我们现在就来探索上述4 种操作方式在数组上要花多少步。