2-1 数组

1. 线性表

何为线性表？顾名思义，线性表就是线性的一种数据结构，即只有前与后，没有其他方向。常见的线性表有数组、链表、队列、栈。

2. 数组概念

数组是最基础的数据结构之一。数组是一种线性表，使用一段连续的内存来存放一组相同数据类型的数据。
那么，数组存在的意义是什么呢？

• 数组采用连续的数据结构，这种特殊的内存方式可以很方便的根据下标进行数据访问。
• 数组用来存放一组相同的数据类型，这样就可以通过寻址公式找到每一个元素的内存位置。

数组的寻址公式如下：

• 一维数组：base_addr + k * data_size。（base_addr 为首地址，data_size为内部存放的数据类型大小）
• 二位数组：假设有一个数组a[m][n]，那么a[i][j]的地址为 base_addr + (i n + j)data_size。

  3. 随机访问

  数组特殊的内存占用方式，使得数组能够通过下标进行随机访问，这就使得通过下标访问数组的复杂度为。
  注意：仅在通过下标访问时时间复杂度为。

因为数组支持随机访问，所以就很容易出现数组越界的行为。例如：数组只有三个元素，却访问了第四个元素。数组越界通常导致程序出现一些难以预料的行为，调试时也很难发现，因此我们一定要避免数组越界。

4. 查找、插入、删除

• 数组是一种线性表，每次查找时均需要遍历，因此最好时间复杂度为，最差时间复杂度为，平均时间复杂度为，计算公式为。
• 数组插入时，若插入位置在数组末尾，此时为最好时间复杂度，若插入位置在数组头部，则原来所有元素均需要后移，此时为最差时间复杂度，平均时间复杂度为，计算公式与查找一样。
• 数组删除时，若删除位置在数组末尾，此时为最好时间复杂度，若插入位置在数组头部，则原来所有元素均需要前移，此时为最差时间复杂度，平均时间复杂度为，计算公式与查找一样。

上述分析可以看出，数组的插入、删除均需要对原有数据进行搬移，那么如何优化呢？

• 若数组有序，则插入、删除只能进行搬移，无法优化。
• 若数组无序，那么插入时，我们就可以将原来位置的数据移至数组末尾，新的数据插入即可。

• 若数组无需，那么删除时，我们可以将删除元素进行标记，当数组满了之后，触发统一的删除、搬移操作，这样就可以避免删除多个数据时引发的多次搬移。

  5. 思考：为什么数组下标从0开始？

  似乎从我们刚接触数组开始，老师就告诉我们数组下标是从0开始的，那么大家有没有想过为什么从0开始呢？
  我们从两方面来分析：

• 从寻址公式来看，若是下标从1开始，那么寻址公式就变为base_addr + （k -1)* data_size，我们可以看到这里多进行了一次减法运算，会造成效率浪费。

• 由于一些历史原因，c语言将数组下标定为从0开始，后续的其他语言也就遵守了这一规则。