天天看點
傳回

資料結構---->線性表

線性表

一、線性表抽象資料類型

1.1、定義

線性表是指n (n>=0)個相同類型的資料元素a0,a1,...an-1所構成的有限線性序列，其一般描述為：LinearList=(a0，a1，…，an－1)

1) 其中LinearList稱為線性表的名稱

2) 每個ai（n-1≥i≥0）稱為線性表的資料元素，可以是整數、浮點數、字元或類

3) 表中相鄰元素之間存在着順序關系：将ai-1稱為ai的直接前趨，ai+1稱為ai的直接後繼

4) 具體n的值稱為線性表中包含有資料元素的個數，也稱為線性表的長度

5) 當n的值等于0時，表示該線性表是空表

離散定義如下：B=<A,R>,其中A包含n個結點的集合(a0,a1,…an-1)，R是關系的集合{(ai-1,ai)|i=1,2,..n}，可見R隻有一種類型的關系，即線性關系。

抽象資料類型定義如下：

         ADT LinearList

         {

         資料對象:D＝{ai|ai∈元素集合,i=0,1,2,..n-1        n>=0}

         資料關系:R={<ai-1,ai>|ai-1,ai∈元素集合,i=1,2,..n}

         基本操作：{插入，删除，查找等}

         }        ADT LinearList

1.2、線性表接口 

package LinearList;

import util.OutOfBoundaryException;

public interface LinearList {
  // 傳回線性表的大小，即資料元素的個數。
  public int getSize();

  // 如果線性表為空傳回true，否則傳回false。
  public boolean isEmpty();

  // 判斷線性表是否包含資料元素e
  public boolean contains(Object e);

  // 傳回資料元素e 線上性表中的序号
  public int indexOf(Object e);

  // 将資料元素e 插入到線性表中i 号位置
  public void insert(int i, Object e) throws OutOfBoundaryException;

  // 将資料元素e 插入到元素obj 之前
  public boolean insertBefore(Object obj, Object e);

  // 将資料元素e 插入到元素obj 之後
  public boolean insertAfter(Object obj, Object e);

  // 删除線性表中序号為i 的元素,并傳回之
  public Object remove(int i) throws OutOfBoundaryException;

  // 删除線性表中第一個與e 相同的元素
  public boolean remove(Object e);

  // 替換線性表中序号為i 的資料元素為e，傳回原資料元素
  public Object replace(int i, Object e) throws OutOfBoundaryException;

  // 傳回線性表中序号為i 的資料元素
  public Object get(int i) throws OutOfBoundaryException;
}

附兩個接口(下面的代碼會用的到)

線性表序号越界異常

package util;

//線性表中出現序号越界時抛出該異常
public class OutOfBoundaryException extends RuntimeException {
  public OutOfBoundaryException(String err) {
    super(err);
  }
}

線性表中比較元素是否相等及大小判斷（類似于comparable接口,indexOf()、contains（）方法會用得到）

package util;

public interface Strategy {
  // 判斷兩個資料元素是否相等
  public boolean equal(Object obj1, Object obj2);

  // 比較兩個資料元素的大小 如果obj1 < obj2 傳回-1 如果obj1 = obj2 傳回0 35 如果obj1 > obj2 傳回1
  public int compare(Object obj1, Object obj2);
}

線性表有兩種存儲方式，對應地把線性表分成了兩類：

   順序存儲結構的順序表（或稱向量存儲、一維數組存儲）

   鍊式存儲結構的連結清單

二、線性表的順序表示和實作

順序表：用順序存儲方法存儲的線性表簡稱為順序表

public class SeqList<T> implements LinearList<T>              //順序表類

2.1順序存儲方法：

即用一組連續的記憶體單元依次存放線性表中的資料元素（元素在記憶體的實體存儲次序與它們線上性表中的邏輯次序相同）。在記憶體中開辟一片連續存儲空間，但該連續存儲空間的大小要大于或等于順序表的長度，然後讓線性表中第一個元素存放在連續存儲空間第一個位置，第二個元素緊跟着第一個之後，其餘依此類推

LOC(ai) = LOC(a0) + i×K

其中LOC(a0)為0 号元素a0的存儲位址，通常稱為線性表的起始位址。

通常利用一維數組來表示順序表的資料存儲區域，這是因為數組具有如下特點：

