親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化：

Presentation on theme: "親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化："— Presentation transcript:

1 親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化：
1、本教具為非賣品，不得作為商業之用。 2、本教具僅授權使用原著作為授課教材之教師作為教學或研究等學術用途。 3、本教具未授權提供學生任何拷貝、影印、引用、翻印等行為。 4、教師若需申請網站或內容授權，可透過您的博碩業務協助處理，謝謝。 博碩文化： 總公司：台北縣汐止市新台五路一段94號6樓A棟 電話：(02) 分機 傳真：(02) 網址： 出書提案信箱

2 資料結構 請老師填入姓名主講 課本：圖解資料結構使 用Java 博碩文化出版發行

3 第三章 鏈結串列 課前指引 是由許多相同資料型態的項目，依特定順序排列而成的線性串列，但特性是在電腦記憶體中位置是不連續、隨機(Random)的存在，優點是資料的插入或刪除都相當方便，有新資料加入就向系統要一塊記憶體空間，資料刪除後，就把空間還給系統。不需要移動大量資料。缺點就是設計資料結構時較為麻煩，另外在搜尋資料時，也無法像靜態資料一般可隨機讀取資料，必須循序找到該資料為止。

4 章節大綱 3-1 單向鏈結串列 3-2 環狀鏈結串列 3-3 雙向鏈結串列 3-4 鏈結串列相關應用簡介 備註：可依進度點選小節

5 3-1 單向鏈結串列 單向鏈結串列: 一個單向鏈結串列節點由兩個欄位，即資料欄及指標欄組成，而指標欄將會指向下一個元素的記憶體所在位置。如右圖所示： 在「單向鏈結串列」中第一個節點是「串列指標首」，指向最後一個節點的鏈結欄位設為NULL表示它是「串列指標尾」，不指向任何地方。如下圖所示：

