tianyi

線性表的概念大家應該還記得，鏈式表是線性表的一個分類，當然也具備線性表的所有特性了，只不過它的結構方式特異而已，也就是和鏈子似的，和順序表的不同之處在于鏈式表引入對象應用，就是其他語言中的指針，每個鏈子（我自己的說法）包含一個數(shù)據(jù)元素 (element) 和一個指針域 (next) ，這個鏈子就稱為節(jié)點，通俗的說有很多節(jié)點連接成的線性表就是鏈式表，根據(jù)其結構方式又可以分為單鏈表、單循環(huán)鏈表、雙向鏈表，還有一種不常用的仿真鏈表，所有的鏈表都有一個共同的特征，都是由節(jié)點組成，根據(jù)前一章的思想我們很自然的會想到要構造一個節(jié)點類 Node.java ：

?

public class Node {

?/**

? * @author 張鈺

? */

?????? Object element;// 數(shù)據(jù)元素

??? Node next;

??? Node(Node nextval){

?????? ???? next=nextval;

??? }

?? Node(Object obj,Node nextval){

?????? ?element=obj;

?????? ?next=nextval;

?? }

public Object getElement() {

?????? return element;

}

public void setElement(Object obj) {

?????? element = obj;

}

public Node getNext() {

?????? return next;

}

public void setNext(Node nextval) {

?????? next = nextval;

}

public String toString(){

?????? return element.toString();

}

?? , 節(jié)點類的構造就是為了實現(xiàn)鏈表的操作，鏈表最常見的是單鏈表，單鏈表就是其每個節(jié)點都只有一個指向直接后繼節(jié)點的指針，其中包括帶頭節(jié)點的和不帶頭節(jié)點的，根據(jù)單鏈表的結構我們可以設計如下的類 LinList.java （注意和 java 中的 LinkList 不一樣， LinkList 是個線性結構容器，提供線性表、堆棧、隊列等操作）：

/**

?* @author 張鈺

?*

?*/

public class LinList implements List {

?

?????? Node head;// 頭指針

?????? Node current;// 當前節(jié)點位置

?????? int size;// 數(shù)據(jù)元素個數(shù)

?????? LinList(){

????????????? head=current=new Node(null);

?????? ??? size=0;

?????? }

?????? public void index(int i) throws Exception{ // 定位元素

? ??????????? if(i<-1||i>size-1){

? ?????????????????? throw new Exception(" 參數(shù)錯誤 ");

? ??????????? }

? ??????????? if(i==-1) return;

? ??????????? current=head.next;

? ??????????? int j=0;

? ??????????? while((current!=null)&&j<i){

? ?????????????????? current=current.next;

? ?????????????????? j++;

? ??????????? }

?????? }

?????? public void insert(int i, Object obj) throws Exception {

????????????? // 插入

?????????? if(i<0||i>size){

??????? ?????? ???throw new Exception(" 參數(shù)錯誤 ");

?????????? }

?????????? index(i-1);

?????????? current.setNext(new Node(obj,current.next));

?????????? size++;

?????? }

?

?

?????? public Object delete(int i) throws Exception {

????????????? // 刪除

????????????? if (size==0){

???????????????????? throw new Exception(" 鏈表已空無元素可刪除！ ");

????????????? }

????????????? if(i<0||i>size-1){

???????????????????? throw new Exception(" 參數(shù)錯誤 ");

????????????? }

????????????? index(i-1);

????????????? Object obj=current.next.getElement();

????????????? current.setNext(current.next.next);

????????????? size--;

????????????? return obj;

?????? }

?

??????

?????? public Object getData(int i) throws Exception {

????????????? // 獲取元素

????????????? if(i<-1||i>size-1){

???????????????????? throw new Exception(" 參數(shù)錯誤 ");

????????????? }

????????????? index(i);

????????????? return current.getElement();

?????? }

?

??????

?????? public int size() {

????????????? // 獲取元素個數(shù)

????????????? return size;

?????? }

?

?????? /* （非 Javadoc ）

?????? ?* @see List#isEmpty()

?????? ?*/

?????? public boolean isEmpty() {

????????????? // 判斷是否為空

????????????? return size==0;

?????? }

?

}

，設計說明：

(1) 構造函數(shù)完成三件事：創(chuàng)建頭節(jié)點，使 head 和 current 均表示所創(chuàng)建的頭節(jié)點，置 s ize 為 0 ；

(2) 定位成員函數(shù) index(int i) 的實現(xiàn)，其設計方式是：用一個循環(huán)過程從頭開始計數(shù)尋找第 i 個節(jié)點；

順序表和單鏈表的比較：順序表和單鏈表的邏輯功能完全一樣，但是兩者的應用背景以及不同情況下的使用效率略有不同，順序表的主要優(yōu)點就是支持隨機讀取，以及內(nèi)存空間利用效率高，順序表的主要特點就是需要給出數(shù)組的最大數(shù)據(jù)元素個數(shù)，而這通常很難準確做到，另外，順序表的插入和刪除操作時需要移動較多的數(shù)據(jù)元素，單鏈表的缺點就是每個節(jié)點中都有個指針，所以其空間利用率略低于順序表，單鏈表不支持隨機讀取。

單鏈表另一種常見的形勢就是循環(huán)單鏈表，其結構特點就是鏈表中最后一個節(jié)點的指針不再是結束標記，而是指向整個鏈表的第一個節(jié)點，從而使單鏈表形成一個環(huán)，，就是在構造函數(shù)中增加 head.next=head ，在定位函數(shù) index(i) 中，把循環(huán)結束條件 current!=null 換成 current!=head ，這樣最后一個節(jié)點就循環(huán)到第一個了！鏈表最常見的一個應用就是循環(huán)雙鏈表， java 中的 LinkedList 就是通過循環(huán)雙鏈表來實現(xiàn)的，其長度可以隨著數(shù)據(jù)元素的增減很容易的變化， LinkedList 提供了線性表、堆棧、隊列、雙端隊列等數(shù)據(jù)結構所要求的全部成員函數(shù)，例如 addFirst() 和 removeFirst() 就是支持堆棧所要求的成員函數(shù)，這里就不過多講解了，回到循環(huán)雙鏈表，雙向鏈表中每個節(jié)點包括三個域： element 、 next 、 prior ，其中 element 是數(shù)據(jù)元素， next 是指向后繼節(jié)點的對象應用， prior 是指向前驅節(jié)點的對象應用，

?

prior

element

next

設 p 為第 i 個節(jié)點，則 p.next 為第 i+1 個節(jié)點， p.next.prior==p, 這就是雙向鏈表的方式，結合前面的內(nèi)容，雙向鏈表類的設計留給大家，有興趣的同學可以和我一起討論！

最后還有仿真鏈表，鏈式儲存結構中，實現(xiàn)元素之間的關系靠的是指針，但是也可以用數(shù)組來構造仿真鏈表，方法是在數(shù)祖中增加一個（或兩個） int 類型的變量域，這些變量用來表示后一個或前一個元素在數(shù)組中的下標，這就是仿真鏈表，其應用不是很多，這里就不多介紹，有興趣的同學可以研究，下一講：堆棧和隊列！