线性表 Java 语言版

---

综述：

线性表是其组成元素之间具有线性关系的一种线性结构。

对线性表的基本操作主要有：获得元素、设置元素值，遍历，插入，删除，查找，替换和排序等。

可以采用　顺序存储结构　和　链式存储结构　表示线性表。

---

1.1 线性表抽象数据类型：

线性表是由 n ( n ≥ 0 ) 个类型相同的数据元素 a0，a1，a2 ... ，a(n-1) 组成的有限序列。元素的类型可以是整数、浮点数、字符或者是类。

n 是线性表元素的个数，称为线性表的 长度（Length）。若 n = 0，则为 空表；若 n > 0，则 a(i) 有且仅有一个 前驱元素 a(i-1) 和一个 后继元素 a(i+1)。a0 没有前驱元素，a(n-1)没有后继元素。

声明线性表抽象数据类型 List<T>如下，描述线性表，获取元素值、设置元素值、插入、删除等操作，其中，采用序号 i 指定进行操作的元素位置。（0 ≤ i < n）

ADT List<T>{
    boolean isEmpty()           // 判断线性表是否为空，为空则返回 true
    int     size()              // 返回线性表元素个数（长度）
    T       get(int i)          // 返回第 i 个元素
    void    set(int i,T x)      // 设置第 i 个元素为 x
    String  toString()          // 返回线性表所有元素的描述字符串
    int     insert(int i, T x)  // 插入 x 作为第 i 个元素，返回 x 序号。
    int     insert(T x)         // 在线性表的最后插入 x 元素，返回 x 序号
    T       remove()            // 删除第 i 个元素，返回被删除元素
    void    clear()             // 删除线性表所有元素
    int     search(T key)       // 查找首次出现的与 key 相等元素，返回元素序号
    boolean cotains(T key)      // 判断是否包含关键字为 key 的元素
    int insertDifferent(T x)    // 插入不重复元素
    T       remove(T key)       // 删除首次出现的与 key 相等的元素，返回被删除元素
    boolean equals(Object obj)  // 比较两个线性表所有元素是否对应相等
    void addAll(List<T> list)   // 在 this 中添加 list 的所有元素，集合并运算
}

---

1.2 线性表的顺序存储和实现：

1.2.1 线性表的顺序存储结构

---- ( 1 ) 数组 ----

数组是实现顺序存储结构的基础。

数组存储具有相同数据结构的元素集合。一维数组占用一块连续的内存空间，数组的存储单元个数称为数组数组容量。计算第 i 个元素地址所需要的时间是一个常量，时间复杂度是 O(1) ，与元素序号 i 无关。

存取元素的时间复杂度是 O(1) 的数据额结构称为 随机存取结构。数组是随机存取结构。

数组通过下标识别元素，元素的下标是其存储单元的序号，表示元素在数组中的位置，一维数组通过一个下标来 唯一确定一个元素，二维数组使用两个下标来唯一确定一个元素，以此类推。

数组一旦占用一片存储空间，其地址和容量就是确定的，不能更改！因此数组只能进行 赋值，取值 两种随机存取操作，不能进行插入，删除操作。当数组容量不够时，不能进行 就地扩容。

**---- ( 2 ) 顺序表 ---- **

image

线性表的顺序存储结构称为顺序表 ( Sequential List )。它使用一维数组依次存放线性表从 a0 到 a(n-1) 的数据元素。所以数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。

设 Loc( a0 ) 表示 a0 的存储地址，每个元素占用 c 个字节，则 **a(i) **的存储地址公式为：

这是 a(i) 元素与 序号 i 的线性函数。同样，计算元素地址的时间复杂度仍然为 O( 1 )。

当顺序表使用的数组容量不够时，解决数据溢出的办法是，申请另一块更大容量的数组空间，并将原数组元素进行复制，这样扩充了顺序表的容量。

---

1.2.2 顺序表类：

声明顺序表类 SeqList<T> 如下：（约定数据元素不能是空对象 null ， 文件名为 SeqList.java，Java 预定文件名同类名）

public class SeqList<T> extends Object{
    protected Objcet[] element;
    protected int n;
    public SeqList(int length){
        this.element = new Object[length]; // 申请数组的存储空间，初始化元素为 null
        // 若 length < 0，则 java 会抛出负数组长度异常 java.lang.NegativeArraySizeException
        this.n = 0;
    }

    public SeqList(){
        this(64);       //创建默认容量 64 的空表;
    }

    public SeqList(T[] values){
        this(values.length);
        for(int i =0; i<values.length; i++ ){
            this.element[i] = values[i];  // 复制元素，O(n)，对象引用赋值    
        }
        this.n = element.length;
    }

    public boolean isEmpty(){
        return this.n == 0;
    }

    public int size(){
        return this.n;
    }

    public T get(int i){
        if( i>=0 && i<this.n )
            return (T)this.elementp[i];
        return null;                    // 返回第 i 个元素，若 i 越界，则返回 null
    }