6 3-1 單向鏈結串列 在其它語言中，當配置的記憶體已不再使用時，就必須釋放該記憶體空間，但由於Java語言的記憶體管理有垃圾回收機制，所以沒有記憶體回收的問題。 例如在java語言中要模擬鏈結串列中的節點，必須宣告如下的Node類別： class Node { int data; Node next; public Node(int data) //節點宣告的建構子 this.data=data; this.next=null; }

7 3-1 單向鏈結串列 接著可以宣告鏈結串列LinkedList類別，該類別定義兩個Node類別節點指標，分別指向鏈結串列的第1節點及最後1個節點，如下所示： class LinkedList { private Node first; private Node last; //定義類別的方法 …………………… }

8 3-1 單向鏈結串列 在Java中要模擬鏈結串列中的此類節點，其Node類別的語法可以宣告如下： class Node {
String name; int no; int score; Node next; public Node(String name,int no,int score) this.name=name; this.no=no; this.score=score; this.next=null; }

9 3-1 單向鏈結串列 建立單向鏈結串列 現在我們嘗試使用java語言的單向鏈結串列處理以下學生的成績問題。學生成績處理會有以下欄位。

10 3-1 單向鏈結串列 首先各位必須宣告節點的資料型態，讓每一個節點包含一筆資料，並且包含指向下一筆資料的指標，使所有資料能被串在一起而形成一個串列結構，如下圖：

11 3-1 單向鏈結串列 步驟1 建立新節點。 步驟2 將鏈結串列的first及last指標欄指向newNode。 步驟3 建立另一個新節點。

12 3-1 單向鏈結串列 步驟4 步驟5 將兩個節點串起來。 last.next=newNode; last=newNode;
依序完成如下圖所示的鏈結串列結構。

13 3-1 單向鏈結串列 接下來各位不妨自行設計此鏈結串列的建立程式。我們建議在此程式中會宣告Node類別及LinkedList類別，在LinkedList類別中，除了定義兩個Node類別節點指標，分別指向鏈結串列的第1個節點及最後1個節點外，並在該類別中宣告了三個方法：

14 3-1 單向鏈結串列 範例 3.1.1 請設計一Java程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個單向鏈結串列。接著再利資料宣告來建立這五個學生成績的單向鏈結串列，並走訪每一個節點來列印成績。

15 3-1 單向鏈結串列 單向鏈結串列刪除節點(1/3) 刪除串列的第一個節點：只要把串列指標首指向第二個節點即可。如下圖所示：
if(first.data==delNode.data) first=first.next;

16 3-1 單向鏈結串列 單向鏈結串列刪除節點(2/3)
刪除串列內的中間節點：只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可。如下圖所示： newNode=first; tmp=first; while(newNode.data!=delNode.data) { tmp=newNode; newNode=newNode.next; } tmp.next=delNode.next;

17 3-1 單向鏈結串列 單向鏈結串列刪除節點(3/3)
刪除串列後的最後一個節點：只要指向最後一個節點ptr的指標，直接指向NULL即可。如下圖所示： if(last.data==delNode.data) { newNode=first; while(newNode.next!=last) newNode=newNode.next; newNode.next=last.next; last=newNode; }

18 3-1 單向鏈結串列 範例 3.1.2 請設計一Java程式，來實作建立一組學生成績的單向鏈結串列程式，包含了座號、姓名與成績三種資料。只要輸入想要刪除的成績，就可以走訪該此串列，並前除該位學生的節點。要結束輸，請輸入”-1”，則此時會列出此串列未刪除的所有學生資料。

19 3-1 單向鏈結串列

20 3-1 單向鏈結串列 單向鏈結串列插入新節點(1/3)
新節點插入第一個節點之前，即成為此串列的首節點：只需把新節點的指標指向串列的原來第一個節點，再把串列指標首移到新節點上即可。

21 3-1 單向鏈結串列 單向鏈結串列插入新節點(2/3)
新節點插入最後一個節點之後：只需把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可。

22 3-1 單向鏈結串列 單向鏈結串列插入新節點(3/3)
將新節點插入串列中間的位置：例如插入的節點是在X與Y之間，只要將X節點的指標指向新節點，新節點的指標指向Y節點即可。如下圖所示： 把插入點指標指向的新節點

23 3-1 單向鏈結串列 範例 3.1.3 請設計一Java程式，來實作單向鏈結串列新增節點過程。

24 3-1 單向鏈結串列 單向鏈結串列的反轉 在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。如下圖所示：

25 3-1 單向鏈結串列 範例 3.1.4 以下範例將以java語言來設計將前面的學生成績程式中的學生成績依照座號反轉列印出來。

26 3-1 單向鏈結串列 單向鏈結串列的連結 對於兩個或以上鏈結串列的連結(Concatenation)，其實作法也很容易；只要將串列的首尾相連即可。如下圖所示：

27 3-1 單向鏈結串列 Java的連結演算法如下所示： class Node { int data; Node next;
public Node(int data) this.data=data; this.next=null; } public class LinkeList public Node first; public Node last; public boolean isEmpty() return first==null; public void print()

28 3-1 單向鏈結串列 Node current=first; while(current!=null) {
System.out.print("["+current.data+"]"); current=current.next; } System.out.println(); /*連結兩個鏈結串列*/ public LinkeList Concatenate(LinkeList head1,LinkeList head2) LinkeList ptr; ptr = head1; while(ptr.last.next != null) ptr.last = ptr.last.next; ptr.last.next = head2.first; return head1;

29 3-2 環狀鏈結串列 環狀鏈結串列插入節點(1/2)
將新節點插在第一個節點前成為串列首：首先將新節點X的指標指向原串列首節點，並移動整個串列，將串列首指向新節點。圖形如下：

30 3-2 環狀鏈結串列 環狀鏈結串列插入節點(2/2)
將新節點X插在串列中任意節點I之後：.首先將新節X的指標指向I節點的下一個節點，並將I節點的指標指向X節點。圖形如下：

31 3-2 環狀鏈結串列 以下是利用Java語言寫出的環狀串列節點插入演算法： class Node { int data;
Node next; public Node(int data) this.data=data; this.next=null; } public class CircleLink public Node first; public Node last;

32 3-2 環狀鏈結串列 public boolean isEmpty() { return first==null; } /*插入節點*/
public void insert(Node trp) Node tmp; Node newNode; if(this.isEmpty()) first=trp; last=trp; last.next=first; else if(trp.next==null) last.next=trp;

33 3-2 環狀鏈結串列 last=trp; last.next=first; } else { newNode=first;
tmp=first; while(newNode.next!=trp.next) if(tmp.next==first) break; tmp=newNode; newNode=newNode.next; tmp.next=trp; trp.next=newNode;

34 3-2 環狀鏈結串列 環狀鏈結串列的刪除節點(1/2)
刪除環狀鏈結串列的第一個節點：首先將串列首移到下一個節點，將最後一個節點的指標移到新的串列首，新的串列首是原串列的第二個節點。圖形如下：

35 3-2 環狀鏈結串列 環狀鏈結串列的刪除節點(2/2)
刪除環狀鏈結串列的中間節點。首先找到節點Y的前一個節點previous，.將previous節點的指標指向節點Y的下一個節點。圖形如下：

36 3-2 環狀鏈結串列 以下為Java語言寫出的環狀串列節點刪除演算法。 class Node { int data; Node next;
public Node(int data) this.data=data; this.next=null; } public class CircleLink public Node first; public Node last;

37 3-2 環狀鏈結串列 public boolean isEmpty() { return first==null; } /*刪除節點*/
public void delete(Node delNode) Node newNode; Node tmp; if(first.data==delNode.data)//要刪除的節點是串列首 first=first.next; if (first==null) System.out.print("[環狀串列已經空了]\n"); return; else if(last.data==delNode.data)//要刪除的節點是串列尾

38 3-2 環狀鏈結串列 newNode=first;
while(newNode.next!=last) newNode=newNode.next; newNode.next=last.next; last=newNode; last.next=first; } else { tmp=first; while(newNode.data!=delNode.data) tmp=newNode; newNode=newNode.next; tmp.next=delNode.next;

39 3-2 環狀鏈結串列 環狀鏈結串列的結合 單向鏈結串列的連結只需改變一個指標就可以了，如下圖所示：

40 3-2 環狀鏈結串列 範例 3.2.1 試設計一Java程式，將二個學生成績處理環狀鏈結串列連結，並列印連結後新串列中每個學生的成績與座號。

41 3-3雙向鏈結串列 雙向鏈結串列的定義(1/3) 對每個節點而言，具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK，其中RLINK指向下一個節點，LLINK指向上一個節點。如下圖所示：

42 3-3雙向鏈結串列 雙向鏈結串列的定義(2/3) 1.每個節點具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK。其中RLINK指向下一個節點，LLINK指向上一個節點。 2.通常加上一個串列首，此串列不存任何資料，其左邊鏈結欄指向串列最後一個節點，而右邊鏈結指向第一個節點。 3.假設ptr為一指向此串列上任一節點的鏈結，則有： ptr=RLINK(LLINK(ptr))=LLINK(RLINK(ptr))

43 3-3雙向鏈結串列 雙向鏈結串列的定義(3/3) 如果使用Java語言來宣告它的結構，方式如下： class Node {
int data; Node rnext; Node lnext; public Node(int data) this.data=data; this.rnext=null; this.lnext=null; }

44 3-3雙向鏈結串列 雙向鏈結串列插入節點(1/3) 將新節點加入此串列的第一個節點前，如下圖： 步驟
1. 將新節點的右鏈結(RLINK)指向原串列的第一個節點。 2.將原串列第一個節點的左鏈結(LLINK)指向新節點。 3.將原串列的串列首指標head指向新節點，且新節點的左鏈結指向null。

45 3-3雙向鏈結串列 雙向鏈結串列插入節點(2/3) 將新節點加入此串列的最後一個節點之後。如下圖： 步驟
1.將原串列的最後一個節點的右鏈結指向新節點。 2.將新節點的左鏈結指向原串列的最後一個節點，並將新節點的右鏈結指向NULL。

46 3-3雙向鏈結串列 雙向鏈結串列插入節點(3/3) 將新節點加入到ptr節點之後，如下圖 步驟 1.將ptr節點的右鏈結指向新節點。

47 3-3雙向鏈結串列 有關雙向鏈結串列節點加入的Java程式演算法如下： 01 import java.util.*;
02          import java.io.*; 03            04          class Node 05          { 06          int data; 07          Node rnext; 08          Node lnext; 09          public Node(int data) 10          { 11          this.data=data; 12          this.rnext=null; 13          this.lnext=null; 14          }                    

48 3-3雙向鏈結串列 15 } 16 17 public class Doubly 18 { 19 public Node first;
15 } 16 17 public class Doubly 18 { 19 public Node first; 20 public Node last; 21 public boolean isEmpty() 22 { 23 return first==null; 24 } 25 26 /*插入節點*/ 27 public void insert(Node newN) 28 { 29 Node tmp; 30 Node newNode; if(this.isEmpty())/*如果雙向鏈結串列為空串列                

49 3-3雙向鏈結串列 32 { 33 first=newN; 34 first.rnext=last; 35 last=newN;
32 { 33 first=newN; 34 first.rnext=last; 35 last=newN;  36last.lnext=first; 37 } 38 else 39 { 40 if(newN.lnext==null) /*插入串列首的位置*/ 41 { first.lnext=newN; newN.rnext=first; first=newN; 45 } 46 else 47 { if(newN.rnext==null)/*插入串列尾的位置*/ {              

50 3-3雙向鏈結串列 50 last.rnext=newN; 51 newN.lnext=last; 52 last=newN; 53 }
}  else /*插入中間節點的位置*/ { newNode=first; tmp=first; while(newN.rnext!=newNode.rnext) { tmp=newNode; newNode=newNode.rnext; } tmp.rnext=newN; newN.rnext=newNode; newNode.lnext=newN; newN.lnext=tmp; } 68 } 69 } 70 } 71 }             

