线性表（数组）

[18888628835]

线性表（数组）

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

特点1：线性表

什么是线性表呢？线性表就是数据像一根线一样排列，它只有前和后的方向。

链表、队列、栈也是同样的线性表结构。

与线性表对立的概念叫非线性表，比如二叉树、图、堆等就是非线性表，因为它的数据之间并不单单只有前和后的关系。

特点2：连续的内存空间，和一组具有相同类型的数据

在 JS 中，我们有时候可能不会定义具有相同类型的数据，不过数组的连续性在各语言中是相同的。由于有了连续性，所以我们可以对数组进行随机访问。

但同样也是因为数组是连续的，所以当我们要插入或者删除数组中元素时，效率是低下的。

试想一下如果要在数组的中间插入一个元素，那么就需要将插入位置后面的元素都后移。

数组是如何实现根据下标随机访问数组元素的

假设现在我们定义一个数组a，数组a内都是 number 类型，长度为10。

计算机给这个数组一块内存空间，假设为1000-1039，那么内存的首块内存是从1000开始的。

base_address = 1000

当我们需要随机访问一个数据时，计算机会根据我们传入的下标 i，动态计算出需要访问的数据的内存地址，然后再传给我们。

这个公式是这样的

target_address = base_address + i * data_size

这个 data_size 就是数组中元素的内存大小。由于number 数据的字节为4个字节，所以就可以计算出最终要访问的地址。

数组和链表的区别

数组适合查找，链表适合插入删除。

数组支持随机访问，根据下标进行随机访问的复杂度为 O(1)。

低效的插入

假设目前有个数组长度为 n，我们需要在它的第 k 个位置插入一个元素，为了将 k 位置腾出来，我们只能将从原来 k~n-1的位置上的元素给往后移一位。

当 k 为最后一个位置时，我们不需要移动任何，这时候时间复杂度为 O(1)。

如果 k 为第一个位置，那么就需要将 n 个元素都往后移一位，那么时间复杂度就是 O(n)。

如果 k 为其他位置，那么我们通过平均时间复杂度计算，就是(1+2+3+...+n)/n,最终时间复杂度依然为 O(n)。

当我们在一个无序的数组中，需要将某个数据插入到一个位置时，最简单、时间复杂度最低的一个办法就是将原先那个位置的数据放到最后，然后直接将新数据放到那个位置上。这时候时间复杂度为 O(1)。

举个例子，我有一个长度为5的数组array，里面的元素为 a,b,c,d,e

现在我需要将 x 元素放到第三个位置，步骤是这样的：

先将c 放到array[5]，然后让元素 x 赋值给array[2]

利用这个技巧，时间复杂度就会降为 O(1)。

线性查找法

线性查找法是最简单的算法。什么是线性查找法呢？

在生活中假设我们需要从一沓试卷中找到自己的试卷该怎么做？一般我会这么做：

翻第一张：是吗？不是

翻第二张：是吗？不是

...

翻第五张：是吗？是的

结束。

这就是线性查找法，从前往后一直查找。这种算法跟数组 for 循环 + 索引查找元素一样的，所以我们可以写这样一段代码

//线性查找法
function LinearSearch<T>(data: Array<T>, target: T) {
  for (let i = 0; i < data.length; i++) {
    if (data[i] === target) return i;
  }
  return -1;
}
console.log(LinearSearch<number>([1, 2, 3, 4, 5], 6));//-1
console.log(LinearSearch<string>(["1", "2", "3", "4", "5"], "4"));//3

循环不变量

上面的代码中，我们已经知道函数的循环体功能是确定是否目标

当第二轮 for 循环开始时，我们可以得知 data[0]并不是目标。

所以我们可以确认，每当循环开始时，有一个条件肯定是不变的：

data[0...i-1]没找到目标

比如，当 i 为1时，它的前提就是上一轮循环data[0]没有找到目标。

当 i 为2时，它的前提就是上一轮循环data[1]没有找到目标。

那么这个前提就是循环不变量。

循环体所维持的就是这个循环不变量。

循环不变量主要作用就是证明算法的正确性，因为这是一个前提条件，只有明白循环不变量到底是什么，才能帮助我们厘清目标，写出正确的代码。