数据结构(五) -- 向量

所谓序列（Sequence），就是依次排列的多个对象。比如，每一计算机程序都可以看作一个序列，它由一系列依次排列的指令组成，正是指令之间的次序决定了程序的具体功能。因此，所谓序列，就是一组对象之间的后继与前驱关系。在实际问题中，序列可以用来实现很多种数据结构，因此被认为是数据结构设计的基础。
栈、队列以及双端队列，都可以看作带有附加限制的序列。

** 向量（Vector）和列表（List）都属于序列 **

一，向量

对数组结构进行抽象与扩展之后，就可以得到向量结构，因此向量也称作数组列表（Array list）。向量提供一些访问方法，使得我们可以通过下标直接访问序列中的元素，也可以将指定下标处的元素删除，或将新元素插入至指定下标。为了与通常数组结构的下标（Index）概念区分开来，我们通常将序列的下标称为秩（Rank）。

假定集合 S 由n 个元素组成，它们按照线性次序存放，于是我们就可以直接访问其中的第一个元素、第二个元素、第三个元素……。也就是说，通过[0, n-1]之间的每一个整数，都可以直接访问到唯一的元素e，而这个整数就等于S 中位于e 之前的元素个数——在此，我们称之为该元素的秩（Rank）。不难看出，若元素e 的秩为r，则只要e 的直接前驱（或直接后继）存在，其秩就是r-1（或r+1）。

支持通过秩直接访问其中元素的序列，称作向量（Vector）或数组列表（Array list）。实际上，秩这一直观概念的功能非常强大——它可以直接指定插入或删除元素的位置。

---

二，向量ADT(AbstractDataType)

操作方法	功能描述
getSize()	报告向量中的元素数目 输入：无 输出：非负整数
isEmpty()	判断向量是否为空 输入：无 输出：布尔值
getAtRank(r)	若0 ≤ r < getSize()，则返回秩为r 的那个元素 ；否则，报错 输入：一个整数 输出：对象
replaceAtRank(r, e)	若0 ≤ r < getSize()，则将秩为r 的元素替换为e，并返回原来的元素 ；否则，报错 输入：一个整数和一个对象 输出：对象
insertAtRank(r, e)	若0 ≤ r ≤ getSize()，则将e 插入向量中，作为秩为r 的元素（原秩不小于r 的元素顺次后移），并返回原来的元素 ；否则，报错 输入：一个整数和一个对象 输出：对象
removeAtRank(r)	若0 ≤ r < getSize()，则删除秩为r 的那个元素并返回之（原秩大于r 的元素顺次前移）；否则，报错 输入：一个整数 输出：对象

---

三，基于数组的简单实现

向量接口：

package dsa.Vector;

/*
 * 向量接口
 */
public interface Vector {

    // 返回向量中元素数目
    public int getSize();

    // 判断向量是否为空
    public boolean isEmpty();

    // 取秩为r的元素
    public Object getAtRank(int r) throws ExceptionBoundaryViolation;

    // 将秩为r的元素替换为obj
    public Object replaceAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation;

    // 插入obj，作为秩为r的元素；返回该元素
    public Object insertAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation;

    // 删除秩为r的元素
    public Object removeAtRank(int r) throws ExceptionBoundaryViolation;
}

当作为参数的秩越界时，对应的意外错为ExceptionBoundaryViolation:

package dsa.Vector;

/*
 * 当作为参数的数组下标、向量的秩或列表的位置越界时，本意外将被抛出
 */

public class ExceptionBoundaryViolation extends RuntimeException {

    public ExceptionBoundaryViolation(String err) {
        super(err);
    }
}

基于数组，可以直接实现向量ADT:

package dsa.Vector;

/*
 * 基于数组的向量实现
 */
public class Vector_Array implements Vector {
    private final int N = 1024;// 数组的容量
    private int n = 0;// 向量的实际规模
    private Object[] A;// 对象数组
    // 构造函数

    public Vector_Array() {
        A = new Object[N];
        n = 0;
    }

    // 返回向量中元素数目
    public int getSize() {
        return n;
    }

    // 判断向量是否为空
    public boolean isEmpty() {
        return (0 == n) ? true : false;
    }

    // 取秩为r的元素
    public Object getAtRank(int r)// O(1)
            throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        return A[r];
    }

    // 将秩为r的元素替换为obj
    public Object replaceAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        Object bak = A[r];
        A[r] = obj;
        return bak;
    }

    // 插入obj，作为秩为r的元素；返回该元素
    public Object insertAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        if (0 > r || r > n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        if (n >= N)
            throw new ExceptionBoundaryViolation("意外：数组溢出");
        for (int i = n; i > r; i--)
            A[i] = A[i - 1];// 后续元素顺次后移
        A[r] = obj;// 插入
        n++;// 更新当前规模
        return obj;
    }

    // 删除秩为r的元素
    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        Object bak = A[r];
        for (int i = r; i < n; i++)
            A[i] = A[i + 1];// 后续元素顺次前移
        n--;// 更新当前规模
        return bak;
    }
}

---

四，基于可扩充数组的向量实现

上面给出的向量实现，有个很大的缺陷——数组容量N固定，我们希望向量能够根据实际需要，动态地扩充数组的容量。当然，Java 语言本身并不支持这一功能，与多数程序语言一样，Java 中数组的容量都是固定的。我们的策略是，一旦数组空间溢出（即n≥N），insertAtRank()方法就会做如下处理：

1. 开辟一个容量为2N的新数组B

2. 将A[ ]中各元素搬迁至B[ ]，即B[i]=A[i]，i=0, …, N-1
3. 将A替换为B，即令A=B

package dsa.Vector;

/*
 * 基于可扩充数组的向量实现
 */
public class Vector_ExtArray implements Vector {
    private int N = 8;// 数组的容量，可不断增加
    private int n;// 向量的实际规模
    private Object A[];// 对象数组
    // 构造函数

    public Vector_ExtArray() {
        A = new Object[N];
        n = 0;
    }

    // 返回向量中元素数目
    public int getSize() {
        return n;
    }

    // 判断向量是否为空
    public boolean isEmpty() {
        return (0 == n) ? true : false;
    }

    // 取秩为r的元素
    public Object getAtRank(int r) throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        return A[r];
    }

    // 将秩为r的元素替换为obj
    public Object replaceAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        Object bak = A[r];
        A[r] = obj;
        return bak;
    }

    // 插入obj，作为秩为r的元素；并返回该元素
    public Object insertAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        if (0 > r || r > n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        if (N <= n) {// 空间溢出的处理
            N *= 2;
            Object B[] = new Object[N];// 开辟一个容量加倍的数组
            for (int i = 0; i < n; i++)
                B[i] = A[i];// A[]中内容复制至B[]
            A = B;// 用B替换A（原A[]将被自动回收）
        }
        for (int i = n; i > r; i--)
            A[i] = A[i - 1];// 后续元素顺次后移
        A[r] = obj;// 插入
        n++;// 更新当前规模
        return obj;
    }

    // 删除秩为r的元素
    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        if (0 > r || r >= n)
            throw new ExceptionBoundaryViolation("意外：秩越界");
        Object bak = A[r];
        for (int i = r; i < n - 1; i++)
            A[i] = A[i + 1];// 后续元素顺次前移
        n--;// 更新当前规模
        return bak;
    }
}

---

Java本身也提供了与向量ADT功能类似的两个类：java.util.ArrayList和java.util.Vector。