Java数据结构(线性表) Java数据结构(线性表)详解
%阳阳羊% 人气:0想了解Java数据结构(线性表)详解的相关内容吗,%阳阳羊%在本文为您仔细讲解Java数据结构(线性表)的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,数据结构,下面大家一起来学习吧。
线性表的链式存储与实现
实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销.
单链表
链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点(node).
结点接口
package com.wjy.Data_Structure.linearlist.common; public interface Node { /** * 获取结点数据域 * * @return */ public Object getData(); /** * 设置结点数据域 * * @param obj */ public void setData(Object obj); }
单链表结点定义
package com.wjy.Data_Structure.linearlist.common; //单链表结点定义 public class SLNode implements Node { private Object element; private SLNode next; public SLNode() { } public SLNode(Object ele, SLNode next) { this.element = ele; this.next = next; } public SLNode getNext() { return next; } public void setNext(SLNode next) { this.next = next; } /******** Methods of Node Interface **********/ @Override public Object getData() { return element; } @Override public void setData(Object obj) { element = obj; } }
线性表的单链表实现
在使用单链表实现线性表的时候,为了使程序更加简洁,我们通常在单链表的前面添 加一个哑元结点,也称为头结点。在头结点中不存储任何实质的数据对象,其 next 域指向 线性表中 0 号元素所在的结点,头结点的引入可以使线性表运算中的一些边界条件更容易处理。
package com.wjy.Data_Structure.linearlist.listslinkimpl; import com.wjy.Data_Structure.linearlist.common.DefaultStrategy; import com.wjy.Data_Structure.linearlist.common.List; import com.wjy.Data_Structure.linearlist.common.SLNode; import com.wjy.Data_Structure.linearlist.common.Strategy; import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException; //线性表的单链表实现 public class ListSLinked implements List { private Strategy strategy; // 数据元素比较策略 private SLNode head; // 单链表首结点引用 private int size;// 线性表中数据元素的个数 public ListSLinked() { this(new DefaultStrategy()); } public ListSLinked(Strategy strategy) { this.strategy = strategy; head = new SLNode(); size = 0; } /** * 辅助方法: 获取数据元素 e 所在结点的前驱结点 * * @param e * @return */ private SLNode getPreNode(Object e) { SLNode p = head; while (p.getNext() != null) if (strategy.equal(p.getNext().getData(), e)) return p; else p = p.getNext(); return null; } /** * 辅助方法: 获取序号为 0<=i<size 的元素所在结点的前驱结点 * * @param i * @return */ private SLNode getPreNode(int i) { SLNode p = head; for (; i > 0; i--) p = p.getNext(); return p; } /** * 辅助方法: 获取序号为 0<=i<size 的元素所在结点 * * @param i * @return */ private SLNode getNode(int i) { SLNode p = head.getNext(); for (; i > 0; i--) p = p.getNext(); return p; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { return indexOf(e) != -1; } @Override public int indexOf(Object e) { SLNode p = head.getNext(); int index = 0; while (p != null) if (strategy.equal(p.getData(), e)) { return index; } else { index++; p = p.getNext(); } return -1; } @Override public void insert(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i > size) throw new OutOfBoundaryException("错误,指定的插入序号越界"); SLNode p = getPreNode(i); SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return; } @Override public boolean insertBefore(Object obj, Object e) { SLNode p = getPreNode(obj); if (p != null) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } return false; } @Override public boolean insertAfter(Object obj, Object e) { SLNode p = head.getNext(); while (p != null) if (strategy.equal(p.getData(), obj)) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } else { p = p.getNext(); } return false; } @Override public Object remove(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误,指定的删除序号越界。"); SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; return obj; } @Override public boolean remove(Object e) { SLNode p = getPreNode(e); if (p != null) { p.setNext(p.getNext().getNext()); size--; return true; } return false; } @Override public Object replace(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误,指定的序号越界。"); SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj; } @Override public Object get(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误,指定的序号越界。"); SLNode p = getNode(i); return p.getData(); } }
简单的测试用例
package com.wjy.Data_Structure.linearlist.listslinkimpl; import org.junit.Test; import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked; public class ListSLinkedTest { @Test public void testInsert() { ListSLinked list = new ListSLinked(); for (int i = 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 (int i = 0; i < list.getSize(); i++) { System.out.println(list.get(i)); } } }
数据结构学习代码仓库:
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!
加载全部内容