Java数据结构(线性表)详解
线性表的链式存储与实现
实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或删除运算时,不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销.
单链表
链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点(node).
结点接口
packagecom.wjy.Data_Structure.linearlist.common; publicinterfaceNode{ /** *获取结点数据域 * *@return */ publicObjectgetData(); /** *设置结点数据域 * *@paramobj */ publicvoidsetData(Objectobj); }
单链表结点定义
packagecom.wjy.Data_Structure.linearlist.common; //单链表结点定义 publicclassSLNodeimplementsNode{ privateObjectelement; privateSLNodenext; publicSLNode(){ } publicSLNode(Objectele,SLNodenext){ this.element=ele; this.next=next; } publicSLNodegetNext(){ returnnext; } publicvoidsetNext(SLNodenext){ this.next=next; } /********MethodsofNodeInterface**********/ @Override publicObjectgetData(){ returnelement; } @Override publicvoidsetData(Objectobj){ element=obj; } }
线性表的单链表实现
在使用单链表实现线性表的时候,为了使程序更加简洁,我们通常在单链表的前面添加一个哑元结点,也称为头结点。在头结点中不存储任何实质的数据对象,其next域指向线性表中0号元素所在的结点,头结点的引入可以使线性表运算中的一些边界条件更容易处理。
packagecom.wjy.Data_Structure.linearlist.listslinkimpl; importcom.wjy.Data_Structure.linearlist.common.DefaultStrategy; importcom.wjy.Data_Structure.linearlist.common.List; importcom.wjy.Data_Structure.linearlist.common.SLNode; importcom.wjy.Data_Structure.linearlist.common.Strategy; importcom.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException; //线性表的单链表实现 publicclassListSLinkedimplementsList{ privateStrategystrategy;//数据元素比较策略 privateSLNodehead;//单链表首结点引用 privateintsize;//线性表中数据元素的个数 publicListSLinked(){ this(newDefaultStrategy()); } publicListSLinked(Strategystrategy){ this.strategy=strategy; head=newSLNode(); size=0; } /** *辅助方法:获取数据元素e所在结点的前驱结点 * *@parame *@return */ privateSLNodegetPreNode(Objecte){ SLNodep=head; while(p.getNext()!=null) if(strategy.equal(p.getNext().getData(),e)) returnp; else p=p.getNext(); returnnull; } /** *辅助方法:获取序号为0<=i<size的元素所在结点的前驱结点 * *@parami *@return */ privateSLNodegetPreNode(inti){ SLNodep=head; for(;i>0;i--) p=p.getNext(); returnp; } /** *辅助方法:获取序号为0<=i<size的元素所在结点 * *@parami *@return */ privateSLNodegetNode(inti){ SLNodep=head.getNext(); for(;i>0;i--) p=p.getNext(); returnp; } @Override publicintgetSize(){ returnsize; } @Override publicbooleanisEmpty(){ returnsize==0; } @Override publicbooleancontains(Objecte){ returnindexOf(e)!=-1; } @Override publicintindexOf(Objecte){ SLNodep=head.getNext(); intindex=0; while(p!=null) if(strategy.equal(p.getData(),e)){ returnindex; }else{ index++; p=p.getNext(); } return-1; } @Override publicvoidinsert(inti,Objecte)throwsOutOfBoundaryException{ if(i<0||i>size) thrownewOutOfBoundaryException("错误,指定的插入序号越界"); SLNodep=getPreNode(i); SLNodeq=newSLNode(e,p.getNext()); p.setNext(q); size++; return; } @Override publicbooleaninsertBefore(Objectobj,Objecte){ SLNodep=getPreNode(obj); if(p!=null){ SLNodeq=newSLNode(e,p.getNext()); p.setNext(q); size++; returntrue; } returnfalse; } @Override publicbooleaninsertAfter(Objectobj,Objecte){ SLNodep=head.getNext(); while(p!=null) if(strategy.equal(p.getData(),obj)){ SLNodeq=newSLNode(e,p.getNext()); p.setNext(q); size++; returntrue; }else{ p=p.getNext(); } returnfalse; } @Override publicObjectremove(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的删除序号越界。"); SLNodep=getPreNode(i); Objectobj=p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; returnobj; } @Override publicbooleanremove(Objecte){ SLNodep=getPreNode(e); if(p!=null){ p.setNext(p.getNext().getNext()); size--; returntrue; } returnfalse; } @Override publicObjectreplace(inti,Objecte)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。"); SLNodep=getNode(i); Objectobj=p.getData(); p.setData(e); returnobj; } @Override publicObjectget(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。"); SLNodep=getNode(i); returnp.getData(); } }
简单的测试用例
packagecom.wjy.Data_Structure.linearlist.listslinkimpl; importorg.junit.Test; importcom.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked; publicclassListSLinkedTest{ @Test publicvoidtestInsert(){ ListSLinkedlist=newListSLinked(); for(inti=0;i<10;i++){ list.insert(i,i+1); } System.out.println("删除:"+list.remove(0)); System.out.println(list.contains(1)); list.insertBefore(2,100); list.insertAfter(2,101); list.replace(list.getSize()-1,1000); for(inti=0;i<list.getSize();i++){ System.out.println(list.get(i)); } } }
数据结构学习代码仓库:
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持毛票票!