数据结构-线性表-数组

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

线性表

• 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向
• 连续的内存空间和相同类型的数据

正是因为这两个限制，让他具有了的特性，但随之带来的是数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

那是如何做到的随机访问的呢

前置知识：

当向计算机申请内存时，不同类型都有 data_type_size，如 int 类型数据就为 4 个字节。

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

数组

例：内存首地址 base_address = 1000，访问 a[1] = 1000 + 1 * 4;

一维数组寻址公式

// 下标为 i 的数组元素的地址 = 首地址 + i * 数据类型大小
a[i]_address = base_address + i * data_type_size

二维数组寻址公式

// 对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为： 
address = base_address + ( i * n + j) * type_size

ps: 谁规定是4个字节的，如果存的是 string 每个元素大小不同，这时要怎么寻址呢？

数组和链表的区别

• 链表适合插入、删除，时间复杂度 O(1)；
• 数组适合查找，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1);

数组的一些淫巧

数组插入、删除等操作就不过多啰嗦了！

在数组第 k 个位置插入数据

• 如果是有序，就是把数据插入，后面的数据进行搬移。
• 如果是无序，就可以偷个懒，避免大规模数据搬移，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。

总结

数组可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。