Chapter 4 資料結構.

Presentation on theme: "Chapter 4 資料結構."— Presentation transcript:

1 Chapter 4 資料結構

2 堆疊(Stack) 定義 資料有序存取而成的串列 資料存取的順序是後進先出(LIFO)，如同玩積木

3 意義 三種狀態 二種動作 例題 ko4_1(堆疊程式) 堆疊是空的(top=0) 堆疊是滿的(top=n) 介於前面兩者之間
加入(add)動作 刪除(delete)動作 例題 ko4_1(堆疊程式)

4 Stack 類別 Java提供了一個與類別有關的Stack 類別，主要用於執行後進先出的作業。 建構子 Stack( ) 方法
add (object), clear( ), clone( ), copy (Stack), elements( ), equals (Object), equals (Stack), finish ( ), hashCode ( ), isEmpty ( ), maxSize ( ), pop ( ), push ( ), remove ( ), size ( ), start ( ), swap (Stack), top ( ), toString ( ) 例題 ko4_1a (利用Stack 類別寫成的堆疊程式) P.112例題、 P.113例題

5 堆疊的應用 副程式的應用 遞迴方法及傳回值的應用處理 運算式(前序式、中序式、後序式)的運算 二元樹的追蹤 系統中斷處理
使用暫存器堆疊指標執行堆疊運算

6 堆疊的應用 副程式的應用 遞迴方法及傳回值的應用處理 以副程式呼叫副程式的方式，先呼叫的副程式被放入堆疊內，先到放置於底層，後到放置於上層。
遞迴方法及傳回值也是應用堆疊的方式處理資料，also see example ko2_1 運算式(前序式、中序式、後序式)的運算 二元樹的追蹤 系統中斷處理 使用暫存器堆疊指標執行堆疊運算

7 堆疊的應用 運算式(前序式、中序式、後序式)的運算 二元樹的追蹤
副程式的應用 遞迴方法的應用 運算式(前序式、中序式、後序式)的運算 由運算元(operator)、運算子(operand)組成的運算式，都是應用堆疊的方式處理。See next section for detail 二元樹的追蹤 二元樹的追蹤是拜訪二元樹的每一個節點，是應用堆疊的方式處理。See chapter 5 系統中斷處理 使用暫存器堆疊指標執行堆疊運算

8 堆疊的應用 系統中斷處理 使用暫存器堆疊指標執行堆疊運算
副程式的應用 遞迴方法的應用 運算式(前序式、中序式、後序式)的運算 二元樹的追蹤 系統中斷處理 系統中斷處理是由中斷的來源裝置送出一個中斷向量，CPU依據中斷向量跳到所指的位址之前，會先將傳回位垃(return address)及狀態暫存器的資料儲存到堆疊中，等完成中斷處理後，再從堆疊中取出資料，繼續執行中斷前未完成的工作。 使用暫存器堆疊指標執行堆疊運算 堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆疊中最上層的資料；並利用push將資料存放於堆疊中，利用pop將資料從堆疊中取出。

9 運算式 算術運算式由運算元(operator)、運算子(operand)組成。 運算元：0~9, 大小寫a~z 運算子： 算術運算子
關係運算子 邏輯運算子 指定運算子 條件運算子 位元運算子

10 運算式 算術運算式有三種型式： 中序式(infix) 前序式(prefix) 後序式(postfix) 習慣性的寫法
將運算子放於兩個運算元的中間。如：x*y 前序式(prefix) 將運算子放於兩個運算元之前。如：*xy 後序式(postfix) 將運算子放於兩個運算元之後。如：xy*

11 中序式轉換成前序式 中序式轉換成前序式步驟如下： 如：a+b*c-d。 Step 1： 將運算式依照運算子優先權全部加上小括號( )
Page117例題*2

