線性表
-
-
-
- 定義
- 線性表的順序存儲結構
- 線性表的鍊式存儲結構
-
-
定義
-
線性表（List）
零個或多個資料元素的有限序列。
現有如下線性表
| a(1) | a(2) | a(3) | a(i-1) | a(i) | a(i+1) | a(n) |
|---|
-
直接前驅元素
a(i-1) 領先于a(i)，稱為a(i-1)是a(i)的直接前驅元素
-
直接後繼元素
a(i+1) 是a(i)的直接後繼元素
-
空表
線性表元素的個數n （n >= 0）定義為線性表的長度，當n=0時，稱為空表。
-
位序
在非空表中，每個資料元素都有一個确定的位置，如a(1)是第一個資料元素，a（n）是最後一個，a(i)是第i個資料元素，稱i為資料元素a(i)線上性表中的位序。
線性表的順序存儲結構
線性表的順序存儲結構，指的是用一段位址連續的存儲單元依次存儲線性表的資料元素。
通俗的講，就是在記憶體中找塊地，通過占位的形式，把一定記憶體空間給占了，然後把相同資料類型的資料元素依次存放在這塊空地。
可以使用一維數組實作。
-
數組長度
存放線性表的存儲空間的長度。
-
線性表長度
線性表中元素的個數。
線性表長度 <= 數組長度
線性表的鍊式存儲結構
線性表的鍊性存儲結構用一組任意的存儲單元存儲線性表的資料元素，這組存儲單元可以試連續的，也可以是不連續的。
為了表示每個資料元素a(i)與其直接後繼資料元素a(i+1)之間的邏輯關系，對a(i)來說，除了需要存儲本身之外，還需存儲直接後繼的位置。
-
資料域
存儲資料元素資訊的域。
-
指針域
存儲直接後繼位置的域成為指針域。
-
指針/鍊
存儲在指針域中的資訊
-
結點
資料域資訊和指針域資訊組成數組元素a(i)的存儲映像，稱為結點。
-
線性表的鍊式存儲
n 個結點鍊結成一個連結清單
-
單連結清單
連結清單的每個結點隻包含一個指針域
-
頭指針
連結清單中每個結點的存儲位置叫做頭指針
-
頭結點
為友善連結清單的操作，有時候會在單連結清單的第一個結點前附設一個結點，稱為頭結點。
頭結點的資料域不可以存儲任何資訊（有特殊情況:可以存儲線性表的長度等附加資訊），頭結點的指針域存儲指向第一個結點的指針。
1. 單連結清單
構造
private static class Node<E> {
E item;
Node<E> next;
}
讀取
算法思路：
周遊所有結點，當要查找的index等于指針移動次數的時候，查找成功
Node<String> node;
... // 初始化node, 并加若幹資料
// 取第index個元素
Node getNodeFromIndex(int index) {
if (node == null) return null;
Node nextNode = node.next;
int i = 1;
if (index == 1 && nextNode == null) return node;
while (nextNode != null) {
i ++;
if (index == i) {
return nextNode;
}
nextNode = nextNode.next;
}
return null;
}
插入
算法思路：
往index處插入結點。周遊結點，查找到index-1處結點，将index-1處結點的next指向插入的結點，将插入的結點的next指向原index結點。
private void addNode(int index, E n) {
Node last = getNodeFromIndex(index - 1);
Node next = last.next;
Node newNode = new Node();
newNode.item = n;
newNode.next = next;
last.next = newNode;
}
删除
算法思路：
删除index處結點。周遊結點，查找到index-1處結點，将index-1處結點的next指向index+1處結點。
private void deleteNode(int index) {
Node last = getNodeFromIndex(index - 1);
Node next = getNodeFromIndex(index + 1);
last.next = next;
}
2. 循環連結清單
循環連結清單是另一種形式的鍊式存貯結構。它的特點是表中最後一個結點的指針域指向頭結點，整個連結清單形成一個環。
3. 雙向連結清單
在單連結清單的每個結點中，再設定一個前驅指針域，指向直接前驅元素。
LinkedList中的讀取(LinkedList, java 中典型的連結清單，它的讀取比較精妙，如果查找的index大于等于總數的一半，就從後開始周遊（最後一個到index個），如果index小于總數的一半，從前開始周遊（第一個到第index個）)。
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
循環連結清單和雙連結清單的擷取，插入，删除等操作，思想和單連結清單差不多的，大家可以自己去實作。
[1] 程傑·清華大學出版社·大話資料結構