线性结构初探:数组，线性表

目录:

1.数组特性

2.数组与线性表的关系

数组特性：

今天我们来讲一讲线性结构，计算机中，数组应该是最常见的数据结构了，这是一种典型的线性结构，它用一组连续的内存空间来存储一组相同类型的数据。它有如下特性：

1.随机访问：他有一个很重要的特性，就是可以通过下标访问，如果你知道你想要的元素的下标，便能非常快的获得数组中对应的值，这个特性很重要，后续介绍的二分查找使用的就是这个特性，在一些课本中，这个特性被称为随机访问。
2.编号从0开始：在大多数程序语言中，数组的下标编号都是从0开始。
3.低效的删除，插入：如果在数组的尾部删除或者插入，则是最好情况的时间复杂度O(1)，但是数组删除，插入操作的平均时间复杂度和最坏时间复杂度都是O(n)，因为需要移动元素。
4.警惕越界异常：使用数组需要注意越界异常，比如下面这段JAVA代码：

int[] temp = new int[10];
temp[10] = 5;

这种情况就会发生数组越界，因为数组的下标都是从0开始。
5.数组的长度是固定的：数组需要在初始化时声明长度。并且运行中无法动态变化。

线性表与数组的关系：

线性表与数组密不可分，因为实际上我们所看到的线性表，它的底层就是数组，只是在数组的基础上，增加了一些操作（算法）。首先看一个代码段:

template<typename E>
class AList:public List<E>{
  int maxSize;/*线性表最大长度*/
  int listSize;/*当前线性表中元素个数*/
  E* listArray;
}

代码的第五行E* listArray 表示的就是一个数组，E是数据的类型。一般我们说底层是什么什么，其实也就是成员变量的事。 一般我们所说的线性表都支持增删改查操作，其实这都是之前的程序员封装好的，在类中操作成员变量，比如append函数（注：该函数i未判断边界为题）。

void append(const E& it){
  listArray[listSize++] = it;
}

其实我们就是直接append一个元素到成员变量-数组中，并且把listSize自增1。其实有兴趣的话可以自己实现一些算法。比如删除某个元素。更新某个元素的值。

由于线性表的底层就是数组，几乎数组有的缺陷，线性表都有。

Q：为什么在有些语言中，线性表可以不带长度？

A：比如在JAVA中，我们经常这么声明线性表：

ArrayList<int> array = new ArrayList<int>();

上文提到的数组在声明时必须要带长度，为什么线性表可以不用呢?因为线性表是程序员自己封装的，所以可以在构造器中，给定了一个默认值，如果在声明时未带长度，则使用这个默认值作为长度。

Q：为什么不带长度的线性表可以无限插入元素？？

数组的长度是不可变的，但是如果达到了数组长度的上限还需要近一步插入元素的话，需要进行以下步骤:

1.声明一个新的线性表;

2.将原线性表的元素插入到新线性表中;

3.删除原线性表；

由于数组是是使用的连续的内存空间，所以第二步中，我们可以使用内存拷贝的方式来快速实现，比如System.arraycopy()。而不用一个个遍历复制。