快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)（線性表）詳解

更新時間：2017年01月24日 08:45:46 作者：%陽陽羊%

本文主要介紹了Java數(shù)據(jù)結(jié)構(gòu)（線性表）的相關(guān)知識。具有很好的參考價值，下面跟著小編一起來看下吧

線性表的鏈?zhǔn)酱鎯εc實(shí)現(xiàn)

實(shí)現(xiàn)線性表的另一種方法是鏈?zhǔn)酱鎯?，即用指針將存儲線性表中數(shù)據(jù)元素的那些單元依次串聯(lián)在一起。這種方法避免了在數(shù)組中用連續(xù)的單元存儲元素的缺點(diǎn)，因而在執(zhí)行插入或刪除運(yùn)算時，不再需要移動元素來騰出空間或填補(bǔ)空缺。然而我們?yōu)榇烁冻龅拇鷥r是，需要在每個單元中設(shè)置指針來表示表中元素之間的邏輯關(guān)系，因而增加了額外的存儲空間的開銷.

單鏈表

鏈表是一系列的存儲數(shù)據(jù)元素的單元通過指針串接起來形成的，因此每個單元至少有兩個域，一個域用于數(shù)據(jù)元素的存儲，另一個域是指向其他單元的指針。這里具有一個數(shù)據(jù)域和多個指針域的存儲單元通常稱為結(jié)點(diǎn)（node）.

結(jié)點(diǎn)接口

package com.wjy.Data_Structure.linearlist.common;
public interface Node {
  /**
   * 獲取結(jié)點(diǎn)數(shù)據(jù)域
   *
   * @return
   */
  public Object getData();
  /**
   * 設(shè)置結(jié)點(diǎn)數(shù)據(jù)域
   *
   * @param obj
   */
  public void setData(Object obj);
}

單鏈表結(jié)點(diǎn)定義

package com.wjy.Data_Structure.linearlist.common;
//單鏈表結(jié)點(diǎn)定義
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;
  }
}

線性表的單鏈表實(shí)現(xiàn)

在使用單鏈表實(shí)現(xiàn)線性表的時候，為了使程序更加簡潔，我們通常在單鏈表的前面添加一個啞元結(jié)點(diǎn)，也稱為頭結(jié)點(diǎn)。在頭結(jié)點(diǎn)中不存儲任何實(shí)質(zhì)的數(shù)據(jù)對象，其 next 域指向線性表中 0 號元素所在的結(jié)點(diǎn)，頭結(jié)點(diǎn)的引入可以使線性表運(yùn)算中的一些邊界條件更容易處理。

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;
//線性表的單鏈表實(shí)現(xiàn)
public class ListSLinked implements List {
  private Strategy strategy; // 數(shù)據(jù)元素比較策略
  private SLNode head; // 單鏈表首結(jié)點(diǎn)引用
  private int size;// 線性表中數(shù)據(jù)元素的個數(shù)
  public ListSLinked() {
    this(new DefaultStrategy());
  }
  public ListSLinked(Strategy strategy) {
    this.strategy = strategy;
    head = new SLNode();
    size = 0;
  }
  /**
   * 輔助方法： 獲取數(shù)據(jù)元素 e 所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
   *
   * @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 的元素所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
   *
   * @param i
   * @return
   */
  private SLNode getPreNode(int i) {
    SLNode p = head;
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }
  /**
   * 輔助方法： 獲取序號為 0<=i<size 的元素所在結(jié)點(diǎn)
   *
   * @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));
    }
  }
}

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)代碼倉庫：

https://git.oschina.net/wjyonlyone/DataStructure

以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時也希望多多支持腳本之家！

您可能感興趣的文章: