阅读 199

详解数据结构中的“数组”与编程语言中的“数组”的区别和联系

在大部分数据结构和算法书籍中,数组作为最基础的数据类型,是最先被介绍的。一般我们都是这么定义数组的。

数组这种数据结构,是存储相同数据类型的一块连续的存储空间。
解读一下这个定义的话,那就是:数组中的数据必须是相同类型的,数组中的数据必须是连续存储的。
只有这样,数组才能实现根据下标快速地(时间复杂度是O(1))定位一个元素。

但是,如果你是一名比较喜欢钻研的程序员,你会发现,在你所熟悉的编程语言中,”数组“这种数据类型,并不一定完全符合上面的定义。比如Javascript这种语言中,数组中的数据不一定是连续存储的,也不一定非得是相同类型,甚至数组可以是变长的。

var arr = new Array(4,'hello', new Date());
复制代码

除此之外,大部分数据结构和算法书籍中,在讲到二维或者多维数组中数据的存储方式的时候,一般都会这么说:

二维数组中的数据,是先按行再按列(或者先按列后按行),依次存储在连续的存储空间中。
如果二维数组定义为a[n][m],那a[i][j]的寻址公式为下面这样(先按行后按列存储):
address_a[i][j] = address_base + (i*m+j) * data_size;

但是,在有些编程语言中,二维数组并不满足上面的说法和寻址公式。比如,Java中的二维数组,第二维可以是不同长度的,而且第二维的三个数组(arr[0]、arr[1]、arr[2])并不是连续存储。

int arr[][] = new int[3][];
arr[0] = new int[1];
arr[1] = new int[2];
arr[2] = new int[3];
复制代码

是不是看的一头雾水?难道数据结构和算法书籍里的讲解脱离实践?难道编程语言中的数组没有完全按照数组的定义来设计?哪个对哪个错呢?

实际上,两个都没错。编程语言中的”数组“并不完全等同于,我们在讲数据结构和算法的时候,提到的”数组“。编程语言在实现自己的”数组“类型的时候,并不是完全遵循数据结构”数组“的定义,而是针对编程语言自身的特点,做了调整。

在不同的编程语言中,数组这种数据类型的实现方式都不大相同,我就拿几个比较典型的编程语言:C/C++、Java、Javascript,来给你展示一下,几种比较有代表性的数组实现方式。

1. C/C++中数组的实现方式

C/C++中的数组,是非常标准的数据结构中的数组,也就是连续存储相同类型的数据的一块内存空间。在C/C++中,不管是基本类型数据,比如int、long、char,还是结构体、对象,在数组中都是连续存储的。我举了一下例子,你可以看下。

int arr[3];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
复制代码

数组arr中存储的是int基本类型的数据,对应的内存存储方式,如果用画图的方式表示出来的话,就是下面这样子。从图中可以看出,数据是存储在一片连续的内存空间中的。

刚刚讲的是用数组存储基本类型数据的例子,我们再来看:用数组存储struct结构体(或者class对象)的例子。

struct Dog {
  char a;
  char b;
};
struct Dog arr[3];
// 为了节省页面,放到了一行里了
arr[0].a = '0'; arr[0].b = '1'; 
arr[1].a = '2'; arr[1].b = '3';
arr[2].a = '4'; arr[2].b = '5';
复制代码

如果我们把这个结构体数组,用画图的方式表示出来,就是下面这个样子。我们发现,结构体数组中的元素,也是存储在一片连续的内存空间中的。

刚刚讲的都是一维数组的数据存储方式,我们再来看下,二维数组的数据存储方式。注意,多维数组跟二维数组大同小异,我们就拿二维数组来讲解。我们来看下面这段代码。

struct Dog {
  char a;  
  char b;
};
struct Dog arr[3][2];
复制代码

我们把上面的struct Dog arr[3][2]对应的数据存储方式,用图画出来的话,就是下面这样子的。从图中,我们发现,C/C++的二维数组,跟数据结构中二维数组是一样的,数据是先按行后按列,并且是连续存储的。

刚刚我们分析了C/C++的基本数据类型数组、结构体或对象数组、以及二维数组。它们的数据存储方式,完全符合数据结构和算法中数组的定义。

你还知道,在其他哪些编程语言中,数组的定义完全符合数据结构中数组的定义吗?

2. Java中数组的实现方式

看完了C/C++中的数组,我们再来看下,Java中的数组。Java中的数组就有点跟数据结构中数组的定义不一样了。我们还是分三种情况来分析。这三种情况分别是:基本数据类型数组、对象数组、二维数组(或多维数组)。

首先,我们先来看下基本数据类型数组,也就是说,数组中存储的是int、long、char等基本数据类型的数据。我们还是拿一段代码来举例。

