资料结构简介

《资料结构简介》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、資料結構簡介1堆疊(Stack)與佇列(Queue)堆疊資料插入(push)與刪除(pop)的動作只能在串列的一端(top)進行。FILO：先進後出(firstinlastout)LIFO：後進先出(lastinfirstout)堆疊是空的，top=0a將a插入(push)堆疊中，top=1ba再將b插入(push)堆疊中，top=2a將b從堆疊中刪除(pop)，top=1再將a從堆疊中刪除(pop)，堆疊空了，top=02堆疊的應用運算式的中序，後序，前序表示法中序(infix)：運算符號在運算元中間，如a+b。後序(postfix)：運算符號在運算元後面，如ab

2、+。前序(prefix)：運算符號在運算元前面，如+ab。中序表示法在運算時，須考慮：運算符號的優先順序（priority）結合性（左結合或右結合）括弧內先處理前序式與後序式則無上述困擾(A+B)/(C-D)*E+F/G3堆疊的應用電腦如何經由後序表示法了解運算式？自左而右輸入後序運算式逢運算元，存入堆疊(push)逢運算符號α，從堆疊取出(pop)必要數目的運算元，執行α運算結果再存回堆疊運算式掃描完畢，後序式之計算結果就在堆疊頂部，pop出來即可計算後序式：63/1-42*+堆疊是空的，top=06將6存入堆疊中，top=136將3再存入堆疊中，top=22將結果

3、2存回堆疊中，top=1將3,6取出，執行/運算，結果=212將1再存入堆疊中，top=21將結果1存回堆疊中，top=1將1,2取出，執行-運算，結果=1241將4,2存入堆疊中，top=381將8存回堆疊中，top=2將2,4取出，執行*運算，結果=89將9存回堆疊中，top=1將8,1取出，執行+運算，結果=94堆疊的應用中序式→後序式：將運算式依各運算符號的優先順序完全地以括弧括起來即每一運算符號對應一對括弧移動運算符號到對應的右括弧前面去掉所有括弧例：將中序式改為後序式：(A+B)/(C-D)*E+F/G(A+B)/(C-D)*E+F/G((((A+B)

4、/(C-D))*E)+(F/G))…((((AB+)(CD-)/)E*)(FG/)+)…AB+CD-/E*FG/+…HW_6第一題：將中序式改為後序式：(a+b*c)-d/e+f5堆疊的應用將後序(postfix)運算式abc*+de*-f+轉換成前序(prefix)運算式之結果為何？Ans：abc*+de*-f+a(b*c)+de*-f+a(b*c)+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+f6堆疊

5、的應用HW_6第二題：後序運算式(postfixexpression)”235*27-/+63*+”中的運算元(operand)皆為個位數，則其運算結果為何？7堆疊(Stack)與佇列(Queue)佇列資料插入(insertion)的動作在串列的尾端(rear)進行資料刪除(deletion)的動作在串列的頭端(front)進行。FIFO：先進先出(firstinfirstout)LILO：後進後出(lastinlastout)ABARear=0Front=0Rear=1Front=0Rear=2Front=0BRear=2Front=1Rear=2Front=28

6、二元樹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。APQRSTUVWXYZ+-*/$HIJKLMNODEFGBC9二元樹的追蹤(trace)中序(inorder)追蹤：BCAEDGFHI左根右前序(preorder)追蹤：ABCDEFGIH根左

7、右後序(postorder)追蹤：CBEGHIFDA左右根GICEFBDAHHome_work_7請將右列二元樹，分別以中序，前序追蹤列出節點順序。GHIJDEFBCA10河內塔(HanoiTower)右圖，如要將n個碟子由A搬到C，則先將n-1個碟子由A搬到B再將最大的碟子由A搬到C最後再將B的n-1個碟子搬到C規定：大盤子不可以疊在小盤子上面ABCABC3211AC2AB1CB3AC1BA2BC1ACN個碟子共須搬2n-1次11