线性表--02---顺序表-平芜编程栈

顺序表

定义;

顺序表是在计算机内存中以数组的形式保存的线性表.

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素.
使得线性表中再逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

顺序表的实现

顺序表API设计：

顺序表的遍历:

一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。

在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则需要做如下操作：

让SequenceList实现Iterable接口，重写iterator方法；
在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；

迭代器模式—Iterator

packagemain.java.Algorithms.linear;importjava.util.Iterator;publicclassSequenceList<T>implementsIterable<T>{//存储元素的数组privateT[]eles;//记录当前顺序表中的元素个数privateintN;//..........省略中....................@OverridepublicIterator<T>iterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusor=0;}@OverridepublicbooleanhasNext(){returncusor<N;}@OverridepublicObjectnext(){returneles[cusor++];}}}

//根据参数newSize，重置eles的大小publicvoidresize(intnewSize){//定义一个临时数组，指向原数组T[]temp=eles;//创建新数组eles=(T[])newObject[newSize];//把原数组的数据拷贝到新数组即可for(inti=0;i<N;i++){eles[i]=temp[i];}}

System.arraycopy(temp,0,eles,0, N);

完整代码实现:

importjava.util.Iterator;publicclassSequenceList<T>implementsIterable<T>{//存储元素的数组privateT[]eles;//记录当前顺序表中的元素个数privateintN;//构造方法publicSequenceList(intcapacity){//初始化数组this.eles=(T[])newObject[capacity];//初始化长度this.N=0;}//无参构造方法,初始长度为8publicSequenceList(){//初始化数组this.eles=(T[])newObject[8];//初始化长度this.N=0;}//将一个线性表置为空表publicvoidclear(){this.eles=(T[])newObject[8];this.N=0;}//判断当前线性表是否为空表publicbooleanisEmpty(){returnN==0;}//获取线性表的长度publicintlength(){returnN;}//获取指定位置的元素publicTget(inti){if(i<0||i>=N){thrownewRuntimeException("当前元素不存在！");}returneles[i];}//向线型表中添加元素tpublicvoidinsert(Tt){//元素已经放满了数组，需要扩容if(N==eles.length){resize(2*eles.length);}eles[N++]=t;}//在i元素处插入元素tpublicvoidinsert(inti,Tt){if(i<0||i>N){thrownewRuntimeException("插入的位置不合法");}//元素已经放满了数组，需要扩容if(N==eles.length){resize(2*eles.length);}//先把i索引处的元素及其后面的元素依次向后移动一位for(intindex=N;index>i;index--){eles[index]=eles[index-1];}//再把t元素放到i索引处即可eles[i]=t;//元素个数+1N++;}//删除指定位置i处的元素，并返回该元素publicTremove(inti){if(i<0||i>N-1){thrownewRuntimeException("当前要删除的元素不存在");}//记录索引i处的值Tcurrent=eles[i];//索引i后面元素依次向前移动一位即可for(intindex=i;index<N-1;index++){eles[index]=eles[index+1];}//元素个数-1N--;if(N<eles.length/4){resize(eles.length/2);}returncurrent;}//查找t元素第一次出现的位置publicintindexOf(Tt){if(t==null){thrownewRuntimeException("查找的元素不合法");}for(inti=0;i<N;i++){if(eles[i].equals(t)){returni;}}return-1;}//根据参数newSize，重置eles的大小publicvoidresize(intnewSize){//定义一个临时数组，指向原数组T[]temp=eles;//创建新数组eles=(T[])newObject[newSize];//把原数组的数据拷贝到新数组即可for(inti=0;i<N;i++){eles[i]=temp[i];}}@OverridepublicIterator<T>iterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusor=0;}@OverridepublicbooleanhasNext(){returncusor<N;}@OverridepublicObjectnext(){returneles[cusor++];}}}

测试

importjava.util.Iterator;publicclassSequenceListTest{publicstaticvoidmain(String[]args){//创建顺序表对象SequenceList<String>sl=newSequenceList<>(10);System.out.println("-----------测试插入获取-------------");//测试插入 获取sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");for(inti=0;i<sl.length();i++){System.out.println(sl.get(i));}System.out.println("-----------测试遍历-------------");//测试删除StringremoveResult=sl.remove(0);System.out.println("删除的元素是："+removeResult);//测试遍历Iterator<String>iterator=sl.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}//测试清空System.out.println("-----------测试清空-------------");sl.clear();System.out.println("清空后的线性表中的元素个数为:"+sl.length());for(Stringstr:sl){System.out.println(str);}}}