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

2023/2/1mayan第三章棧和隊(duì)列棧棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng)用優(yōu)先級(jí)隊(duì)列定義：棧限定只能在表的一端進(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ī)制可通過(guò)棧來(lái)實(shí)現(xiàn)計(jì)算機(jī)正是利用棧來(lái)實(shí)現(xiàn)函數(shù)的調(diào)用和返回的n=3階乘函數(shù)fact(n)的執(zhí)行過(guò)程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)用中棧的變化將十進(jìn)制整數(shù)轉(zhuǎn)換成二至九之間的任一進(jìn)制數(shù)輸出

將一個(gè)十進(jìn)制數(shù)4327轉(zhuǎn)換成八進(jìn)制數(shù)(10347)8：abc32111213121YXZ2023/2/1mayan第三章棧和隊(duì)列--棧的定義

棧和隊(duì)列稱為運(yùn)算受限的線性表。棧（stack）是指只允許在表的末端進(jìn)行插入和刪除的線性表。棧又叫做后進(jìn)先出（LIFO）的線性表。棧的基本概念棧是一種“特殊”的線性表，這種線性表上的插入和刪除運(yùn)算限定在表的某一端進(jìn)行。棧頂：允許進(jìn)行插入和刪除的這一端。棧底：反之為棧底。棧頂元素：處于棧頂位置的數(shù)據(jù)元素稱為～。棧頂元素的位置由棧頂指針變量記錄；空棧:當(dāng)棧中不含任何數(shù)據(jù)元素時(shí)稱為～2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--順序棧的類定義template<classT>classSeqStack{//順序棧類定義private:

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

inttop; //棧頂指針

intmaxSize;//棧最大容量public:

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

~SeqStack(){delete[]elements;}//析構(gòu)函數(shù)2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--順序棧的函數(shù)實(shí)現(xiàn)//順序棧的構(gòu)造函數(shù)template<classT>SeqStack<T>::SeqStack(intsz):top(-1),maxSize(sz){ elements=newT[maxSize];

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

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

returntrue;//退棧成功}

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

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;}2023/2/1mayan第三章棧和隊(duì)列--雙棧共享一個(gè)?？臻g為了既能減少由于棧滿而引起的溢出，又能有效的利用存儲(chǔ)空間，提出一種雙棧共享一個(gè)?？臻g的策略。2023/2/1mayan第三章棧和隊(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]//棧頂指針相遇棧空條件：t[0]=b[0]或t[1]=b[1]//退到棧底2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--鏈?zhǔn)綏ｆ準(zhǔn)綏Ｊ菞５逆溄哟鎯?chǔ)表示。鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^。因此，新結(jié)點(diǎn)的插入和棧頂結(jié)點(diǎn)的刪除都在鏈表的表頭，即棧頂進(jìn)行。2023/2/1mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５念惗xtemplate<classT>classLinkedStack:publicStack<T>{//鏈?zhǔn)綏ｎ惗xprivate: LinkNode<T>*top;

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

//構(gòu)造函數(shù)2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--鏈?zhǔn)綏５暮瘮?shù)實(shí)現(xiàn)//返回棧頂元素的值template<classT>boolLinkedStack<T>::getTop(T&x)const{

if(IsEmpty()==true)returnfalse;//棧空返回

x=top->data;returntrue;}2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之括號(hào)匹配觀察：每個(gè)右括號(hào)將與最近遇到的那個(gè)未匹配的左括號(hào)相匹配。

(a×(b+c)-d)(a+b))((((沒(méi)有與右括號(hào)匹配的左括號(hào)沒(méi)有與左括號(hào)匹配的右括號(hào)(2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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)開(kāi)始計(jì)算。2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值應(yīng)用后綴表示計(jì)算表達(dá)式的值說(shuō)明：這里只考慮雙目運(yùn)算的情形。從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)。計(jì)算例ABCD－×+EF/－2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值通過(guò)后綴表示計(jì)算表達(dá)式值的過(guò)程：順序掃描表達(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/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之表達(dá)式求值A(chǔ)BCD－×+EF/－步掃描項(xiàng)項(xiàng)類型動(dòng)作棧中內(nèi)容1置空?？?A操作數(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸遞歸的定義 若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱這個(gè)過(guò)程是遞歸的過(guò)程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸定義是遞歸的例如：求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}分解過(guò)程求值過(guò)程2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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);}fffffabcde遞歸找鏈尾123452023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸問(wèn)題的解法是遞歸的例如漢諾塔(TowerofHanoi)問(wèn)題 問(wèn)題描述： 有A,B,C三個(gè)塔座，A上套有n個(gè)直徑不同的圓盤(pán)，按直徑從小到大疊放，形如寶塔,編號(hào)1,2,3……n。要求將n個(gè)圓盤(pán)從A移到C，疊放順序不變，移動(dòng)過(guò)程中遵循下列原則：每次只能移一個(gè)圓盤(pán)圓盤(pán)可在三個(gè)塔座上任意移動(dòng)任何時(shí)刻，每個(gè)塔座上不能將大盤(pán)壓到小盤(pán)上2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸解決方法： 如果n=1，則將這一個(gè)盤(pán)子直接從A柱移到C柱上。否則，執(zhí)行以下三步： 用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤(pán)子移到B柱上： 將A柱上最后一個(gè)盤(pán)子直接移到C柱上； 用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤(pán)子移到C柱上。2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸解決漢諾塔問(wèn)題的算法#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/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程2023/2/1mayan第三章棧和隊(duì)列--棧的應(yīng)用之棧與遞歸Ackerman函數(shù)定義如下：學(xué)生課下學(xué)習(xí)部分2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--隊(duì)列的定義隊(duì)列（Queue）是只允許在表的一端插入，在另一端刪除的線性表。隊(duì)列又叫先進(jìn)先出（FIFO）的線性表。2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;2023/2/1mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxSize==front;注意，在循環(huán)隊(duì)列中，最多只能存放maxSize-1個(gè)元素。2023/2/1mayan第三章棧和隊(duì)列--循環(huán)隊(duì)列的類定義template<classT>classSeqQueue{ //隊(duì)列類定義protected:intrear,front; //隊(duì)尾與隊(duì)頭指針

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

intmaxSize; //隊(duì)列最大容量2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列--鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列是基于單鏈表的一種存儲(chǔ)表示。隊(duì)列的隊(duì)頭指針指向單鏈表的第一個(gè)結(jié)點(diǎn)，隊(duì)尾指針指向單鏈表的最后一個(gè)結(jié)點(diǎn)。隊(duì)空條件為front==NULL;2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(duì)列

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

--隊(duì)列的應(yīng)用之打印楊輝三角形2023/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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/2/1mayan第三章棧和隊(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í)先來(lái)先服務(wù)。任務(wù)編號(hào)12345優(yōu)先權(quán)200403010執(zhí)行順序315422023/2/1mayan第三章棧和隊(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:

T

*pqelements;

//存放數(shù)組

intco