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

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

*

* @param i

* @return

*/

private SLNode getPreNode(int i) {

SLNode p = head;

for (; i > 0; i--)

p = p.getNext();

return p;

}

/**

* 辅助方法： 获取序号为 0<=i

*

* @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();

}

http:// 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

*

* @param i

* @return

*/

private SLNode getPreNode(int i) {

SLNode p = head;

for (; i > 0; i--)

p = p.getNext();

return p;

}

/**

* 辅助方法： 获取序号为 0<=i

*

* @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();

}

http:// 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

*

* @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();

}

http:// 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。