数据结构之数组

以你之姓@ 2023-01-22 14:52 3阅读 0赞

**一.什么是数组？**  
今天要介绍的主角就是-数组，数组也是数据呈线性排列的一种数据结构。在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。

**数组**  
![在这里插入图片描述][20210520135602879.png]  
如上就是数组的概念图，Blue、Yellow、Red 作为数据存储在数组中，其中 a 是数组的名字，后面 \[\] 中的数字表示该数据是数组中的第几个数据，该数字也就是数组下标，下标从 0 开始计数，比如 Red 就是数组 a 的第 2 个数据。

那么为什么许多编程语言中的数组都从 0 开始编号的呢？先别急，可以先自己思考下，将会在文末进行讲解。  
![在这里插入图片描述][20210520135623184.png]  
从图中可以看出来，数组的数据是按顺序存储在内存的连续空间内的。  
![在这里插入图片描述][20210520135637973.png]  
由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据，也就是随机访问。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]  
比如现在我们想要访问 Red，如果是链表的话，只能使用指针就只能从头开始查找，但在数组中，只需要指定 a\[2\]，便能直接访问 Red。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 1]  
但是，如果想在任意位置上添加或者删除数据，数组的操作就要比链表复杂多了。这里我们尝试将 Green 添加到第 2 个位置上  
![在这里插入图片描述][20210520135748499.png]  
首先，在数组的末尾确保需要增加的存储空间。  
![在这里插入图片描述][20210520135810835.png]  
为了给新数据 Green 腾出位置，要把已有数据一个个移开，首先把 Red 往后移。  
![在这里插入图片描述][20210520135829917.png]  
然后把 Yellow 往后移。  
![在这里插入图片描述][20210520135848959.png]  
最后在空出来的位置上写入 Green  
![在这里插入图片描述][20210520135901996.png]  
添加数据的操作就完成了。

反过来，如果想要删除 Green 呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 2]首先，删掉目标数据 Green。  
![在这里插入图片描述][20210520135937620.png]

然后把后面的数据一个个往空位移，先把 Yellow 往前移。  
![在这里插入图片描述][20210520140000689.png]  
接下来移动 Red。  
![在这里插入图片描述][20210520140016846.png]  
最后再删掉多余的空间，这样一来 Green 便被删掉了。  
补充  
这里讲解一下对数组操作所花费的运行时间，假设数组中有 n 个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的 O（1）。

通过数组下标计算出内存地址的寻址公式如下：

a[i]_address = base_address + i * data_type_size

其中 base\_address 为内存块的首地址，data\_type\_size 表示数组中每个元素的大小。

但另一方面，想要向数组中添加新数据时，必须把目标位置后面的数据一个个移开。所以，如果在数组头部添加数据，就需要 O（n） 的时间，删除操作同理。

在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂。

我们可以根据哪种操作较为频繁来决定使用哪种数据结构。  
![在这里插入图片描述][20210520140111999.png]  
最后，让我们一起来思考下刚开始提到的问题：为什么很多编程语言中数组都从 0 开始编号？  
解惑  
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。如果用 a 来表示数组的首地址，a\[0\] 就是偏移为 0 的位置，也就是首地址，a\[k\] 就表示偏移 k 个 type\_size 的位置，所以计算 a\[k\] 的内存地址只需要用这个公式：

a[k]_address = base_address + k * type_size

但是，如果数组从 1 开始计数，那我们计算数组元素 a\[k\] 的内存地址就会变为：

a[k]_address = base_address + (k-1)*type_size

对比两个公式，可以发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

除此之外还有历史原因，C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比如 Matlab。甚至还有一些语言支持负数下标，比如 Python。

**总结**

这篇文章主要介绍了数据结构中常用的数组，数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。有一种高效的查找算法是二分查找法，就是利用了数组随机访问的特性。

总得来说，数组适用于多操作多、写操作少的场景。

[20210520135602879.png]: /images/20221020/a34eb90a7c5c47a58abeb77b90e195c1.png
[20210520135623184.png]: /images/20221020/4236a7202cf040cca80a6be5082608ed.png
[20210520135637973.png]: /images/20221020/24a3dc88ee964dbeb5a2688e7a08ad09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]: /images/20221020/8172812199764e2c8dd7e1b72dca60cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221020/20740328076b4e1e96f4091db86901e0.png
[20210520135748499.png]: /images/20221020/1d3db39b48694cea84d4cb350a76dd3c.png
[20210520135810835.png]: /images/20221020/4a24c8e1c1ae4eb18d2376c60173d754.png
[20210520135829917.png]: /images/20221020/0f0ac366bfdd4e93af433d1859d9f612.png
[20210520135848959.png]: /images/20221020/c201813ca7b24b6aa873acba11a28504.png
[20210520135901996.png]: /images/20221020/d48b1db6c9004813a9c1f6679eda4e2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 2]: /images/20221020/c8c203f970d64c1cbb585a9bf99e9164.png
[20210520135937620.png]: /images/20221020/af799373ca6743289ea68af8b86db570.png
[20210520140000689.png]: /images/20221020/4c61f5e799914a3aaec9f1d89b187eb9.png
[20210520140016846.png]: /images/20221020/e0050a5230c741258e4e9c327513cb8d.png
[20210520140111999.png]: /images/20221020/e701afa68fec4801912927dad642fcbe.png