12 中序式轉換成後序式 中序式轉換成後序式步驟如下： 如：a+b*c-d。 Page118&119例題
Step 1： 將運算式依照運算子優先權全部加上小括號( ) Step 2： 將運算子取代右邊的小括號，直到右邊小括號完全消失為止 Step 3： 刪除所有左邊的小括號 如：a+b*c-d。 1. ((a+(b*c))-d) 2. ((a+(bc*)-d) 3. ((a(bc*+-d) 4 . ((a(bc*+d- 5. abc*+d- Page118&119例題 Page 119例題ko4_2中序式轉換成後序式

13 前序式轉換成中序式 前序式轉換成中序式步驟如下： 例題：將前序式 +*/ab-cde 轉換成中序式 Step 1： 由右至左讀取運算式。
Step 1 前序式 +*/ab-cde ← Step 2 +*(/ab)(-cd)e → +(*(/ab)(-cd))e → (+(*(/ab)(-cd))e) Step 3 (+(*(/ab)(-cd))e) → (+(*(a/b)(c-d))e) → (+( (a/b) *(c-d))e) → ( ( (a/b) *(c-d)) + e) → a/b*(c-d) + e 中序式

14 前序式轉換成中序式 例題：將前序式 +*a-bc/de 轉換成中序式
Step 1 前序式 +*a-bc/de ← Step 2 +*a(-bc)(/de) → +(*a(-bc))(/de) → (+(*a(-bc))(/de)) Step 3 (+(*a(-bc))(/de)) → (+(*a(b-c))(d/e)) → (+(a* (b-c))(d/e)) → ( (a* (b-c)) +(d/e)) → a* (b-c) +d/e中序式 例題：前序式 +*a-bc/de，其值為何？(其中a=3, b=8, c=3, d=9, e=3) 前序式 +*a-bc/de → a* (b-c) +d/e中序式 已知a=3, b=8, c=3, d=9, e=3代入中序式 a* (b-c) +d/e a* (b-c) +d/e = 3*(8-3)+9/3 = 18

15 後序式轉換成中序式 後序式轉換成中序式步驟如下： 例題：將後序式 ab*cd+-a/ 轉換成中序式 Step 1： 由左至右讀取運算式。
Step 1 前序式 ab*cd+-a/ ← Step 2 ab*cd+-a/ → (ab*)(cd+)-a/ →(((ab*)(cd+)-)a/) Step 3 (((ab*)(cd+)-)a/) → (((a*b)(c+d)-)a/) → (((a*b) -(c+d))a/) → (((a*b) -(c+d)) /a) → (a*b -(c+d)) /a中序式

16 後序式轉換成中序式 例題：若a=2, b=3, c=4, d=5, 計算後序式 ab*cd+-a/ 的值為何
後序式 ab*cd+-a/ → (a*b -(c+d)) /a中序式 已知a=2, b=3, c=4, d=5代入中序式 (a*b -(c+d)) /a (a*b -(c+d)) /a = (2*3 -(4+5)) /2 = -3/2

17 前序式轉換成後序式 前序式轉換成後序式： 例題：將前序式 =a+-bc/*de-fg 轉換成後序式 前序式轉換成中序式，中序式轉換成後序式。
Step 1 前序式 =a+-bc/*de-fg ← Step 2 =a+-bc/*de-fg →= a+-bc/(*de)(-fg) → =a+(-bc)(/(*de)(-fg)) → =a(+(-bc)(/(*de)(-fg))) → (=a(+(-bc)(/(*de)(-fg)))) Step 3 a(+(-bc)(/(*de)(-fg))) →(= a(+(-bc)(/(d*e)(f-g)))) → (=a(+(b-c)( (d*e) /(f-g)))) → (=a(+(-bc)(/(*de)(-fg)))) → a= b-c +d*e /(f-g)中序式 中序式轉換成後序式 Step 1中序式 a= b-c +d*e /(f-g) → (a= ((b-c) +(d*e /(f-g)))) Step 2 (a= ((b-c) +(d*e /(fg-))) → (a= ((b-c) +((de* /(fg-)) → (a= ((bc- +((de* (fg-/)) → (a= ((bc- ((de* (fg-/+) → (a ((bc- ((de* (fg-/+ = Step 3 (a ((bc- ((de* (fg-/+ = →abc-de*fg-/+ =

18 前序式轉換成後序式 直接由前序式轉換成後序式： 例題：將前序式 a+-bc/*de-fg 轉換成後序式 後序式轉換成前序式方法類似
Step 1 由右至左讀取運算式 前序式 =a+-bc/*de-fg ← Step 2 若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來為止。 =a+-bc/*de-fg →= a+-bc/(*de)(-fg) → =a+(-bc)(/(*de)(-fg)) → =a(+(-bc)(/(*de)(-fg))) → (=a(+(-bc)(/(*de)(-fg)))) Step 3 將運算子取代相對應的右邊小括號，直到右邊小括號都消失為止。 (=a(+(-bc)(/(*de)(-fg)))) → (=a(+(-bc)(/(*de)(fg-))) → (=a(+(-bc)( (de* (fg-/)) → (=a(+(bc- ( (de* (fg-/)) → (=a( (bc- ( (de* (fg-/+) /)) → (a( (bc- ( (de* (fg-/+= Step 4 刪除所有左小括號 (a( (bc- ( (de* (fg-/+= → abc-de*fg-/+= 後序式轉換成前序式方法類似

19 佇列(Queue) 佇列是先進先出(First In First Out, FIFO)，如： 先到者先處理，後到者後處理
排隊買票，先排隊者先買票 排隊上車，先到者先上車 列印文件 磁碟機讀取或寫入資料 先到者先處理，後到者後處理 購票口 ○ ○ ○ ○ ○ 加入(add) 離開(刪除 delete) 前端(front) 後端(rear)

20 佇列 佇列是一個資料有序的串列，資料加入與刪除的動作，發生在不同的位置。
資料加入的一端稱為尾端(rear)，資料出來的一端稱為前端(front)。 資料加入與刪除的動作具有先進先出的特性。 在加入資料與刪除資料時，先判斷佇列串列儲存資料空間是否己滿或空白；己滿時僅能刪除資料，空白時僅能加入資料。 例題 ko4_3佇列程式

21 佇列 線性佇列：加入時尾端位置編號往後編，刪除時前端位置編號往後編。
線性佇列遇到佇列資料刪除時，必須將所有資料往前移動，勢必花費不少時間，這是線性佇列的缺點。 Page 133 例題

22 佇列與堆疊之異同 相同點：佇列與堆疊都可以做資料加入與刪除的動作。
相異點：佇列做資料加入與刪除的動作可以發生在串列的前端或尾端，堆疊則只發生在串列的頂端。

23 佇列的變形 環狀佇列(Circular Queue) 雙向佇列(Deque) 優先佇列(Priority Queue)

24 佇列的變形 環狀佇列 將線狀佇列的前端與尾端連接而成。 資料移走時不會影響到其他資料，不若線狀佇列資料移走時，後面的資料必須往前移。
參考page 135 & 136 圖4-5。 Page 136 例題

25 佇列的變形 雙向佇列 加入和刪除元素都可以在串列兩端發生 一種堆疊與佇列的組合體
輸入限制雙向佇列：雙向佇列只有一端加入資料，刪除資料發生在兩端。 輸出限制雙向佇列：雙向佇列只有一端刪除資料，加入資料發生在兩端。 See page138 例題

26 佇列 優先佇列 不必遵守先進先出的特性 享有優先權，如： 行程：即一個正在執行的程式
讓老幼婦孺先上車 醫院的急診室 作業系統的行程排班 行程：即一個正在執行的程式 行程排班：在單一處理器系統，同一時間只能執行一個行程，若有多個行程必須置於主記憶體的工作佇列中等待，直到CPU有空才順序執行。 See page 138 例題

27 鏈結串列 鏈結串列(Linked List)是由資料部份與指標部分連接而成的鍊條狀資料結構，此資料結構是一個資料與指標的集合體。
鏈結串列與陣列均為資料的集合體，差異在於: 鏈結串列使用指標連接資料，陣列無指標。 陣列以連續的記憶體空間儲存資料，鏈結串列不以連續的記憶體空間儲存資料。 陣列若有資料變動，可能許多資料隨之變動，費時也效率不彰。故陣列用以資料內容較少變動的資料結構；較多變動的資料結構，使用鏈結串列。

28 鏈結串列 典型鏈結串列結構 LinkedList 類別 see page 140
建構子: LinkedList( ), LinkedList(Collection c) 方法: add (int index, Object element), add (Object c), addAll(Collection c), addAll (int index, Object element), addFirst (Object c), addLast (Object c), clear(), clone(), contains (Object c), get (int index),………… 例排 ko4_4 建立鏈結串列

29 鏈結串列 種類 單向鏈結串列 雙向鏈結串列 環狀鏈結串列 多重鏈結串列

30 鏈結串列 為何使用單向鏈結串列 處理資料的插入、刪除動作 簡單、節省時間

31 鏈結串列─單向鏈結串列 插入-鏈結串列最前端

32 插入-鏈結串列最前端 例題 ko4_5 插入-鏈結串列最前端 例題 ko4_6 插入-鏈結串列最中間 例題 ko4_7 插入-鏈結串列最尾端

33 鏈結串列─單向鏈結串列 刪除-鏈結串列最前端 例題 ko4_8刪除-鏈結串列最前端 例題 ko4_9刪除-鏈結串列最中間

34 鏈結串列─雙向鏈結串列 具有兩個指標可以左右指向下一個節點 優點 缺點 處理加入或刪除一個節點速度較快。
任何一端連結錯誤或脫落，可以迅速修補。 缺點 比單向鏈結串列多一個連結節點，較浪費記憶體空間。 加入或刪除時，須更改較多連結節點。

35 鏈結串列─環狀鏈結串列 將單向鏈結之最後節點指向最前面節點，形成一環狀，即成環狀串列

36 一般化串列 多項式的表示 如：f(x)=23x3+12x+11 係數 次方 link

37 一般化串列-多項式相加 f s g t 5 3 7 1 2 6 多項詩運算是使用鏈結串列，有兩個多項式f、g相加 p

38 一般化串列-稀疏矩陣 是用環狀串列來表示稀疏矩陣，其資料結構如下：
其中Down指向同一行中下一個非零元素，Row指非零元素的列數，Col指非零元素的行數，Right指向同一列中下一個非零元素Value為非零元素的值。 Down Row Col Right x Y VALUE axy (a)典型的節點 (b)axy節點表示法

39 動態記憶體管理 動態記憶體管理：記憶體配置與程式執行完畢後將其收回的動作。 最適法 最不適法 先適法
從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找大於或等於放置程式的記憶體空間。 最不適法 從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找最大放置程式的記憶體空間。 先適法 不需要從頭到尾掃描整個鏈結串列，只要從頭開始找到比程式大的記憶體空間即可。

40 無用記憶體空間的回收 無用記憶體空間是指可以回收而沒有回收的記憶體空間。
無用記憶體的回收，先檢查相鄰的節點是否存在，並將其合併。透過持續的合併直到所有相鄰節點合併完成為止，以產生較大的記憶體空間供大程式使用，讓記憶體空間得到充分利用，避免記憶體碎片過多造成浪費。

41 邊界標誌法 邊界標誌法用於處理記憶體的配置與回收。 TAG=0 (記憶體已被釋放) TAG=1 (記憶體已被配置)

42 邊界標誌法 一、配置節點： 可用空間節點： 起始位置 結束位置 TAG1=1 SIZE TAG2=1 LLINK TAG1=0 SIZE
TAG1=1，TAG2=1 表示已配置的節點。SIZE表示記憶體大小 LLINK TAG1=0 SIZE RLINK TAG2=0 UPLINK

43 伙伴系統 將記憶體配置與回收都以2的次方空間大小處理。 64k 32k 16k 提供給15k使用

44 伙伴系統-結構 一、配置節點： 二、可用空間節點 TAG=1 SIZE
TAG=0表示可用空間的節點，TAG=1表示已配置的節點。SIZE表示記憶體大小。 LLINK TAG=0 NVAL RLINK LLINK、RLINK為左、右鏈結。TAG=0表示可用空間節點。NVAL表示記憶體大小為2n。