1) 資料中的元素間的位址是連續的

2) 數組中所有元素的資料類型是相同的

3) 這與線性表的順序存儲結構(順序表)是類似的

2.2、線性表的數組實作 

package sequence_Linear_List;

import util.OutOfBoundaryException;
import util.Strategy;
import LinearList.LinearList;

//線性表的順序存儲
public class SeqList implements LinearList {
  private final int LEN = 8; // 數組的預設大小
  private Strategy strategy; // 資料元素比較政策
  private int size; // 線性表中資料元素的個數
  private Object[] elements; // 資料元素數組

  // 構造方法

  public SeqList() {
    // this(new DefaultStrategy());
  }

  public SeqList(Strategy strategy) {
    this.strategy = strategy;
    size = 0;
    elements = new Object[LEN];
  }

  // 傳回線性表的大小，即資料元素的個數。
  public int getSize() {
    return size;
  }

  // 如果線性表為空傳回true，否則傳回false。
  public boolean isEmpty() {
    return size == 0;
  }

  // 判斷線性表是否包含資料元素e
  public boolean contains(Object e) {
    for (int i = 0; i < size; i++)

      if (strategy.equal(e, elements[i]))
        return true;
    return false;
  }

  // 傳回資料元素e 線上性表中的序号
  public int indexOf(Object e) {
    for (int i = 0; i < size; i++)
      if (strategy.equal(e, elements[i]))
        return i;
    return -1;
  }

  // 将資料元素e 插入到線性表中i 号位置
  public void insert(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i > size)
      throw new OutOfBoundaryException("錯誤，指定的插入序号越界。");
    if (size >= elements.length)
      expandSpace();
    for (int j = size; j > i; j--)
      elements[j] = elements[j - 1];
    elements[i] = e;
    size++;
    return;
  }

  private void expandSpace() {
    Object[] a = new Object[elements.length * 2];
    for (int i = 0; i < elements.length; i++)
      a[i] = elements[i];
    elements = a;
  }

  // 将資料元素e 插入到元素obj 之前
  public boolean insertBefore(Object obj, Object e) {
    int i = indexOf(obj);
    if (i < 0)
      return false;
    insert(i, e);
    return true;
  }

  // 将資料元素e 插入到元素obj 之後
  public boolean insertAfter(Object obj, Object e) {
    int i = indexOf(obj);
    if (i < 0)
      return false;
    insert(i + 1, e);
    return true;

  }

  // 删除線性表中序号為i 的元素,并傳回之
  public Object remove(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("錯誤，指定的删除序号越界。");
    Object obj = elements[i];
    for (int j = i; j < size - 1; j++)
      elements[j] = elements[j + 1];
    elements[--size] = null;
    return obj;
  }

  // 删除線性表中第一個與e 相同的元素
  public boolean remove(Object e) {
    int i = indexOf(e);
    if (i < 0)
      return false;
    remove(i);
    return true;
  }

  // 替換線性表中序号為i 的資料元素為e，傳回原資料元素
  public Object replace(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("錯誤，指定的序号越界。");
    Object obj = elements[i];
    elements[i] = e;
    return obj;
  }

  // 傳回線性表中序号為i 的資料元素
  public Object get(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("錯誤，指定的序号越界。");
    return elements[i];
  }
}

三、線性表的鍊式表示和實作

實作線性表的另一種方法是鍊式存儲，即用指針将存儲線性表中資料元素的那些單元依次串聯在一起。這種方法避免了在數組中用連續的單元存儲元素的缺點，因而在執行插入或删除運算時，不再需要移動元素來騰出空間或填補空缺。然而我們為此付出的代價是，需要在每個單元中設定指針來表示表中元素之間的邏輯關系，因而增加了額外的存儲空間的開銷。

首先給出各種接口，下面的單連結清單和雙向連結清單實作類中會用到。

連結清單的節點接口：

package linked_list;

public interface Node {
  // 擷取結點資料域
  public Object getData();

  // 設定結點資料域
  public void setData(Object obj);
}

疊代器接口 Iterator：提供一種方法順序通路一個聚集對象中各個元素，而又不需暴露該對象的内部表示。（java也有）

package util;

public interface Iterator {
  // 移動到第一個元素
  public void first();

