2.1-第三章 棧和隊(duì)列ppt課件_第1頁
2.1-第三章 棧和隊(duì)列ppt課件_第2頁
2.1-第三章 棧和隊(duì)列ppt課件_第3頁
2.1-第三章 棧和隊(duì)列ppt課件_第4頁
2.1-第三章 棧和隊(duì)列ppt課件_第5頁
已閱讀5頁,還剩56頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、進(jìn)棧示例進(jìn)棧示例 出棧示例出棧示例 例例: 假定有假定有4個(gè)元素個(gè)元素A,B,C,D,按所列次序進(jìn)棧,試寫出所有可按所列次序進(jìn)棧,試寫出所有可能的出棧序列。注意,每一個(gè)元能的出棧序列。注意,每一個(gè)元素進(jìn)棧后都允許出棧,如素進(jìn)棧后都允許出棧,如ACDB就是一種出棧序列。就是一種出棧序列。 解:可能的出棧序列有解:可能的出棧序列有ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA。棧的基本操作棧的基本操作1、初始化、初始化2、進(jìn)棧、進(jìn)棧PUSH3、出棧、出棧POP4、取棧頂元素、取棧頂元素GetTop5、判棧是

2、否非空、判棧是否非空3.2 棧的存儲結(jié)構(gòu)棧的存儲結(jié)構(gòu)順序存儲順序存儲-順序棧順序棧鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?鏈棧鏈棧 template class SeqStack T dataMaxSize; /存放棧元存放棧元素素 int top; /棧頂指針棧頂指針 public: SeqStack( ) ; /構(gòu)造函數(shù)構(gòu)造函數(shù) void Push(T x); /入棧入棧 T Pop( ); /出棧出棧 T Top( ); /取棧頂元素取棧頂元素 bool Empty( ); /判斷棧是判斷棧是否為空否為空 ; template class LinkStack Node *top; /棧頂指針 public:

3、LinkStack( ); /構(gòu)造函數(shù) LinkStack( ); /析構(gòu)函數(shù) void Push(T x); /入棧 T Pop( ); /出棧 T Top( ); /取棧頂元素 bool Empty( ); /判斷鏈棧是否為空棧 ;3.3 棧的操作算法棧的操作算法 1. 順序棧的操作算法順序棧的操作算法 2. 鏈?zhǔn)綏5牟僮魉惴ㄦ準(zhǔn)綏5牟僮魉惴? 順序棧的操作算法順序棧的操作算法 順序棧的初始化順序棧的初始化 template SeqStack:SeqStack( ) top=-1; (2) 順序棧的入棧操作順序棧的入棧操作 template void SeqStack:Push(T x)

4、if (top= MaxSize-1) cerr上溢; exit(1); top+; datatop=x; (3) 順序棧的出棧操作 template T SeqStack:Pop( ) if (top=-1) cerr下溢下溢; exit(1); x=datatop; top-; return x; (4) 取棧頂元素操作取棧頂元素操作 template T SeqStack:Top( ) if (top=-1) cerr下溢; exit(1);return datatop; (5) 判斷順序棧是否為空判斷順序棧是否為空 template bool SeqStack:Empty( ) ret

5、urn top=-1; 2 鏈棧的操作算法鏈棧的操作算法 (6) 鏈棧初始化 template LinkStack:LinkStack( ) top=NULL; 鏈棧入棧操作鏈棧入棧操作 template void LinkStack:Push( T x) s=new Node; s-data=x; s-next=top; top=s; (8) 鏈棧出棧操作鏈棧出棧操作template T LinkStack:Pop( ) if (top=NULL) cerrdata; p=top; top=top-next; delete p;return x;(9) 取棧頂元素操作取棧頂元素操作 temp

6、late T LinkStack:Top( ) if (top=NULL) cerrdata; (10) 判斷鏈棧是否為空判斷鏈棧是否為空 template bool LinkStack:Empty( ) return top=NULL; (11) (11) 鏈棧的析構(gòu)函數(shù)鏈棧的析構(gòu)函數(shù)template template LinkStack:LinkStack( )LinkStack:LinkStack( ) p=top;p=top;while (p)while (p) q=p;q=p;p=p-next;p=p-next;delete q;delete q; top=NULL;top=NULL

