一，序列
本文将定义并实现一个通用的序列 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));
}
}