  // 移動到下一個元素
  public void next();

  // 檢查疊代器中是否還有剩餘的元素
  public boolean isDone();

  // 傳回目前元素
  public Object currentItem();
}

連結表的疊代實作類

package linked_list;

import util.Iterator;
import util.OutOfBoundaryException;

public class LinkedListIterator implements Iterator {
  private LinkedList list;// 連結表
  private Node current;// 目前結點

  // 構造方法

  public LinkedListIterator(LinkedList list) {
    this.list = list;
    if (list.isEmpty()) // 若清單為空
      current = null; // 則目前元素置空
    else
      current = list.first();// 否則從第一個元素開始
  }

  // 移動到第一個元素
  public void first() {
    if (list.isEmpty()) // 若清單為空
      current = null; // 則目前元素置空
    else
      current = list.first();// 否則從第一個元素開始
  }

  // 移動到下一個元素
  public void next() throws OutOfBoundaryException {
    if (isDone())
      throw new OutOfBoundaryException("錯誤：已經沒有元素。");
    if (current == list.last())
      current = null; // 目前元素後面沒有更多元素
    else
      current = list.getNext(current);
  }

  // 檢查疊代器中是否還有剩餘的元素
  public boolean isDone() {
    return current == null;
  }

  // 傳回目前元素
  public Object currentItem() throws OutOfBoundaryException {
    if (isDone())
      throw new OutOfBoundaryException("錯誤：已經沒有元素。");
    return current.getData();
  }
}

InvalidNodeException類

package util;

//InvalidNodeException 異常
public class InvalidNodeException extends RuntimeException {
  public InvalidNodeException(String err) {
    super(err);
  }
}

3.1單連結清單

單連結清單結點定義

package single_Linked_LinerList;

public class SLNode {
  private Object element;
  private SLNode next;

  public SLNode() {
    this(null, null);
  }

  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 **************/
  public Object getData() {

    return element;
  }

  public void setData(Object obj) {
    element = obj;
  }
}

線性表的單連結清單實作（基于資料或者序号的操作）

package single_Linked_LinerList;

import util.OutOfBoundaryException;
import util.Strategy;
import LinearList.LinearList;

//線性表的單連結清單實作
public class SingleLinkedList implements LinearList {
  private Strategy strategy; // 資料元素比較政策
  private SLNode head; // 單連結清單首結點引用
  private int size; // 線性表中資料元素的個數

  public SingleLinkedList() {
    // this(new DefaultStrategy());
  }

  public SingleLinkedList(Strategy strategy) {
    this.strategy = strategy;
    head = new SLNode();
    size = 0;
  }

  // 輔助方法：擷取資料元素e 所在結點的前驅結點
  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 的元素所在結點的前驅結點
  private SLNode getPreNode(int i) {
    SLNode p = head;
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }

  // 擷取序号為0<=i<size 的元素所在結點
  private SLNode getNode(int i) {
    SLNode p = head.getNext();

    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }

  // 傳回線性表的大小，即資料元素的個數。
  public int getSize() {
    return size;
  }

  // 如果線性表為空傳回true，否則傳回false。
  public boolean isEmpty() {
    return size == 0;
  }

  // 判斷線性表是否包含資料元素e
  public boolean contains(Object e) {
    SLNode p = head.getNext();
    while (p != null)
      if (strategy.equal(p.getData(), e))
        return true;
      else
        p = p.getNext();
    return false;
  }

  // 傳回資料元素e 線上性表中的序号
  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;
  }

  // 将資料元素e 插入到線性表中i 号位置
  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;
  }

  // 将資料元素e 插入到元素obj 之前
  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;
  }

  // 将資料元素e 插入到元素obj 之後
  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;
  }

  // 删除線性表中序号為i 的元素,并傳回之
  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;
  }

  // 删除線性表中第一個與e 相同的元素
  public boolean remove(Object e) {
    SLNode p = getPreNode(e);
    if (p != null) {
      p.setNext(p.getNext().getNext());
      size--;
      return true;

    }
    return false;
  }

  // 替換線性表中序号為i 的資料元素為e，傳回原資料元素
  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;
  }

  // 傳回線性表中序号為i 的資料元素
  public Object get(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("錯誤，指定的序号越界。");
    SLNode p = getNode(i);
    return p.getData();
  }
}