7、; 考慮:兩個(gè)棧共享同一段內(nèi)容空間,為了使得空考慮:兩個(gè)棧共享同一段內(nèi)容空間,為了使得空間利用率最高,應(yīng)如何分配棧空間?間利用率最高,應(yīng)如何分配棧空間?-兩個(gè)堆棧共享空間兩個(gè)堆棧共享空間0maxsize-1lefttoprighttop3.4 棧的應(yīng)用舉例棧的應(yīng)用舉例1. 棧的應(yīng)用之一棧的應(yīng)用之一: 遞歸調(diào)用遞歸調(diào)用例例: Hanoi塔問題塔問題. void Hanoi(int n, char a, char b, char c) if (n=1) Move (a, c); else Hanoi(n-1,a,c,b); Move(a,c); Hanoi(n-1,b,a,c); 一定要搞清執(zhí)行過

8、程一定要搞清執(zhí)行過程2. 棧的應(yīng)用之二棧的應(yīng)用之二: 算術(shù)表達(dá)式求值算術(shù)表達(dá)式求值 表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題。它的實(shí)現(xiàn)需要借助棧來完成。這里介紹一種簡單直觀的算法,即“算符優(yōu)先法”。 輸入包含+、*、/、圓括號和正整數(shù)組成的中綴算術(shù)表達(dá)式,以“”作為表達(dá)式結(jié)束符。計(jì)算該表達(dá)式的運(yùn)算結(jié)果。 運(yùn)算優(yōu)先級運(yùn)算優(yōu)先級()(=當(dāng)前運(yùn)算符棧頂運(yùn)算符算法思想:算法思想: 為實(shí)現(xiàn)算符優(yōu)先算法,使用兩個(gè)工作為實(shí)現(xiàn)算符優(yōu)先算法,使用兩個(gè)工作棧。棧。 1.運(yùn)算符運(yùn)算符OPTR棧棧, 用以寄存運(yùn)算符用以寄存運(yùn)算符; 2.操作數(shù)操作數(shù)OPND棧棧, 用以寄存操作數(shù)用以寄存操作數(shù) 或運(yùn)或運(yùn)算結(jié)果。算

9、結(jié)果。 (1首先置操作數(shù)棧首先置操作數(shù)棧OPND為空棧,表為空棧,表達(dá)式起始符達(dá)式起始符“”“”為運(yùn)算符的棧底元素;為運(yùn)算符的棧底元素; (2從左到右掃描,依次讀入中綴表達(dá)從左到右掃描,依次讀入中綴表達(dá)式中的每個(gè)字符,依次讀入表達(dá)式中每個(gè)式中的每個(gè)字符,依次讀入表達(dá)式中每個(gè)字符字符, 若是操作數(shù)若是操作數(shù),則進(jìn)則進(jìn)OPND棧,若是運(yùn)棧,若是運(yùn)算符,則與算符,則與OPTR棧的棧頂運(yùn)算符進(jìn)行比棧的棧頂運(yùn)算符進(jìn)行比較,作相應(yīng)操作,直至整個(gè)表達(dá)式求值完較,作相應(yīng)操作,直至整個(gè)表達(dá)式求值完畢即畢即OPTR棧的棧頂元素和當(dāng)前讀入的棧的棧頂元素和當(dāng)前讀入的字符均為字符均為“”“”)。)。 若讀到的是操作符若

10、讀到的是操作符c),則應(yīng)與操作符),則應(yīng)與操作符棧的棧頂元素棧的棧頂元素pre_op進(jìn)行比較,會進(jìn)行比較,會出現(xiàn)以下三種情況:出現(xiàn)以下三種情況: 若若pre_opc,則,則pre_op出棧,并在出棧,并在操作數(shù)棧中退棧操作數(shù)棧中退棧2次,依次得到操作數(shù)次,依次得到操作數(shù)b和和a,然后進(jìn)行,然后進(jìn)行a pre_op b運(yùn)算,并將運(yùn)算,并將運(yùn)算的結(jié)果壓入操作數(shù)棧中。運(yùn)算的結(jié)果壓入操作數(shù)棧中。 (舉例舉例)double Expression_Eval() SeqStack OPTR; / 運(yùn)算符棧運(yùn)算符棧SeqStack OPND; / 運(yùn)算數(shù)棧運(yùn)算數(shù)棧OPTR.Push();ch=getchar(

11、); while (ch!= | OPTR.Top( )!=) if (!InOPTR(ch,OP) OPND.Push(ch); ch=getchar( ); /讀到的是操作數(shù)則入棧讀到的是操作數(shù)則入棧else /讀到的是操作符讀到的是操作符 pre_op=OPTR.Top( ); switch (Precede(pre_op,ch) case : /情況情況b=OPND.Pop( ); a=OPND.Pop( ); pre_op=OPTR.Pop( );OPND.Push(Operate(a, pre_op, b); break; return OPND.Top( ); 后綴表達(dá)式求值后綴

12、表達(dá)式求值 中綴表達(dá)式中綴表達(dá)式后綴表達(dá)式后綴表達(dá)式求值求值 將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí),將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí),表達(dá)式中操作數(shù)次序不變,而操作符次表達(dá)式中操作數(shù)次序不變,而操作符次序會發(fā)生變化,同時(shí)去掉圓括號。因此序會發(fā)生變化,同時(shí)去掉圓括號。因此設(shè)置一個(gè)棧設(shè)置一個(gè)棧OPTR用以存放操作符。用以存放操作符。 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的基本思路中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的基本思路: 從左到右掃描中綴表達(dá)式,依次讀入表達(dá)從左到右掃描中綴表達(dá)式,依次讀入表達(dá)式中的每個(gè)字符,對于不同類型的字符按不式中的每個(gè)字符,對于不同類型的字符按不情況進(jìn)行處理。情況進(jìn)行處理。 若讀到的是操作

13、數(shù),則輸出該操作數(shù),并若讀到的是操作數(shù),則輸出該操作數(shù),并讀入下一個(gè)字符。讀入下一個(gè)字符。 若讀到的是左括號,則把它壓入到若讀到的是左括號,則把它壓入到OPTR棧中,并讀入下一個(gè)字符。棧中,并讀入下一個(gè)字符。 若讀到的是右括號,則表明括號內(nèi)的中綴若讀到的是右括號,則表明括號內(nèi)的中綴表達(dá)式已經(jīng)掃描完畢,將表達(dá)式已經(jīng)掃描完畢,將OPTR棧從棧頂頂棧從棧頂頂直到左括號之前的操作符依次出棧并輸出,直到左括號之前的操作符依次出棧并輸出,然后將左括號也出棧,并讀入下一個(gè)字符。然后將左括號也出棧,并讀入下一個(gè)字符。 若讀到的是操作符若讀到的是操作符c),則應(yīng)與操作符),則應(yīng)與操作符棧的棧頂元素棧的棧頂元素p