51 3-3雙向鏈結串列 雙向鏈結串列節點刪除(1/3) 刪除串列的第一個節點。如下圖： 步驟 1.將串列首指標head指到原串列的第二個節點。
2.將新的串列首指標指向NULL。

52 3-3雙向鏈結串列 雙向鏈結串列節點刪除(2/3) 刪除此串列的最後一個節點。如下圖： 步驟
1.將原串列最後一個節點之前一個節點的右鏈結指向NULL即可。

53 3-3雙向鏈結串列 雙向鏈結串列節點刪除(2/3) 刪除串列中間的ptr節點。如下圖： 步驟
1.將ptr節點的前一個節點右鏈結指向ptr節點的下一個節點。 2.將ptr節點的下一個節點左鏈結指向ptr節點的上一個節點。

54 3-3雙向鏈結串列 有關雙向鏈結串列宣告的資料結構、建立、節點刪除的Java程式演算法如下： 01 import java.util.*;
02 import java.io.*; 03 04 class Node 05 { 06 int data; 07 Node rnext; 08 Node lnext; 09 public Node(int data) 10 { 11 this.data=data; 12 this.rnext=null; 13 this.lnext=null; 14 } 15 }                 

55 3-3雙向鏈結串列 16 17 public class Doubly 18 { 19 public Node first;
18 { 19 public Node first; 20 public Node last; 21 /*刪除節點*/ 22 public void delete(Node delNode) 23 { 24 Node newNode; 25 Node tmp; 26 if(first==null) 27 { 28 System.out.print("[串列是空的]\n"); 29 return; 30 } 31 if(first.data==delNode.data)//要刪除的節點是串列首 32 {                

56 3-3雙向鏈結串列 33 first=first.rnext; 34 first.lnext=null; 35 }
35 } 36 else if(last.data==delNode.data)//要刪除的節點是串列尾 37 { 38 newNode=first; 39 while(newNode.rnext!=last) newNode=newNode.rnext; 41 newNode.rnext=null; 42 last=newNode; } 44 else //要刪除的節點是串列的中間節點 45 { 46 newNode=first; 47 tmp=first; 48 while(newNode.data!=delNode.data)                

57 3-3雙向鏈結串列 49 { 50 tmp=newNode; 51 newNode=newNode.rnext; 52 }
49 { tmp=newNode; newNode=newNode.rnext; 52 } 53 tmp.rnext=delNode.rnext; 54 tmp.lnext=delNode.lnext; 55 } 56 } 57 }               

