堆與棧ppt課件

1、1The Abstract Data Type Derived Classes and InheritanceFormula-Based RepresentationLinked RepresentationApplicationsChapter5 堆棧(Stacks)2堆棧的實現(xiàn)堆棧的應(yīng)用本章重點(diǎn)3定義 堆棧是一個線性表，其插入(也稱為添加)和刪除操作都在表的同一端進(jìn)行。允許插入和刪除的一端被稱為棧頂(top)，另一端被稱為棧底(bot tom)。堆棧是一個后進(jìn)先出（last-in-first-out, LIFO）的數(shù)據(jù)結(jié)構(gòu)。堆棧(Stacks)4堆棧5堆棧ADT6公式化描述(Formula

2、-Based Representation)效率、改進(jìn)鏈接描述(Linked) Representation效率比較堆棧7n堆棧數(shù)據(jù)對象是更通用的線性表對象的限制版本。(插入和刪除操作僅能在表的同一端進(jìn)行)n例如，如果把表的左端定義為棧底，右端定義為棧頂，那么堆棧的添加操作等價于在表的右端進(jìn)行插入操作，刪除操作等價于在表的右端進(jìn)行刪除操作。繼承8templateclass Stack : private LinearList / LIFO 對象public:Stack(int MaxStackSize = 10):LinearList(MaxStackSize) bool IsEmpty()

