Java数据结构（线性表）详解

2024-03-01 19:12:02 405

线性表的链式存储与实现

实现线性表的另一种方法是链式存储，即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销.

单链表

链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点（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

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！

Java数据结构（线性表）详解

热门推荐

随机推荐