Ch03 鏈結串列結構 淡江大學 周清江.

Presentation on theme: "Ch03 鏈結串列結構 淡江大學 周清江."— Presentation transcript:

1 Ch03 鏈結串列結構 淡江大學 周清江

2 鏈結物件與一般變數的比較 (ch3.java)
class Node { public int data; public Node link; } 當鏈結物件參考的設定 (=) 後沒有 new 時，如範例程 式的 Node node3 = node1，是讓它們指向相同記憶 體位置，所以 node1 及 node3 間會有連動反應 而一般變數的設定，如範例程式之 int i3 = i1 ，則是 將 = 後的運算式的值設定給 = 前的變數，它們佔有各 自的記憶體位置，是互相獨立的

3 3.1 前言 3 3

4 Node node1 = new Node( ); //有 new 運算子才會呼叫建構子，分配記憶體
node1.data = 1; Node node2 = new Node( ); //有 new 運算子才會呼叫建構子，分配記憶體 node2.data = 2; node1.link = node2; // 將 node1.link 設為 node2 的記憶體位址 Node node3 = node1; // 沒有 new 運算， //node3 與 node1 指向相同記憶體位址 // 它們目前是一體的 node3.data = 3; // 改變 node3 的 data 值， // 其記憶體位置與 node1.data 相同 System.out.println( "node1.data = " + node1.data + " node2.data = " + node3.link.data); int i1 = 1; int i2 = 2; int i3 = i1; //i3 與 i1 的記憶體位址不同， //這將 i1 的值放在 i3 的記憶體位置，i3 與 i1 各自獨立 System.out.println( "i1=" + i1 +" i2=" + i2 + " i3=" + i3); i3 = 3;

5

6 陣列與鏈結串列之比較 易 難 訂正：p3-4 表 3.1 參考課本：ch3-5 至 ch3-7 頁說明

7 3.2 單向鏈結串列

8 3.2 單向鏈結串列 (節點資料依應用決定是否排序)

9 3.2 單向鏈結串列 Node link 的初始值設定為 NULL

10 3.2 單向鏈結串列 串列類別 public class List { private Node front; }
link 的初始值設定為 NULL

11 3.2 單向鏈結串列 判斷給定的單向鏈結 串列是否為一空串列 的方法 建立包含兩節點的單 向鏈結串列
boolean isempty( ) { if (front.link == null) return true; else return false; } 建立包含兩節點的單 向鏈結串列 Node front = new Node( ); Node first = new Node( ); Node second = new Node( ); front.link = first; first.data = 25; first.link = second; second.data = 78; 參考：課本 p.3-10

12 3.2 單向鏈結串列 給定以下已排序單向鏈結串列 將 70 插入此串列之步驟 70

13 新增節點進入排序鏈結串列的 4 種狀況 1.串列為空 2.新節點的資料比串列最前面節點還小，要插在原本 最前面節點之前
3.新節點的資料要插在串列某 2 個節點之間 4.新節點的資料比串列最後面節點還大，要插在原本 最後面節點之後 那新增節點進入未排序鏈結串列有幾 種狀況？

14 3.2 排序單向鏈結串列 給定以下排序單向鏈結串列 自此串列刪除 83 之步驟

15 自排序鏈結串列刪除某節點的 4 種狀況 1.串列僅有該節點，刪除後為空 2.該節點為串列最前面節點 3.該節點在串列中間(前後都有節點)
4.該節點在串列最後面

16 3.2 單向鏈結串列 課本範例程式 ch3_list.java 其 front 與講義不太一樣，兩種做法都可以
訂正：課本第 3-15 頁，第 74 列應為 if(preNode.link == null) front 22 78 31 83 98 NULL

17 課本範例程式 ch3_list.java 因上頁設計改變造成的程式變動範例
建立包含兩節點的單向鏈結 串列 Node first = new Node( ); Node second = new Node( ); front = first; first.data = 25; first.link = second; second.data = 78; 判斷給定的單向鏈結串 列是否為一空串列的方 法 boolean isempty( ) { if (front == null) return true; else return false; }

18 3.2 單向鏈結串列 課本範例程式 ch3_list.java 中 delNode(int data) 方法的改寫 (ch3_list_2.java) 練習：將 ch3_list.java 中 insertNode(int data) 方法的 for 迴圈改以 while 寫過

19 作業 2 1. 生成如講義第 8 頁的單向無排序鏈結串列(前 4 個節 點就可以)，再另外生成一個資料相同之單向排序鏈結 串列 (參考 ch3.java) 2. 將課本範例程式 ch3_list.java 改以講義的 front 方式 寫過 3. 將多項式及相關方法 (建構子, eval, display, add, add2) 改以串列重新設計

20 3.2 單向鏈結串列的應用 3.2.1 堆疊的應用 (第 4 章再看) 3.2.2 佇列的應用 (第 4 章再看)
堆疊的應用 (第 4 章再看) 佇列的應用 (第 4 章再看) 計算串列的長度 串列的合併 將單向鏈結串列反轉 20

