快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)之線性表

更新時(shí)間：2017年03月10日 10:19:19 作者：朝向遠(yuǎn)方

線性表是其組成元素間具有線性關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)，對(duì)線性表的基本操作主要有，獲取元素，設(shè)置元素值，遍歷，插入，刪除，查找，替換，排序等。而線性表可以采用順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，本節(jié)主要講解順序表、單鏈表以及雙鏈表的各種基本操作。

1：線性表抽象的數(shù)據(jù)類型

線性表：是由n（n>=0）個(gè)數(shù)據(jù)相同的元素組成的有限序列。線性表的定義接口如下

public interface IList<T> {
 /**
 * 是否為空
 * @return
 */
 boolean isEmpty();
 /**
 * 表的長度
 * @return
 */
 int length();
 /**
 * 根據(jù)索引獲取長度
 * @param i
 * @return
 */
 T get(int i);
 /**
 * 設(shè)置第i個(gè)元素值為x
 * @param i
 * @param x
 */
 void set(int i,T x);
 /**
 * 在線性表最后插入x元素
 * @param x
 */
 void append(T x);
 /**
 * 異常第i個(gè)元素并返回值
 * @param i
 * @return
 */
 T remove(int i);
 /**
 * 刪除線性表中所有元素
 */
 void removeAll();
 /**
 * 查詢首次出現(xiàn)關(guān)鍵字為key的元素
 * @param key
 * @return
 */
 T search(T key);
 void insert(int i,T x);
 /**
 * 升序添加
 * @param x
 */
 void insert(T x);
 /**
 * 升序刪除
 * @param x
 */
 void remove(T x);
}

2：線性表順序表示和實(shí)現(xiàn)

線性表的順序存儲(chǔ)結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元依次存放的線性表的數(shù)據(jù)元素，元素的物理地址和邏輯地址次序是相同的。我們叫做這種存儲(chǔ)方式為順序表。

由于數(shù)組只能進(jìn)行賦值和取值，而且長度是不可變化的，所以給我們的操作帶來很大的麻煩，但是用順序表就可以進(jìn)行刪除，插入等操作。其實(shí)順序表內(nèi)部同樣適用數(shù)組來表示的，只不過這個(gè)數(shù)據(jù)我們可以改變他的長度，這樣說來我們就好辦了，首先我們要為順序表定義一個(gè)數(shù)組，同時(shí)在定義一個(gè)值來記錄線性表的長度，所以第一步我們就有了如下

準(zhǔn)備事件做好了以后，我們肯定會(huì)對(duì)順序表進(jìn)行初始化，剛剛開始數(shù)組的長度肯定是0。但是我們必須要為數(shù)組開辟一個(gè)內(nèi)存空間，來存儲(chǔ)要插入的元素，如下

其他的都比較簡單，我主要說下插入和刪除

插入一個(gè)元素的時(shí)候，如果插在第i個(gè)位置，那么意味著它后面所有的元素前部往后面移一位，但是我們必須把i個(gè)位置留出來給即將插入的元素。但是我們還必須考慮，如果這個(gè)數(shù)組滿了的情況。如果滿了，我們必須重新為順序表開辟內(nèi)存空間，然后把以前的元素進(jìn)行遷移到新的表中，java實(shí)現(xiàn)如下

代碼看出，我們把從第i個(gè)位置的元素全部往后移（包括第i個(gè)元素）然后在把第i個(gè)元素進(jìn)行賦值

刪除第i個(gè)元素，這個(gè)和上面的正好相反，如果刪除第i個(gè)元素意味著在i之后的元素前部往前移一位。

3：順序表操作效率分析

因?yàn)轫樞虮硎蔷哂兴饕模詆et()和set()效率極高，時(shí)間復(fù)雜度都是O(n)。

從上面發(fā)現(xiàn)，在插入和刪除的時(shí)候都是需要大量元素的移動(dòng)，因?yàn)樵诟鱾€(gè)位置插入元素的概率相同，所以平均插入一個(gè)元素要移動(dòng)的元素是2/n。那么它的時(shí)間復(fù)雜度就是O(n)，如果要容器滿了，那么就需要申請(qǐng)更大的容器來存儲(chǔ)新加入的元素，那么效率會(huì)更加的低下。所以順序表的靜態(tài)性好，動(dòng)態(tài)性就很差了，所以在選擇的時(shí)候就要注意一下。

4：單鏈表的實(shí)現(xiàn)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的2個(gè)元素，物理地址不一定相同，這么說來就充分的利用了內(nèi)存中的地址。但是我們必須用附加信息來連接2個(gè)不同的數(shù)據(jù)元素，所以這里就引進(jìn)了2個(gè)概念，數(shù)據(jù)域(data)和地址域(next)，其中數(shù)據(jù)域存儲(chǔ)的是這個(gè)元素的值，地址域存儲(chǔ)下一個(gè)元素的地址。其中數(shù)據(jù)域和地址域聯(lián)合起來我們稱為節(jié)點(diǎn)（node）。如果只有后繼節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)我們就稱為單鏈表，那么現(xiàn)在我們來看看單鏈表的實(shí)現(xiàn)。

