數(shù)據(jù)結(jié)構(gòu)課件C++版=

2023/8/16mayan第三章棧和隊(duì)列棧棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng)用優(yōu)先級(jí)隊(duì)列2023/8/5mayan第三章棧和隊(duì)列棧定義：棧限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。定義：棧限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。遞歸函數(shù)的實(shí)現(xiàn)

在遞歸函數(shù)的執(zhí)行中，

需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。A(){…B();…}C(){……}B(){…C();…}調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序ABC函數(shù)返回順序CBA后調(diào)用的函數(shù)先返回

函數(shù)調(diào)用機(jī)制可通過棧來實(shí)現(xiàn)計(jì)算機(jī)正是利用棧來實(shí)現(xiàn)函數(shù)的調(diào)用和返回的遞歸函數(shù)的實(shí)現(xiàn)A(){C(){B(){調(diào)用調(diào)用返回返回n=3階乘函數(shù)fact(n)的執(zhí)行過程Main(){intn=3,y;Ly=fact(n);}調(diào)用調(diào)用調(diào)用intfact(n){

If（n=1）

return（1）；

ElseL1return（n*fact(n-1)）；}n=3intfact(intn){

If（n=1）

return（1）；

Else

L1return（n*fact(n-1)）；}n=2intfact(intn){

If（n=1）

return（1）；

ElseL1return（n*fact(n-1)）；}//factn=1L3L11L12返回1返回2返回61n*fact(n-1)n*fact(n-1)fact(n)返回地址實(shí)參

遞歸調(diào)用中棧的變化n=3階乘函數(shù)fact(n)的執(zhí)行過程Main(){調(diào)將十進(jìn)制整數(shù)轉(zhuǎn)換成二至九之間的任一進(jìn)制數(shù)輸出

將一個(gè)十進(jìn)制數(shù)4327轉(zhuǎn)換成八進(jìn)制數(shù)(10347)8：將十進(jìn)制整數(shù)轉(zhuǎn)換成二至九之間的任一進(jìn)制數(shù)輸出將一個(gè)十進(jìn)制數(shù)abc32111213121YXZabc32111213121YXZ數(shù)據(jù)結(jié)構(gòu)ppt課件C++版=2023/8/16mayan第三章棧和隊(duì)列--棧的定義

棧和隊(duì)列稱為運(yùn)算受限的線性表。棧（stack）是指只允許在表的末端進(jìn)行插入和刪除的線性表。棧又叫做后進(jìn)先出（LIFO）的線性表。2023/8/5mayan第三章棧和隊(duì)列-棧的基本概念棧是一種“特殊”的線性表，這種線性表上的插入和刪除運(yùn)算限定在表的某一端進(jìn)行。棧頂：允許進(jìn)行插入和刪除的這一端。棧底：反之為棧底。棧頂元素：處于棧頂位置的數(shù)據(jù)元素稱為～。棧頂元素的位置由棧頂指針變量記錄；空棧:當(dāng)棧中不含任何數(shù)據(jù)元素時(shí)稱為～棧的基本概念棧是一種“特殊”的線性表，這種線性表上的插入和刪2023/8/16mayan第三章棧和隊(duì)列--順序?；跀?shù)組的存儲(chǔ)表示實(shí)現(xiàn)的棧稱為順序棧。當(dāng)前棧頂位置由數(shù)組下標(biāo)指針top指示，即top指示最后加入的元素的存儲(chǔ)位置，當(dāng)top=-1時(shí)?？眨?dāng)top=maxSize-1時(shí)棧滿。順序棧的類定義2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的類定義template<classT>classSeqStack{//順序棧類定義private:

T*elements; //棧元素存放數(shù)組

inttop; //棧頂指針

intmaxSize;//棧最大容量public:

SeqStack(intsz=50); //構(gòu)造函數(shù)

~SeqStack(){delete[]elements;}//析構(gòu)函數(shù)2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的類定義

voidPush(constT&x);//進(jìn)棧

boolPop(T&x);

//出棧

boolgetTop(T&x);

//取棧頂內(nèi)容

boolIsEmpty()const{returntop=-1;}

boolIsFull()const{returntop=maxSize-1;}intgetSize()const{returntop+1;}//返回棧中元素個(gè)數(shù)

voidmakeEmpty(){top=-1}//清空棧的內(nèi)容};2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的函數(shù)實(shí)現(xiàn)//順序棧的構(gòu)造函數(shù)template<classT>SeqStack<T>::SeqStack(intsz):top(-1),maxSize(sz){ elements=newT[maxSize];

}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的函數(shù)實(shí)現(xiàn)//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理template<classT>voidSeqStack<T>::Push(constT&x){

if(IsFull()==true)printf(“棧滿，不能入?！?;return;//棧滿

elements[++top]=x;

//棧頂指針先加1,再進(jìn)棧}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的函數(shù)實(shí)現(xiàn)//函數(shù)退出棧頂元素并返回棧頂元素的值template<classT>boolSeqStack<T>::Pop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top--];//棧頂指針退1

returntrue;//退棧成功}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--順序棧的函數(shù)實(shí)現(xiàn)//若棧不空則函數(shù)返回該棧棧頂元素template<classT>boolSeqstack<T>::getTop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--雙棧共享一個(gè)?？臻g為了既能減少由于棧滿而引起的溢出，又能有效的利用存儲(chǔ)空間，提出一種雙棧共享一個(gè)?？臻g的策略。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--雙棧共享一個(gè)?？臻g兩個(gè)棧共享一個(gè)數(shù)組空間V[maxSize]設(shè)立棧頂指針數(shù)組t[2]和棧底指針數(shù)組b[2]t[i]和b[i]分別指示第i個(gè)棧的棧頂與棧底初始t[0]=b[0]=-1,t[1]=b[1]=maxSize滿條件：t[0]+1==t[1]//棧頂指針相遇?？諚l件：t[0]=b[0]或t[1]=b[1]//退到棧底2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--雙棧共享一個(gè)?？臻g//雙棧的插入算法boolpush(DualStack&DS,Tx,intd){if(DS.t[0]+1==DS.t[1])returnfalse;

if(d==0)DS.t[0]++;elseDS.t[1]--;DS.Vector[DS.t[d]]=x;returntrue;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--雙棧共享一個(gè)?？臻g//雙棧的刪除算法boolPop(DualStack&DS,T&x,intd){if(DS.t[d]==DS.b[d])returnfalse;x=DS.Vector[DS.t[d]];if(d==0)DS.t[0]--;elseDS.t[1]++;returntrue;}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏ｆ準(zhǔn)綏Ｊ菞５逆溄哟鎯?chǔ)表示。鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^。因此，新結(jié)點(diǎn)的插入和棧頂結(jié)點(diǎn)的刪除都在鏈表的表頭，即棧頂進(jìn)行。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５念惗xtemplate<classT>classLinkedStack:publicStack<T>{//鏈?zhǔn)綏ｎ惗xprivate: LinkNode<T>*top;

//棧頂指針public:LinkedStack():top(NULL){}

//構(gòu)造函數(shù)2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５念惗x

~LinkedStack(){makeEmpty();

}//析構(gòu)函數(shù)

voidPush(constT&x);

//進(jìn)棧

boolPop(T&x);

//退棧

boolgetTop(T&x)const;//取棧頂

boolIsEmpty()const{returntop==NULL;} intgetSize()const;//求棧中元素個(gè)數(shù)

voidmakeEmpty();

//清空棧的內(nèi)容

friendostream&operator<<(ostream&os, LinkedStack<T>&s);};2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//逐次刪去鏈?zhǔn)綏Ｖ械脑刂敝翖ｍ斨羔槥榭?。template<classT>LinkedStack<T>::makeEmpty(){

LinkNode<T>*p; while(top!=NULL) //逐個(gè)結(jié)點(diǎn)釋放

{p=top;top=top->link;

deletep;}}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//將元素值x插入到鏈?zhǔn)綏５臈ｍ?即鏈頭。template<classT>voidLinkedStack<T>::Push(constT&x){top=newLinkNode<T>(x,top);

//創(chuàng)建新結(jié)點(diǎn)

assert(top!=NULL);

//創(chuàng)建失敗退出}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//刪除棧頂結(jié)點(diǎn),返回被刪棧頂元素的值。template<classT>boolLinkedStack<T>::Pop(T&x){

if(IsTmpty()==true)returnfalse;//?？辗祷?/p>

LinkNode<T>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

//釋放結(jié)點(diǎn)

returntrue; }2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//返回棧頂元素的值template<classT>boolLinkedStack<T>::getTop(T&x)const{

