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

資料結構Chapter4資料結構Chapter41堆疊(Stack)定義資料有序存取而成的串列資料存取的順序是後進先出(LIFO)，如同玩積木堆疊(Stack)定義2意義三種狀態堆疊是空的(top=0)堆疊是滿的(top=n)介於前面兩者之間二種動作加入(add)動作刪除(delete)動作例題ko4_1(堆疊程式)意義三種狀態3Stack類別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例題Stack類別Java提供了一個與類別有關的Stack類4堆疊的應用副程式的應用遞迴方法及傳回值的應用處理運算式(前序式、中序式、後序式)的運算二元樹的追蹤系統中斷處理使用暫存器堆疊指標執行堆疊運算堆疊的應用副程式的應用5堆疊的應用副程式的應用以副程式呼叫副程式的方式，先呼叫的副程式被放入堆疊內，先到放置於底層，後到放置於上層。遞迴方法及傳回值的應用處理遞迴方法及傳回值也是應用堆疊的方式處理資料，alsoseeexampleko2_1運算式(前序式、中序式、後序式)的運算二元樹的追蹤系統中斷處理使用暫存器堆疊指標執行堆疊運算堆疊的應用副程式的應用6堆疊的應用副程式的應用遞迴方法的應用運算式(前序式、中序式、後序式)的運算由運算元(operator)、運算子(operand)組成的運算式，都是應用堆疊的方式處理。Seenextsectionfordetail二元樹的追蹤二元樹的追蹤是拜訪二元樹的每一個節點，是應用堆疊的方式處理。Seechapter5系統中斷處理使用暫存器堆疊指標執行堆疊運算堆疊的應用副程式的應用7堆疊的應用副程式的應用遞迴方法的應用運算式(前序式、中序式、後序式)的運算二元樹的追蹤系統中斷處理系統中斷處理是由中斷的來源裝置送出一個中斷向量，CPU依據中斷向量跳到所指的位址之前，會先將傳回位垃(returnaddress)及狀態暫存器的資料儲存到堆疊中，等完成中斷處理後，再從堆疊中取出資料，繼續執行中斷前未完成的工作。使用暫存器堆疊指標執行堆疊運算堆疊指標是一種持殊暫存器，程設師利用堆疊指標取得堆疊中最上層的資料；並利用push將資料存放於堆疊中，利用pop將資料從堆疊中取出。堆疊的應用副程式的應用8運算式算術運算式由運算元(operator)、運算子(operand)組成。運算元：0~9,大小寫a~z運算子：算術運算子關係運算子邏輯運算子指定運算子條件運算子位元運算子運算式算術運算式由運算元(operator)、運算子(ope9運算式算術運算式有三種型式：中序式(infix)習慣性的寫法將運算子放於兩個運算元的中間。如：x*y前序式(prefix)將運算子放於兩個運算元之前。如：*xy後序式(postfix)將運算子放於兩個運算元之後。如：xy*運算式算術運算式有三種型式：10中序式轉換成前序式步驟如下：Step1：將運算式依照運算子優先權全部加上小括號()Step2：將運算子取代左邊的小括號，直到左邊的小括號完全消失為止Step3：刪除所有右邊的小括號如：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例題*2中序式轉換成前序式步驟如下：中序式轉換成前序式Page11711中序式轉換成後序式步驟如下：Step1：將運算式依照運算子優先權全部加上小括號()Step2：將運算子取代右邊的小括號，直到右邊小括號完全消失為止Step3：刪除所有左邊的小括號如：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例題Page119例題ko4_2中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式步驟如下：中序式轉換成後序式12前序式轉換成中序式步驟如下：Step1：由右至左讀取運算式。Step2：若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來為止。Step3：將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。例題：將前序式+*/ab-cde轉換成中序式Step1 前序式+*/ab-cde←987654321Step2 +*(/ab)(-cd)e→+(*(/ab)(-cd))e→(+(*(/ab)(-cd))e)Step3 (+(*(/ab)(-cd))e)→(+(*(a/b)(c-d))e)→(+((a/b)*(c-d))e)→(((a/b)*(c-d))+e)→a/b*(c-d)+e中序式前序式轉換成中序式前序式轉換成中序式步驟如下：前序式轉換成中序式13例題：將前序式+*a-bc/de轉換成中序式Step1 前序式+*a-bc/de←987654321Step2 +*a(-bc)(/de)→+(*a(-bc))(/de)→(+(*a(-bc))(/de))Step3 (+(*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前序式轉換成中序式例題：將前序式+*a-bc/de轉換成中序式前序式轉換成14後序式轉換成中序式步驟如下：Step1：由左至右讀取運算式。Step2：若讀取的是運算子，將左邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來為止。Step3：將運算子移到兩個運算元之間，最後整理，刪除不必要的小括號。例題：將後序式ab*cd+-a/轉換成中序式Step1 前序式ab*cd+-a/←123456789Step2 ab*cd+-a/→(ab*)(cd+)-a/→(((ab*)(cd+)-)a/)Step3 (((ab*)(cd+)-)a/)→(((a*b)(c+d)-)a/)→(((a*b)-(c+d))a/)→(((a*b)-(c+d))/a)→(a*b-(c+d))/a中序式後序式轉換成中序式後序式轉換成中序式步驟如下：後序式轉換成中序式15例題：若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後序式轉換成中序式例題：若a=2,b=3,c=4,d=5,計算後序式16前序式轉換成後序式前序式轉換成後序式：前序式轉換成中序式，中序式轉換成後序式。例題：將前序式=a+-bc/*de-fg轉換成後序式前序式轉換成中序式Step1 前序式=a+-bc/*de-fg←13121110987654321Step2 =a+-bc/*de-fg→=a+-bc/(*de)(-fg)→=a+(-bc)(/(*de)(-fg))→=a(+(-bc)(/(*de)(-fg)))→(=a(+(-bc)(/(*de)(-fg))))Step3 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)中序式中序式轉換成後序式Step1中序式a=b-c+d*e/(f-g)→(a=((b-c)+(d*e/(f-g))))Step2(a=((b-c)+(d*e/(fg-)))→(a=((b-c)+((de*/(fg-))→(a=((bc-+((de*(fg-/))→(a=((bc-((de*(fg-/+)→(a((bc-((de*(fg-/+=Step3(a((bc-((de*(fg-/+=→abc-de*fg-/+=前序式轉換成後序式前序式轉換成後序式：17前序式轉換成後序式直接由前序式轉換成後序式：例題：將前序式a+-bc/*de-fg轉換成後序式Step1 由右至左讀取運算式 前序式=a+-bc/*de-fg←13121110987654321Step2 若讀取的是運算子，將右邊兩個運算元連同運算子以小括號圍起來，直到所有運算子都被圍起來為止。 =a+-bc/*de-fg→=a+-bc/(*de)(-fg)→=a+(-bc)(/(*de)(-fg))→=a(+(-bc)(/(*de)(-fg)))→(=a(+(-bc)(/(*de)(-fg))))Step3 將運算子取代相對應的右邊小括號，直到右邊小括號都消失為止。(=a(+(-bc)(/(*de)(-fg))))→(=a(+(-bc)(/(*de)(fg-)))→(=a(+(-bc)((de*(fg-/))→(=a(+(bc-((de*(fg-/))→(=a((bc-((de*(fg-/+)/))→(a((bc-((de*(fg-/+=Step4刪除所有左小括號 (a((bc-((de*(fg-/+=→abc-de*fg-/+=後序式轉換成前序式方法類似前序式轉換成後序式直接由前序式轉換成後序式：18佇列(Queue)佇列是先進先出(FirstInFirstOut,FIFO)，如：排隊買票，先排隊者先買票排隊上車，先到者先上車列印文件磁碟機讀取或寫入資料先到者先處理，後到者後處理購票口12345○○○○○加入(add)離開(刪除delete)前端(front)後端(rear)佇列(Queue)佇列是先進先出(FirstInFirs19佇列佇列是一個資料有序的串列，資料加入與刪除的動作，發生在不同的位置。資料加入的一端稱為尾端(rear)，資料出來的一端稱為前端(front)。資料加入與刪除的動作具有先進先出的特性。在加入資料與刪除資料時，先判斷佇列串列儲存資料空間是否己滿或空白；己滿時僅能刪除資料，空白時僅能加入資料。例題ko4_3佇列程式佇列佇列是一個資料有序的串列，資料加入與刪除的動作，發生在不20佇列線性佇列：加入時尾端位置編號往後編，刪除時前端位置編號往後編。線性佇列遇到佇列資料刪除時，必須將所有資料往前移動，勢必花費不少時間，這是線性佇列的缺點。Page133例題佇列線性佇列：加入時尾端位置編號往後編，刪除時前端位置編號往21佇列與堆疊之異同相同點：佇列與堆疊都可以做資料加入與刪除的動作。相異點：佇列做資料加入與刪除的動作可以發生在串列的前端或尾端，堆疊則只發生在串列的頂端。佇列與堆疊之異同相同點：佇列與堆疊都可以做資料加入與刪除的動22佇列的變形環狀佇列(CircularQueue)雙向佇列(Deque)優先佇列(PriorityQueue)佇列的變形環狀佇列(CircularQueue)23佇列的變形環狀佇列將線狀佇列的前端與尾端連接而成。資料移走時不會影響到其他資料，不若線狀佇列資料移走時，後面的資料必須往前移。參考page135&136圖4-5。Page136例題佇列的變形環狀佇列24佇列的變形雙向佇列加入和刪除元素都可以在串列兩端發生一種堆疊與佇列的組合體輸入限制雙向佇列：雙向佇列只有一端加入資料，刪除資料發生在兩端。輸出限制雙向佇列：雙向佇列只有一端刪除資料，加入資料發生在兩端。Seepage138例題佇列的變形雙向佇列25佇列優先佇列不必遵守先進先出的特性享有優先權，如：讓老幼婦孺先上車醫院的急診室作業系統的行程排班行程：即一個正在執行的程式行程排班：在單一處理器系統，同一時間只能執行一個行程，若有多個行程必須置於主記憶體的工作佇列中等待，直到CPU有空才順序執行。Seepage138例題佇列優先佇列26鏈結串列鏈結串列(LinkedList)是由資料部份與指標部分連接而成的鍊條狀資料結構，此資料結構是一個資料與指標的集合體。鏈結串列與陣列均為資料的集合體，差異在於:鏈結串列使用指標連接資料，陣列無指標。陣列以連續的記憶體空間儲存資料，鏈結串列不以連續的記憶體空間儲存資料。陣列若有資料變動，可能許多資料隨之變動，費時也效率不彰。故陣列用以資料內容較少變動的資料結構；較多變動的資料結構，使用鏈結串列。鏈結串列鏈結串列(LinkedList)是由資料部份與指標27鏈結串列典型鏈結串列結構LinkedList類別seepage140建構子:LinkedList(),LinkedList(Collectionc)方法:add(intindex,Objectelement),add(Objectc),addAll(Collectionc),addAll(intindex,Objectelement),addFirst(Objectc),addLast(Objectc),clear(),clone(),contains(Objectc),get(intindex),…………例排

ko4_4

建立鏈結串列鏈結串列典型鏈結串列結構28鏈結串列種類單向鏈結串列雙向鏈結串列環狀鏈結串列多重鏈結串列鏈結串列種類29鏈結串列為何使用單向鏈結串列處理資料的插入、刪除動作簡單、節省時間

鏈結串列為何使用單向鏈結串列

30鏈結串列─單向鏈結串列插入-鏈結串列最前端鏈結串列─單向鏈結串列插入-鏈結串列最前端31插入-鏈結串列最前端例題ko4_5

插入-鏈結串列最前端例題ko4_6

插入-鏈結串列最中間例題ko4_7

插入-鏈結串列最尾端插入-鏈結串列最前端32鏈結串列─單向鏈結串列刪除-鏈結串列最前端

例題ko4_8刪除-鏈結串列最前端 例題ko4_9刪除-鏈結串列最中間 例題ko4_10刪除-鏈結串列最尾端鏈結串列─單向鏈結串列刪除-鏈結串列最前端33鏈結串列─雙向鏈結串列具有兩個指標可以左右指向下一個節點優點處理加入或刪除一個節點速度較快。任何一端連結錯誤或脫落，可以迅速修補。缺點比單向鏈結串列多一個連結節點，較浪費記憶體空間。加入或刪除時，須更改較多連結節點。鏈結串列─雙向鏈結串列具有兩個指標可以左右指向下一個節點34鏈結串列─環狀鏈結串列將單向鏈結之最後節點指向最前面節點，形成一環狀，即成環狀串列鏈結串列─環狀鏈結串列將單向鏈結之最後節點指向最前面節點，形35一般化串列多項式的表示如：f(x)=23x3+12x+11係數次方link一般化串列多項式的表示係數次方link36一般化串列-多項式相加多項詩運算是使用鏈結串列，有兩個多項式f、g相加fsgt53712003362500p0一般化串列-多項式相加多項詩運算是使用鏈結串列，有兩個多項式37一般化串列-稀疏矩陣是用環狀串列來表示稀疏矩陣，其資料結構如下：其中Down指向同一行中下一個非零元素，Row指非零元素的列數，Col指非零元素的行數，Right指向同一列中下一個非零元素Value為非零元素的值。DownRowColRightxYVALUEaxy

(a)典型的節點

(b)axy節點表示法一般化串列-稀疏矩陣是用環狀串列來表示稀疏矩陣，其資料結構如38動態記憶體管理動態記憶體管理：記憶體配置與程式執行完畢後將其收回的動作。最適法從頭到尾掃描整個鏈結