1、第5章 堆棧,-后進(jìn)先出：一種操作受限的線性表,a,2,主要內(nèi)容,堆棧的定義 堆棧的描述 公式化描述 鏈表描述 堆棧的應(yīng)用 括號(hào)匹配、漢諾塔、火車車廂重排 迷宮、開關(guān)盒布線、離線等價(jià)類,a,3,堆棧定義,棧頂,棧底,堆棧（stack）是一個(gè)線性表，其插入和刪除操作都在表的同一端進(jìn)行，這端被稱為棧頂（top），另一端被稱為棧底（bottom） LIFO Last in, First out,a,4,a,5,a,6,抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型Stack 實(shí)例 元素線性表，棧底，棧頂 操作 Create()：創(chuàng)建一個(gè)空的堆棧 IsEmpty()：如果堆棧為空，則返回true，否則返回false Is

2、Full()：如果堆棧滿，則返回true，否則返回false Top()：返回棧頂元素 Push(x)：向堆棧中添加元素x Pop(x)：刪除棧頂元素，并將它傳遞給x ,a,7,主要內(nèi)容,堆棧的定義 堆棧的描述 公式化描述 鏈表描述 堆棧的應(yīng)用 括號(hào)匹配、漢諾塔、火車車廂重排 迷宮、開關(guān)盒布線、離線等價(jià)類,a,8,公式化描述：繼承線性表,template class Stack : private LinearList / LIFO objects public: Stack(int MaxStackSize = 10) : LinearList (MaxStackSize) bool IsE

3、mpty() const return LinearList:IsEmpty(); bool IsFull() const return (Length() = GetMaxSize();,線性表尾部作為棧頂,a,9,公式化描述（續(xù)）,T Top() const if (IsEmpty() throw OutOfBounds(); T x; Find(Length(), x); return x; Stack,取棧頂提取最后一個(gè)元素,壓棧添加到表尾,出棧提取最后一個(gè)元素,a,10,實(shí)現(xiàn)方法分析,IsFull需要獲取數(shù)組大小 方法一將類LinearList的成員MaxSize變?yōu)閜rotecte

4、d類型 方法二：LinearList類增加函數(shù)protected: int GetMaxSize() const return MaxSize;LinearList類的變化不會(huì)影響Stack類，更好！,a,11,實(shí)現(xiàn)方法分析,繼承方式為什么是private？ private繼承會(huì)把基類的所有成員變?yōu)榕缮惖乃接谐蓡T 棧雖可看作線性表的特例，但畢竟不是 用戶使用Stack類，我們希望他們使用Push、Pop，而不是Insert、Delete 而private繼承恰好可使Insert、Delete成為Stack的私有成員，用戶無法看到,a,12,Stack的效率,構(gòu)造函數(shù)、析構(gòu)函數(shù)與LinearL

5、ist相同 T：基本類型，(1) T：用戶自定義類， (MaxStackSize) 其他函數(shù)：(1),a,13,H1.自定義的Stack類,template class Stack public: Stack(int MaxStackSize = 10); Stack() delete stack; bool IsEmpty() const return top = -1; bool IsFull() const return top = MaxTop; T Top() const; Stack,a,14,構(gòu)造函數(shù),template Stack:Stack(int MaxStackSize)