3、constreturn LinearList:IsEmpty();bool IsFull() constreturn (Length() = GetMaxSize();T Top() constif (IsEmpty() throw OutOfBounds(); T x; Find(Length(), x); return x;Stack& Add(const T& x)Insert(Length(), x); return *this;Stack& Delete(T& x)LinearList : Delete (Length(), x);return *th

4、is; ;公式化描述的堆棧類(派生)9templateclass Stack / LIFO 對象public:Stack(int MaxStackSize = 10);Stack () delete stack;bool IsEmpty() const return top = -1;bool IsFull() const return top = MaxTo p ; T Top() const;Stack& Add(const T& x);Stack& Delete(T& x);private :int top; / 棧頂int MaxTop; / 最大的棧頂

5、值T *stack; / 堆棧元素數(shù)組 ;自定義Stack10templateStack:Stack(int MaxStackSize)MaxTop = MaxStackSize - 1;stack = new TMaxStackSize;top = -1;Stack 類構(gòu)造函數(shù)11templateT Stack:Top() constif (IsEmpty() throw OutOfBounds();else return stacktop; 復(fù)雜性?返回棧頂元素12templateStack& Stack:Add(const T& x) if (IsFull() throw

6、 NoMem();stack+top = x;return *this; 復(fù)雜性?添加元素x13templateStack& Stack:Delete(T& x)if (IsEmpty() throw OutOfBounds();x = stacktop-;return *this; 復(fù)雜性?刪除棧頂元素，并將其送入x14哪一端對應(yīng)棧頂?鏈表描述15templateclass LinkedStack : private Chain public:bool IsEmpty() constreturn Chain:IsEmpty();bool IsFull() const;T To

7、p() constif (IsEmpty() throw OutOfBounds();T x; Find(1, x); return x;LinkedStack& Add(const T& x)Insert(0, x); return *this;LinkedStack& Delete(T& x)Chain:Delete(1, x); return *this; ;從Chain派生的鏈表形式的堆棧16templatebool LinkedStack:IsFu11() const/ 堆棧是否滿?try ChainNode *p = new ChainNode;de

8、lete p; return false; catch (NoMem) return true;從Chain派生的鏈表形式的堆棧17template class Nodefriend LinkedStack;private:T data;Node *link; ;自定義鏈表形式的堆棧18templateclass LinkedStack public:LinkedStack () top = 0;LinkedStack( ) ;bool IsEmpty() const return top=0;bool IsFull() const;T Top() const;LinkedStack&

9、 Add(const T& x);LinkedStack& Delete(T& x);private:Node *top; / 指向棧頂節(jié)點(diǎn) :自定義鏈表形式的堆棧19templateLinkedStack:LinkedStack( )Node *next;while (top) next = top-link;delete top;top = next;析構(gòu)函數(shù)20templatebool LinkedStack:IsFu11() consttry Node *p = new Node;delete p;return false;catch (NoMem) retur

10、n true;堆棧是否滿?21templateT LinkedStack:Top() constif (IsEmpty() throw OutOfBounds();return top-data;返回棧頂元素22templateLinkedStack& LinkedStack:Add(const T& x)Node *p = new Node;p-data = x;p-link = top;top = p;return *this;添加元素x23templateLinkedStack& LinkedStack:Delete(T& x)if (IsEmpty()

11、throw OutOfBounds();x = top-data;Node *p = top;top = top-link;delete p;return *this;刪除棧頂元素，并將其送入x24鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作比較25括號匹配(Parenthesis Matching)漢諾塔(Towers of Hanoi)火車車廂重排(Rearranging Railroad Cars)開關(guān)盒布線(Switch Box Routing)離線等價類(Offline Equivalence Problem)迷宮老鼠(Rat in a Maz

12、e)應(yīng)用26n目標(biāo):輸入一個字符串，輸出相互匹配的括號以及未能匹配的括號。n例：字符串(a*(b+c)+d)n例：字符串(a+b)(括號匹配27n如果從左至右掃描一個字符串，那么每個右括號將與最近遇到的那個未匹配的左括號相匹配。n如何實現(xiàn)？觀察28n可以在從左至右的掃描過程中把所遇到的左括號存放到堆棧內(nèi)。每當(dāng)遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ枺ㄈ绻嬖冢┫嗥ヅ洌瑫r從棧頂刪除該左括號。方法293031n已知n個碟子和3座塔。初始時所有的碟子按從大到小次序從塔1的底部堆放至頂部，需要把碟子都移動到塔2，每次移動一個碟子，而且任何時候都不能把大碟子放到小碟子的上面。漢諾塔問題32n為了把最大的

13、碟子移動到塔2，必須把其余n- 1個碟子移動到塔3，然后把最大的碟子移動到塔2。n接下來是把塔3上的n-1個碟子移動到塔2，為此可以利用塔2和塔1?？梢酝耆鲆曀?上已經(jīng)有一個碟子的事實，因為這個碟子比塔3上將要移過來的任一個碟子都大，因此，可以在它上面堆放任何碟子。漢諾塔問題-遞歸方法33void TowersOfHanoi(int n, int x, int y, int z) / /把n 個碟子從塔x 移動到塔y，可借助于塔zif (n 0) TowersOfHanoi(n-1, x, z, y);coutMove top disk from tower x to top of towe

14、r yendl;TowersOfHanoi(n-l, z, y, x);求解漢諾塔問題的遞歸程序34n希望給出每次移動之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一步要求35class Hanoifriend void TowersOfHanoi(i n t);public:void TowersOfHanoi(int n, int x, int y, int z);private:Stack *S4; ;使用堆棧求解漢諾塔問題36void Hanoi:TowersOfHanoi(int n, int x, int y, int z)/ 把n 個碟子從塔x 移動到塔y，可借助于塔zint d;

15、/ 碟子編號if (n 0) TowersOfHanoi(n-l, x, z, y);Sx-Delete(d); /從x中移走一個碟子Sy-Add(d); /把這個碟子放到y(tǒng) 上ShowState() ;TowersOfHanoi(n-l, z, y, x);使用堆棧求解漢諾塔問題37void TowersOfHanoi(int n)/ Hanoi:towersOfHanoi的預(yù)處理程序Hanoi X；X.S1 = new Stack (n);X.S2 = new Stack (n);X.S3 = new Stack (n);for (int d = n; d 0; d-) / 初始化X.S1

16、-Add(d); / 把碟子d 放到塔1上/把塔1上的n個碟子移動到塔2上，借助于塔3 的幫助X.TowersOfHanoi(n, 1, 2, 3);使用堆棧求解漢諾塔問題38n在一個轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個入軌、一個出軌和k個緩沖鐵軌(位于入軌和出軌之間)。火車車廂重排問題39n從前至后依次檢查入軌上的所有車廂。n如果正在檢查的車廂就是下一個滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動到緩沖鐵軌上，直到按輸出次序要求輪到它時才將它放到出軌上。n緩沖鐵軌按照何種方式使用?火車車廂重排方案40bool Railroad(int p, int n, int

17、 k)/ k 個緩沖鐵軌，車廂初始排序為p 1 : n / 如果重排成功，返回true，否則返回false/ 如果內(nèi)存不足，則引發(fā)異常NoMem 。/創(chuàng)建與緩沖鐵軌對應(yīng)的堆棧LinkedStack *H;H = new LinkedStack k + 1;int NowOut = 1; /下一次要輸出的車廂int minH = n+l; /緩沖鐵軌中編號最小的車廂int minS; /minH號車廂對應(yīng)的緩沖鐵軌火車車廂重排程序41/車廂重排for(int i = 1; i = n; i+)if (pi = NowOut) / 直接輸出tcout“將車廂”pi“從入軌移至出軌endl;NowO

18、ut+ ;/從緩沖鐵軌中輸出while (minH = NowOut) Output(minH, minS, H, k, n);NowOut+ ;else / 將pi 送入某個緩沖鐵軌if (!Hold(pi, minH, minS, H, k, n)return false; return true; 火車車廂重排程序42void Output(int& minH, int& minS, LinkedStack H , int k, int n)/把車廂從緩沖鐵軌送至出軌處，同時修改minS和minHint c; / 車廂索引/ 從堆棧minS中刪除編號最小的車廂minHHm

19、inS.Delete(c) ;cout Move car minH from holding track minS to output endl;/ 通過檢查所有的棧頂，搜索新的minH和minSminH = n + 2;for (int i = 1; i = k; i+)if (!Hi.IsEmpty() & (c = Hi.Top() minH) minH = c;minS = i;Output 函數(shù)43bool Hold(int c, int& minH, int &minS, LinkedStack H, int k, int n)(/ 在一個緩沖鐵軌中放入車廂

20、c/ 如果沒有可用的緩沖鐵軌，則返回false/ 如果空間不足，則引發(fā)異常NoMem，否則返回true/ 為車廂c尋找最優(yōu)的緩沖鐵軌/ 初始化int BestTrack = 0, / 目前最優(yōu)的鐵軌BestTop= n + 1, / 最優(yōu)鐵軌上的頭輛車廂x;/ 車廂索引Hold函數(shù)44/掃描緩沖鐵軌for (int i = 1; i = k; i+)if (!Hi.IsEmpty() / 鐵軌i 不空x = Hi.Top( ) ;if (c x & x BestTop) /鐵軌i 頂部的車廂編號最小BestTop= x;BestTrack = i;else / 鐵軌i 為空if (!B

21、estTrack) BestTrack = i;Hold函數(shù)45if (!BestTrack) return false; /沒有可用的鐵軌/把車廂c 送入緩沖鐵軌HBestTrack.Add(c) ;cout Move car c from input to holding track BestTrack endl;/必要時修改minH 和minSif (c minH) minH = c; minS = BestTrack ; return true; 復(fù)雜性？Hold函數(shù)46n給定一個矩形布線區(qū)域，其外圍有若干針腳。兩個針腳之間通過布設(shè)一條金屬線路而實現(xiàn)互連。這條線路被稱為電線，被限制在矩

22、形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會發(fā)生電流短路。所以，不允許電線間的交叉。每對互連的針腳被稱為網(wǎng)組。n目標(biāo)是要確定對于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。開關(guān)盒布線問題47n四個網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)n可布線開關(guān)盒(routable switch box)開關(guān)盒布線示例48n當(dāng)兩個針腳互連時，其電線把布線區(qū)分成兩個分區(qū)。n如果有一個網(wǎng)組，其兩個針腳分別位于這兩個不同的分區(qū)，那么這個網(wǎng)組是不可以布線的，因而整個電路也是不可布線的。n如果沒有這樣的網(wǎng)組，則可以繼續(xù)判斷每個獨(dú)立的分區(qū)是不是可布線的。為此，可以從一個分區(qū)中取出一個網(wǎng)組，利用該網(wǎng)組把這個分區(qū)又

23、分成兩個子分區(qū)，如果任一個網(wǎng)組的兩個針腳都分布在同一個子分區(qū)之中(即不會出現(xiàn)兩個針腳分別位于兩個子分區(qū)的情形)，那么這個分區(qū)就是可布線的。策略49n可以按順時針或反時針方向沿著開關(guān)盒的外圍進(jìn)行遍歷。n例：按順時針方向從針腳1開始遍歷，將依次檢查針腳1, 2, ., 8。n針腳1和4屬于同一個網(wǎng)組，那么在針腳1至針腳4之間出現(xiàn)的所有針腳構(gòu)成了第一個分區(qū)，而在針腳4至針腳1之間未出現(xiàn)的所有針腳構(gòu)成了第二個分區(qū)。n把針腳1放入堆棧，然后繼續(xù)處理，直至遇到針腳4。這個過程使我們僅在處理完一個分區(qū)之后才能進(jìn)入下一個分區(qū)。方案50n輸入是元素數(shù)目n、關(guān)系數(shù)目r 以及r 對關(guān)系，問題的目標(biāo)是把n個元素分配至

24、相應(yīng)的等價類。離線等價類問題5152 53 54 0,1,2,3,4,5,6,7,8,9, 10,11 0,4,1,2,3,5,6,7,8,9,10,11 0,4, 1,3,2,5,6,7,8,9,10,110,4,1,3,2,5,6,10,7,8,9,11 0,4,1,3,2,5,6,10,7,8,9,11 0,4,7,1,3,2,5,6,10,8,9,11 0,4,7,1,3,2,5,6,8,9,10,11 0,4,7,1,3,5,2,6,8,9,10,110,4,7,1,3,5,2,11,6,8,9,100,2,4,7,11,1,3,5,6,8,9,10555657 鏈鏈序序號號等等價價

25、 對對OUT初初態(tài)態(tài)輸輸出出OUT終終態(tài)態(tài) 棧棧 0False 0 True 0 11 False 11 True 11 0 4 False 4 True 11,4 4 7 False 7 True 11,7 4 0 True True 11,7 鏈鏈序序號號等等價價 對對OUT初初態(tài)態(tài)輸輸出出OUT終終態(tài)態(tài)棧棧 7 4 True True 11 11 0 True True 11 0 True True 11 2 False 2 True 2 2 11 True True58void main(void)/ 離線等價類問題int n, r;/輸入n 和rcout Enter number o

26、f elements n;if (n 2) cerr Too few elements endl; exit(l);cout Enter number of relations r;if (r 1) cerr Too few relations endl; exit(l);離線等價類程序(一)59/創(chuàng)建一個指向n個鏈表的數(shù)組Chain *chain;try chain = new Chain n+1;catch (NoMem) cerr Out of memory endl; exit(1);/輸入r個關(guān)系，并存入鏈表for (int i = 1; i = r; i+) cout Enter

27、next relation/pair a b;chaina.Insert(0,b) ;chainb.Insert(0,a) ;離線等價類程序(一)60/對欲輸出的等價類進(jìn)行初始化LinkedStack stack;bool *out;try out = new bool n+1;catch (NoMem) cerrOut of memoryendl; exit(l);for (int i = 1; i = n; i+)outi = false;/輸出等價類for (int i = 1; i = n; i+)if (!outi) /開始一個新的等價類cout Next class is: i ;

28、outi = true;stack.Add(i) ;離線等價類程序(二)61/從堆棧中取其余的元素while (!stack.IsEmpty() int *q, j;stack.Delete(j) ;/鏈表chainj中的元素在同一個等價類中，使用遍歷器取這些元素ChainIterator c;q = c.Initialize(chainj);while (q)if (!out*q) cout q ; out*q = true; stack.Add(*q); q = c.Next();cout endl;cout endl End of class list endl;離線等價類程序(二)62

29、n迷宮老鼠(rat in a maze)問題要求尋找一條從入口到出口的路徑。n路徑是由一組位置構(gòu)成的，每個位置上都沒有障礙，且每個位置(第一個除外)都是前一個位置的東、南、西或北的鄰居。迷宮老鼠問題63n假定用nm的矩陣來描述迷宮，位置( 1 , 1 )表示入口，(n,m) 表示出口，n和m分別代表迷宮的行數(shù)和列數(shù)。n迷宮中的每個位置都可用其行號和列號來指定。在矩陣中，當(dāng)且僅當(dāng)在位置(i,j)處有一個障礙時其值為1，否則其值為0。迷宮的描述64迷宮的描述65n首先把迷宮的入口作為當(dāng)前位置。n如果當(dāng)前位置是迷宮出口，那么已經(jīng)找到了一條路徑，搜索工作結(jié)束。n如果當(dāng)前位置不是迷宮出口，則在當(dāng)前位置上

30、放置障礙物，以便阻止搜索過程又繞回到這個位置。n然后檢查相鄰的位置中是否有空閑的(即沒有障礙物)，如果有，就移動到這個新的相鄰位置上，然后從這個位置開始搜索通往出口的路徑。如果不成功，選擇另一個相鄰的空閑位置，并從它開始搜索通往出口的路徑。n如果所有相鄰的空閑位置都已經(jīng)被探索過，并且未能找到路徑，則表明在迷宮中不存在從入口到出口的路徑。方案66n對于迷宮內(nèi)部的位置(非邊界位置)，有四種可能的移動方向：右、下、左和上。n對于迷宮的邊界位置，只有兩種或三種可能的移動。n為了避免在處理內(nèi)部位置和邊界位置時存在差別，可以在迷宮的周圍增加一圈障礙物。簡化算法67迷宮的描述68n可以用行號和列號來指定每個

31、迷宮位置，行號和列號被分別稱之為迷宮位置的行坐標(biāo)和列坐標(biāo)。n可以定義一個相應(yīng)的類Position來表示迷宮位置，它有兩個私有成員row和col。n為保存從入口到當(dāng)前位置的路徑，可以采用以下基于公式化描述的堆棧：Stack path(MaxPathLength);n其中MaxPathLength是指最大可能的路徑長度（從入口到迷宮中任一位置）。位置表示69n按一種固定的方式來選擇可行的位置，將可以使問題得到簡化。n例如，可以首先嘗試向右移動，然后是向下，向左，最后是向上。移動到相鄰位置的方法70移動到相鄰位置的方法71假定maze、m (迷宮的大小)和path都是按如下方式定義的全局變量：int *maze, m;Stack *path;迷宮算法實現(xiàn)72bool FindPath()/ 尋找從位置( 1 , 1 )到出口( m , m )的路徑/如果成功則返回true ，否則返回f a l s e/ 如果內(nèi)存不足則引發(fā)異常N o M e mpath = new Stack(m * m - 1);/對偏移量進(jìn)行初始化Position offset 4 ;offset0.row = 0; offset0.col = 1; /向右of