3.2基于結點的操作

線性表抽象資料類型中，其提供的操作主要是指對線性表中的資料元素及其序号的。例如插入作就是基于序号和元素進行的，insert(i,e)是在序号為i 的地方插入元素，insertBefore 、與insertAfter 是在某個資料元素之前或之後插入新的元素。這種基于序号的操作實際上并不适合采用（單向或雙向）連結清單來實作，因為為了在連結清單中定位資料元素或序号，我們不得不沿着結點間的next（或pre）引用，從連結清單前端（雙向連結清單也可以從後端）開始逐一掃描。

我們考察一種經常需要完成的操作：順序的将線性表中每個資料元素都通路一遍。如果使用鍊式存儲實作的線性表ListSLinked所提供的get(i)操作來實作，則需要Ο(n2)時間。因為在使用連結清單實作取i号資料元素的操作時，需要将結點的引用從連結清單前端向後移動i次，而取i+1 号資料元素時不能在上一次操作——取i号資料元素——的過程中受益，而必須重新從連結清單前端開始定位，則通路線性表中每個元素一次所需要的總時間為0+1+2+…+n-1=Ο(n2)。這一時間複雜度是難以接受的。

實際上，除了通過序号來通路線性結構中的元素，還可通過其他途徑來得到線性結構中的元素。例如我們能夠直接通過結點來通路資料元素，通過3.3.1 中定義的結點接口，我們看到結點實際上可以看成是可以存取資料元素的容器，資料元素與存放它的容器是一一對應的。如果能夠取得結點的引用，則可以取得相應結點存儲的資料元素，并且在實際應用中的許多情況下更希望以結點作為參數來完成某些操作。如果能夠以結點作為參數，那麼就可以在Ο(1)時間内定位結點的位址，進而可以在更短的時間内完成相應的操作。例如如果能夠直接定位在連結清單中進行插入和删除結點的前驅，那麼相應的插入和删除操作都可以在Ο(1)完成。

3.3連結清單接口（基于結點）

（初始化、為空、為滿、傳回長度、get、set、查找、插入、删除、置空、周遊、前驅、後繼）

package linked_list;

import util.InvalidNodeException;
import util.Iterator;
import util.OutOfBoundaryException;

//連結表接口

public interface LinkedList {
  // 查詢連結表目前的規模
  public int getSize();

  // 判斷清單是否為空
  public boolean isEmpty();

  // 傳回第一個結點
  public Node first() throws OutOfBoundaryException;

  // 傳回最後一結點
  public Node last() throws OutOfBoundaryException;

  // 傳回p 之後的結點
  public Node getNext(Node p) throws InvalidNodeException,
      OutOfBoundaryException;

  // 傳回p 之前的結點
  public Node getPre(Node p) throws InvalidNodeException,
      OutOfBoundaryException;

  // 将e 作為第一個元素插傳入連結接表,并傳回e 所在結點
  public Node insertFirst(Object e);

  // 将e 作為最後一個元素插入清單,并傳回e 所在結點
  public Node insertLast(Object e);

  // 将e 插入至p 之後的位置,并傳回e 所在結點
  public Node insertAfter(Node p, Object e) throws InvalidNodeException;

  // 将e 插入至p 之前的位置,并傳回e 所在結點
  public Node insertBefore(Node p, Object e) throws InvalidNodeException;

  // 删除給定位置處的元素，并傳回之
  public Object remove(Node p) throws InvalidNodeException;

  // 删除首元素，并傳回之
  public Object removeFirst() throws OutOfBoundaryException;

  // 删除末元素，并傳回之
  public Object removeLast() throws OutOfBoundaryException;

  // 将處于給定位置的元素替換為新元素，并傳回被替換的元素
  public Object replace(Node p, Object e) throws InvalidNodeException;

  // 元素疊代器
  public Iterator elements();
}

3.4雙向連結清單

雙向連結清單節點定義

package double_linked_list;

import linked_list.Node;

//雙向連結清單結點定義
public class DLNode implements Node {
  private Object element;
  private DLNode pre;
  private DLNode next;

  public DLNode() {
    this(null, null, null);
  }

  public DLNode(Object ele, DLNode pre, DLNode next) {
    this.element = ele;
    this.pre = pre;
    this.next = next;
  }