58 3-4 鏈結串列相關應用簡介 多項式表式法 假如一個多項式P(x)=anxn+an-1xn-1+……+a1x+a0，則稱P(x)為一n次多項式。 而一個多項式如果使用陣列結構儲存在電腦中的話，表示法有以下兩種，第一種是使用一個n+2長度的一維陣列存放，陣列的第一個位置儲存最大指數n，其他位置依照指數n遞減，依序儲存相對應的係數，例如P(x)=12x5+23x4+5x2+4x+1，可轉換為成A陣列來表示，例如： A={12,23,0,5,4,1}

59 3-4 鏈結串列相關應用簡介 範例 3.4.1 請寫出以下兩多項式的任一陣列表示法。 A(X)=X100+6X10+1
B(X)=X5+9X3+X2+1 解答： 對於A(X)可以採用儲存非零項次的表示法，也就是使用2m+1長度的陣列，m表示非零項目的數目，因此A陣列的內容為 A=(3,1,100,6,10,1,0) 另外B(X)多項式的非零項較多，因此可使用m+2長度的一維陣列，n表示位高項指數。 B=(5,1,0,9,1,0,1)

60 3-4 鏈結串列相關應用簡介 使用陣列表示法經常會出現以下的困擾：
這時如果使用鏈結串列來表示多項式，就可以克服以上的問題。多項式的鏈結串列表示法主要是儲存非零項目，並且每一項均符合以下資料結構： 多項式內容變動時，對陣列結構的影響相當大，演算法處理不易。 由於陣列是靜態資料結構，所以事先必須尋找一塊連續夠大的記憶體，容易形成空間的浪費。

