树德科技大学资讯管理系DataStructures一般化串列多项式相加多项.pptx

1 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures資料結構資料結構資料結構資料結構Chapter 4Chapter 42 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊堆疊(Stack)p定義定義資料有序存取而成的串列資料有序存取而成的串列資料存取的順序是後進先出資料存取的順序是後進先出(LIFO)，如，如同玩積木同玩積木3 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures 意義意義p三種狀態三種狀態堆疊是空的堆疊是空的(top=0)堆疊是滿的堆疊是滿的(top=n)介於前面兩者之間介於前面兩者之間p二種動作二種動作加入加入(add)動作動作刪除刪除(delete)動作動作p例題例題 ko4_1(堆疊程式堆疊程式)4 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresStack 類別類別pJava提供了一個與類別有關的提供了一個與類別有關的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()p例題例題 ko4_1a(利用利用Stack 類別寫成的堆疊程式類別寫成的堆疊程式)pP.112例題、例題、P.113例題例題5 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法及傳回遞迴方法及傳回值值的應用處理的應用處理p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算6 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用以副程式呼叫副程式的方式，先呼叫的副程以副程式呼叫副程式的方式，先呼叫的副程式被放入堆疊式被放入堆疊內內，先到放置於底層，後到放，先到放置於底層，後到放置於上層。置於上層。p遞迴方法及傳回遞迴方法及傳回值值的應用處理的應用處理遞迴方法及傳回遞迴方法及傳回值值也是應用堆疊的方式處理也是應用堆疊的方式處理資料，資料，also see example ko2_1p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算7 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法的應用遞迴方法的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算由運算元由運算元(operator)、運算子、運算子(operand)組成的組成的運算式，都是應用堆疊的方式處理。運算式，都是應用堆疊的方式處理。See next section for detailp二元樹的追蹤二元樹的追蹤二元樹的追蹤是拜訪二元樹的每一個節點，二元樹的追蹤是拜訪二元樹的每一個節點，是應用堆疊的方式處理。是應用堆疊的方式處理。See chapter 5p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算8 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法的應用遞迴方法的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理系統中斷處理是由中斷的來源裝置送出一個中斷向量，系統中斷處理是由中斷的來源裝置送出一個中斷向量，CPU依據中斷向量跳到所指的位址之前，會先將傳回位垃依據中斷向量跳到所指的位址之前，會先將傳回位垃(return address)及狀態暫存器的資料儲存到堆疊中，等完成及狀態暫存器的資料儲存到堆疊中，等完成中斷處理後，再從堆疊中取出資料，繼續執行中斷前未完中斷處理後，再從堆疊中取出資料，繼續執行中斷前未完成的工作。成的工作。p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆疊中最上層的資料；並利用疊中最上層的資料；並利用push將資料存放於堆疊中，利將資料存放於堆疊中，利用用pop將資料從堆疊中取出。將資料從堆疊中取出。9 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式由運算元算術運算式由運算元(operator)、運算子、運算子(operand)組成。組成。運算元：運算元：09,大小寫大小寫az運算子：運算子：算術運算子算術運算子關係運算子關係運算子邏輯運算子邏輯運算子指定運算子指定運算子條件運算子條件運算子位元運算子位元運算子10 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式有三種型式：算術運算式有三種型式：中序式中序式(infix)習慣性的寫法習慣性的寫法將運算子放於兩個運算元的中間。如：將運算子放於兩個運算元的中間。如：x*y前序式前序式(prefix)將運算子放於兩個運算元之前。如：將運算子放於兩個運算元之前。如：*xy後序式後序式(postfix)將運算子放於兩個運算元之後。如：將運算子放於兩個運算元之後。如：xy*11 樹德科技大學樹德科技大學 資訊管理系資訊管理系 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中序式轉換成前序式中序式轉換成前序式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.abc*+d-pPage118&119例題例題pPage 119例題例題ko4_2中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式13 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp前序式轉換成中序式步驟如下：前序式轉換成中序式步驟如下：Step 1：由右至左讀取運算式。由右至左讀取運算式。Step 2：若讀取的是運算子，將右邊兩個運算元連同若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來運算子以小括號圍起來，直到所有運算子都被圍起來為止。為止。Step 3：將運算子移到兩個運算元之間，最後整理，將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。刪除不必要的小括號。p例題：將例題：將前序式前序式+*/ab-cde 轉換成中序式轉換成中序式Step 1前序式前序式+*/ab-cde 987654321Step 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 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp例題：將例題：將前序式前序式+*a-bc/de 轉換成中序式轉換成中序式Step 1前序式前序式+*a-bc/de 987654321Step 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-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：若讀取的是運算子，將左邊兩個運算元連同若讀取的是運算子，將左邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來運算子以小括號圍起來，直到所有運算子都被圍起來為止。為止。Step 3：將運算子移到兩個運算元之間，最後整理，將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。刪除不必要的小括號。p例題：將例題：將後序式後序式 ab*cd+-a/轉換成中序式轉換成中序式Step 1前序式前序式 ab*cd+-a/123456789Step 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 樹德科技大學樹德科技大學 資訊管理系資訊管理系 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前序式轉換成後序式前序式轉換成後序式p前序式轉換成後序式：前序式轉換成後序式：前序式轉換成中序式，中序式轉換成後序式。前序式轉換成中序式，中序式轉換成後序式。p例題：將例題：將前序式前序式=a+-bc/*de-fg 轉換成後序式轉換成後序式前序式轉換成中序式前序式轉換成中序式Step 1 前序式前序式=a+-bc/*de-fg 13 12 11 10 9 8 7 6 5 4 3 2 1Step 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 樹德科技大學樹德科技大學 資訊管理系資訊管理系 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 1Step 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-/+=p後序式轉換成前序式方法類似後序式轉換成前序式方法類似19 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列(Queue)p佇列是先進先出佇列是先進先出(First In First Out,FIFO)，如：，如：排隊買票，先排隊者先買票排隊買票，先排隊者先買票排隊買票，先排隊者先買票排隊買票，先排隊者先買票 排隊上車，先到者先上車排隊上車，先到者先上車排隊上車，先到者先上車排隊上車，先到者先上車 列印文件列印文件列印文件列印文件 磁碟機讀取或寫入資料磁碟機讀取或寫入資料磁碟機讀取或寫入資料磁碟機讀取或寫入資料pp先到者先處理，後到者後處理先到者先處理，後到者後處理先到者先處理，後到者後處理先到者先處理，後到者後處理購購票票口口1 2 3 4 5 加入加入(add)離開離開(刪除刪除 delete)前端前端(front)後端後端(rear)20 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列p佇列是一個資料有序的串列，資料加入與刪除佇列是一個資料有序的串列，資料加入與刪除的動作，發生在不同的位置。的動作，發生在不同的位置。p資料加入的一端稱為尾端資料加入的一端稱為尾端(rear)，資料出來的一，資料出來的一端稱為前端端稱為前端(front)。p資料加入與刪除的動作具有先進先出的特性。資料加入與刪除的動作具有先進先出的特性。p在加入資料與刪除資料時，先判斷佇列串列儲在加入資料與刪除資料時，先判斷佇列串列儲存資料空間是否己滿或空白；己滿時僅能刪除存資料空間是否己滿或空白；己滿時僅能刪除資料，空白時僅能加入資料。資料，空白時僅能加入資料。p例題例題 ko4_3佇列程式佇列程式21 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列p線性佇列：加入時尾端位置編號往後線性佇列：加入時尾端位置編號往後編，刪除時前端位置編號往後編。編，刪除時前端位置編號往後編。p線性佇列遇到佇列資料刪除時，必須線性佇列遇到佇列資料刪除時，必須將所有資料往前移動，勢必花費不少將所有資料往前移動，勢必花費不少時間，這是線性佇列的缺點。時間，這是線性佇列的缺點。pPage 133 例題例題22 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列與堆疊之異同佇列與堆疊之異同pp相同點：相同點：相同點：相同點：佇列與堆疊都可以做資料佇列與堆疊都可以做資料加入與刪除的加入與刪除的加入與刪除的加入與刪除的動作。動作。動作。動作。pp相異點：相異點：相異點：相異點：佇列做資料佇列做資料加入與刪除的動作可以發生加入與刪除的動作可以發生加入與刪除的動作可以發生加入與刪除的動作可以發生在串列的前端或尾端，在串列的前端或尾端，在串列的前端或尾端，在串列的前端或尾端，堆疊則只堆疊則只發生在串列的發生在串列的發生在串列的發生在串列的頂端。頂端。頂端。頂端。23 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列的變形佇列的變形p環狀佇列環狀佇列(Circular Queue)p雙向佇列雙向佇列(Deque)p優先佇列優先佇列(Priority Queue)24 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列的變形的變形p環狀佇列環狀佇列將線狀佇列的前端與尾端連接而成。將線狀佇列的前端與尾端連接而成。資料移走時不會影響到其他資料，不若資料移走時不會影響到其他資料，不若線狀佇列資料移走時，後面的資料必須線狀佇列資料移走時，後面的資料必須往前移。往前移。參考參考page 135&136 圖圖4-5。Page 136 例題例題25 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列的變形的變形p雙向佇列雙向佇列加入和刪除元素都可以在串列兩端發生加入和刪除元素都可以在串列兩端發生一種堆疊與佇列的組合體一種堆疊與佇列的組合體輸入限制雙向佇列：雙向佇列只有一端輸入限制雙向佇列：雙向佇列只有一端加入資料，刪除資料發生在兩端。加入資料，刪除資料發生在兩端。輸出限制雙向佇列：雙向佇列只有一端輸出限制雙向佇列：雙向佇列只有一端刪除資料，加入資料發生在兩端。刪除資料，加入資料發生在兩端。See page138 例題例題26 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列pp優先佇列優先佇列不必遵守先進先出的特性不必遵守先進先出的特性不必遵守先進先出的特性不必遵守先進先出的特性享有優先權，如：享有優先權，如：享有優先權，如：享有優先權，如：讓老幼婦孺先上車讓老幼婦孺先上車讓老幼婦孺先上車讓老幼婦孺先上車 醫院的急診室醫院的急診室醫院的急診室醫院的急診室 作業系統的行程排班作業系統的行程排班作業系統的行程排班作業系統的行程排班行程：即一個正在執行的程式行程：即一個正在執行的程式行程：即一個正在執行的程式行程：即一個正在執行的程式行程排班：在單一處理器系統，同一時間只能執行程排班：在單一處理器系統，同一時間只能執行程排班：在單一處理器系統，同一時間只能執行程排班：在單一處理器系統，同一時間只能執行一個行程，若有多個行程必須置於主記憶體的行一個行程，若有多個行程必須置於主記憶體的行一個行程，若有多個行程必須置於主記憶體的行一個行程，若有多個行程必須置於主記憶體的工作佇列中等待，直到工作佇列中等待，直到工作佇列中等待，直到工作佇列中等待，直到CPUCPU有空才順序執行。有空才順序執行。有空才順序執行。有空才順序執行。See page 138 See page 138 例題例題例題例題27 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列pp鏈結串列鏈結串列鏈結串列鏈結串列(Linked List)(Linked List)是由資料部份與指標部分是由資料部份與指標部分是由資料部份與指標部分是由資料部份與指標部分連接而成的鍊條狀資料結構，此資料結構是一連接而成的鍊條狀資料結構，此資料結構是一連接而成的鍊條狀資料結構，此資料結構是一連接而成的鍊條狀資料結構，此資料結構是一個資料與指標的集合體。個資料與指標的集合體。個資料與指標的集合體。個資料與指標的集合體。pp鏈結串列與陣列均為資料的集合體，差異在於鏈結串列與陣列均為資料的集合體，差異在於鏈結串列與陣列均為資料的集合體，差異在於鏈結串列與陣列均為資料的集合體，差異在於:鏈結串列使用指標連接資料，陣列無指標。鏈結串列使用指標連接資料，陣列無指標。鏈結串列使用指標連接資料，陣列無指標。鏈結串列使用指標連接資料，陣列無指標。陣列以連續的記憶體空間儲存資料，鏈結串列不以陣列以連續的記憶體空間儲存資料，鏈結串列不以陣列以連續的記憶體空間儲存資料，鏈結串列不以陣列以連續的記憶體空間儲存資料，鏈結串列不以連續的記憶體空間儲存資料。連續的記憶體空間儲存資料。連續的記憶體空間儲存資料。連續的記憶體空間儲存資料。陣列若有資料變動，可能許多資料隨之變動，費時陣列若有資料變動，可能許多資料隨之變動，費時陣列若有資料變動，可能許多資料隨之變動，費時陣列若有資料變動，可能許多資料隨之變動，費時也效率不彰。故陣列用以資料也效率不彰。故陣列用以資料也效率不彰。故陣列用以資料也效率不彰。故陣列用以資料內內內內容較少變動的資料容較少變動的資料容較少變動的資料容較少變動的資料結構；較多變動的資料結構，使用鏈結串列。結構；較多變動的資料結構，使用鏈結串列。結構；較多變動的資料結構，使用鏈結串列。結構；較多變動的資料結構，使用鏈結串列。28 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p典型鏈結典型鏈結串串串串列列列列結構結構結構結構ppLinkedList LinkedList 類別類別類別類別 see page 140see page 140 建構子建構子建構子建構子:LinkedList(),LinkedList(Collection c):LinkedList(),LinkedList(Collection c)方法方法方法方法:add(int index,Object element),add(Object c),:add(int index,Object element),add(Object c),addAll(Collection c),addAll(int index,Object element),addAll(Collection c),addAll(int index,Object element),addFirst(Object c),addLast(Object c),clear(),clone(),addFirst(Object c),addLast(Object c),clear(),clone(),contains(Object c),get(int index),contains(Object c),get(int index),例排例排例排例排 ko4_4ko4_4 建立建立建立建立鏈結鏈結串串串串列列列列29 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p種類種類單向鏈結串列單向鏈結串列單向鏈結串列單向鏈結串列雙向鏈結串列雙向鏈結串列雙向鏈結串列雙向鏈結串列環狀鏈結串列環狀鏈結串列環狀鏈結串列環狀鏈結串列多重鏈結串列多重鏈結串列多重鏈結串列多重鏈結串列30 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列p為何使用單向鏈結串列為何使用單向鏈結串列處理資料的插入、刪除動作處理資料的插入、刪除動作簡單、節省時間簡單、節省時間31 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列單向鏈結串列p插入插入-鏈結串列最前端鏈結串列最前端32 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp插入插入-鏈結串列最前端鏈結串列最前端p例題例題 ko4_5 插入插入-鏈結串列最前端鏈結串列最前端p例題例題 ko4_6 插入插入-鏈結串列最中間鏈結串列最中間p例題例題 ko4_7 插入插入-鏈結串列最尾端鏈結串列最尾端33 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列單向鏈結串列p刪除刪除-鏈結串列最前端鏈結串列最前端例題例題 ko4_8刪除刪除-鏈結串列最前端鏈結串列最前端例題例題 ko4_9刪除刪除-鏈結串列最中間鏈結串列最中間例題例題 ko4_10刪除刪除-鏈結串列最尾端鏈結串列最尾端34 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列雙向鏈結串列pp具有兩個指標可以左右指向下一個節點具有兩個指標可以左右指向下一個節點p優點優點處理加入或刪除一個節點速度較快。處理加入或刪除一個節點速度較快。處理加入或刪除一個節點速度較快。處理加入或刪除一個節點速度較快。任何一端連結錯誤或任何一端連結錯誤或任何一端連結錯誤或任何一端連結錯誤或脫脫脫脫落，可以迅速修補。落，可以迅速修補。落，可以迅速修補。落，可以迅速修補。p缺點缺點比單向鏈結串列多一個連結節點，較浪費記憶比單向鏈結串列多一個連結節點，較浪費記憶比單向鏈結串列多一個連結節點，較浪費記憶比單向鏈結串列多一個連結節點，較浪費記憶體空間。體空間。體空間。體空間。加入或刪除時，須更改較多連結節點。加入或刪除時，須更改較多連結節點。加入或刪除時，須更改較多連結節點。加入或刪除時，須更改較多連結節點。35 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures鏈結串列鏈結串列環狀鏈結串列p將單向鏈結之最後節點指向最前面節點，將單向鏈結之最後節點指向最前面節點，形成一環狀，即成環狀串列形成一環狀，即成環狀串列36 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列p多項式的表示多項式的表示p如：如：f(x)=23x3+12x+11係數係數次方次方link37 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列-多項式相加多項式相加p多項詩運算是使用鏈結串列，多項詩運算是使用鏈結串列，有兩個多項式有兩個多項式f、g相加相加fsgt5 37 12 0 03 36 25 0 0p 038 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一般化串列一般化串列-稀疏矩陣稀疏矩陣p是用環狀串列來表示稀疏矩陣，其資料是用環狀串列來表示稀疏矩陣，其資料結構如下：結構如下：p其中其中Down指向同一行中下一個非零元素，指向同一行中下一個非零元素，Row指非零指非零元素的列數，元素的列數，Col指非零元素的行數，指非零元素的行數，Right指向同一列指向同一列中下一個非零元素中下一個非零元素Value為非零元素的為非零元素的值值。Down RowColRightxYVALUEaxy (a)典型的節點(b)axy節點表示法39 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures動態記憶體管理動態記憶體管理p動態記憶體管理：動態記憶體管理：記憶體配置與程式執行完畢記憶體配置與程式執行完畢記憶體配置與程式執行完畢記憶體配置與程式執行完畢後將其收回的動作。後將其收回的動作。後將其收回的動作。後將其收回的動作。pp最適法最適法最適法最適法 從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找大於或等於放置程式的記憶體空間。大於或等於放置程式的記憶體空間。大於或等於放置程式的記憶體空間。大於或等於放置程式的記憶體空間。pp最不適法最不適法最不適法最不適法 從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找從頭到尾掃描整個鏈結串列，在整個鏈結串列尋找最大放置程式的記憶體空間。最大放置程式的記憶體空間。最大放置程式的記憶體空間。最大放置程式的記憶體空間。pp先適法先適法先適法先適法 不需要從頭到尾掃描整個鏈結串列，只要從頭開始不需要從頭到尾掃描整個鏈結串列，只要從頭開始不需要從頭到尾掃描整個鏈結串列，只要從頭開始不需要從頭到尾掃描整個鏈結串列，只要從頭開始找到比程式大的記憶體空間即可。找到比程式大的記憶體空間即可。找到比程式大的記憶體空間即可。找到比程式大的記憶體空間即可。40 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures無用記憶體空間的回收無用記憶體空間的回收p無用記憶體空間是指可以回收而沒有回無用記憶體空間是指可以回收而沒有回收的記憶體空間。收的記憶體空間。p無用記憶體的回收，先檢無用記憶體的回收，先檢查查相鄰的節點相鄰的節點是否存在，並將其合併。透過持續的合是否存在，並將其合併。透過持續的合併直到所有相鄰節點合併完成為止，以併直到所有相鄰節點合併完成為止，以產產生較大的記憶體空間供大程式使用，生較大的記憶體空間供大程式使用，讓記憶體空間得到充分利用，避免記憶讓記憶體空間得到充分利用，避免記憶體碎片過多造成浪費。體碎片過多造成浪費。41 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures邊界標誌法邊界標誌法p邊界標誌法用於處理記憶體的配置與回邊界標誌法用於處理記憶體的配置與回收。收。pTAG=0(記憶體已被釋放記憶體已被釋放)pTAG=1(記憶體已被配置記憶體已被配置)42 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures邊界標誌法邊界標誌法p一、配置節點：一、配置節點：p可用空間節點：可用空間節點：起始位置起始位置結束位置結束位置TAG1=1SIZETAG2=1TAG1=1，TAG2=1 表示已配置的節點。表示已配置的節點。SIZE表示記憶體大小表示記憶體大小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。