14、re_op進(jìn)行比較:進(jìn)行比較: 若若cpre_op,則將,則將c入棧,并讀下一個(gè)字符入棧,并讀下一個(gè)字符; 若若c= pre_op,則將,則將pre_op出棧并輸出。出棧并輸出。 按照以上過程掃描到中綴表達(dá)式結(jié)束符時(shí),按照以上過程掃描到中綴表達(dá)式結(jié)束符時(shí),把棧中剩余的操作符依次出棧并輸出,就得把棧中剩余的操作符依次出棧并輸出,就得到了轉(zhuǎn)換后的后綴表達(dá)式。到了轉(zhuǎn)換后的后綴表達(dá)式。 書中例子書中例子: 后綴表達(dá)式求值時(shí),不需要再考慮操作后綴表達(dá)式求值時(shí),不需要再考慮操作符的優(yōu)先級,只需從左到右掃描一遍后符的優(yōu)先級,只需從左到右掃描一遍后綴表達(dá)式即可??稍O(shè)置一個(gè)棧綴表達(dá)式即可。可設(shè)置一個(gè)棧OPND用

15、用以存放操作數(shù)。以存放操作數(shù)。 后綴表達(dá)式求值算法的基本思路:后綴表達(dá)式求值算法的基本思路: 從左到右掃描,依次讀入表達(dá)式中的每從左到右掃描,依次讀入表達(dá)式中的每個(gè)字符,直至表達(dá)式結(jié)束。個(gè)字符,直至表達(dá)式結(jié)束。 若讀到的是操作數(shù),則入棧OPND。 若讀到的是操作符,則在OPND棧中退出2個(gè)元素先退出的在操作符右,后退出的在操作符左),然后用該操作符進(jìn)行運(yùn)算,并將運(yùn)算結(jié)果壓入OPND棧中。 后綴表達(dá)式掃描完畢時(shí),OPND棧中僅有一個(gè)元素,即為運(yùn)算的結(jié)果。 書中例子:隊(duì)列的基本操作隊(duì)列的基本操作1、構(gòu)造一個(gè)隊(duì)列、構(gòu)造一個(gè)隊(duì)列2、進(jìn)隊(duì)操作、進(jìn)隊(duì)操作-將新元素插入隊(duì)將新元素插入隊(duì)尾尾3、出隊(duì)操作、出隊(duì)