if(IsEmpty()==true)returnfalse;//?？辗祷?/p>

x=top->data;returntrue;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//返回棧中元素個(gè)數(shù)template<classT>intLinkedStack<T>::getSizeconst{

LinkNode<T>*p=top;intk=0;

while(top!=NULL){top=top->link;k++;}

returnk;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//輸出棧中元素template<classT>ostream&operator<<(ostream&os,LinkedStack<T>&s){ os<<”棧中元素個(gè)數(shù)：”<<s.getSize()<<endl; LinkNode<T>*p=s.top;inti=0;

while(p!=NULL) {os<<++i<<”:”<<p->data<<endl;p=p->link;}

returnos;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列例1：一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是（C）。

A．edcbaB．decbaC．dceabD．a(chǎn)bcde例2：對(duì)于一個(gè)棧，給出輸入項(xiàng)a、b、c。如果輸入序列由a、b、c組成，試給出全部可能的輸出序列。

abcacbbacbcacba2023/8/5mayan第三章棧和隊(duì)列例1：一個(gè)棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之括號(hào)匹配觀察：每個(gè)右括號(hào)將與最近遇到的那個(gè)未匹配的左括號(hào)相匹配。

(a×(b+c)-d)(a+b))((((沒有與右括號(hào)匹配的左括號(hào)沒有與左括號(hào)匹配的右括號(hào)(2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值一個(gè)表達(dá)式由操作數(shù)（亦稱運(yùn)算對(duì)象）、操作符（亦稱運(yùn)算符）和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值表達(dá)式示例中綴表達(dá)式A+B*(C-D)-E/F后綴表達(dá)式ABCD-*+EF/-前綴表達(dá)式-+A*B-CD/EF表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開始計(jì)算。2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值應(yīng)用后綴表示計(jì)算表達(dá)式的值說明：這里只考慮雙目運(yùn)算的情形。從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)。計(jì)算例ABCD－×+EF/－2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值通過后綴表示計(jì)算表達(dá)式值的過程：順序掃描表達(dá)式的每一項(xiàng)，如果該項(xiàng)是操作數(shù)，則將其入棧；如果該項(xiàng)是操作符<op>，則連續(xù)從棧中退出兩個(gè)操作數(shù)X和Y，形成運(yùn)算指令X<op>Y，并將計(jì)算結(jié)果重新壓入棧中。當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值A(chǔ)BCD－×+EF/－步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容1置空棧空2A操作數(shù)進(jìn)棧A3B操作數(shù)進(jìn)棧AB4C操作數(shù)進(jìn)棧ABC5D操作數(shù)進(jìn)棧ABCD6－操作符D、C退棧，計(jì)算C－D，結(jié)果R1進(jìn)棧ABR17×操作符R1、B退棧，計(jì)算B×R1，結(jié)果R2進(jìn)棧AR22023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值8+操作符R2、A退棧，計(jì)算A+R2，結(jié)果R3進(jìn)棧R39E操作數(shù)進(jìn)棧R3EF10F操作數(shù)進(jìn)棧R3EF11/操作符E、F退棧，計(jì)算E/F，結(jié)果R4進(jìn)棧R3R412－操作符R3、R4退棧，計(jì)算R3－R4，結(jié)果R5進(jìn)棧R5步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容ABCD－×+EF/－2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值中綴表示→轉(zhuǎn)后綴表示先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序加上括號(hào)；再把操作符后移到右括號(hào)的后面并以就近移動(dòng)為原則；最后將所有括號(hào)消去。

例：中綴表示(A+B)*D-E/(F+A*D)+C，轉(zhuǎn)換為后綴表示(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后綴表示

AB+D*EFAD*+/-C+2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值中綴表示→轉(zhuǎn)前綴表示先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序通統(tǒng)加上括號(hào)再把操作符前移到左括號(hào)前并以就近移動(dòng)為原則最后將所有括號(hào)消去。 例：中綴表示(A+B)*D-E/(F+A*D)+C，轉(zhuǎn)換為前綴表示(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)前綴表示

+-*+ABD/E+F*ADC2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值利用棧將中綴表示轉(zhuǎn)換為后綴表示 使用棧可將表達(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。操作符優(yōu)先級(jí) 為了實(shí)現(xiàn)這種轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)。優(yōu)先級(jí)操作符1單目－，！2×，／，%3＋，－4<，<=，>，>=5==，！=6&&7||2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值各個(gè)算術(shù)操作符的優(yōu)先級(jí)isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“#”號(hào)與輸入流最后的“#”號(hào)配對(duì)時(shí)。操作符ch#(×,／,%＋,－)isp01536icp064212023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法操作符棧初始化，將結(jié)束符‘#’進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。重復(fù)執(zhí)行以下步驟，直到ch=‘#’，同時(shí)棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個(gè)字符ch。若ch是操作符，判斷ch的優(yōu)先級(jí)icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級(jí)isp：2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個(gè)字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號(hào)讀入下一個(gè)字符ch。算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值例：給定中綴表達(dá)式A+B*(C-D)-E/F，按上述算法轉(zhuǎn)換為后綴表達(dá)式。步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容輸出0‘#’

進(jìn)棧#1A操作數(shù)#A2＋操作符isp(‘#’)<icp(‘＋’)進(jìn)棧#＋A3B操作數(shù)

#＋AB4×操作符isp(‘＋’)<icp(‘×’)進(jìn)棧#＋×AB2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容輸出5(操作符isp(‘×’)<icp(‘(’)進(jìn)棧#＋×(AB6C操作數(shù)#＋×(ABC7－操作符isp(‘(’)<icp(‘－’)進(jìn)棧#＋×(－ABC8D操作數(shù)#＋×(－ABCD9)操作符isp(‘－’)>icp(‘)’)退棧#＋×(ABCD－isp(‘(’)==icp(‘)’)退棧#＋×ABCD－10－操作符isp(‘×’)>icp(‘－’)退棧#＋ABCD－×isp(‘＋’)>icp(‘－’)退棧#ABCD－×＋isp(‘#’)<icp(‘－’)進(jìn)棧#－ABCD－×＋A+B*(C-D)-E/F2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容輸出11E操作數(shù)#－ABCD－×＋E12／操作符isp(‘－’)<icp(‘/’)進(jìn)棧#－／ABCD－×＋E13F操作數(shù)#－／ABCD－×＋EF14#操作符isp(‘/’)>icp(‘#’)退棧#－ABCD－×＋EF/isp(‘－’)>icp(‘#’)退棧#ABCD－×＋EF/－A+B*(C-D)-E/F2023/8/5mayan第三章棧和隊(duì)列--棧的2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸遞歸的定義 若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸定義是遞歸的例如：求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}分解過程求值過程2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸數(shù)據(jù)結(jié)構(gòu)是遞歸的例如，單鏈表結(jié)構(gòu) 一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;

一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。f

f

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classT>

voidPrint(ListNode<T>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffff

abcde遞歸找鏈尾123452023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸問題的解法是遞歸的例如漢諾塔(TowerofHanoi)問題 問題描述： 有A,B,C三個(gè)塔座，A上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號(hào)1,2,3……n。要求將n個(gè)圓盤從A移到C，疊放順序不變，移動(dòng)過程中遵循下列原則：每次只能移一個(gè)圓盤圓盤可在三個(gè)塔座上任意移動(dòng)任何時(shí)刻，每個(gè)塔座上不能將大盤壓到小盤上2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸解決方法： 如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步： 用C柱做過渡，將A柱上的(n-1)個(gè)盤子移到B柱上： 將A柱上最后一個(gè)盤子直接移到C柱上； 用A柱做過渡，將B柱上的(n-1)個(gè)盤子移到C柱上。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸解決漢諾塔問題的算法#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復(fù)計(jì)算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過程其他情形必須借助棧實(shí)現(xiàn)非遞歸過程2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸Ackerman函數(shù)定義如下：學(xué)生課下學(xué)習(xí)部分2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸遞歸算法：unsignedakm(unsignedm,unsignedn){

if(m==0)returnn+1;//m==0

elseif(n==0)returnakm(m-1,1);//m>0,n==0 elsereturnakm(m-1,akm(m,n-1));//m>0,n>0}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸非遞歸算法：#include<iostream.h>#include”stack.h”#definemaxSize3500;unsignedakm(unsignedm,unsignedn){

structnode{unsignedvm,vn;} stack<node>st(maxSize);nodew;unsignedv; w.vm=m;w.vn=n;st.Push(w);2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸do{

while(st.GetTop().vm>0){

while(st.GetTop().vn>0){w.vn--;st.Push(w);} w=st.GetTop();st.Pop();w.vm--;w.vn=1;st.Push(w);} w=st.GetTop();st.Pop();v=w.vn++;

if(st.IsEmpty()==0) {w=st.GetTop();st.Pop();w.vm--;w.vn=v;st.Push(w);}}while(st.IsEmpty()==0);returnv;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--隊(duì)列的定義隊(duì)列（Queue）是只允許在表的一端插入，在另一端刪除的線性表。隊(duì)列又叫先進(jìn)先出（FIFO）的線性表。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--隊(duì)列的類定義template<classT>classQueue{public:Queue(){};

//構(gòu)造函數(shù)

～Queue(){};

//析構(gòu)函數(shù)voidEnQueue(T&x);//進(jìn)隊(duì)列boolDeQueue();//出隊(duì)列boolgetFront();//取隊(duì)頭boolIsEmpty();//判隊(duì)列空boolIsFull(); //判隊(duì)列滿intgetSize();//求隊(duì)列元素個(gè)數(shù)};2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列順序隊(duì)列的概念 隊(duì)列的基于數(shù)組的存儲(chǔ)表示稱為順序隊(duì)列。利用一個(gè)一維數(shù)組elements[maxSize]作為隊(duì)列元素的存儲(chǔ)結(jié)構(gòu)。設(shè)置兩個(gè)指針(下標(biāo)變量)front和rear，分別指示對(duì)頭和隊(duì)尾位置。初始化時(shí)令front=rear=0。隊(duì)尾指針rear指示了實(shí)際隊(duì)尾位置的后一位置，隊(duì)頭指針front則指示真正隊(duì)頭元素所在位置。當(dāng)front==rear，隊(duì)列為空；當(dāng)rear==maxSize，隊(duì)列滿。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列循環(huán)隊(duì)列的概念 解決假溢出的辦法之一：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊(duì)列。隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxSize==front;注意，在循環(huán)隊(duì)列中，最多只能存放maxSize-1個(gè)元素。2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的類定義template<classT>classSeqQueue{ //隊(duì)列類定義protected:intrear,front; //隊(duì)尾與隊(duì)頭指針

T*elements; //隊(duì)列存放數(shù)組

intmaxSize; //隊(duì)列最大容量2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的類定義public:

SeqQueue(intsz=10);//構(gòu)造函數(shù)

~SeqQueue(){

delete[]elements;}//析構(gòu)函數(shù)

boolEnQueue(constT&x);//新元素進(jìn)隊(duì)列

boolDeQueue();//退出隊(duì)頭元素

boolgetFront();

//取隊(duì)頭元素值

voidmakeEmpty(){front=rear=0;}//隊(duì)列做空

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的類定義 boolIsEmpty()const{returnfront==rear;} //判斷隊(duì)空

boolIsFull()const//判斷隊(duì)滿

{return((rear+1)%maxSize==front);}

intgetSize()const//隊(duì)中元素個(gè)數(shù){return(rear-front+maxSize)%maxSize;} voiddisplay()const;//輸出隊(duì)中元素

};2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的函數(shù)實(shí)現(xiàn)//構(gòu)造函數(shù)template<classT>SeqQueue<T>::SeqQueue(intsz):front(0),rear(0),maxSize(sz){elements=newT[maxSize];

}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的函數(shù)實(shí)現(xiàn)//若隊(duì)列不滿,則將x插入到該隊(duì)列隊(duì)尾,否則返回template<classT>boolSeqQueue<T>::EnQueue(constT&x){if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

rear=(rear+1)%maxSize;//尾指針加一

returntrue; }2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的函數(shù)實(shí)現(xiàn)//若隊(duì)列不空則函數(shù)退隊(duì)頭元素并返回其值template<classT>boolSeqQueue<T>::DeQueue(){intx;if(IsEmpty()==true)returnfalse;

x=elements[front];//先取隊(duì)頭

front=(front+1)%maxSize;

//再隊(duì)頭指針加一

returntrue;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的函數(shù)實(shí)現(xiàn)//若隊(duì)列不空則函數(shù)返回該隊(duì)列隊(duì)頭元素的值template<classT>boolSeqQueue<T>::getFront()const{intx;if(IsEmpty()==true)returnfalse;//隊(duì)列空

x=elements[front]; //返回隊(duì)頭元素

returntrue;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的函數(shù)實(shí)現(xiàn)//輸出隊(duì)列中的元素template<classT>voidSeqQueue<T>::display()const{ inti; if(IsEmpty()==true)return;//隊(duì)列空

cout<<"隊(duì)列中的元素為："<<endl; for(i=front;i!=rear;i=(i+1)%maxSize) cout<<elements[i]<<""; cout<<endl;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列是基于單鏈表的一種存儲(chǔ)表示。隊(duì)列的隊(duì)頭指針指向單鏈表的第一個(gè)結(jié)點(diǎn)，隊(duì)尾指針指向單鏈表的最后一個(gè)結(jié)點(diǎn)。隊(duì)空條件為front==NULL;2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的類定義#include<iostream.h>#include“LinkedList.h”#include“Queue.h”template<classT>classLinkedQueue:publicQueue<T>{

private:

LinkNode<T>*front,*rear;//隊(duì)頭、隊(duì)尾指針public: LinkedQueue():rear(NULL),front(NULL){}

~LinkedQueue(){makeEmpty();}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的類定義

boolEnQueue(constT&x);boolDeQueue(T&x);

boolgetFront(T&x)const;

voidmakeEmpty();boolIsEmpty()const

{returnfront==NULL;

}intgetSize()const;friendostream&operator<<(ostream&os,LinkedQueue<T>&Q);};

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)//置空隊(duì)列template<classT>boolLinkedQueue<T>::makeEmpty(){ LinkNode<T>*p;

while(front!=NULL){ p=front;front=front->link;deletep;}}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)template<classT>//將新元素x插入到隊(duì)列的隊(duì)尾boolLinkedQueue<T>::EnQueue(constT&x){if(front==NULL){