  public DLNode getNext() {
    return next;
  }

  public void setNext(DLNode next) {
    this.next = next;
  }

  public DLNode getPre() {
    return pre;
  }

  public void setPre(DLNode pre) {
    this.pre = pre;
  }

  /**************** Node Interface Method **************/
  public Object getData() {
    return element;
  }

  public void setData(Object obj) {
    element = obj;
  }
}

雙向連結清單實作（基于節點的操作）

package double_linked_list;
import util.InvalidNodeException;
import util.Iterator;
import util.OutOfBoundaryException;
import linked_list.LinkedList;
import linked_list.LinkedListIterator;
import linked_list.Node;


//基于雙向連結清單實作的連結表
public class Double_linked_list implements LinkedList {
  private int size; // 規模
  private DLNode head;// 頭結點,啞元結點
  private DLNode tail;// 尾結點,啞元結點

  
  public Double_linked_list() {
    size = 0;
    head = new DLNode();// 建構隻有頭尾結點的連結清單
    tail = new DLNode();
    head.setNext(tail);
    tail.setPre(head);
  }

  // 輔助方法，判斷結點p 是否合法，如合法轉換為DLNode
  protected DLNode checkPosition(Node p) throws InvalidNodeException {
    if (p == null)
      throw new InvalidNodeException("錯誤：p 為空。");
    if (p == head)
      throw new InvalidNodeException("錯誤：p 指向頭節點，非法。");
    if (p == tail)
      throw new InvalidNodeException("錯誤：p 指向尾結點，非法。");
    DLNode node = (DLNode) p;
    return node;
  }

  // 查詢連結表目前的規模
  public int getSize() {
    return size;
  }

  // 判斷連結表是否為空
  public boolean isEmpty() {
    return size == 0;
  }

  // 傳回第一個結點
  public Node first() throws OutOfBoundaryException {
    if (isEmpty())
      throw new OutOfBoundaryException("錯誤：連結表為空。");
    return head.getNext();
  }

  // 傳回最後一結點
  public Node last() throws OutOfBoundaryException {
    if (isEmpty())
      throw new OutOfBoundaryException("錯誤：連結表為空。");
    return tail.getPre();
  }

  // 傳回p 之後的結點
  public Node getNext(Node p) throws InvalidNodeException,
      OutOfBoundaryException {
    DLNode node = checkPosition(p);
    node = node.getNext();
    if (node == tail)
      throw new OutOfBoundaryException("錯誤：已經是連結表尾端。");
    return node;
  }

  // 傳回p 之前的結點
  public Node getPre(Node p) throws InvalidNodeException,
      OutOfBoundaryException {
    DLNode node = checkPosition(p);
    node = node.getPre();
    if (node == head)
      throw new OutOfBoundaryException("錯誤：已經是連結表前端。");
    return node;
  }

  // 将e 作為第一個元素插傳入連結接表
  public Node insertFirst(Object e) {

    DLNode node = new DLNode(e, head, head.getNext());
    head.getNext().setPre(node);
    head.setNext(node);
    size++;
    return node;
  }

  // 将e 作為最後一個元素插入清單,并傳回e 所在結點
  public Node insertLast(Object e) {
    DLNode node = new DLNode(e, tail.getPre(), tail);
    tail.getPre().setNext(node);
    tail.setPre(node);
    size++;
    return node;
  }

  // 将e 插入至p 之後的位置,并傳回e 所在結點
  public Node insertAfter(Node p, Object e) throws InvalidNodeException {
    DLNode node = checkPosition(p);
    DLNode newNode = new DLNode(e, node, node.getNext());
    node.getNext().setPre(newNode);
    node.setNext(newNode);
    size++;
    return newNode;
  }

  // 将e 插入至p 之前的位置,并傳回e 所在結點
  public Node insertBefore(Node p, Object e) throws InvalidNodeException {
    DLNode node = checkPosition(p);
    DLNode newNode = new DLNode(e, node.getPre(), node);
    node.getPre().setNext(newNode);
    node.setPre(newNode);
    size++;
    return newNode;
  }