21 3.2.4 計算串列的長度 21

22 3.2.5 串列的合併 22

23 23

24 Code: ch3_concatenate2list_1.java
// 將front_y串列合併到front_x串列之後，並以front_z為新串列的前端 public void cancatenate(Node front_x, Node front_y, Node front_z){ Node this_node; if(front_x.link == null) // front_x 為空串列 front_z.link = front_y.link; else{ if(front_y.link == null) // front_y 為空串列 front_z.link = front_x.link; else{ // front_x, front_y 均不為空 this_node = front_x.link; while(this_node.link != null) this_node = this_node.link; this_node.link = front_y.link; } 24

25 ch3_concatenate2list_2.java // 將front_y串列合併到front_x串列之後，並以front_z為新串列的前端 public void cancatenate(Node front_x, Node rear_x, Node front_y, Node rear_y, Node front_z, Node rear_z) { Node this_node; if(front_x.link == null){ // front_x 為空串列 front_z.link = front_y.link; rear_z.link = rear_y.link; }else{ if(front_y.link == null){ // front_y 為空串列 front_z.link = front_x.link; rear_z.link = rear_x.link; }else{ // front_x, front_y 均不為空 this_node = rear_x.link; this_node.link = front_y.link; rear_z.link = rear_y.link; } 25

26 3.2.3 將單向鏈結串列反轉 (ch3_singlelist.java)
22 78 31 83 98 front rear NULL 反轉後的單向鍊結串列 26

27 27

28 28

29 3.3 雙向鍊結串列 29

30 3.3 雙向鍊結串列 (ch3_doublelist.java)
30

31 3.3 雙向鍊結串列(插入) 31

32 3.3 雙向鍊結串列(刪除) 32

33 3.3 雙向鍊結串列 (ch3_doublelist.java)
這會使得 ch3_doublelist.java 的部份程式與圖 3.24、 3.25、3.26 不一致。基本上只要 link 的部份處理好， 兩者都可以。 31 front rear 5 65 83 78 98

34 3.3 ch3_doublelist.java 程式範例
public void insert_node(int key){ Node new_node, prev_node, this_node; new_node = new Node(); new_node.data = key; new_node.l_link = null; new_node.r_link = null; if(is_empty()){ front.r_link = new_node; rear.r_link = new_node; new_node.l_link = front; new_node.r_link = front; }else{ this_node = front.r_link; if(key < this_node.data){ new_node.r_link = this_node; this_node.l_link = new_node; ……… public void print_front(){ Node this_node; if( !is_empty() ){ // 若非空串列 this_node = front.r_link; System.out.print(" ==> 串列內容為 : "); while(this_node.r_link != front){ System.out.print(this_node.data+" . "); this_node = this_node.r_link; } System.out.print(this_node.data+"\n"); }else System.out.println("!!!空串列"); public void delete_node(int key) 有多處訂正 public void print_rear( ) 由後往前印

35 public void delete_node(int key){
Node this_node, prev_node, temp_node; prev_node = front; this_node = front.r_link; while(this_node.r_link != front){ // 當不是最後一個節點時 if(key == this_node.data){ // temp_node = this_node; 訂正，這列不需要 prev_node.r_link = this_node.r_link; this_node.r_link.l_link = prev_node; return; } prev_node = this_node; // prev_node 往右前進一個節點 this_node = this_node.r_link; // this_node 往右前進一個節點 if(key == this_node.data){ // 判斷最後一個節點 // temp_node = this_node; // 訂正，這列不需要 if (front.r_link == this_node) { // 訂正，新增判斷 this 是否為串列僅存的節點 front.r_link = null; rear.r_link = null; } else { prev_node.r_link = front; // 我們將最後一個節點的r_link指向front rear.r_link = prev_node; } else System.out.println("... 找不到資料 ");

36 3.4 環狀串列

37 3.4.1 環狀單向鍊結串列 圖 3.27(a):環狀單向鍊結串列(有使用尾端指標) 圖 3.27(a):環狀單向鍊結串列(未使用尾端指標)

38 3.4.1 環狀單向鍊結串列(未使用尾端指標 rear)
新增或刪除的節點為第一個節點時需額外處理，一般節點的新增 與刪除比照單向 鍊結串列 將資料 10 加到 圖 3.27(a)，並維持串列由小到大的排序 刪除圖 3.27(a)資料 22 31 front 22 83 78 98   SKIP 3.4.2 3.4.3

39 3.5 多項式表示法 陣列表示法，請參考學期初 多項式 投影片 適合表示稀疏型 (即多個係數為 0)的多項式
3.5 多項式表示法 陣列表示法，請參考學期初 多項式 投影片 適合表示稀疏型 (即多個係數為 0)的多項式 7 x4 + 8 x x + 6

40 作業 3 請實作 3.4.1 之環狀單向鍊結串列，必須含有之方法： 建構子
insert( int data ): 要區別新增的是一般節點、前端節點 delete( int data): 要區別刪除的是一般節點、前端節點 print( ): 將串列各節點的值印出來 length( ): 列印此鍊結串列之長度