//創(chuàng)建第一個(gè)結(jié)點(diǎn)

front=rear=newLinkNode<T>(x);if(front==NULL)returnfalse;} //分配失敗

else{ //隊(duì)列不空,插入

rear->link=newLinkNode<T>(x);if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)//如果隊(duì)列不空，將隊(duì)頭結(jié)點(diǎn)從鏈?zhǔn)疥?duì)列中刪去template<classT>boolLinkedQueue<T>::DeQueue(T&x){

if(IsEmpty()==true)returnfalse;//判隊(duì)空

LinkNode<T>*p=front; x=front->data;front=front->link;

deletep;

returntrue; }

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)//若隊(duì)列不空，則函數(shù)返回隊(duì)頭元素的值template<classT>boolLinkedQueue<T>::GetFront(T&x){ if(IsEmpty()==true)returnfalse; x=front->data; returntrue;}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)//求隊(duì)列元素個(gè)數(shù)template<classT>intLinkedQueue<T>::getSize()const{ LinkNode<T>*p=front;intk=0;

while(p!=NULL){p=p->link;k++;}

returnk;}

2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列的函數(shù)實(shí)現(xiàn)//輸出隊(duì)列中的元素template<classT>ostream&operator<<(ostream&os,LinkedQueue<T>&Q){ os<<”隊(duì)列中元素個(gè)數(shù)有”<<Q.getSize()<<endl; LinkNode<T>*p=Q.front;inti=0;