6、/ Stack constructor. MaxTop = MaxStackSize - 1; stack = new TMaxStackSize; top = -1; ,空棧,a,15,Top函數(shù),template T Stack:Top() const / Return top element. if (IsEmpty() throw OutOfBounds(); return stacktop; ,a,16,Push函數(shù),template Stack ,a,17,Pop函數(shù),template Stack ,a,18,數(shù)組描述缺陷,與線性表數(shù)組描述類似，空間利用率低 兩個(gè)堆棧特例，空間利用

7、率較高 Push最壞情況（數(shù)組滿）仍為(ArraySize) Pop (1),a,19,主要內(nèi)容,堆棧的定義 堆棧的描述 公式化描述 鏈表描述 堆棧的應(yīng)用 括號(hào)匹配、漢諾塔、火車車廂重排 迷宮、開關(guān)盒布線、離線等價(jià)類,a,20,鏈表描述,棧頂在鏈表哪一端？ 尾節(jié)點(diǎn) Push(x)Insert(n, x)： (n) Pop(x)Delete(n, x)： (n) 首節(jié)點(diǎn) Push(x)Insert(0, x)： (1) Pop(x)Delete(1, x)： (1),a,21,LinkedStack類,template class LinkedStack : private Chain publ

8、ic: bool IsEmpty() const return Chain:IsEmpty(); bool IsFull() const; T Top() const if (IsEmpty() throw OutOfBounds(); T x; Find(1, x); return x;,a,22,LinkedStack類,LinkedStack,a,23,IsFull函數(shù),template bool LinkedStack:IsFull() const /Is stack full? try ChainNode *p = new ChainNode; delete p; return fa

9、lse; catch (NoMem) return true; 笨拙！,a,24,H2.自定義的鏈表實(shí)現(xiàn),template class Node friend LinkedStack; private: T data; Node *link; ;,a,25,自定義的鏈表實(shí)現(xiàn)（續(xù)）,template class LinkedStack public: LinkedStack() top = 0; LinkedStack(); bool IsEmpty() const return top = 0; bool IsFull() const; T Top() const; LinkedStack,a

10、,26,析構(gòu)函數(shù),template LinkedStack:LinkedStack() / Stack destructor. Node *next; while (top) next = top-link; delete top; top = next; ,a,27,IsFull函數(shù),template bool LinkedStack:IsFull() const / Is the stack full? try Node *p = new Node; delete p; return false; catch (NoMem) return true; ,a,28,Top函數(shù),templat

11、e T LinkedStack:Top() const / Return top element. if (IsEmpty() throw OutOfBounds(); return top-data; ,a,29,Push,template LinkedStack ,a,30,Pop,template LinkedStack ,a,31,H1-2小結(jié),堆棧的兩種實(shí)現(xiàn)方式,a,32,主要內(nèi)容,堆棧的定義 堆棧的描述 公式化描述 鏈表描述 堆棧的應(yīng)用 括號(hào)匹配、漢諾塔、火車車廂重排 迷宮、開關(guān)盒布線、離線等價(jià)類,a,33,括號(hào)匹配,(a*(b+c)+d)+(e-b)符合語法 (a+b)(不符合語

12、法 尋找匹配括號(hào)對(duì)正確處理和未匹配括號(hào)錯(cuò)誤報(bào)告 括號(hào)匹配是一個(gè)基礎(chǔ)問題，可以引申到 C+編譯器 數(shù)學(xué)公式自動(dòng)求解,a,34,a,35,a,36,算法設(shè)計(jì)思路,( a * ( b + c ) + d ) + (e - b)，匹配括號(hào)的規(guī)律？ 右括號(hào)與誰匹配（如果有的話）？ 由左至右處理符號(hào)的話，“右”“后”，靠后的先匹配LIFO 用一個(gè)棧保存未匹配的左括號(hào) 由左至右掃描表達(dá)式串，遇左括號(hào)，push 遇右括號(hào)，與棧頂左括號(hào)匹配，pop,嵌套或者并列,最近（右）未匹配左括號(hào),a,37,匹配失敗的情況,( a + b ) ) (失敗情況的規(guī)律 兩種情況對(duì)應(yīng)棧中情況,右括號(hào)之前無與之匹配的左括號(hào) 左括號(hào)

13、之后無與之匹配的右括號(hào),遇到一個(gè)右括號(hào)時(shí)，無未匹配的左括號(hào)?？?右括號(hào)都處理完時(shí)，還有未匹配的左括號(hào)表達(dá)式串處理完時(shí)，棧不空,a,38,括號(hào)匹配程序,#include #include #include #include stack.h const int MaxLength = 100; / max expression length,a,39,括號(hào)匹配程序（續(xù)）,void PrintMatchedPairs(char *expr) / Parenthesis matching. Stack s(MaxLength); int j, length = strlen(expr); / scan

14、 expression expr for ( and ) for (int i = 1; i = length; i+) if (expri - 1 = () s.Push(i);,a,40,括號(hào)匹配程序（續(xù)）,else if (expri - 1 = ) try s.Pop(j); / unstack match cout j i endl; catch (OutOfBounds) cout No match for right parenthesis” at i endl; ,a,41,括號(hào)匹配程序（續(xù)）,/ remaining ( in stack are unmatched while

15、 (!s.IsEmpty() s.Pop(j); cout No match for left parenthesis at j endl; ,a,42,括號(hào)匹配程序（續(xù)）,void main(void) char exprMaxLength; cout Type an expression of length at most MaxLength endl; cin.getline(expr, MaxLength); cout The pairs of matching parentheses in” endl; puts(expr); cout are endl; PrintMatchedP

16、airs(expr); ,a,43,運(yùn)行實(shí)例,Type an expression of length at most 100 (d+(a+b)*c*(d+e)-f)() The pairs of matching parentheses in (d+(a+b)*c*(d+e)-f)() are 4 8 12 16 1 19 No match for right parenthesis at 20 22 23 No match for left parenthesis at 21,a,44,漢諾塔,5800+億年,a,45,問題抽象,3個(gè)塔，n個(gè)碟子 初始：所有碟子放在1號(hào)塔，大的在底下，小的

17、在上面 任務(wù)：把碟子移動(dòng)到2號(hào)塔，順序不變， 可用3號(hào)塔輔助 限制 每次只能移動(dòng)一個(gè)碟子 總是大碟子在下，小的在上,a,46,遞歸解法,移動(dòng)碟子的方法：move(n, t1, t2, t3)將n個(gè)碟子從t1移到t2，t3輔助 可分解為3個(gè)步驟 將n-1個(gè)碟子從t1移到t3：move(n-1, t1, t3, t2) 將最大的碟子從t1移到t2 將n-1個(gè)碟子從t3移到t2：move(n-1, t3, t2, t1),遞歸規(guī)則,基本情況,a,47,漢諾塔遞歸程序,void TowersOfHanoi(int n, int x, int y, int z) / Move the top n dis

18、ks from tower x to tower y. / Use tower z for intermediate storage. if (n 0) TowersOfHanoi(n-1, x, z, y); cout Move top disk from tower x to top of tower y endl; TowersOfHanoi(n-1, z, y, x); moves(n)=2n-1最少次數(shù)，(2n),a,48,漢諾塔的棧實(shí)現(xiàn),#include #include stack.h“ class Hanoi friend void TowersOfHanoi(int); pu

19、blic: void TowersOfHanoi(int n, int x, int y, int z); private: Stack *S4; / array of pointers to stacks ;,a,49,漢諾塔的棧實(shí)現(xiàn),void Hanoi:TowersOfHanoi(int n, int x, int y, int z) int d; / disk number if (n 0) TowersOfHanoi(n-1, x, z, y); Sx-Pop(d); / remove a disk from x Sy-Push(d); / put this disk on towe

20、r y cout Move disk d from tower x to tower y endl; TowersOfHanoi(n-1, z, y, x); ,a,50,漢諾塔棧實(shí)現(xiàn),void TowersOfHanoi(int n) / Preprocessor for Hanoi:TowersOfHanoi. Hanoi X; X.S1 = new Stack (n); X.S2 = new Stack (n); X.S3 = new Stack (n); for (int d = n; d 0; d-) / initialize X.S1-Pop(d); / add disk d to

21、 tower 1 X.TowersOfHanoi(n, 1, 2, 3); ,a,51,漢諾塔棧實(shí)現(xiàn),void main(void) cout Moves for a three disk problem are endl; TowersOfHanoi(3); ,a,52,火車車廂重排問題,貨運(yùn)列車，n節(jié)車廂，編號(hào)1n 經(jīng)過車站n車站1，每站卸掉同號(hào)車廂 在始發(fā)站重新排列車廂，使得車廂按編號(hào)排列每站卸掉最后一節(jié)車廂即可 轉(zhuǎn)軌站一個(gè)入軌、一個(gè)出軌、k個(gè)緩沖鐵軌完成重排 允許三種操作 入軌緩沖軌 緩沖軌出軌 入軌出軌,a,53,圖示,列車行進(jìn)方向,a,54,我們?cè)囍约嚎偨Y(jié)出算法,初始：58174

22、2963,H1,H2,H3,a,55,繼續(xù),入：581742出：,H1,H2,H3,3,6,9,a,56,繼續(xù),入：581出：,H1,H2,H3,3,6,9,2,4,7,a,57,繼續(xù),入：5出：,H1,H2,H3,6,9,7,1 2 3 4,8,a,58,重排算法,緩沖軌后進(jìn)先出，用堆棧保存車廂號(hào) 考慮在出軌順序，必須棧底大，棧頂小 依次檢查入軌車廂編號(hào) 如果出軌所需要的下一車廂，緩沖軌 依次檢查緩沖軌，若新來的棧頂，入棧 如果=出軌所需要的下一車廂，出軌 緩沖軌中車廂可能滿足出軌需要，檢查緩沖軌棧頂車廂，如有可能，出棧，出軌，不是一次，要反復(fù)做，直至棧中無滿足出軌需要的車廂,a,59,重排

23、程序,bool Railroad(int p, int n, int k) / k track rearrangement of car order p1:n. / Return true if successful, false if impossible. / Throw NoMem exception if inadequate space. / create stacks for holding tracks LinkedStack *H; H = new LinkedStack k + 1; int NowOut = 1; / next car to output int minH

24、= n+1; / smallest car in a track int minS; / track with car minH,k=?,為什么不是Stack？,a,60,重排程序（續(xù)）,/ rearrange cars for (int i = 1; i = n; i+) if (pi = NowOut) / send straight out cout “Move car ” pi “ from input to output”; cout endl; NowOut+; while (minH = NowOut) Output(minH, minS, H, k, n); NowOut+;

25、,a,61,重排程序（續(xù)）,else / put car pi in a holding track if (!Hold(pi, minH, minS, H, k, n) return false; return true; ,a,62,Output：緩沖鐵軌出軌,void Output(int,a,63,Output：緩沖鐵軌出軌,/ find new minH and minS / by checking top of all stacks minH = n + 2; for (int i = 1; i = k; i+) if (!Hi.IsEmpty() ,a,64,Hold：入軌緩沖鐵軌,bool Hold(int c, int / a car index,a,65,Hold：入軌緩沖鐵軌（續(xù)）,for (int i = 1; i = k; i+) if (!Hi.IsEmpty() / track i not empty x = Hi.Top(); if (c x /