    // 设置第 i 个元素为 x, i∈[0,n], 若 i 越界，则抛出序号异常; 若 x == null, 则抛出空对象异常
    public void set(int i, T x){
        if(x == null)
            throw new NullPointerException("x == NULL");
        if( i>=0 && i<this.n )
            this.element[i] = x;
        else
            throw new IndexOutOfBoundsException(i+"");
    }

    public String toString(){
        String str = this.getClass().getName()+":(";   // 返回类名
        if(this.n>0)
            str += this.element[0].toString();
        for(int i = 1; i<this.n; i++)
            str += "," + this.element[i].toString();  
        // 执行 T类型的 toString() 方法，运行时多态
        return str + ")";
    }
}

顺序表对象引用实例的存储结构

---

1.3 顺序表的插入操作：

顺序表的插入和删除操作都需要移动数据元素。插入x作为顺序表的第 i 个元素，首先要先把 向后移动，空出第 i 个 位置，然后将 x 插入。

插入元素

如果数组已满，则不能插入，称为 数组溢出( Overflow )。解决的办法是：申请一个更大容量的数组并复制原有的全部元素，扩充了顺序表。

数组满时插入元素

接下来我们给出 insert() 的代码实现：

public int insert(int i, T x){
    if( x == null )
        throw new NullPointerException("x == null");
    if( i < 0 )
        i = 0;
    if( i > this.n )
        i = this.n;
    Object[] source = this.element;
    if( this.n == element.length ){         // 若数组满了，则扩充顺序表的容量
        this.element = new Object[source.length*2];     // 重新申请一个更大的数组
        for(int j = 0; j<i; j++){
            this.element[j] = source[j];    // 复制当前数组前 i-1 个元素
        }
        for(int j = this.n - 1; j>=i; j--)  // 从 i 开始至表尾的元素向后移动，次序从后向前
            this.element[j+1] = source[j];
        this.element[i] = x;
        this.n++；
        return i;       // 返回 i 的序号
    }
}

// 顺序表尾部插入 x 元素，返回 x 序号，成员方法重载:
public int insert(T x){     return this.insert(this.n, x)   }

对顺序表进行插入操作时，算法所花费的时间主要在于移动元素。若插在最前面，则需要移动 n 个元素；若插在最后面，则移动元素个数为 0，设插入 x 作为第 i 个元素的概率为 ，则插入一个元素的平均移动次数为：

如果在各个位置插入元素的概率相同，，则有：

换言之，在等概率的情况下，插入一个元素平均需要移动顺序表元素总量的一半，时间复杂度是 O(n)。

---

1.4 顺序表的删除操作：

顺序表删除元素 a(i)，必须将其之后的所有元素由依次向前移动，如下图所示：

顺序表删除

接下来我们给出 SeqList<T> 类声明以下 remove( i ) 和 clear() 成员方法，删除元素：

public T remove(int i){
    if( this.n > 0 && i >= 0 && i < this.n ){
        T old = (T) this.element[i];
        for(int j = i; j<this.n; j++)
            this.element[j] = this.element[j+1];
        this.element[this.n - 1] = null;
        this.n --;
        return old;
    }
    return null;
}

public void clear(){
    this.n = 0;  // 直接设置长度为0， 释放数组空间由 Java的垃圾回收机制完成
}

删除元素操作所花费的时间主要用于移动元素，同添加的操作一样，在等概率情况下删除一个元素平均移动 个元素，时间复杂度为 O( n )。

---

1.5 顺序表的查找操作

根据查找条件，对顺序表进行查找操作，采用顺序查找算法。

在查找过程中，需要将 key 与顺序表元素逐个比较是否相等。而比较对象相等的规则由元素所属的 T 类的 equals(Object) 方法实现。

SeqList<T>类声明以下 search( key ) 成员方法实现查找操作，key 包含作为查找依据的关键字的数据项。

public int search(T key){
    for(int i = 0; i<this.n; i++){
        if( key.equals(this.element[i]))    // 执行 T 类的 equals 方法，运行时多态
            return i;
        return -1;                          // 空表或者未找到
    }
}

// 判断是否包含关键字为 key 元素
public boolean contains(T key){ return this.search(key) != -1 }

顺序查找的比较次数，取决于元素位置。设顺序表元素个数为 n，若各元素的查找概率，第 i ( 0 ≤ i < n ) 个元素查找成功的比较次数为 i+1，平均比较次数为 ；查找不成功比较 n 次。因此顺序查找的时间复杂度为 O( n )。

---

小结：

综上所述，顺序表的静态特性良好，动态特性很差，具体说明如下：

1. 顺序表利用元素的物理存储次序反应线性表元素的逻辑次序，顺序表示随机存取结构，存取元素 a(i) 和获得其前驱、后继元素 的时间复杂度都为 O( 1 ) 。

2. 插入和删除的效率很低，每插入或删除一个元素，元素移动量大，平均移动一半数量的元素。再者，数组的容量不可更改，容易因为容量小而造成数组溢出。

   当申请了另一个更大容量的数组时，进行数组复制，需要移动全部元素，操作效率更低了。