数据结构(七) -- 序列

一，序列

本文将定义并实现一个通用的序列 ADT，从而将向量ADT与列表ADT中的所有方法集成起来——也就是说，这一ADT 将同时支持以秩或位置来访问其中的元素。因此，这种数据结构将适用于解决更多的实际问题。

数据结构(五) -- 向量

数据结构(六) -- 列表

---

二，序列ADT(AbstractDataType)

序列ADT将同时支持向量ADT与列表ADT中的所有方法，此外，还支持以下两个方法——正是借助这两个方法，我们才得以将秩和位置的概念联系起来：

操作方法	功能描述
rank2Pos(r)	若0 ≤ r < getSize()，则返回秩为r 的元素所在的位置 ；否则，报错 输入：一个（作为秩的）整数 输出：位置
pos2Rank(p)	若p 是序列中的合法位置，则返回存放于p 处的元素的秩 ；否则，报错 输入：一个位置 输出：（作为秩的）整数

---

三，基于双向链表实现序列

接口：

package dsa.Sequence;

import other.Position;
import dsa.List.ExceptionPositionInvalid;
import dsa.List.List;
import dsa.Vector.ExceptionBoundaryViolation;
import dsa.Vector.Vector;

/*
 * 序列接口
 */

public interface Sequence extends Vector, List {
    // 若0 <= r < getSize()，则返回秩为r的元素所在的位置；否则，报错
    public Position rank2Pos(int r) throws ExceptionBoundaryViolation;

    // 若p是序列中的合法位置，则返回存放于p处的元素的秩；否则，报错
    public int pos2Rank(Position p) throws ExceptionPositionInvalid;
}

实现：

package dsa.Sequence;

import other.Position;
import dsa.Deque.DLNode;
import dsa.List.ExceptionPositionInvalid;
import dsa.List.List_DLNode;
import dsa.Vector.ExceptionBoundaryViolation;

/*
 * 基于双向链表实现序列
 */
public class Sequence_DLNode extends List_DLNode implements Sequence {
    // 检查秩r是否在[0, n)之间
    protected void checkRank(int r, int n) throws ExceptionBoundaryViolation {
        if (r < 0 || r >= n)
            throw new ExceptionBoundaryViolation("意外：非法的秩" + r + "，应该属于[0, "
                    + n + ")");
    }

    // 若0 <= r < getSize()，则返回秩为r的元素所在的位置；否则，报错--O(n)
    public Position rank2Pos(int r) throws ExceptionBoundaryViolation {
        DLNode node;
        checkRank(r, getSize());
        if (r <= getSize() / 2) {// 若秩较小，则
            node = header.getNext();// 从前端开始
            for (int i = 0; i < r; i++)
                node = node.getNext();// 逐一扫描
        } else {// 若秩较大，则
            node = trailer.getPrev();// 从后端开始
            for (int i = 1; i < getSize() - r; i++)
                node = node.getPrev();// 逐一扫描
        }
        return node;
    }

    // 若p是序列中的合法位置，则返回存放于p处的元素的秩；否则，报错--O(n)
    public int pos2Rank(Position p) throws ExceptionPositionInvalid {
        DLNode node = header.getNext();
        int r = 0;
        while (node != trailer) {
            if (node == p)
                return (r);
            node = node.getNext();
            r++;
        }
        throw new ExceptionPositionInvalid("意外：作为参数的位置不属于序列");
    }

    // 取秩为r的元素--O(n)
    public Object getAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return rank2Pos(r).getElem();
    }

    // 将秩为r的元素替换为obj--O(n)
    public Object replaceAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return replace(rank2Pos(r), obj);
    }

    // 插入obj，作为秩为r的元素--O(n)；返回该元素
    public Object insertAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        checkRank(r, getSize() + 1);
        if (getSize() == r)
            insertLast(obj);
        else
            insertBefore(rank2Pos(r), obj);
        return obj;
    }

    // 删除秩为r的元素--O(n)
    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return remove(rank2Pos(r));
    }
}