0001 /* 0002 * 基于双向链表实现序列 0003 */ 0004 0005 package dsa; 0006 0007 public class Sequence_DLNode extends List_DLNode implements Sequence { 0008 //检查秩r是否在[0, n)之间 0009 protected void checkRank(int r, int n) 0010 throws ExceptionBoundaryViolation { 0011 if (r < 0 || r >= n) 0012 throw new ExceptionBoundaryViolation("意外:非法的秩" + r + ",应该属于[0, " + n + ")"); 0013 } 0014 0015 //若0 <= r < getSize(),则返回秩为r的元素所在的位置;否则,报错--O(n) 0016 public Position rank2Pos(int r) throws ExceptionBoundaryViolation { 0017 DLNode node; 0018 checkRank(r, getSize()); 0019 if (r <= getSize() / 2) { //若秩较小,则 0020 node = header.getNext( );//从前端开始 0021 for (int i = 0; i < r; i++) node = node.getNext(); //逐一扫描 0022 } else {//若秩较大,则 0023 node = trailer.getPrev();//从后端开始 0024 for (int i = 1; i < getSize() - r; i++) node = node.getPrev(); //逐一扫描 0025 } 0026 return node; 0027 } 0028 0029 //若p是序列中的合法位置,则返回存放于p处的元素的秩;否则,报错--O(n) 0030 public int pos2Rank(Position p) throws ExceptionPositionInvalid { 0031 DLNode node = header.getNext(); 0032 int r = 0; 0033 while (node != trailer) { 0034 if (node == p) return(r); 0035 node = node.getNext(); r++; 0036 } 0037 throw new ExceptionPositionInvalid("意外:作为参数的位置不属于序列"); 0038 } 0039 0040 //取秩为r的元素--O(n) 0041 public Object getAtRank(int r) throws ExceptionBoundaryViolation { 0042 checkRank(r, getSize()); 0043 return rank2Pos(r).getElem(); 0044 } 0045 0046 //将秩为r的元素替换为obj--O(n) 0047 public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation { 0048 checkRank(r, getSize()); 0049 return replace(rank2Pos(r), obj); 0050 } 0051 0052 //插入obj,作为秩为r的元素--O(n);返回该元素 0053 public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation { 0054 checkRank(r, getSize() + 1); 0055 if (getSize() == r) insertLast(obj); 0056 else insertBefore(rank2Pos(r), obj); 0057 return obj; 0058 } 0059 0060 //删除秩为r的元素--O(n) 0061 public Object removeAtRank(int r) throws ExceptionBoundaryViolation { 0062 checkRank(r, getSize()); 0063 return remove(rank2Pos(r)); 0064 } 0065 }