美文网首页
数据结构之数组

数据结构之数组

作者: Sun东辉 | 来源:发表于2022-06-30 10:02 被阅读0次

    在计算机科学中,数组数据结构(Array Data Structure),简称数组(Array),是由相同类型的元素(Element)的集合所组成的数据结构,在存储时使用一块连续的存储空间。利用元素的索引(Index)可以计算出该元素对应的存储地址。

    根据维度区分,有两种不同的数组,分别为:

    • 一维数组;
    • 多维数组(数组中的元素为数组),如二维数组,对应于数学上的矩阵概念,可表示为二维矩形格。

    数组是计算机科学中最基本的数据结构之一,其他数据结构,比如栈和队列都是由数组衍生出来的。它有多种用途,适用于各种场景。

    特点

    1. 数组是相同数据类型的元素的集合。
    2. 数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放。
    3. 数组中的元素通过它在数组中的顺序位置来表示。如 Array[0] 表示名字为 Array 的数组中的第一个元素。

    性能

    数组数据结构有以下 4 种操作:

    • 读取:查看数据结构中某一位置上的数据。对于数组来说,这意味着查看某个索引所指的数据值。
    • 查找:从数据结构中找出某个数据值的所在。对于数组来说,这意味着检查其是否包含某个值,如果包含,返回其索引。
    • 插入:给数据结构增加一个数据值。对于数组来说,这意味着增加一块儿空间并填入一个值。
    • 删除:从数据结构中移除一个数据值。对于数组来说,这意味着把数组中的某个数据项移除。

    我们从一个例子讨论,数组的 4 种操作的复杂度:

    下面是一个用户的购物清单:

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

    读取

    读取的时间复杂度为 O(1)。因为计算机本身就有跳到任一索引位置的能力(通过程序计数器 PC)。

    在上面的例子中,如果想要读取索引 2 的值,计算机会执行如下过程:

    1. 找到数组的地址。根据数组名称,找到数组的内存地址,即数组开头的地址 1010;
    2. 计算元素的地址。由于索引从 0 算起,索引为 2 的元素在数组的第三个格子上,1010+3=1013;
    3. 返回元素的内容。一步跳到 1013,获取到 “dates” 这个值,返回。

    查找

    查找的时间复杂度为 O(n)。因为计算机在查找数组中是否存在某个值时,会先从索引为 0 的位置开始,检查其值,如果不匹配,则继续下一个索引,以此类推,直至找到或返回不存在。

    在上面的例子中,如果想要查找 “dates”,计算机会执行如下过程:

    1. 找到数组的地址。根据数组名称,找到数组的内存地址,即数组开头的地址 1010;
    2. 对元素的值进行匹配。取出索引为 0 的元素,与待匹配的元素“dates”进行比较,匹配结果为 false,索引加 1,继续取索引为 1 的元素进行匹配,以此类推,直至找到或返回不存在。
    3. 返回结果。历尽千幸万苦,终于找到了“dates”,它在索引为 3 那里,自此,计算机不用再往后跳了,因为结果已经得到。

    插入

    插入的时间复杂度为 O(n)。

    插入元素分两种情况

    • 往数组的末尾插入元素。这种情况下,计算机知道数组的开头的内存地址,也知道数组中包含多少个元素,所以可算出要插入的内存的地址,然后一步跳到那里插入就可以了。

    • 在数组的开头或中间插入元素。这种情况下,我们需要移动其他元素以腾出空间,于是得花费额外的步数。假设我们需要在索引为 2 处插入 “figs”,具体情况如下:

      1. "elderberries"右移;
      2. "dates"右移;
      3. "cucembers"右移;
      4. 在索引 2 处插入"figs”;

      整个过程有 4 步,前 3 步都在移动数据,最后 1 步才是真正的插入数据。

    最低效(花费最多步数)的插入是插入在数组开头。这时需要把数组所有的元素都往右移。于是,一个含有 n 各元素的数组,其插入数据的最坏情况会花费 n+1 步。

    删除

    删除的时间复杂度为 O(n)。

    删除的过程相当于插入的反向操作。假设,我们要删除索引为 2 的值,即“cucembers”,执行过程如下:

    1. 删除 “cucembers”;
    2. 将"dates"左移;
    3. 将"elderberries"左移;

    整个删除过程花了 3 步,其中,第 1 步是真正的删除,剩下的 2 步是移数据去填空格。

    不去填空格可以吗?答案是不行。因为数组是通过索引进行读取的,如果存在空格,数组的读取就会受到影响,其次,当频繁更新时,会产生很多空格,这些空格如果不通过填空格的方式进行“回收再利用”,势必会造成很大的空间浪费。

    参考资料:

    相关文章

      网友评论

          本文标题:数据结构之数组

          本文链接:https://www.haomeiwen.com/subject/iphxbrtx.html