【数据结构】数组

【数据结构】数组

Richard

2019 年 07 月 17 日

739 次浏览

暂无评论

1975字数

数据结构与算法

提到数组，大部分人应该都不会陌生。我们都知道，基本所有的编程语言中都有数组这个数据类型，同时数组也是一个最基本的数据结构。那么现在有一些问题：数组的特性是什么？它是如何实现这个特性的？数组下标为什么要从0开始？

如果答不上来的话，就请往下看吧 :D

1. 数组的定义

数组是个什么东西想必大家都很清楚。这里我就放上专业的定义吧：

数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来储存一组具有类型的数据。

这个定义里面有一些关键词，下面我来解释一下这些关键词的意思吧。

2. 数组的特性

线性表

线性表顾名思义，就是一种将数据排成一条线的数据结构。比如链表，数组。对于线性表中的任意一个数据，它们都只有前，后两个方向。(图是随手画的看看就好了 XD)
线性表.png

与线性表相对应的就是非线性表。如二叉树，堆这类数据结构。对于非线性表而言，数据之间并不是只有简单的前后关系。如下图：
非线性表.png

可以看到里面节点的关系并不是简单地前后可以表示的。

连续的内存空间和相同类型的数据

这两个性质很重要，因为它们让数组有了一个“杀手锏”般的特性：随机访问。平时我们使用下标来访问数组的元素就是利用了数组的随机访问特性。

但是有利必有弊，随机访问带来的弊端就是数组需要连续的内存，同时为了保证这个特性，数组的很多操作变得十分低效。比如在数组中插入和删除，就要对目标位置以后的所有数据进行数据搬移。

那么数组是如何实现这个根据下标随机访问的特性的呢？

我们开一个大小为10的数组 int *a = new int [10];

根据上图可以看出计算机分配了一片连续的空间 1000~1039 (十进制) 给a[10]。其中1000为首地址。

如果我们想要访问a[5]的内容，计算机会用下列公式计算出该元素的内存地址：

a[i]_address = a[0]_adress + i * type_size

其中 type_size 为数组中每个元素所占的大小。

我们开的是 int 型数组，所以 type_size = 4 。至此a[5] 的地址就计算出来了，为 1020~1023 。数组的随机访问特性就是这么实现的。

3. 数组操作的时间复杂度

增加与删除

前面说了，数组在进行增加或删除的时候需要对后面的数据进行搬移。按照之前的复杂度分析，最好的情况是在数组末尾增加或删除，此时复杂度是 O(1)。最坏的情况是在数组头进行增删，此时的复杂度是 O(n)。均摊下来，忽略系数之类的，数组的增加和删除的平均时间复杂度为 O(n)。

但是，在某些情况下，数组增删的时间复杂度是可以降低的。
对于增加来说，如果对数组的有序没有要求的话，可以将需插入的数插入到数组尾部，再将其和需插入位置的数进行交换。由于数组随机访问的特性，时间复杂度就降低到了O(1)。
对于删除来说，如果有一段连续的数据要被删除，我们可以先标记其为“可删除的数据”，在空间不够时就可以一次性释放掉。
举个例子：我们现在有一个数组 a[10]，里面有五个数据：a, b, c, d, e。如果我们需要依次删除a, b, c的话，就会触发三次数据搬移。如果我们标记了它们是可删除的，在空间不够用的时候再进行删除，就可以减少两次数据搬移。这样可以节省很多时间。

查找

如果被问到数组和链表的区别的话，我想很多人会说：“数组适合查找，而链表适合插入和删除，它们的时间复杂度都是O(1)”吧？(我原先也是这么认为的 XD) 但事实上，即使是一个有序的数组，利用二分查找也需要 O(nlogn) 的时间复杂度。所以，正确的说法应该是：数组支持随机访问，其利用下标随机访问的时间复杂度是O(1)。

4. 数组越界问题

在谈这个问题之前我们先来看一段代码吧：

#include <cstdio>

int main()
{
    int i = 0;
    int a[3] = {0};
    
    for (i = 0;i <= 3; i++)
    {
        arr[i] = 0;
        printf("Hello world!\n");
    }
    
    return 0;
}

发现问题了吗？这段代码会在屏幕上无限输出 "Hello world!" 。这是为什么呢？

对于C语言来说，只要访问的不是受限的内存，都是合法的。数组的本质就是一段连续的内存，只要计算出来是合法的地址就可以访问。所以数组访问越界在C中是一种“未决”的行为。这就导致数组越界会发生一些神奇的逻辑错误，甚至对电脑系统造成损害。