int arr[] = new int[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
复制代码

如果我们把arr中数据在内存中的存储方式,用图画出来的话,就是下面这个样子的。注意,new申请的空间在堆上,arr存储在栈上。arr存储的是数组空间的首地址。

从图中来看,在Java中,基本数据类型数组还是符合数据结构中数组的定义的。数组中数据是相同类型的、并且存储在一片连续的内存空间中。

看完了基本数据类型数组,我们再来看下对象数组,也就是说,数组中存储的不是int、long、char这种基本类型数据了,而是对象。我们还是拿一个例子来说明。

class Person {  
  private String name;  
  public Person(String name) {
    this.name = name;  
  }
}

Person arr[] = new Person[3];
arr[0] = new Person("0");
arr[1] = new Person("1");
arr[2] = new Person("2");
复制代码

在上面的代码中,数组arr中存储是Person对象。同样,我们还是把数组中数据在内存中的存储方式,用画图的方式表示出来。

从图中,你有没有发现,在Java中,对象数组的存储方式,已经跟C/C++中对象数组的存储方式,不大一样了。在Java中,对象数组中存储的是对象在内存中的地址,而非对象本身。对象本身在内存中并不是连续存储的,而是散落在各个地方的。

了解了一维数组的存储方式,我们再来看下,Java中的二维数组或者多维数组。前面也提到了,因为多维数组跟二维数组类似,我们还是只拿二维数组来讲解。

Java中的二维数组,跟数据结构中二维数组,有很大区别。在Java中,二维数组中的第二维,可以是不同长度的。这句话有点不好理解。我举个例子说明一下。

int arr[][] = new int[3][];
arr[0] = new int[1];
arr[1] = new int[2];
arr[2] = new int[3];
复制代码

在上面的代码中,arr是一个二维数组,第一维长度是3,第二维的长度各不相同:arr[0]长度是1,arr[1]长度是2,arr[2]长度是3。如果我们把这个数组在内存中的存储方式,用图画出来的话,就是下面这个样子。

刚刚这个二维数组存储的是基本数据类型,我们再来看下,如果二维数组中存储的是对象,那又会是怎么的数据存储方式呢?我们还是拿个例子来说明。

Person arr[][] = new Person[3][];
arr[0] = new Person[1];
arr[1] = new Person[2];
arr[2] = new Person[3];

arr[0][0] = new Person("0");
arr[1][1] = new Person("1");
复制代码

在上面的代码中,Person arr[][]是一个二维对象数组。对于它在内存中存储方式,你可以在纸上先画下,或者在自己脑海中想下,然后,再来对比一下我画的下面这张图。

我总结一下。在Java这种编程语言中,数组这种数据类型,除了存储基本数据类型的一维数组之外,对象数组、二维数组,都跟数据结构中数组的定义,有很大区别了。

3. JavaScript中数组的实现方式

如果我们说,Java中的数组,只是根据语言自己的特点,在数据结构数组基础之上,做的改造的话,那JavaScript这种动态脚本语言中的数组,完全就被改的“面目全非”了。

在开头的时候,我们已经提到过,JavaScript中的数组,可以存储不同类型的数据,数组中的数据也不一定是连续存储的(按照下标随机访问的效率不高),并且还能支持变长数组。这完全就是跟数据结构中数组的定义反着的。如果你是一名Web前端工程师,你应该会对此很困惑吧?

实际上,JavaScript中数组的底层实现原理,已经不是依赖数据结构中的数组了。也就是说,JavaScript中的数组只不过是名字叫数组而已,跟数据结构中数组没啥太大关系。

接下来,我们就来看下,JavaScript中的数组,底层是如何实现的呢?实际上,JavaScript中的数组,会根据你存储数据的不同,选择不从的实现方式。

如果数组中存储的是相同类型的数据,那JavaScript就真的用数据结构中数组来实现。也就是说,会分配一块连续的内存空间来存储数据。

如果数组中存储的是非相同类型的数据,那JavaScript就用类似散列表的结构来存储数据。也就是说,数据并不是连续存储在内存中的。这也是JavaScript数组支持存储不同类型数据的原因。

如果你往一个存储了相同类型数据的数组中,插入一个不同类型的数据,那JavaScript会将底层的存储结构,从数组变成散列表。

如果你熟悉JavaScript,你应该知道,JavaScript为了照顾一些底层应用的开发者,还提供了另外一种数据类型,叫做ArrayBuffer。而ArrayBuffer才符合标准的数据结构中数组的定义。它分配一片连续的内存空间,仅仅用来存储相同类型的数据。

最后,总结

数据结构和算法先于编程语言出现。编程语言中是一些数据类型,并不能跟数据结构和算法书籍中讲到的经典数据结构,完全一一对应。比如我们今天讲到的数组,很多编程语言中,都会有数组这种数据类型,而它们往往会根据自己语言的特点,在实现上做了调整。

欢迎留言说说,在你熟悉的语言中,数组这种数据类型符不符合标准的数据结构中数组的定义?或者,说一说,还有哪些数据类型,虽然名字跟数据结构中讲到的一样,但在实现上却有很大不同呢?

关注我的微信公众号:小争哥,获取更多、更新的技术、非技术分享。
作者:前Google工程师,5万人订阅《数据结构和算法之美》专栏作者。
希望通过我加速你的技术、职场进步。

关注下面的标签,发现更多相似文章
评论