0001 /* 0002 * 基于数组的向量实现 0003 */ 0004 0005 package dsa; 0006 0007 public class Vector_Array implements Vector { 0008 private final int N = 1024;//数组的容量 0009 private int n = 0;//向量的实际规模 0010 private Object[] A;//对象数组 0011 0012 //构造函数 0013 public Vector_Array() { 0014 A = new Object[N]; 0015 n = 0; 0016 } 0017 0018 //返回向量中元素数目 0019 public int getSize() { return n; } 0020 0021 //判断向量是否为空 0022 public boolean isEmpty() { return (0 == n) ? true : false; } 0023 0024 //取秩为r的元素 0025 public Object getAtRank(int r)//O(1) 0026 throws ExceptionBoundaryViolation { 0027 if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外:秩越界"); 0028 return A[r]; 0029 } 0030 0031 //将秩为r的元素替换为obj 0032 public Object replaceAtRank(int r, Object obj) 0033 throws ExceptionBoundaryViolation { 0034 if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外:秩越界"); 0035 Object bak = A[r]; 0036 A[r] = obj; 0037 return bak; 0038 } 0039 0040 //插入obj,作为秩为r的元素;返回该元素 0041 public Object insertAtRank(int r, Object obj) 0042 throws ExceptionBoundaryViolation { 0043 if (0 > r || r > n) throw new ExceptionBoundaryViolation("意外:秩越界"); 0044 if (n >= N) throw new ExceptionBoundaryViolation("意外:数组溢出"); 0045 for (int i = n; i > r; i--) A[i] = A[i-1]; //后续元素顺次后移 0046 A[r] = obj;//插入 0047 n++;//更新当前规模 0048 return obj; 0049 } 0050 0051 //删除秩为r的元素 0052 public Object removeAtRank(int r) 0053 throws ExceptionBoundaryViolation { 0054 if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外:秩越界"); 0055 Object bak = A[r]; 0056 for (int i = r; i < n; i++) A[i] = A[i+1]; //后续元素顺次前移 0057 n--;//更新当前规模 0058 return bak; 0059 } 0060 }