线性表

定义：n个元素的线性序列即为线性表。

1 package ds.linerlist;  2 /**  3  * 顺序表的实现  4  * @author Bao Yiming  5  * @param 
     
        6  */  7 public class ArrayList
      
        {  8     private Object[] data = null; // data: 用来保存此线性表数据的数组  9     private int capacity; // capacity： 线性表的容量 10     private int current; // current： 当前数据的下标 11     /** 12      * 初始化为声明大小，则设置为10。 13      */ 14     ArrayList() { 15         this(10); 16     } 17     /** 18      * 初始化线性表，声明保存数据的数组大小。 19      * @param initialSize 顺序表的初始化大小 20      */ 21     ArrayList(int initialSize) { 22         if (initialSize >= 0) { 23             this.capacity = initialSize; 24             data = new Object[initialSize]; 25             current = 0; 26         } else { 27             throw new RuntimeException("初始化大小不能小于0：" + initialSize); 28         } 29     } 30     /** 31      * 在线性表的末尾添加元素，添加之前确认线性表是否已满 32      * @param e 待加入的元素 33      * @return 34      */ 35     public boolean AddElement(E e) { 36         ensureCapacity(); 37         data[current] = e; 38         ++current; 39         return true; 40     } 41     /** 42      * 检查存储数据的数组容量，如果数组已经满，则扩充容量；否则不操作。 43      */ 44     private void ensureCapacity() { 45         int index; 46         if (current == capacity) { 47             capacity *= 2; 48             Object[] newData = new Object[capacity]; 49             for(index = 0; index < current; ++index) { 50                 newData[index] = data[index]; 51             } 52             data = newData; 53         } 54     } 55     /** 56      * 返回下标为index的元素 57      * @param index 欲取得元素的下标 58      * @return 59      */ 60     public E get(int index) { 61         validateIndex(index); 62         return (E) data[index]; 63     } 64     /** 65      *  66      * @param index 待插入的位置 67      * @param e 待插入的元素 68      * @return 69      */ 70     public boolean set(int index, E e) { 71         validateIndex(index); 72         data[index] = e; 73         return true; 74     } 75     /** 76      * 验证下标值是否合法，非法时抛出异常 77      * @param index 待验证的下标值 78      */ 79     private void validateIndex(int index) { 80         if (index < 0 || index > current) { 81             throw new RuntimeException("无效的下标：" + index); 82         } 83     } 84     /** 85      * 返回当前顺序表的大小 86      * @return 87      */ 88     public int size() { 89         return current; 90     } 91     /** 92      * 在指定位置插入指定元素 93      * @param index 待插入的位置 94      * @param e 待插入的元素 95      * @return 96      */ 97     public boolean insert(int index, E e) { 98         validateIndex(index); 99         ensureCapacity();100         for (int temp = current; temp > index; --temp) {101             data[temp] = data[temp - 1];102         }103         data[index] = e;104         return true;105     }106     /**107      * 删除下标为index元素108      * @param index 待删除元素的下标109      * @return110      */111     public boolean delete(int index) {112         validateIndex(index);113         for ( ; index < current - 1; ++index) {114             data[index] = data[index + 1];115         }116         data[current - 1] = null;117         --current;118         return true;119     }120     @Override121     public String toString() {122         String str = "[ ";123         for (Object o : data) {124             if (o != null) {125                 str += o + " ";126             }127         }128         str += "]";129         return str;130     }131 }