16、操作-隊(duì)列頭元素出隊(duì)列頭元素出隊(duì)隊(duì)4、取隊(duì)列頭元素、取隊(duì)列頭元素5、判定隊(duì)列是否為空、判定隊(duì)列是否為空3.6 隊(duì)列的存儲結(jié)構(gòu) 順序存儲順序存儲-循環(huán)隊(duì)列循環(huán)隊(duì)列 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?鏈隊(duì)鏈隊(duì) 考慮考慮: 為什么要構(gòu)造循環(huán)隊(duì)列為什么要構(gòu)造循環(huán)隊(duì)列? template class SeqQueue T data MaxSize; /存放隊(duì)列元存放隊(duì)列元素素 int front, rear; /隊(duì)頭和隊(duì)尾隊(duì)頭和隊(duì)尾指針指針 public: SeqQueue( ); /構(gòu)造函數(shù),置構(gòu)造函數(shù),置空隊(duì)空隊(duì) void EnQueue(T x); /將元素將元素x入隊(duì)入隊(duì) T DeQueue( ); /將隊(duì)頭元

17、素出將隊(duì)頭元素出隊(duì)隊(duì) T GetQueue( ); /取隊(duì)頭元素取隊(duì)頭元素 bool Empty( ); /判斷隊(duì)列是否判斷隊(duì)列是否為空為空 ;n 進(jìn)隊(duì)時(shí)隊(duì)尾指針進(jìn)隊(duì)時(shí)隊(duì)尾指針 rear = rear + 1,將新元素,將新元素按按 rear 指示位置加入。指示位置加入。n 出隊(duì)時(shí)隊(duì)頭指針出隊(duì)時(shí)隊(duì)頭指針 front = front + 1,再將下,再將下標(biāo)為標(biāo)為 front 的元素取出。的元素取出。n 考慮:上圖中,元素再進(jìn)隊(duì),將如何?考慮:上圖中,元素再進(jìn)隊(duì),將如何?呈現(xiàn)呈現(xiàn)“假上溢假上溢現(xiàn)象現(xiàn)象 解決辦法解決辦法: 將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾相接的

18、循環(huán)結(jié)構(gòu)相接的循環(huán)結(jié)構(gòu) 即循環(huán)隊(duì)列即循環(huán)隊(duì)列 循環(huán)隊(duì)列的隊(duì)空隊(duì)滿問題循環(huán)隊(duì)列的隊(duì)空隊(duì)滿問題為了方便起見,約定:為了方便起見,約定:初始化建空隊(duì)時(shí),令初始化建空隊(duì)時(shí),令front=rear=0, 當(dāng)隊(duì)空時(shí):當(dāng)隊(duì)空時(shí):front=rear 當(dāng)隊(duì)滿時(shí):當(dāng)隊(duì)滿時(shí):front=rear 亦成立亦成立 因而,只憑等式因而,只憑等式front=rear 無法判斷隊(duì)空還是隊(duì)滿。無法判斷隊(duì)空還是隊(duì)滿。 有三種方法處理上述問題:有三種方法處理上述問題: 浪費(fèi)一個(gè)單元。當(dāng)使用MaxSize-1個(gè)單元時(shí)即認(rèn)為是隊(duì)滿, 此時(shí) (rear+1) % MaxSize=front 設(shè)置一個(gè)布爾變量flag。當(dāng)flag=fla

