顺序存储结构
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); } }?
?
?