线性表

线性表：零个或多个数据元素的有限序列

线性表的数据对象集合为{a1, a2, ……, an}，每个数据元素的类型相同。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

线性表的顺序存储结构

用一段地址连续的存储单元一次存储线性表的数据元素

a1	a2	......	ai-1	ai	......	an

顺序存储结构需要三个属性：

• 存储空间的起始位置：数据data，它的存储位置就是存储空间的存储位置。

• 线性表的最大存储容量：数组长度MaxSize。

• 线性表的当前长度：length。

  注意，数组长度与线性表长度的区别：数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作而变化。在任意时刻，线性表的长度应该小于等于数组的长度。

内存地址计算方法

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入删除操作，因此分配的数组空间要大于等于当前线性表的长度。

内存中的地址，就和图书馆里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，即地址。由于是顺序结构，所以当第一个位置确定之后，后面的位置都是可以计算的。比如，我在班里的成绩为第五名，我后面的10名同学成绩名次分别就是6，7，...，15，因为5+1，5+2，...，5+10。每个数据元素，不管他是整形、实型还是字符型，他都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系：

LOC(ai+1)=LOC(ai)+c

所以对于第i个数据元素ai的存储位置可以有a1推算得出：

LOC(ai)=LOC(a1)+(i-1)*c

通过这个公式，可以算出线性表中任意位置的地址，任何位置，都是相同的时间。它的时间复杂度为O(1)。通常把具有这一特点的存储结构称为随机存取结构。

顺序存储结构的插入与删除(Java的ArraryList类)

1. 获取元素操作代码：

public class ArrayList<E> {
 
  transient Object[] elementData;
  
  public E get(int index) {
    Objects.checkIndex(index, this.size);
    return this.elementData(index);
  }
  
  E elementData(int index) {
        return this.elementData[index];
    }
}

2. 插入操作

举个例子，春运买火车票。大家都排队排的好好的。这是来了个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，家里母亲病了，着急回去看她，队伍这么长，你可否让我排你的前面？”你心一软，就同意了。后面的人就得全部都退一步。这个例子其实已经说明了线性表的顺序存储结构，在插入数据时的实现过程。

插入的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i，表长加1。

代码实现：

public boolean add(E e) {
        ++this.modCount;
        this.add(e, this.elementData, this.size);
        return true;
}
​
public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }
​
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}

3. 删除操作

接着上面的例子。就在此时，出现一个警察对美女说，“跟我到局里走一趟。”女子离开了队伍。原来她是倒卖火车票的黄牛，装可怜来插队买票。这时排队的人，又均向前移动了一步。这就是线性表的顺序存储结构删除元素的过程。

删除思路：

如果删除位置不合理，抛出异常；

取出删除元素；

从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；

表长减1。

代码实现：

public E remove(int index) {
    Objects.checkIndex(index, this.size);
    Object[] es = this.elementData;
    E oldValue = es[index];
    this.fastRemove(es, index);
    return oldValue;
}
​

插入和删除的时间复杂度。

最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素。

最坏的情况，如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度为O(n)，因为向后或向前移动了原来1位置后的所有元素。

至于平均的情况，由于元素插入到第i个位置，或者删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或者删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为(n-1)/2，即O(n)。

分析得，线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。说明它比较适合元素个数不太变化，而更多是存取数据的应用。

线性表顺序存储结构的优缺点

优点：

• 无须为表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地取表中任意位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的”碎片“

参考：

《大话数据结构》程杰