19、se時(shí)為空,當(dāng)flag=true時(shí)為滿。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的個(gè)數(shù)。如num,當(dāng)num=0時(shí)隊(duì)空, 當(dāng)num=MaxSize時(shí)隊(duì)滿。2隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu) template class LinkQueue private: Node *front, *rear; public: LinkQueue( ); /構(gòu)造函數(shù)構(gòu)造函數(shù) LinkQueue( ); /析構(gòu)函數(shù)析構(gòu)函數(shù) void EnQueue(T x); /將元素將元素x入隊(duì)入隊(duì) T DeQueue( ); /將隊(duì)頭元素出隊(duì)將隊(duì)頭元素出隊(duì) T GetQueue( ); /取鏈隊(duì)列的隊(duì)頭元素取鏈隊(duì)列的隊(duì)頭元素 bo

20、ol Empty( ); /判斷鏈隊(duì)列是否為空判斷鏈隊(duì)列是否為空 ;3.7 隊(duì)列的操作算法 1循環(huán)隊(duì)列的操作循環(huán)隊(duì)列的操作 2鏈隊(duì)列的操作鏈隊(duì)列的操作1循環(huán)隊(duì)列的操作循環(huán)隊(duì)列的操作(1循環(huán)隊(duì)列的初始化循環(huán)隊(duì)列的初始化template SeqQueue: SeqQueue () front=rear=0; (2循環(huán)隊(duì)列的入隊(duì)操作循環(huán)隊(duì)列的入隊(duì)操作 template void SeqQueue: EnQueue(T x) if (rear+1) % MaxSize =front) cerr上溢上溢; exit(1);rear=(rear+1) % MaxSize; datarear=x; 隊(duì)尾處插

21、入元素隊(duì)尾處插入元素 (3循環(huán)隊(duì)列的出隊(duì)操作循環(huán)隊(duì)列的出隊(duì)操作 template T SeqQueue:DeQueue( ) if (rear=front) cerr下溢下溢; exit(1);front=(front+1) % MaxSize; return datafront; (4判斷循環(huán)隊(duì)列是否為空判斷循環(huán)隊(duì)列是否為空 template bool SeqQueue:Empty( ) return rear=front; 2鏈隊(duì)列的操作鏈隊(duì)列的操作 (1) 鏈隊(duì)列的初始化鏈隊(duì)列的初始化 template LinkQueue:LinkQueue( )s=new Node;s-next=NU

22、LL;front=rear=s;(2鏈隊(duì)列入隊(duì)操作鏈隊(duì)列入隊(duì)操作 template void LinkQueue:EnQueue(T x) s=new Node; s-data=x;s-next=NULL;rear-next=s; /將結(jié)點(diǎn)將結(jié)點(diǎn)s插入到隊(duì)插入到隊(duì)尾尾rear=s; /將隊(duì)尾指針指向結(jié)點(diǎn)將隊(duì)尾指針指向結(jié)點(diǎn)s (3) 鏈隊(duì)列的出隊(duì)操作 template T LinkQueue:DeQueue() if (rear=front) cerrnext; x=p-data; front-next=p-next; if (p-next=NULL) rear=front; delete p;return x; (1問題描述問題描述 設(shè)有設(shè)有n個(gè)人排成一列,從前往后個(gè)人排成一列,從前往后“0,1連續(xù)報(bào)數(shù)。凡是報(bào)到連續(xù)報(bào)數(shù)。凡是報(bào)到“0的人出列,凡的人出列,凡是報(bào)到是報(bào)到“1的人立即站到隊(duì)伍的最后。的人立即站到隊(duì)伍的最后。反復(fù)進(jìn)行報(bào)數(shù),直到所有人均出列

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論