递回树德科技大学PWS伺服主机课件.ppt

1、1 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures資料結構資料結構Chapter 42 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊堆疊(Stack)p定義定義 資料有序存取而成的串列資料有序存取而成的串列 資料存取的順序是後進先出資料存取的順序是後進先出(LIFO)，如，如同玩積木同玩積木3 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures 意義意義p三種狀態三種狀態 堆疊是空的堆疊是空的(top=0)堆

2、疊是滿的堆疊是滿的(top=n)介於前面兩者之間介於前面兩者之間p二種動作二種動作 加入加入(add)動作動作 刪除刪除(delete)動作動作p例題例題 ko4_1(堆疊程式堆疊程式)4 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresStack 類別類別pJava提供了一個與類別有關的提供了一個與類別有關的Stack 類別，主類別，主要用於執行後進先出的作業。要用於執行後進先出的作業。建構子建構子 Stack()方法方法add(object),clear(),clone(),copy(Stack),elements(),equal

3、s(Object),equals(Stack),finish(),hashCode(),isEmpty(),maxSize(),pop(),push(),remove(),size(),start(),swap(Stack),top(),toString()p例題例題 ko4_1a(利用利用Stack 類別寫成的堆疊程式類別寫成的堆疊程式)pP.112例題、例題、P.113例題例題5 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法及傳回值的應用處理遞迴方法及傳回值的應用處理p運

4、算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算6 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用 以副程式呼叫副程式的方式，先呼叫的副程以副程式呼叫副程式的方式，先呼叫的副程式被放入堆疊內，先到放置於底層，後到放式被放入堆疊內，先到放置於底層，後到放置於上層。置於上層。p遞迴方法及傳回值的應用處理遞迴方法及傳回值的應用處理 遞迴方法及傳回值也是應用堆疊

5、的方式處理遞迴方法及傳回值也是應用堆疊的方式處理資料，資料，also see example ko2_1p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算7 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法的應用遞迴方法的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算 由運算元由運算元(operator)、運算子

6、、運算子(operand)組成的組成的運算式，都是應用堆疊的方式處理。運算式，都是應用堆疊的方式處理。See next section for detailp二元樹的追蹤二元樹的追蹤 二元樹的追蹤是拜訪二元樹的每一個節點，二元樹的追蹤是拜訪二元樹的每一個節點，是應用堆疊的方式處理。是應用堆疊的方式處理。See chapter 5p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算8 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法的應用遞迴方法

7、的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理 系統中斷處理是由中斷的來源裝置送出一個中斷向量，系統中斷處理是由中斷的來源裝置送出一個中斷向量，CPU依據中斷向量跳到所指的位址之前，會先將傳回位垃依據中斷向量跳到所指的位址之前，會先將傳回位垃(return address)及狀態暫存器的資料儲存到堆疊中，等完及狀態暫存器的資料儲存到堆疊中，等完成中斷處理後，再從堆疊中取出資料，繼續執行中斷前未成中斷處理後，再從堆疊中取出資料，繼續執行中斷前未完成的工作。完成的工作。p使用暫存器堆疊指標執行堆疊運算使用暫存器堆

8、疊指標執行堆疊運算 堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆疊中最上層的資料；並利用疊中最上層的資料；並利用push將資料存放於堆疊中，利將資料存放於堆疊中，利用用pop將資料從堆疊中取出。將資料從堆疊中取出。9 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式由運算元算術運算式由運算元(operator)、運算子、運算子(operand)組成。組成。運算元：運算元：09,大小寫大小寫az 運算子：運算子：算術運算子算術運算子 關係運算子關係運算子 邏

9、輯運算子邏輯運算子 指定運算子指定運算子 條件運算子條件運算子 位元運算子位元運算子10 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式有三種型式：算術運算式有三種型式：中序式中序式(infix)習慣性的寫法習慣性的寫法 將運算子放於兩個運算元的中間。如：將運算子放於兩個運算元的中間。如：x*y 前序式前序式(prefix)將運算子放於兩個運算元之前。如：將運算子放於兩個運算元之前。如：*xy 後序式後序式(postfix)將運算子放於兩個運算元之後。如：將運算子放於兩個運算元之後。如：xy*11 樹德科技大

10、學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp中序式轉換成前序式步驟如下：中序式轉換成前序式步驟如下：Step 1：將運算式依照運算子優先權全部加上小括號將運算式依照運算子優先權全部加上小括號()Step 2：將運算子取代左邊的小括號，直到左邊的小將運算子取代左邊的小括號，直到左邊的小括號完全消失為止括號完全消失為止 Step 3：刪除所有右邊的小括號刪除所有右邊的小括號p如：如：a+b*c-d。1.(a+(b*c)-d)2.(a+*bc)-d)3.(+a*bc)-d)4.-+a*bc)d)5.-+a*bcd中序式轉換成前序式中序式轉換成前

