什么是靜態鏈表？
對于線性鏈表，也可用一維數組來進行描述。這種描述方法便于在沒有指針類型的高級程序設計語言中使用鏈表結構。
用數組描述的鏈表，即稱為靜態鏈表。
在C語言中，靜態鏈表的表現形式即為結構體數組，結構體變量包括數據域data和游標CUR。
靜態鏈表的節點
數據域：用于存儲數據元素的值
游標：即數組下標，表示直接后繼元素所在數組中的位置
public class StaticLinkedListNode<T> {
public T data; // 數據
public int cursor; // 游標
...
}
注：通常靜態鏈表會將第一個數據元素放到數組下標為1(即a[1])的位置中。
備用鏈表
靜態鏈表中，除了數據本身通過游標組成鏈表外，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表。
作用：回收數組中未使用或者之前使用過(現在不用)的存儲空間，留待后期使用。即靜態鏈表使用數組申請的物理空間中，存在兩個鏈表，一條連接數據，另一條連接數組中為使用的空間。
注：通常備用鏈表的表頭位于數組下標為0(a[0])的位置,而數據鏈表的表頭位于數組下標為1(a[1])的位置。
靜態鏈表中設置備用鏈表的好處是，可以清楚地知道數組中是否有空閑位置，以便數據鏈表添加新數據時使用。比如，若靜態鏈表中數組下標為 0 的位置上存有數據，則證明數組已滿。
完整代碼
public class StaticLinkedListNode<T> {
public T data;
private int cursor;
public StaticLinkedListNode(T data, int cursor) {
this.cursor = cursor;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public int getCursor() {
return cursor;
}
public void setCursor(int cursor) {
this.cursor = cursor;
}
}
public class StaticLinkedList<T> {
StaticLinkedListNode[] nodes;
private static final int MAX_SIZE = 100;
private int length;
public StaticLinkedList() {
nodes = new StaticLinkedListNode[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
nodes[i] = new StaticLinkedListNode<T>(null, i + 1);
}
nodes[MAX_SIZE - 1].setCursor(0);
this.length = 0;
}
// 鏈表實際長度
public int Length() {
return length;
}
// 判斷使用數組是否為空
public boolean isEmpty() {
return length == 0;
}
// 判斷備用鏈表是否為空
public boolean isFull() {
return length == MAX_SIZE;
}
// 插入一個節點
public boolean addTo(T data, int index) {
if (isFull() || index > MAX_SIZE || index < -1 || data == null)
return false;
if (index == 0) {
insert(data);
return true;
}
if (index > Length()) {
index = Length();
}
// 獲取第一個使用節點的下標
int firstUse = nodes[MAX_SIZE - 1].getCursor();
// 獲取備用數組第一個節點的下標
int firstNull = nodes[0].getCursor();
for (int i = 1; i < index; i++) {
firstUse = nodes[firstUse].getCursor();
}
// 獲取目標節點的后續節點
int nextUse = nodes[firstUse].getCursor();
int nextNull = nodes[firstNull].getCursor();
nodes[0].setCursor(nextNull);
nodes[firstUse].setCursor(firstNull);
nodes[firstNull].setCursor(nextUse);
nodes[firstNull].setData(data);
length++;
return true;
}
public void insert(T data) {
int t = nodes[MAX_SIZE - 1].getCursor();
int firstNull = nodes[0].getCursor();
nodes[MAX_SIZE - 1].setCursor(firstNull);
nodes[0].setCursor(nodes[firstNull].getCursor());
nodes[firstNull].setCursor(t);
nodes[firstNull].setData(data);
length++;
}
public void print() {
int first = nodes[MAX_SIZE - 1].getCursor();
System.out.println("鏈表：");
for (int i = first; i != 0; ) {
System.out.print(nodes[i].getData() + " ");
i = nodes[i].getCursor();
}
}
// 刪除指定節點
public boolean delete(T data) {
if (isEmpty()) {
return false;
}
int temp = MAX_SIZE - 1;
while (temp != 0) {
if (nodes[nodes[temp].getCursor()].getData() == data) {
int p = nodes[temp].getCursor();
nodes[temp].setCursor(nodes[p].getCursor());
nodes[p].setCursor(nodes[0].getCursor());
nodes[0].setCursor(p);
nodes[p].setData(null);
length--;
return true;
}
temp = nodes[temp].getCursor();
}
return false;
}
// 刪除所有節點
public boolean deleteAll() {
if (isEmpty()) {
return true;
}
for (int i = 0; i < MAX_SIZE - 1; i++) {
nodes[i].setCursor(i + 1);
nodes[i].setData(null);
}
nodes[MAX_SIZE - 1].setCursor(0);
nodes[MAX_SIZE - 1].setData(null);
length = 0;
return true;
}
public void printAll() {
System.out.println("鏈表：");
for (int i = 0; i < MAX_SIZE; i++) {
System.out.print("[" + i + " " + nodes[i].getData() + " " + nodes[i].getCursor() + "]");
if (i % 5 == 0 && i != 0) {
System.out.println();
}
}
}
public static void main(String[] args) {
StaticLinkedList<String> list = new StaticLinkedList<String>();
list.insert("A");
list.insert("B");
list.insert("C");
list.insert("D");
list.insert("E");
list.addTo("X", 2);
System.out.println(list.Length());
list.print();
// list.printAll();
// list.deleteAll();
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
