线性表的多种实现（如：数组，向量，链表）

/** * 使用可扩展数组实现线性表 */ package com.cn.edu.hust.list; public class ExpandableArrayList<T> implements ListInterface<T> { private T[] entry; //线性表元素数组 private int length; //线性表元素当前的个数 private static final int DEFAUL_INITIAL_CAPACITY=10; //线性表的缺省长度 /** * default constructor */ public ExpandableArrayList(){ this(DEFAUL_INITIAL_CAPACITY); } /** * constructor * @param maxSize */ public ExpandableArrayList(int initialCapacity){ length=0; entry=(T[])new Object[initialCapacity]; } /** *Task:从一个给定的对象数组创建线性表 * @param array */ public ExpandableArrayList(T[] array){ int arrayLength=array.length; entry=(T[])new Object[arrayLength]; for(int index=0;index<arrayLength;index++) entry[index]=array[index]; length=arrayLength; } /** * task:往线性表的末尾插入新元素 * @param newEntry作为新元素插入的对象 * @return 如果插入成功则返回true,否则返回false */ public boolean add(T newEntry){ if(isArrayFull()) doubleArray(); //在当前元素的最后插入一个新元素 entry[length]=newEntry; length++; return true; } /** * task:往线性表的指定位置插入一个新元素。原本位于指定位置及其以上的元素移动到线性表中下一个更高的位置。线性表的大小加1 * @param newPosition 指定新元素位置的一个整数；newPosition>=1并且newPositon<=getLength()+1 * @param newEntry 作为新元素插入的对象 * @return 如果插入成功则返回true，否则返回false */ public boolean add(int newPosition,T newEntry){ boolean isSuccessful=false; if((newPosition>=1)&&(newPosition<=length+1)){ if(isArrayFull()) doubleArray(); makeRoom(newPosition); entry[newPosition-1]=newEntry; length++; isSuccessful=true; } return isSuccessful; } /** * task:从线性表中删除指定位置的元素，原本位于比指定位置更高位置的元素移动到线性表中下一个更低的位置，线性表的大小减1 * @param givenPositon指定删除元素位置的一个整数；givenPositon>=1并且givenPositon<=getLength()+1 * @return 如果删除成功,返回givenPositon位置的元素,否则返回null */ public T remove(int givenPosition){ T result=null;//返回值 if((givenPosition>=1)&&(givenPosition<=length)){ assert!isEmpty();//断言,如果正确，什么也不做，如果错误，报断言错误，并停止程序的执行 result=entry[givenPosition-1];//获得要删除的元素 //将后继元素向前移动 if(givenPosition<length){ removeGap(givenPosition); } length--; } return result; } /** * Task:删除线性表中所有的元素 */ public void clear(){ for(int index=0;index<length-1;index++){ entry[index]=null;//释放数组中的元素 //remove(index);//与上面的语句效果是一样的 } length=0; } /** * Task:替换线性表中指定位置的元素 * @param givenPositon指定替换元素位置的一个整数；givenPositon>=1并且givenPositon<=getLength() * @param newEntry用以替换givenPositon位置的元素的对象 * @return 如果替换成功则返回true，否则返回false */ public boolean replace(int givenPosition,T newEntry){ boolean isSuccessful=false; if(givenPosition>=1&&givenPosition<=length){ entry[givenPosition-1]=newEntry; isSuccessful=true; } return isSuccessful; } /** * Task:检索线性表中指定位置的元素 * @param givenPositon指定元素位置的一个整数；givenPositon>=1并且givenPositon<=getLength() * @return 如果找到指定的线性表元素，返回对它的引用，非法返回null */ public T getEntry(int givenPosition){ T result=null; if((givenPosition>=1)&&(givenPosition<=length)){ assert!isEmpty(); result=entry[givenPosition];//获得指定位置的元素 } return result; } /**Task:确定线性表是否含有一个给定的元素 * @param anEntry表示待查元素的对象 * @return 如果线性表含有anEntry，返回true，否则返回false */ public boolean contains(T anEntry){ boolean found=false; for(int index=0;!found&&(index<length);index++){ if(anEntry.equals(entry[index])) found=true; } return found; } /**Task：获取线性表的长度 * @return 返回线性表中当前所含元素个数的整数 */ public int getLength(){ return length; } /**Task:确定线性表是否为空 * @return 如果线性表为空，返回true，否则返回false */ public boolean isEmpty(){ return length==0; } /**Task:确定当前线性表是否已满 * @return 如果线性表已满，返回true，否则返回false */ public boolean isArrayFull(){ return length==entry.length; } /**Task:确定线性表是否已满 * @return false */ public boolean isFull(){ return false;//可扩展数组永远不会满的 } /**Task:按照它们在线性表中的顺序显示线性表中的所有的元素，每行一个元素 */ public void display(){ for(int index=0;index<length;index++){ System.out.println(entry[index]); } } /** * Task:返回线性表中一个给定对象的位置 * @return如果找到指定的元素，返回其在线性表中的位置，否则返回0 */ public int getPosition(T anEntry){ int result=0; for(int index=0;index<length;index++){ if(anEntry.equals(entry[index])){ result=index+1; break; } } return result; } /** * Task:交换线性表中两个元素的位置 * @param firstPosition firstPosition>=1&&firstPosition<=length * @param secondPosition secondPosition>=1&&secondPosition<=length */ public boolean exchangePosition(int firstPosition,int secondPosition){ boolean isSuccessful=false; if((firstPosition>=1)&&(firstPosition<=length)&&(secondPosition>=1)&&(secondPosition<=length)){ exchange(firstPosition,secondPosition); isSuccessful=true; } return isSuccessful; } /** * Task:比较两个线性表中元素是否相等 * @param secondEntry * @return 当两个线性表中对应的元素都相等时，返回true，否则false */ public boolean equals(ListInterface<T> secondEntry){ boolean isEquals=true; int firstLength=this.getLength(); int secondLength=secondEntry.getLength(); if(firstLength==secondLength){ for(int index=0;index<firstLength;index++){ if(!this.getEntry(index).equals(secondEntry.getEntry(index))){ isEquals=false; break; } } }else isEquals=false; return isEquals; } /** * 本类特有的方法 * Task:为一个新元素在newPosition位置腾出空间 * newPosition>=1并且newPositon<=getLength()+1 */ private void makeRoom(int newPosition){ for(int index=length;index>=newPosition;index--){ entry[index]=entry[index-1]; } } /** * Task:将删除元素之后的元素平移到下一个更低的位置 * gievenPosition>=1并且gievenPosition<=getLength() */ private void removeGap(int givenPosition){ assert(givenPosition>=1&&givenPosition<length); int removeIndex=givenPosition-1; int lastIndex=length-1; for(int index=removeIndex;index<lastIndex;index++){ entry[index]=entry[index+1]; } } /** * Task:将存放线性表元素的数组的长度加倍 */ public void doubleArray(){ T[] oldList=entry; int oldSize=oldList.length; entry=(T[])new Object[2*oldSize]; //将元素从旧数组复制到更大的新数组里面 for(int index=0;index<oldSize;index++){ entry[index]=oldList[index]; } } /** * Task:交换线性表中两个元素的位置 * @param firstPosition * @param secondPosition */ private void exchange(int firstPosition,int secondPosition){ assert firstPosition!=secondPosition; T temp=entry[firstPosition-1]; entry[firstPosition-1]=entry[secondPosition-1]; entry[secondPosition-1]=temp; } }