首先我們要定義一個(gè)節(jié)點(diǎn)Node

public class Node<T> {
 public T data;//數(shù)據(jù)域
 public Node next;//地址域
 public Node() {
 this(null, null);
 }
 public Node(T data, Node next) {
 this.data = data;
 this.next = next;
 }
}

現(xiàn)在我們想象一下，A(x)和B(y)2個(gè)節(jié)點(diǎn)，其中A的后繼節(jié)點(diǎn)是B，那么我們?cè)趺幢硎灸兀缦?/p>

Node<String> A=new Node<T>(x,null);
Node<String> B=new Node<T>(y,null);
A.next=B。

也可以把A寫成Node<String> A=new Node<T>(x,B);

ok現(xiàn)在我們正式開始實(shí)現(xiàn)一個(gè)帶有頭節(jié)點(diǎn)的單鏈表

我們可以把頭指針想象成一個(gè)指針來便于我們的操作，我們先看如何實(shí)現(xiàn)單鏈表的長度

public int length() {
 int i = 0;
 Node<T> p = this.head.next;
 while (p != null) {
  p = p.next;
  i++;
 }
 return i;
 }

因?yàn)檫@是一個(gè)鏈?zhǔn)降慕Y(jié)構(gòu)，我們無法得知長度，只能通過循環(huán)來知道鏈表中節(jié)點(diǎn)的個(gè)數(shù)，因?yàn)轭^指針的后繼節(jié)點(diǎn)就是我們鏈表中第一個(gè)節(jié)點(diǎn)，所以我們就可以這樣往下循環(huán)來得知。

獲取第i個(gè)節(jié)點(diǎn)的值

同樣我們無法直接獲取節(jié)點(diǎn)，這個(gè)時(shí)候同樣采用循環(huán)，如果循環(huán)第i個(gè)元素值等于我們i那么我們就獲取這個(gè)節(jié)點(diǎn)，然后得到值

public T get(int i) {
 if (i >= 0) {
  Node<T> p = this.head;
  for (int j = 0; j <= i; j++) {
  p = p.next;
  }
  if (p!=null){
  return p.data;
  }
 }
 return null;
 }

在第i個(gè)位置插入一個(gè)節(jié)點(diǎn)

首先我們必須要找到要插入節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),然后前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向這個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向原來前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)。

從代碼看出我們是根據(jù)頭節(jié)點(diǎn)進(jìn)行循環(huán)的。加入p.next!=null的目的是為了當(dāng)循環(huán)到最后一個(gè)節(jié)點(diǎn)的時(shí)候就停止，不在繼續(xù)了。

移除第i個(gè)節(jié)點(diǎn)

如果我們要?jiǎng)h除第i個(gè)節(jié)點(diǎn)和上面差不多，同樣我們要找到這個(gè)第i個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，和上面代碼差不多。

在鏈表后追加一個(gè)節(jié)點(diǎn)。

如果傳統(tǒng)的話我們可以采取insert(this.length,x);但是這樣一來計(jì)算長度的時(shí)候就需要遍歷鏈表無疑速度減慢，只需要如下

insert(Integer.MAX_VALUE, x)即可，從插入代碼可以看到當(dāng)循環(huán)到最后一個(gè)節(jié)點(diǎn)就不會(huì)繼續(xù)了，然后把新的節(jié)點(diǎn)加入最后即可。

5：排序單鏈表

排序首先我們需要我們的元素要繼承comparable。

我們就說插入和刪除。先說插入

如果插入一個(gè)元素，我們先獲取要插入這個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。（x.compareTo(y)<0 表示小于y）

其中p.data.next.compareTo(x)<0如果跳出循環(huán)說明p節(jié)點(diǎn)值大于或等于x

如果刪除一個(gè)元素，和上面的基本一樣，但是要加上一個(gè)判斷如下

其中通過上面判斷我們知道p節(jié)點(diǎn)大于或等于x節(jié)點(diǎn)了，所以需要再次判斷。

6：單鏈表操作效率分析

單鏈表在獲取元素和設(shè)置元素的時(shí)候都需要進(jìn)行遍歷所以時(shí)間復(fù)雜度O(n)

如果在p節(jié)點(diǎn)插入或刪除元素，只需要修改鏈的后繼節(jié)點(diǎn)的地址即可所以時(shí)間復(fù)雜度O(1),但是如果插入類似insert(i,x)就需要進(jìn)行遍歷了，那么時(shí)間復(fù)雜度就是O(n).

對(duì)單鏈表進(jìn)行插入和刪除只需要改變少量節(jié)點(diǎn)的鏈，不需要移動(dòng)元素，單鏈表的插入和刪除都是動(dòng)態(tài)申請(qǐng)和釋放的，不需要預(yù)先分配存儲(chǔ)空間，從而不會(huì)因?yàn)榇鎯?chǔ)空間不足而進(jìn)行擴(kuò)容，提高了運(yùn)行效率。

7：雙鏈表的實(shí)現(xiàn)

雙鏈表和單鏈表大多是相同的只不過多了前驅(qū)節(jié)點(diǎn)，現(xiàn)在我們先定義一下雙鏈表