11、序式Page117例題例題*212 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp中序式轉換成後序式步驟如下：中序式轉換成後序式步驟如下：Step 1：將運算式依照運算子優先權全部加上小括號將運算式依照運算子優先權全部加上小括號()Step 2：將運算子取代右邊的小括號，直到右邊小括號完全消失為止將運算子取代右邊的小括號，直到右邊小括號完全消失為止 Step 3：刪除所有左邊的小括號刪除所有左邊的小括號p如：如：a+b*c-d。1.(a+(b*c)-d)2.(a+(bc*)-d)3.(a(bc*+-d)4.(a(bc*+d-5.a

12、bc*+d-pPage118&119例題例題pPage 119例題例題ko4_2中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式13 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp前序式轉換成中序式步驟如下：前序式轉換成中序式步驟如下：Step 1：由右至左讀取運算式。由右至左讀取運算式。Step 2：若讀取的是運算子，將右邊兩個運算元連同若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來運算子以小括號圍起來，直到所有運算子都被圍起來為止。為止。Step 3：將運算子移到兩

13、個運算元之間，最後整理，將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。刪除不必要的小括號。p例題：將例題：將前序式前序式+*/ab-cde 轉換成中序式轉換成中序式 Step 1前序式前序式+*/ab-cde 987654321 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 樹德科技大學樹德科技大學 資訊管理系資訊管理

14、系 Data StructuresData Structuresp例題：將例題：將前序式前序式+*a-bc/de 轉換成中序式轉換成中序式 Step 1前序式前序式+*a-bc/de 987654321 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中序式中序式p例題：例題：前序式前序式+*a-bc/de，其值為何？，其值為何？(其中其中a=3,b=8,c=3,d=9,e=3)前序式前序式+*a

15、-bc/de a*(b-c)+d/e中序式中序式 已知已知a=3,b=8,c=3,d=9,e=3代入中序式代入中序式 a*(b-c)+d/ea*(b-c)+d/e=3*(8-3)+9/3=18前序式轉換成中序式前序式轉換成中序式15 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp後序式轉換成中序式步驟如下：後序式轉換成中序式步驟如下：Step 1：由左至右讀取運算式。由左至右讀取運算式。Step 2：若讀取的是運算子，將左邊兩個運算元連同若讀取的是運算子，將左邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來運算子以小

16、括號圍起來，直到所有運算子都被圍起來為止。為止。Step 3：將運算子移到兩個運算元之間，最後整理，將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。刪除不必要的小括號。p例題：將例題：將後序式後序式 ab*cd+-a/轉換成中序式轉換成中序式 Step 1前序式前序式 ab*cd+-a/123456789 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中序式中序式後序式轉換成中序式後序式轉換成

17、中序式16 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp例題：例題：若若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 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures前序式轉換

18、成後序式前序式轉換成後序式p前序式轉換成後序式：前序式轉換成後序式：前序式轉換成中序式，中序式轉換成後序式。前序式轉換成中序式，中序式轉換成後序式。p例題：將例題：將前序式前序式=a+-bc/*de-fg 轉換成後序式轉換成後序式 前序式轉換成中序式前序式轉換成中序式 Step 1 前序式前序式=a+-bc/*de-fg 13 12 11 10 9 8 7 6 5 4 3 2 1 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

19、(+(-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*f

20、g-/+=18 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures前序式轉換成後序式前序式轉換成後序式p直接由前序式轉換成後序式：直接由前序式轉換成後序式：p例題：將例題：將前序式前序式 a+-bc/*de-fg 轉換成後序式轉換成後序式 Step 1由右至左讀取運算式由右至左讀取運算式前序式前序式=a+-bc/*de-fg 13 12 11 10 9 8 7 6 5 4 3 2 1 Step 2若讀取的是運算子，將右邊兩個運算元連同運算子若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來為止。以小括號

21、圍起來，直到所有運算子都被圍起來為止。=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

22、 4 刪除所有左小括號刪除所有左小括號(a(bc-(de*(fg-/+=abc-de*fg-/+=p後序式轉換成前序式方法類似後序式轉換成前序式方法類似19 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列(Queue)p佇列是先進先出佇列是先進先出(First In First Out,FIFO)，如：，如：購票口購票口1 2 3 4 5 加入加入(add)離開離開(刪除刪除 delete)前端前端(front)後端後端(rear)20 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData

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

24、3佇列程式佇列程式21 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列22 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列與堆疊之異同佇列與堆疊之異同佇列與堆疊都可以做資料佇列與堆疊都可以做資料佇列做資料佇列做資料堆疊則只堆疊則只23 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列的變形佇列的變形24 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Str

25、uctures佇列佇列的變形的變形p環狀佇列環狀佇列 將線狀佇列的前端與尾端連接而成。將線狀佇列的前端與尾端連接而成。資料移走時不會影響到其他資料，不若資料移走時不會影響到其他資料，不若線狀佇列資料移走時，後面的資料必須線狀佇列資料移走時，後面的資料必須往前移。往前移。參考參考page 135&136 圖圖4-5。Page 136 例題例題25 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列的變形的變形 加入和刪除元素都可以在串列兩端發生加入和刪除元素都可以在串列兩端發生 一種堆疊與佇列的組合體一種堆疊與佇列的組合體 輸入限

26、制雙向佇列：雙向佇列只有一端輸入限制雙向佇列：雙向佇列只有一端加入資料，刪除資料發生在兩端。加入資料，刪除資料發生在兩端。輸出限制雙向佇列：雙向佇列只有一端輸出限制雙向佇列：雙向佇列只有一端刪除資料，加入資料發生在兩端。刪除資料，加入資料發生在兩端。See page138 例題例題26 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列27 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列28 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data S

27、tructuresData Structures鏈結串列鏈結串列p典型鏈結典型鏈結鏈結鏈結29 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p種類種類30 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列31 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p插入插入-鏈結串列最前端鏈結串列最前端32 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data Str

28、ucturesData Structuresp插入插入-鏈結串列最前端鏈結串列最前端p例題例題 ko4_5 插入插入-鏈結串列最前端鏈結串列最前端p例題例題 ko4_6 插入插入-鏈結串列最中間鏈結串列最中間p例題例題 ko4_7 插入插入-鏈結串列最尾端鏈結串列最尾端33 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p刪除刪除-鏈結串列最前端鏈結串列最前端例題例題 ko4_8刪除刪除-鏈結串列最前端鏈結串列最前端例題例題 ko4_9刪除刪除-鏈結串列最中間鏈結串列最中間例題例題 ko4_10刪除刪除-鏈結串列最尾

29、端鏈結串列最尾端34 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p優點優點p缺點缺點35 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p將單向鏈結之最後節點指向最前面節點，將單向鏈結之最後節點指向最前面節點，形成一環狀，即成環狀串列形成一環狀，即成環狀串列36 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列p多項式的表示多項式的表示p如：如：f(x)=2

30、3x3+12x+11係數係數次方次方link37 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列-多項式相加多項式相加p多項詩運算是使用鏈結串列，多項詩運算是使用鏈結串列，有兩個多項式有兩個多項式f、g相加相加fsgt5 37 12 0 03 36 25 0 0p 038 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列-稀疏矩陣稀疏矩陣p是用環狀串列來表示稀疏矩陣，其資料是用環狀串列來表示稀疏矩陣，其資料結構如下：結構如下：p其中其

31、中Down指向同一行中下一個非零元素，指向同一行中下一個非零元素，Row指非零指非零元素的列數，元素的列數，Col指非零元素的行數，指非零元素的行數，Right指向同一列指向同一列中下一個非零元素中下一個非零元素Value為非零元素的值。為非零元素的值。Down RowColRightxYVALUEaxy (a)典型的節點(b)axy節點表示法39 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures動態記憶體管理動態記憶體管理p動態記憶體管理：動態記憶體管理：40 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data Structu

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

33、系資訊管理系 Data StructuresData Structures邊界標誌法邊界標誌法p邊界標誌法用於處理記憶體的配置與回邊界標誌法用於處理記憶體的配置與回收。收。pTAG=0(記憶體已被釋放記憶體已被釋放)pTAG=1(記憶體已被配置記憶體已被配置)42 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures邊界標誌法邊界標誌法p一、配置節點：一、配置節點：p可用空間節點：可用空間節點：起始位置起始位置結束位置結束位置TAG1=1SIZETAG2=1TAG1=1，TAG2=1 表示已配置的節點。表示已配置的節點。SIZE表示記憶體

34、大小表示記憶體大小LLINKTAG1=0SIZERLINKTAG2=0UPLINK43 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures伙伴系統伙伴系統p將記憶體配置與回收都以將記憶體配置與回收都以2的次方空間大的次方空間大小處理。小處理。64k32k32k16k16k16k16k提供給提供給15k使用使用44 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures伙伴系統伙伴系統-結構結構p一、配置節點：一、配置節點：p二、可用空間節點二、可用空間節點TAG=1SIZETAG=0表示可用空間的節點，表示可用空間的節點，TAG=1表示已配置的節點。表示已配置的節點。SIZE表示記憶體大小。表示記憶體大小。LLINKTAG=0NVALRLINKLLINK、RLINK為左、右鏈結。為左、右鏈結。TAG=0表示可用空間節點。表示可用空間節點。NVAL表示記憶體大小為表示記憶體大小為2n。