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