在计算机科学中,数组数据结构(Array Data Structure),简称数组(Array),是由相同类型的元素(Element)的集合所组成的数据结构,在存储时使用一块连续的存储空间。利用元素的索引(Index)可以计算出该元素对应的存储地址。
根据维度区分,有两种不同的数组,分别为:
- 一维数组;
- 多维数组(数组中的元素为数组),如二维数组,对应于数学上的矩阵概念,可表示为二维矩形格。
数组是计算机科学中最基本的数据结构之一,其他数据结构,比如栈和队列都是由数组衍生出来的。它有多种用途,适用于各种场景。
特点
- 数组是相同数据类型的元素的集合。
- 数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放。
- 数组中的元素通过它在数组中的顺序位置来表示。如 Array[0] 表示名字为 Array 的数组中的第一个元素。
性能
数组数据结构有以下 4 种操作:
- 读取:查看数据结构中某一位置上的数据。对于数组来说,这意味着查看某个索引所指的数据值。
- 查找:从数据结构中找出某个数据值的所在。对于数组来说,这意味着检查其是否包含某个值,如果包含,返回其索引。
- 插入:给数据结构增加一个数据值。对于数组来说,这意味着增加一块儿空间并填入一个值。
- 删除:从数据结构中移除一个数据值。对于数组来说,这意味着把数组中的某个数据项移除。
我们从一个例子讨论,数组的 4 种操作的复杂度:
下面是一个用户的购物清单:
array = ["apples","bananas","cucumbers","dates","elderberries"]
读取
读取的时间复杂度为 O(1)。因为计算机本身就有跳到任一索引位置的能力(通过程序计数器 PC)。
在上面的例子中,如果想要读取索引 2 的值,计算机会执行如下过程:
- 找到数组的地址。根据数组名称,找到数组的内存地址,即数组开头的地址 1010;
- 计算元素的地址。由于索引从 0 算起,索引为 2 的元素在数组的第三个格子上,1010+3=1013;
- 返回元素的内容。一步跳到 1013,获取到 “dates” 这个值,返回。
查找
查找的时间复杂度为 O(n)。因为计算机在查找数组中是否存在某个值时,会先从索引为 0 的位置开始,检查其值,如果不匹配,则继续下一个索引,以此类推,直至找到或返回不存在。
在上面的例子中,如果想要查找 “dates”,计算机会执行如下过程:
- 找到数组的地址。根据数组名称,找到数组的内存地址,即数组开头的地址 1010;
- 对元素的值进行匹配。取出索引为 0 的元素,与待匹配的元素“dates”进行比较,匹配结果为 false,索引加 1,继续取索引为 1 的元素进行匹配,以此类推,直至找到或返回不存在。
- 返回结果。历尽千幸万苦,终于找到了“dates”,它在索引为 3 那里,自此,计算机不用再往后跳了,因为结果已经得到。
插入
插入的时间复杂度为 O(n)。
插入元素分两种情况
-
往数组的末尾插入元素。这种情况下,计算机知道数组的开头的内存地址,也知道数组中包含多少个元素,所以可算出要插入的内存的地址,然后一步跳到那里插入就可以了。
-
在数组的开头或中间插入元素。这种情况下,我们需要移动其他元素以腾出空间,于是得花费额外的步数。假设我们需要在索引为 2 处插入 “figs”,具体情况如下:
- "elderberries"右移;
- "dates"右移;
- "cucembers"右移;
- 在索引 2 处插入"figs”;
整个过程有 4 步,前 3 步都在移动数据,最后 1 步才是真正的插入数据。
最低效(花费最多步数)的插入是插入在数组开头。这时需要把数组所有的元素都往右移。于是,一个含有 n 各元素的数组,其插入数据的最坏情况会花费 n+1 步。
删除
删除的时间复杂度为 O(n)。
删除的过程相当于插入的反向操作。假设,我们要删除索引为 2 的值,即“cucembers”,执行过程如下:
- 删除 “cucembers”;
- 将"dates"左移;
- 将"elderberries"左移;
整个删除过程花了 3 步,其中,第 1 步是真正的删除,剩下的 2 步是移数据去填空格。
不去填空格可以吗?答案是不行。因为数组是通过索引进行读取的,如果存在空格,数组的读取就会受到影响,其次,当频繁更新时,会产生很多空格,这些空格如果不通过填空格的方式进行“回收再利用”,势必会造成很大的空间浪费。
网友评论