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

1. 读取
首先看看读取，即查看数组中某个索引所指的数据值。
这只要一步就够了，因为计算机本身就有跳到任一索引位置的能力。在["apples","bananas", "cucumbers", "dates", "elderberries"]的例子中，如果要查看索引2 的值，那么计算机就会直接跳到索引2，并告诉你那里有"cucumbers" 。
计算机为什么能一步到位呢？原因如下。
计算机的内存可以被看成一堆格子。下图是一片网格，其中有些格子有数据，有些则是空白。

文章插图
当程序声明一个数组时，它会先划分出一些连续的空格子以备使用。换句话说，如果你想创建一个包含5 个元素的数组，计算机就会找出5 个排成一行的空格子，将其当成数组。

文章插图
内存中的每个格子都有各自的地址，就像街道地址，例如大街123 号。不过内存地址就只用一个普通的数字来表示。而且，每个格子的内存地址都比前一个大1，如下图所示。

文章插图
购物清单数组的索引和内存地址，如下图所示。

文章插图
计算机之所以在读取数组中某个索引所指的值时，能直接跳到那个位置上，是因为它具备以下条件。
(1) 计算机可以一步就跳到任意一个内存地址上。（就好比，要是你知道大街123 号在哪儿，那么就可以直奔过去。）
(2) 数组本身会记有第一个格子的内存地址，因此，计算机知道这个数组的开头在哪里。
(3) 数组的索引从0 算起。
回到刚才的例子，当我们叫计算机读取索引3 的值时，它会做以下演算。
(1) 该数组的索引从0 算起，其开头的内存地址为1010 。
(2) 索引3 在索引0 后的第3 个格子上。
(3) 于是索引3 的内存地址为1013，因为1010 + 3 = 1013 。
当计算机一步跳到1013 时，我们就能获取到"dates"这个值了。
所以，数组的读取是一种非常高效的操作，因为它只要一步就好。一步自然也是最快的速度。这种一步读取任意索引的能力，也是数组好用的原因之一。
如果我们问的不是“索引3 有什么值”，而是“"dates"在不在数组里”，那么这就需要进行查找操作了。下面我们就来看看。
2.查找
如前所述，对于数组来说，查找就是检查它是否包含某个值，如果包含，还得给出其索引。
那么，我们就试试在数组中查找"dates"要用多少步。
对于我们人来说，可以一眼就看到这个购物清单上的"dates"，并数出它的索引为3 。但是，计算机并没有眼睛，它只能一步一步地检查整个数组。
想要查找数组中是否存在某个值，计算机会先从索引0 开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到为止。
我们用以下图来演示计算机如何从购物清单中查找"dates" 。
首先，计算机检查索引0 。

文章插图
因为索引0 的值是"apples"，并非我们所要的"dates"，所以计算机跳到下一个索引上。

文章插图
索引1 也不是"dates"，于是计算机再跳到索引2 。

文章插图
但索引2 的值仍不匹配，计算机只好再跳到下一格。

文章插图
啊，真是千辛万苦，我们找到"dates"了，它就在索引3 那里。自此，计算机不用再往后跳了，因为结果已经得到。
在这个例子中，因为我们检查了4 个格子才找到想要的值，所以这次操作总计是4 步。
这种逐个格子去检查的做法，就是最基本的查找方法——线性查找。当然还可以学习其他查找方法，但在那之前，我们再思考一下，在数组上进行线性查找最多要多少步呢？
如果我们要找的值刚好在数组的最后一个格子里（如本例的elderberries），那么计算机从头到尾检查每个格子，会在最后才找到。同样，如果我们要找的值并不存在于数组中，那么计算机也还是得查遍每个格子，才能确定这个值不在数组中。