顺序存储结构

import java.util.Arrays;

/**
* <顺序存储结构>
* 
* @author  
* @version  [版本号, 2011-9-19]
* @see  [相关类/方法]
* @since  [产品/模块版本]
*/
public class SequenceList<T>{
    //初始化容量
    static final int DEFAULT_INITIAL_CAPACITY = 10;
    
    //保存数组的长度
    private int capacity;
    
    //定义一个数组，用于保存顺序线性表的元素
    private Object[] elementData;
    
    //保存顺序表中元素的当前个数
    private int size = 0;
    
    /**
     * <默认构造函数>
     */
    public SequenceList(){
        capacity = DEFAULT_INITIAL_CAPACITY;
        elementData = new Object[capacity];
    }
    
    /**
     * <以一个初始化元素创建顺序线性表>
     */
    public SequenceList(T elment){
        this();
        elementData[0] = elment;
        size++;
    }
    
    public SequenceList(T elment, int initSize){
        capacity = 1;
        //把capacity设为大于initSize的最小的2的N次方
        while (capacity < initSize){
            capacity <<= 1;
        }
        elementData = new Object[capacity];
        elementData[0] = elment;
        size++;
    }
    
    /**
     * <获取顺序线性表的长度>
     * @return [参数说明]
     * 
     * @return int [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public int length(){
        return size;
    }
    
    /**
     * <获取顺序线性表中索引为i处得元素>
     * @param i
     * @return [参数说明]
     * 
     * @return T [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    @SuppressWarnings("unchecked")
    public T get(int i){
        if (i<0 || i>size-1){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        return (T)elementData[i];
    }
    
    /**
     * <查找顺序线性表中指定元素的索引>
     * @param element
     * @return [参数说明]
     * 
     * @return int [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public int locate(T element){
        for (int i=0; i<size; i++){
            if (elementData[i].equals(element)){
                return i;
            }
        }
        return -1;
    }
    
    /**
     * <扩容>
     * @param minCapacity [参数说明]
     * 
     * @return void [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public void ensureCapacity(int minCapacity){
        //如果数组的原有长度小于目前所需的长度
        if (minCapacity > capacity){
            while (capacity < minCapacity){
                //不断地将capacity*2,直到capacity大于minCapacity
                capacity <<= 1;     
            }
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
    
    /**
     * <向顺序线性表的指定位置插入一个元素>
     * @param element
     * @param index [参数说明]
     * 
     * @return void [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public void insert(T element, int index){
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        ensureCapacity(size+1);
        //将指定索引处index之后的所有元素向后移动一格
        System.arraycopy(elementData, index, elementData, 
                index+1, size-index);
        elementData[index] = element;
        size++;
    }
    
    /**
     * <在线性顺序表的开始处添加一个元素>
     * @param element [参数说明]
     * 
     * @return void [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public void add(T element){
        insert(element, size);
    }
    
    /**
     * <删除指定索引处的元素,并返回被删除的元素>
     * @param index
     * @return [参数说明]
     * 
     * @return T [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    @SuppressWarnings("unchecked")
    public T delete(int index){
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        T oldValue = (T)elementData[index];
        int numMoved = size-index-1;
        if (numMoved > 0){
            System.arraycopy(elementData, index+1, 
                    elementData, index, numMoved);
        }
        //清空最后一个元素
        elementData[--size] = null;
        return oldValue;
    }
    
    /**
     * <删除最后一个元素,并返回被删除的元素>
     * @return [参数说明]
     * 
     * @return T [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public T remove(){
        return delete(size-1);
    }
    
    /**
     * <判断线性顺序表是否为空>
     * @return [参数说明]
     * 
     * @return boolean [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public boolean isEmpty(){
        return size==0;
    }
    
    /**
     * <清空线性表>
     * 
     * @return void [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public void clear(){
        Arrays.fill(elementData, null);
    }
    
    /**
     * 输出顺序线性表中的元素
     * @return
     */
    public String toString(){
        if (size == 0){
            return "[]";
        }
        
        StringBuilder sb = new StringBuilder("[");
        for (int i=0; i<size; i++){
            sb.append(elementData[i].toString()+", ");
        }
        int len = sb.length();
        return sb.delete(len-2, len).append("]").toString();
    }
}

 

测试

 

public class Test{
    
    /** <一句话功能简述>
     * <功能详细描述>
     * @param args [参数说明]
     * 
     * @return void [返回类型说明]
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     * @author 
     * @date 2011-9-19
     */
    public static void main(String[] args){
        SequenceList<String> list = new SequenceList<String>();
        list.add("aaaa");
        list.add("bbbb");
        list.add("cccc");
        System.out.println(list);
        //在索引为1处插入一个新的元素
        list.insert("dddd",1);
        System.out.println(list);
        //删除索引为2处得元素
        list.delete(2);
        System.out.println(list);
        //获取cccc字符串在顺序线性表中的位置
        int index = list.locate("cccc");
        System.out.println(index);
    }
    
}