数据结构与算法（极客时间-王争）05丨数组

关于数组：

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

1、线性表

顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。还有链表、栈和队列。

与之对应的是非线性表，比如二叉树、堆、图等。数据之间不是简单的前后关系。

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

由于这两个特性，数组支持随机访问。但也让其他操作变得低效，如插入、删除。因为为了保证数组的连续性，在进行插入和删除操作时，需要数据搬移。

但在实际操作中，在某些特殊场景下我们将多次删除操作集中在一起执行，会提高删除的效率。

3、如何实现随机访问？

当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i*type_size

 

注意：

1、警惕数组的访问越界问题

2、对于业务开发，直接使用容器就足够了。但是对于一些非常底层的开发，比如开发网络框架，数组优于容器。

 

数组寻址公式

一维

a[k]_address = base_address + k*type_size

二维

对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：

a[i][j]_address = base_address + ( i * n + j) * type_size