  // 删除給定位置處的元素，并傳回之
  public Object remove(Node p) throws InvalidNodeException {
    DLNode node = checkPosition(p);
    Object obj = node.getData();
    node.getPre().setNext(node.getNext());
    node.getNext().setPre(node.getPre());
    size--;
    return obj;

  }

  // 删除首元素，并傳回之
  public Object removeFirst() throws OutOfBoundaryException {
    return remove(head.getNext());
  }

  // 删除末元素，并傳回之
  public Object removeLast() throws OutOfBoundaryException {
    return remove(tail.getPre());
  }

  // 将處于給定位置的元素替換為新元素，并傳回被替換的元素
  public Object replace(Node p, Object e) throws InvalidNodeException {
    DLNode node = checkPosition(p);
    Object obj = node.getData();
    node.setData(e);
    return obj;
  }

  // 元素疊代器
  public Iterator elements() {
    return new LinkedListIterator(this);
  }
}

3.5 單向循環連結清單

3.6 雙向循環連結清單

四、兩種實作的對比

4.1 基于時間的比較

線性表的操作主要有查找、插入、删除三類操作。對于查找操作有基于序号的查找，即存取線性表中i 号資料元素。由于數組有随機存取的特性，線上性表的順序存儲實作中可以在Θ(1)的時間内完成；而在鍊式存儲中由于需要從頭結點開始順着連結清單才能取得，無法在常數時間内完成，是以順序存儲優于鍊式存儲。查找操作還有基于元素的查找，即線性表是否包含某個元素、元素的序号是多少，這類操作線性表的順序存儲與鍊式存儲都需要從線性表中序号為0 的元素開始依次查找，是以兩種實作的性能相同。綜上所述，如果線上性表的使用中主要操作是查找，那麼應當選用順序存儲實作的線性表。

對于基于資料元素的插入、删除操作而言，當使用數組實作相應操作時，首先需要采用順序查找定位相應資料元素，然後才能插入、删除，并且在插入、删除過程又要移動大量元素；相對而言連結清單的實作隻需要在定位資料元素的基礎上，簡單的修改幾個指針即可完成，是以鍊式存儲優于順序存儲。對于基于序号的插入、删除操作，因為在順序存儲中平均需要移動一半元素；而在鍊式存儲中不能直接定位，平均需要比較一半元素才能定位。是以順序存儲與鍊式存儲性能相當。綜上所述，如果線上性表的使用中主要操作是插入、删除操作，那麼選用鍊式存儲的線性表為佳。

4.2 基于空間的比較

線性表的順序存儲，其存儲空間是預先靜态配置設定的，雖然在實作的過程中可以動态擴充數組空間，但是如果線性表的長度變化範圍較大，空間在使用過程中由于會存在大量空閑空間，使得存儲空間的使用率不高。而線性表的鍊式存儲，其結點空間是動态配置設定的，不會存在存儲空間沒有完全利用的情況。是以當線性表長度變化較大時，宜采用鍊式存儲結構。當線性表的資料元素結構簡單，并且線性表的長度變化不大時。由于鍊式存儲結構使用了額外的存儲空間來表示資料元素之間的邏輯關系，是以針對資料域而言，指針域所占比重較大；而線上性表的順序存儲結構中，沒有使用額外的存儲空間來表示資料元素之間的邏輯關系，盡管有一定的空閑空間沒有利用，但總體而言由于線性表長度變化不大，是以沒有利用的空間所占比例較小。是以當線性表資料元素結構簡單，長度變化不大時可以考慮采用順序存儲結構。

 順序存儲的優點是存儲密度大(＝1)，存儲空間使用率高。缺點是插入或删除元素時不友善。 鍊式存儲的優點是插入或删除元素時很友善，使用靈活。缺點是存儲密度小（<1），存儲空間使用率低。事實上，連結清單插入、删除運算的快捷是以空間代價來換取時間。順序表适宜于做查找這樣的靜态操作；連結清單宜于做插入、删除這樣的動态操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、删除操作，則采用連結清單。 

五、線性表的應用：

5.1、多項式的表示及運算

順序存儲

鍊式存儲

5.2、多項式加減乘（鍊式存儲的實作）

item.java

//多項式的項
public class item {
  private float coef; //系數
  private int exponent; //幂
  private item next;

  item(float d, int exp) {
    this.coef = d;
    this.exponent = exp;
    this.next = null;
  }