61 3-4 鏈結串列相關應用簡介 例如假設多項式有n個非零項，且P(x)=an-1xen-1+an-2xen-2+…+a0，則可表示成：
例如A(x)=3X2+6X-2的表示方法如下圖：

62 3-4 鏈結串列相關應用簡介 多項式以單向鏈結方式表式的功用，主要是在不同的四則運算，例如加法或減法運算。如以下兩多項式A(X)、B(X)，求兩式相加的結果C(X)：

63 3-4 鏈結串列相關應用簡介 範例 3.4.2 請設計一Java程式，以單向鏈結串列來實作兩個多項式相加的過程。

64 3-4 鏈結串列相關應用簡介 範例3.4.3 請設計一串列資料結構表示
P(x,y,z)=x10y3z10+2x8y3z2+3x8y2z2+x4y4z+6x3y4z+2yz 解答： 我們可建立一資料結構如下：

65 3-4 鏈結串列相關應用簡介 稀疏矩陣表示法 例如下圖的稀疏矩陣： 以3-tuple的陣列表示如下：

66 3-4 鏈結串列相關應用簡介 環狀鏈結串列也可以用來表現稀疏矩陣，而且簡單方便許多。使用鏈結串列法的最大優點，在更動矩陣內的資料時，不需大量移動資料。 主要的技巧是可用節點來表示非零項，由於是二維的矩陣，每個節點除了必須有3個資料欄位：row(列)、col(行)及value(資料)外，還必須有兩個鏈結欄位：right、down，其中right指標可用來連結同一列的節點，而down指標則可用來連結同一行的節點。

67 3-4 鏈結串列相關應用簡介 Value: 表示此非零項的值 Row: 以i表示非零項元素所在列數 Col: 以j表示非零項元素所在行數
Down: 為指向同一行中下一個非零項元素的指標 Right: 為指向同一列中下一個非零項元素的指標

68 3-4 鏈結串列相關應用簡介 下圖是將上例稀疏矩陣以環狀鏈結串列表示：

69 3-4 鏈結串列相關應用簡介 範例3.4.4 如以下4*4稀疏矩陣A： 請以環狀鏈結串列表示。

70 3-4 鏈結串列相關應用簡介 解答：

71 本章結束 Q&A討論時間