資料結構簡介.

Presentation on theme: "資料結構簡介."— Presentation transcript:

1 資料結構簡介

2 再將a從堆疊中刪除(pop)，堆疊空了，top=0
堆疊(Stack)與佇列(Queue) 堆疊 資料插入(push)與刪除(pop)的動作只能在串列的一端(top)進行。 FILO：先進後出(first in last out) LIFO：後進先出(last in first out) 堆疊是空的，top=0  再將a從堆疊中刪除(pop)，堆疊空了，top=0 a 將a插入(push)堆疊中，top=1   b a 再將b插入(push)堆疊中，top=2 a 將b從堆疊中刪除(pop)，top=1 

3 堆疊的應用 運算式的中序，後序，前序表示法 中序表示法在運算時，須考慮： 中序(infix)：運算符號在運算元中間，如a+b。
後序(postfix)：運算符號在運算元後面，如ab+。 前序(prefix)：運算符號在運算元前面，如+ab。 中序表示法在運算時，須考慮： 運算符號的優先順序（priority） 結合性（左結合或右結合） 括弧內先處理 前序式與後序式則無上述困擾 (A+B)/(C-D)*E+F/G

4 堆疊的應用 電腦如何經由後序表示法了解運算式？ 自左而右輸入後序運算式 逢運算元，存入堆疊(push)
逢運算符號α，從堆疊取出(pop)必要數目的運算元，執行α運算 結果再存回堆疊 運算式掃描完畢，後序式之計算結果就在堆疊頂部，pop出來即可 2 4 1 計算後序式：63/1-42*+ 將4,2存入堆疊中，top=3 1 將結果1存回堆疊中，top=1  堆疊是空的，top=0  將1,2取出，執行-運算，結果=1   8 1 將8存回堆疊中，top=2 1 2 6 將6存入堆疊中，top=1 將1再存入堆疊中，top=2 將2,4取出，執行*運算，結果=8    3 6 將3再存入堆疊中，top=2 將結果2存回堆疊中，top=1  2 9 將9存回堆疊中，top=1 將3,6取出，執行/運算，結果=2 將8,1取出，執行+運算，結果=9

5 堆疊的應用 中序式 → 後序式： 例：將中序式改為後序式：(A+B)/(C-D)*E+F/G
將運算式依各運算符號的優先順序完全地以括弧括起來 即每一運算符號對應一對括弧 移動運算符號到對應的右括弧前面 去掉所有括弧 例：將中序式改為後序式：(A+B)/(C-D)*E+F/G (A+B)/(C-D)*E+F/G ((((A+B)/(C-D))*E)+(F/G))… ((((AB+) (CD-)/) E*) (FG/)+)… AB+CD-/ E*FG/+ … HW_6 第一題：將中序式改為後序式：(a+b*c)-d/e+f

6 (((a+(b*c))-(d*e))+f)
堆疊的應用 將後序(postfix)運算式abc*+de*-f+轉換成前序(prefix)運算式之結果為何？ Ans： abc*+de*-f+ a(b*c)+de*-f+ (a+(b*c))de*-f+ (a+(b*c))(d*e)-f+ ((a+(b*c))-(d*e))f+ (((a+(b*c))-(d*e))+f) (a+b*c)-d*e+f

7 堆疊的應用 HW_6 第二題： 後序運算式(postfix expression)”235*27-/+63*+”中的運算元(operand)皆為個位數，則其運算結果為何？

8 堆疊(Stack)與佇列(Queue) 佇列 資料插入(insertion)的動作在串列的尾端(rear)進行
資料刪除(deletion)的動作在串列的頭端(front)進行。 FIFO：先進先出(first in first out) LILO：後進後出(last in last out) Rear=0 Front=0  Rear=1 Front=0 Rear=2 Front=2 A   Rear=2 Front=0 Rear=2 Front=1  B A B

9 二元樹 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z + - * / $
A是B,C的父節點，D,E是B的子節點，M是Z,+的父節點，P,Q是H的子節點。 A(樹根)有B,C兩棵子樹…，C是C子樹的樹根。 P,Q,R,S,T…*,/,$是終端節點(樹葉)，其餘的皆是非終端節點，如A,D,F,M…。 階度(level)：樹根A階度為1，B,C階度為2，J,K,L,M…階度為4。 高度(hight)：整棵樹的高度為4，F子樹的高度為3，H子樹的高度為2。

10 二元樹的追蹤(trace) 中序(inorder)追蹤：BC A EDGFHI 左根 右
前序(preorder)追蹤： A BC DEFGIH 根左 右 後序(postorder)追蹤：CB EGHIFD A 左右 根 A B D C E F G I Home_work_7 請將右列二元樹，分別以中序，前序追蹤列出節點順序。 A H B C D E F G H I J

11 河內塔(Hanoi Tower) 右圖，如要將n個碟子由A搬到C，則 先將n-1個碟子由A搬到B 再將最大的碟子由A搬到C
最後再將B的n-1個碟子搬到C 規定：大盤子不可以疊在小盤子上面 A B C 1 AC 2 AB 1 CB 3 AC 1 BA 2 BC 1 N個碟子共須搬2n-1次 2 3 A B C