最新资料结构导论ppt课件.ppt

《最新资料结构导论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、资料结构导论4.1前言堆疊(Stack)結構只有單一的出入口，我們稱之為頂端(Top)。資料的「新增」和「刪除」都從堆疊的頂端進出。後進入堆疊的資料反而先出來。佇列(Queue)結構有一個入口和一個出口，我們稱入口為尾端(Rear)，出口為頭端(Front)(或稱前端)。資料從尾端「新增」，從頭端「刪除」。先進入佇列的資料將先出來。2資料結構導論-C語言實作4.2堆疊(Stack)堆疊具有以下特徵：堆疊是一個有順序性的資料結構。資料的「新增」和「刪除」都從堆疊的頂端(Top)這個唯一的出入口。具有「後進先出(LastInFirstOut：LIFO)」(或「先進後出」(Fir

2、stInLastOut：FILO))的特性。3資料結構導論-C語言實作4.2.1以陣列實作堆疊【例1】以陣列來實作堆疊的新增和刪除7資料結構導論-C語言實作4.2.2以鏈結串列實作堆疊以「鏈結串列」實作堆疊時可歸納成底下幾個基本操作：建立堆疊結構：宣告一個鏈結串列結構，一開始只有一個名為top的頭節點，它的鏈結欄指向null。判斷堆疊是否已空：當top節點指向null時，表示堆疊已空無一物。8資料結構導論-C語言實作4.2.2以鏈結串列實作堆疊新增資料：將資料放入堆疊的動作我們稱之為push。首先，向記憶體索取一個節點空間x，然後將要新增的資料存入節點x的資料欄。接下

3、來令top所指的節點為y，將x指向y，再將top指向x。刪除資料：從堆疊頂端取出資料的動作我們稱之為pop。若非空堆疊，則令top所指之節點為x，且x所指的節點為y。輸出x的資料欄，更改top鏈結指標值，將它指向y。9資料結構導論-C語言實作4.2.2以鏈結串列實作堆疊【例2】以鏈結串列來實作堆疊的新增和刪除10資料結構導論-C語言實作4.2.2以鏈結串列實作堆疊11資料結構導論-C語言實作4.3堆疊的應用4.3.1副程式的呼叫和返回4.3.2河內塔(TowersofHanoi)4.3.3運算式的轉換4.3.4運算式的求值12資料結構導論-C語言實作4.3.1副程式的呼叫

4、和返回13資料結構導論-C語言實作4.3.2河內塔(TowersofHanoi)河內塔問題是一個非常有趣的智力遊戲，問題描述如下：假設有編號分別為a、b、c的三根柱子，一開始在a柱上放置了n個中間有孔的圓盤，圓盤的編號由上到下分別為1，2，…，n，且編號愈大代表圓盤的直徑也愈大。所謂河內塔問題乃是要將所有n個圓盤從a柱搬移到c柱，且在圓盤搬移的過程中必須遵守下列3條規則：1.無論何時，每一根柱子上直徑較小的圓盤都要放在直徑較大的圓盤的上面，亦即須保持「上小下大」的排列方式。2.每次僅能移動一個圓盤。3.圓盤可以在3根柱子間任意的移動。14資料結構導論-C語言實作4.3.2河

5、內塔(TowersofHanoi)15資料結構導論-C語言實作4.3.2河內塔(TowersofHanoi)當n=2(有2個圓盤)時，一共需3次搬動，搬動的順序如下：步驟1：將1號圓盤從a柱搬到b柱。步驟2：將2號圓盤從a柱搬到c柱。步驟3：將1號圓盤從b柱搬到c柱。16資料結構導論-C語言實作4.3.2河內塔(TowersofHanoi)當n=3(有3個圓盤)時，一共需7次搬動，搬動的順序如下：步驟1：將1號圓盤從a柱搬到c柱。步驟2：將2號圓盤從a柱搬到b柱。步驟3：將1號圓盤從c柱搬到b柱。步驟4：將3號圓盤從a柱搬到c柱。步驟5：將1號圓盤從b柱搬到a柱。步驟6：將

6、2號圓盤從b柱搬到c柱。步驟7：將1號圓盤從a柱搬到c柱。17資料結構導論-C語言實作4.3.2河內塔(TowersofHanoi)18資料結構導論-C語言實作4.3.3運算式的轉換「a+b/(c-d)*e」是一個運算式(Expression)運算元(Operand)：a、b、c、d、e。運算子(Operator)：+、-、*、/。運算式求值必須遵守下列規則：1.括號內的運算式須優先處理。2.由左至右。3.依運算子的優先順序處理，例如先乘除後加減等。19資料結構導論-C語言實作4.3.3運算式的轉換20資料結構導論-C語言實作4.3.3運算式的轉換運算式的表示法：1.前置(

7、Prefix)運算式：運算子放在兩個運算元前面，沒有括號，不易閱讀。2.中置(Infix)運算式：運算子放在兩個運算元之間，可以有括號，最容易閱讀。3.後置(Postfix)運算式：運算子是放在兩個運算元之後，沒有括號，不易閱讀。21資料結構導論-C語言實作4.3.3運算式的轉換運算式的表示法：22資料結構導論-C語言實作4.3.3運算式的轉換中置運算式轉換成前置運算式：依據運算式的求值規則，先用括號將相關的運算組合括起來。將運算子取代左邊最接近的左括號(。移除所有的右括號)。23資料結構導論-C語言實作4.