  item() {
    this.exponent = 0;
    this.next = null;
  }

  item(float d) {
    this.coef = d;
    this.exponent = 0;
    this.next = null;
  }

  public float getcoef() {
    return coef;
  }

  public int getexp() {
    return exponent;
  }

  public item getnext() {
    return next;
  }

  public void setcoef(float d) {
    this.coef = d;
  }

  public void setexp(int exp) {
    this.exponent = exp;
  }

  public void setnext(item n) {
    this.next = n;
  }

  public void print() {
    String s="";
    System.out.print(s + this.coef + "X" + this.exponent);
    if (this.next != null)
    {
      System.out.print("+");
      next.print();
      
    }
  }
}

poly.java

//多項式
public class poly {
  private int count;
  private item head;
  private item tail;

  poly() {
    count = 0;
    head = null;
    tail = null;
  }

  poly(float c, int exp) {
    item i = new item(c, exp);
    head = i;
    tail = i;
    count++;
  }

  public item gethead() {
    return head;
  }

  public item gettail() {
    return tail;
  }

  public int getcount() {
    return count;
  }

  // 多項式加
  public void addpoly(float c) {
    item it = new item(c);
    addpoly(it);
  }

  public void addpoly(float c, int exp) {
    item it = new item(c, exp);
    addpoly(it);
  }

  public void addpoly(item it) {
    item prev = head;
    item p = head;
    float c = it.getcoef(); // 要添加的項的系數
    int exp = it.getexp(); // 要添加的項的幂

    if (prev == null) { // 目前的多項式為空，則直接多項式的頭尾指針都指向該項
      head = it;
      tail = it;
    } else {
      do {
        if (prev.getexp() < exp) { // 目前項的幂小于要添加的項
          p = prev;
          prev = prev.getnext();
        } else if (prev.getexp() == exp) { // 目前項的幂等于要添加的項
          prev.setcoef(prev.getcoef() + c); // 系數相加
          if (prev.getcoef() == 0) { // 系數相加後結果為0，則删除結果項
            if (prev == head) { // 結果項在表達式頭部，頭指針指向下一項
              head = prev.getnext();
            } else if (prev.getnext() == null) { // 結果項在表達式尾部，尾指針指向前一項
              tail = p;
            } else {
              p.setnext(prev.getnext()); // 結果項在表達式中間，删除該項
            }
          }
          break;
        } else if (prev.getexp() > exp) { // 目前項的幂大于要添加的項
          if (prev == head) {
            head = it;
            it.setnext(prev);
            break;
          } else {
            p.setnext(it);
            it.setnext(prev);
            break;
          }
        }
      } while (prev != null);
      if (p.getexp() < exp) {
        p.setnext(it);
        tail = it;
      }
    }
    count++;
  }

  public void addpoly(poly p) {
    item prev = p.gethead();
    do {
      addpoly(prev);
      prev = prev.getnext();
    } while (prev != null);
  }

  // 多項式減
  public void subtractPoly(poly p) {
    item prev = p.gethead();
    do {
      prev.setcoef(0 - prev.getcoef());
      addpoly(prev);
      prev = prev.getnext();
    } while (prev != null);
  }

  // 多項式乘
  public void multiplyPoly(poly p) {
    item prev = head;
    item pp = p.gethead();
    poly pt = new poly();
    do {
      do {
        item temp = new item();
        temp.setcoef(prev.getcoef() * pp.getcoef());
        temp.setexp(prev.getexp() + pp.getexp());
        pt.addpoly(temp);
        prev = prev.getnext();
      } while (prev != null);
      pp = pp.getnext();
    } while (pp != null);
    head = pt.gethead();
  }

  public void printpoly() {
    item prev = head;
    prev.print();
  }
}

測試

//使用多項式

public class usepoly {
  public static void main(String[] arg) throws Exception {
    poly pl = new poly();
    poly p2 = new poly();
    pl.addpoly(12, 3);
    pl.addpoly(4, 9);
    pl.addpoly(3, 4);
    p2.addpoly(1, 2);
    pl.multiplyPoly(p2);
    pl.printpoly();
  }
}
線性表 資料 結點 連結清單 順序存儲
上一篇: 資料結構（二）——線性表
下一篇: 分析CPU性能瓶頸

繼續閱讀