线性表--02---顺序表

顺序表定义;顺序表是在计算机内存中以数组的形式保存的线性表.顺序表是在计算机内存中以数组的形式保存的线性表线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素.使得线性表中再逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。顺序表的实现顺序表API设计顺序表的遍历:一般作为容器存储数据都需要向外部提供遍历的方式因此我们需要给顺序表提供遍历方式。在java中遍历集合的方式一般都是用的是foreach循环如果想让我们的SequenceList也能支持foreach循环则需要做如下操作让SequenceList实现Iterable接口重写iterator方法在SequenceList内部提供一个内部类SIterator,实现Iterator接口重写hasNext方法和next方法迭代器模式—Iteratorpackagemain.java.Algorithms.linear;importjava.util.Iterator;publicclassSequenceListTimplementsIterableT{//存储元素的数组privateT[]eles;//记录当前顺序表中的元素个数privateintN;//..........省略中....................OverridepublicIteratorTiterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusor0;}OverridepublicbooleanhasNext(){returncusorN;}OverridepublicObjectnext(){returneles[cusor];}}}顺序表的容量可变:考虑容器的容量伸缩性其实就是改变存储数据元素的数组的大小那我们需要考虑什么时候需要改变数组的大小1.添加元素时添加元素时应该检查当前数组的大小是否能容纳新的元素如果不能容纳则需要创建新的容量更大的数组我们这里创建一个是原数组两倍容量的新数组存储元素。2.移除元素时移除元素时应该检查当前数组的大小是否太大比如正在用100个容量的数组存储10个元素这样就会造成内存空间的浪费应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4则创建一个是原数组容量的1/2的新数组存储元素。//根据参数newSize重置eles的大小publicvoidresize(intnewSize){//定义一个临时数组指向原数组T[]tempeles;//创建新数组eles(T[])newObject[newSize];//把原数组的数据拷贝到新数组即可for(inti0;iN;i){eles[i]temp[i];}}System.arraycopy(temp,0,eles,0, N);完整代码实现:importjava.util.Iterator;publicclassSequenceListTimplementsIterableT{//存储元素的数组privateT[]eles;//记录当前顺序表中的元素个数privateintN;//构造方法publicSequenceList(intcapacity){//初始化数组this.eles(T[])newObject[capacity];//初始化长度this.N0;}//无参构造方法,初始长度为8publicSequenceList(){//初始化数组this.eles(T[])newObject[8];//初始化长度this.N0;}//将一个线性表置为空表publicvoidclear(){this.eles(T[])newObject[8];this.N0;}//判断当前线性表是否为空表publicbooleanisEmpty(){returnN0;}//获取线性表的长度publicintlength(){returnN;}//获取指定位置的元素publicTget(inti){if(i0||iN){thrownewRuntimeException(当前元素不存在);}returneles[i];}//向线型表中添加元素tpublicvoidinsert(Tt){//元素已经放满了数组需要扩容if(Neles.length){resize(2*eles.length);}eles[N]t;}//在i元素处插入元素tpublicvoidinsert(inti,Tt){if(i0||iN){thrownewRuntimeException(插入的位置不合法);}//元素已经放满了数组需要扩容if(Neles.length){resize(2*eles.length);}//先把i索引处的元素及其后面的元素依次向后移动一位for(intindexN;indexi;index--){eles[index]eles[index-1];}//再把t元素放到i索引处即可eles[i]t;//元素个数1N;}//删除指定位置i处的元素并返回该元素publicTremove(inti){if(i0||iN-1){thrownewRuntimeException(当前要删除的元素不存在);}//记录索引i处的值Tcurrenteles[i];//索引i后面元素依次向前移动一位即可for(intindexi;indexN-1;index){eles[index]eles[index1];}//元素个数-1N--;if(Neles.length/4){resize(eles.length/2);}returncurrent;}//查找t元素第一次出现的位置publicintindexOf(Tt){if(tnull){thrownewRuntimeException(查找的元素不合法);}for(inti0;iN;i){if(eles[i].equals(t)){returni;}}return-1;}//根据参数newSize重置eles的大小publicvoidresize(intnewSize){//定义一个临时数组指向原数组T[]tempeles;//创建新数组eles(T[])newObject[newSize];//把原数组的数据拷贝到新数组即可for(inti0;iN;i){eles[i]temp[i];}}OverridepublicIteratorTiterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusor0;}OverridepublicbooleanhasNext(){returncusorN;}OverridepublicObjectnext(){returneles[cusor];}}}测试importjava.util.Iterator;publicclassSequenceListTest{publicstaticvoidmain(String[]args){//创建顺序表对象SequenceListStringslnewSequenceList(10);System.out.println(-----------测试插入获取-------------);//测试插入 获取sl.insert(姚明);sl.insert(科比);sl.insert(麦迪);sl.insert(1,詹姆斯);for(inti0;isl.length();i){System.out.println(sl.get(i));}System.out.println(-----------测试遍历-------------);//测试删除StringremoveResultsl.remove(0);System.out.println(删除的元素是removeResult);//测试遍历IteratorStringiteratorsl.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);}}}分析:顺序表的时间复杂度:get(i):不难看出不论数据元素量N有多大只需要一次eles[i]就可以获取到对应的元素所以时间复杂度为O(1);insert(int i,T t):每一次插入都需要把i位置后面的元素移动一次随着元素数量N的增大移动的元素也越多时间复杂为O(n);remove(int i):每一次删除都需要把i位置后面的元素移动一次随着数据量N的增大,移动的元素也越多时间复 杂度为O(n);扩容操作:由于顺序表的底层由数组实现数组的长度是固定的所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的在某些需要扩容的结点处耗时会突增尤其是元素越多这个问题越明显顺序表查找效率高,插入和删除效率低java中ArrayList实现:java中ArrayList集合的底层也是一种顺序表使用数组实现同样提供了增删改查以及扩容等功能。Java集合—03–List为什么有ArrayList,还要自己编写顺序表?ArrayList为了实现其通用性,健壮性,代码写的有些臃肿(接近1500行),可能实际效率不是很高,我们可以根据自己开发中的需求,自定义适合具体需求的数据结构,来提高代码的实际运行效率