搜索
数据结构中的线性表，对应着Collection中的List接口。在本节中，我们将做以下三件事第一。我们先来看看线性表的特征第二，自己用JAVA实现List第三，对比的线性表、链式表性能，以及自己的List性能与JDKList性能对比线性表特征：第一，一个特定的线性表，应该是用来存放特定的某一个类型的元素的（元素的“同一性”）第二，除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最后一个元素外，其他每一个元素有且仅有一个直接后继（元素的“序偶性”）第二，元素在线性表中的“下标”唯一地确定该元素在表中的相对位置（元素的“索引性”）又，一.线性表只是数据的一种逻辑结构，其具体存储结构可以为顺序存储结构和链式储存结构来完成，对应可以得到顺序表和链表，二.对线性表的入表和出表顺序做一定的限定，可以得到特殊的线性表，栈(FILO)和队列（FIFO）自己实现线性表之顺序表思路：1.顺序表因为采用顺序存储形式，所以内部使用数组来存储数据2.因为存储的具体对象类型不一定，所以采用泛型操作3.数组操作优点：1.通过指针快速定位到下表，查询快速缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）具体实现代码如下Java代码1./**2.*自己用数组实现的线性表3.*/4.publicclassArrayListE{5.Object[]data=null;//用来保存此队列中内容的数组6.intcurrent;//保存当前为第几个元素的指标7.intcapacity;//表示数组大小的指标8.9./**10.*如果初始化时，未声明大小，则默认为1011.*/12.publicArrayList(){13.this(10);14.}15.16./**17.*初始化线性表，并且声明保存内容的数组大小18.*@paraminitalSize19.*/20.publicArrayList(intinitalSize){21.if(initalSize0){22.thrownewRuntimeException(数组大小错误:+initalSize);23.}else{24.this.data=newObject[initalSize];25.this.current=0;26.capacity=initalSize;27.}28.}29.30./**31.*添加元素的方法添加前，先确认是否已经满了32.*@parame33.*@return34.*/35.publicbooleanadd(Ee){36.ensureCapacity(current);//确认容量37.this.data[current]=e;38.current++;39.returntrue;40.}41.42./**43.*确认系统当前容量是否满足需要,如果满足，则不执行操作如果不满足，增加容量44.*@paramcur当前个数45.*/46.privatevoidensureCapacity(intcur){47.if(cur==capacity){48.//如果达到容量极限，增加10的容量，复制当前数组49.this.capacity=this.capacity+10;50.Object[]newdata=newObject[capacity];51.for(inti=0;icur;i++){52.newdata[i]=this.data[i];53.}54.this.data=newdata;55.}56.}57.58./**59.*得到指定下标的数据60.*@paramindex61.*@return62.*/63.publicEget(intindex){64.validateIndex(index);65.return(E)this.data[index];66.}67.68./**69.*返回当前队列大小70.*@return71.*/72.publicintsize(){73.returnthis.current;74.}75.76./**77.*更改指定下标元素的数据为e78.*@paramindex79.*@parame80.*@return81.*/82.publicbooleanset(intindex,Ee){83.validateIndex(index);84.this.data[index]=e;85.returntrue;86.}87.88./**89.*验证当前下标是否合法，如果不合法，抛出运行时异常90.*@paramindex下标91.*/92.privatevoidvalidateIndex(intindex){93.if(index0||indexcurrent){94.thrownewRuntimeException(数组index错误：+index);95.}96.}97.98./**99.*在指定下标位置处插入数据e100.*@paramindex下标101.*@parame需要插入的数据102.*@return103.*/104.publicbooleaninsert(intindex,Ee){105.validateIndex(index);106.Object[]tem=newObject[capacity];//用一个临时数组作为备份107.//开始备份数组108.for(inti=0;icurrent;i++){109.if(iindex){110.tem[i]=this.data[i];111.}elseif(i==index){112.tem[i]=e;113.}elseif(iindex){114.tem[i]=this.data[i-1];115.}116.}117.this.data=tem;118.returntrue;119.}120.BRBR/**BR*删除指定下标出的数据BR*@paramindexBR*@returnBR*/BRpublicbooleandelete(intindex){BRvalidateIndex(index);BRObject[]tem=newObject[capacity];//用一个临时数组作为备份BR//开始备份数组BRfor(inti=0;icurrent;i++){BRif(iindex){BRtem[i]=this.data[i];BR}elseif(i==index){BRtem[i]=this.data[i+1];BR}elseif(iindex){BRtem[i]=this.data[i+1];BR}BR}BRthis.data=tem;BRreturntrue;BR}BRBR}自己实现线性表之链表思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。实现代码如下Java代码1./**2.*自己用链式存储实现的线性表3.*/4.publicclassLinkedListE{5.6.privateNodeEheader=null;//头结点7.intsize=0;//表示数组大小的指标8.9.publicLinkedList(){10.this.header=newNodeE();11.}12.13.publicbooleanadd(Ee){14.if(size==0){15.header.e=e;16.}else{17.//根据需要添加的内容，封装为结点18.NodeEnewNode=newNodeE(e);19.//得到当前最后一个结点20.NodeElast=getNode(size-1);21.//在最后一个结点后加上新结点22.last.addNext(newNode);23.}24.size++;//当前大小自增加125.returntrue;26.}27.28.publicbooleaninsert(intindex,Ee){29.NodeEnewNode=newNodeE(e);30.//得到第N个结点31.NodeEcNode=getNode(index);32.newNode.next=cNode.next;33.cNode.next=newNode;34.size++;35.returntrue;36.37.}38.39./**40.*遍历当前链表，取得当前索引对应的元素41.*42.*@return43.*/44.privateNodeEgetNode(intindex){45.//先判断索引正确性46.if(indexsize||index0){47.thrownewRuntimeException(索引值有错：+index);48.}49.NodeEtem=newNodeE();50.tem=header;51.intcount=0;52.while(count!=index){53.tem=tem.next;54.count++;55.}56.returntem;57.}58.59./**60.*根据索引，取得该索引下的数据61.*62.*@paramindex63.*@return64.*/65.publicEget(intindex){66.//先判断索引正确性67.if(index=size||index0){68.thrownewRuntimeException(索引值有错：+index);69.}70.NodeEtem=newNodeE();71.tem=header;72.intcount=0;73.while(count!=index){74.tem=tem.next;75.count++;76.}77.Ee=tem.e;78.returne;79.}80.81.publicintsize(){82.returnsize;83.}84.85./**86.*设置第N个结点的值87.*88.*@paramx89.*@parame90.*@return91.*/92.publicbooleanset(intindex,Ee){93.//先判断索引正确性94.if(indexsize||index0){95.thrownewRuntimeException(索引值有错：+index);96.}97.NodeEnewNode=newNodeE(e);98.//得到第x个结点99.NodeEcNode=getNode(index);100.cNode.e=e;101.returntrue;102.}103.104./**105.*用来存放数据的结点型内部类106.*/107.classNodee{108.privateEe;//结点中存放的数据109.110.Node(){111.}112.113.Node(Ee){114.this.e=e;115.}116.117.NodeEnext;//用来指向该结点的下一个结点118.119.//在此结点后加一个结点120.voidaddNext(NodeEnode){121.next=node;122.}123.}124.125.}自己实现线性表之栈栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)特点：后进先出(LIFO)或，先进后出（FILO）因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