while(p!=NULL){ os<<++i<<”:”<<p->data<<endl; p=p->link;}

returnos;}2023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列

--隊(duì)列的應(yīng)用之打印楊輝三角形將二項(xiàng)式展開，其系數(shù)構(gòu)成楊輝三角形。2023/8/5mayan第三章棧和隊(duì)列

2023/8/16mayan第三章棧和隊(duì)列

--隊(duì)列的應(yīng)用之打印楊輝三角形2023/8/5mayan第三章棧和隊(duì)列

2023/8/16mayan第三章棧和隊(duì)列

--隊(duì)列的應(yīng)用之打印楊輝三角形#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGVI(intn){ Queueq(n+2);

//隊(duì)列初始化

inti=1,j,s=k=0,t,u; q.EnQueue(i);q.EnQueue(i);2023/8/5mayan第三章棧和隊(duì)列

2023/8/16mayan第三章棧和隊(duì)列

--隊(duì)列的應(yīng)用之打印楊輝三角形for(int

i=1;i<=n;i++){//逐行計(jì)算

cout<<endl; q.EnQueue(k);

for(intj=1;j<=i+2;j++){//下一行

q.DeQueue(t); u=s+t;q.EnQueue(u); s=t;

if(j!=i+2)cout<<s<<'';//第j+2個(gè)是0

}}}2023/8/5mayan第三章棧和隊(duì)列

2023/8/16mayan第三章棧和隊(duì)列--優(yōu)先級(jí)隊(duì)列的概念每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素，這種隊(duì)列就是優(yōu)先級(jí)隊(duì)列（PriorityQueue）。最小優(yōu)先級(jí)隊(duì)列（minPriorityQueue）：數(shù)字越小優(yōu)先權(quán)越高最大優(yōu)先級(jí)隊(duì)列（maxPriorityQueue）：數(shù)字越大優(yōu)先權(quán)越高優(yōu)先權(quán)相同時(shí)先來先服務(wù)。任務(wù)編號(hào)12345優(yōu)先權(quán)200403010執(zhí)行順序315422023/8/5mayan第三章棧和隊(duì)列-2023/8/16mayan第三章棧和隊(duì)列

--優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示與實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的數(shù)組存儲(chǔ)表示#include<assert.h>#include<iostream.h>#include<stdlib.h>template<classT>classPQueue{private: