什么是靜態(tài)鏈表？
創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),無棣企業(yè)網(wǎng)站建設(shè),無棣品牌網(wǎng)站建設(shè),網(wǎng)站定制,無棣網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,無棣網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
對于線性鏈表，也可用一維數(shù)組來進行描述。這種描述方法便于在沒有指針類型的高級程序設(shè)計語言中使用鏈表結(jié)構(gòu)。
用數(shù)組描述的鏈表，即稱為靜態(tài)鏈表。
在C語言中，靜態(tài)鏈表的表現(xiàn)形式即為結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體變量包括數(shù)據(jù)域data和游標CUR。
靜態(tài)鏈表的節(jié)點
數(shù)據(jù)域：用于存儲數(shù)據(jù)元素的值
游標：即數(shù)組下標，表示直接后繼元素所在數(shù)組中的位置
public class StaticLinkedListNode{ public T data; // 數(shù)據(jù) public int cursor; // 游標 ... }
注：通常靜態(tài)鏈表會將第一個數(shù)據(jù)元素放到數(shù)組下標為1(即a[1])的位置中。
備用鏈表
靜態(tài)鏈表中，除了數(shù)據(jù)本身通過游標組成鏈表外，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表。
作用：回收數(shù)組中未使用或者之前使用過(現(xiàn)在不用)的存儲空間，留待后期使用。即靜態(tài)鏈表使用數(shù)組申請的物理空間中，存在兩個鏈表，一條連接數(shù)據(jù)，另一條連接數(shù)組中為使用的空間。
注：通常備用鏈表的表頭位于數(shù)組下標為0(a[0])的位置,而數(shù)據(jù)鏈表的表頭位于數(shù)組下標為1(a[1])的位置。
靜態(tài)鏈表中設(shè)置備用鏈表的好處是，可以清楚地知道數(shù)組中是否有空閑位置，以便數(shù)據(jù)鏈表添加新數(shù)據(jù)時使用。比如，若靜態(tài)鏈表中數(shù)組下標為 0 的位置上存有數(shù)據(jù)，則證明數(shù)組已滿。
完整代碼
public class StaticLinkedListNode{ 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{ 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 (null, i + 1); } nodes[MAX_SIZE - 1].setCursor(0); this.length = 0; } // 鏈表實際長度 public int Length() { return length; } // 判斷使用數(shù)組是否為空 public boolean isEmpty() { return length == 0; } // 判斷備用鏈表是否為空 public boolean isFull() { return length == MAX_SIZE; } // 插入一個節(jié)點 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(); } // 獲取第一個使用節(jié)點的下標 int firstUse = nodes[MAX_SIZE - 1].getCursor(); // 獲取備用數(shù)組第一個節(jié)點的下標 int firstNull = nodes[0].getCursor(); for (int i = 1; i < index; i++) { firstUse = nodes[firstUse].getCursor(); } // 獲取目標節(jié)點的后續(xù)節(jié)點 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(); } } // 刪除指定節(jié)點 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; } // 刪除所有節(jié)點 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 list = new StaticLinkedList (); 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(); } }
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
重慶分公司
重慶分公司
