數(shù)據(jù)結(jié)構(gòu)院(系):信息工程學(xué)院教師:余云3.1

棧3.2棧的應(yīng)用3.3棧與遞歸3.4隊(duì)列3.5隊(duì)列的應(yīng)用教學(xué)內(nèi)容第3章棧和隊(duì)列掌握棧和隊(duì)列的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用熟練掌握棧的兩種存儲結(jié)構(gòu)的基本操作實(shí)現(xiàn)算法，特別應(yīng)注意棧滿和棧空的條件熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的條件理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程教學(xué)目標(biāo)棧（Stack）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式3.1棧1.定義用順序?；蜴湕４鎯?，但以順序棧更常見3.存儲結(jié)構(gòu)與線性表相同，仍為一對一關(guān)系2.邏輯結(jié)構(gòu)只能在表的一端（棧頂）進(jìn)行插入和刪除運(yùn)算的線性表只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則4.運(yùn)算規(guī)則關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５牟煌煌静僮饔腥霔?、出棧、讀棧頂元素值、建棧、判斷棧滿、?？盏?.實(shí)現(xiàn)方式棧是一種特殊的線性表，它只能在表的一端（棧頂）進(jìn)行插入和刪除運(yùn)算棧與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同“進(jìn)”＝壓入=PUSH（)“出”＝彈出=POP()一般線性表

邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表運(yùn)算規(guī)則：隨機(jī)、順序存取棧邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：后進(jìn)先出棧與一般線性表的區(qū)別“進(jìn)”＝壓入=PUSH（)“出”＝彈出=POP()a1a2……an順序棧Sai……表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預(yù)設(shè)棧頂指針top！低地址高地址v[i]a1a2

aian

……順序表V[n]

……an+1順序棧與順序表

順序棧的表示空棧base==top是?？諛?biāo)志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的棧頂元素之上的下標(biāo)地址棧滿時的處理方法：1、報錯,返回操作系統(tǒng)。2、分配更大的空間，作為棧的存儲空間,將原棧的內(nèi)容移入新棧。#defineMAXSIZE100typedefstruct{

SElemType*base; SElemType*top; intstacksize;}SqStack;順序棧的表示構(gòu)造一個空棧步驟：(1)分配空間并檢查空間是否分配失敗，若失敗則返回錯誤順序棧初始化basestacksizetops(2)設(shè)置棧底和棧頂指針S.top=S.base;(3)設(shè)置棧大小StatusInitStack(SqStack&S){

S.base=newSElemType[MAXSIZE]； if(!S.base) returnOVERFLOW;

S.top=S.base; S.stackSize=MAXSIZE; returnOK;}順序棧初始化判斷順序棧是否為空boolStackEmpty(SqStackS){ if(S.top==S.base)returntrue;elsereturnfalse;}basetop3120求順序棧的長度intStackLength(SqStackS){ returnS.top–S.base;}basetopABStatusClearStack(SqStackS){ if(S.base)S.top=S.base; returnOK;}清空順序棧basetop3120StatusDestroyStack(SqStack&S){ if(S.base) { deleteS.base;

S.stacksize=0; S.base=S.top=NULL; }returnOK;}銷毀順序棧(1)判斷是否棧滿，若滿則出錯(2)元素e壓入棧頂(3)棧頂指針加1順序棧進(jìn)棧StatusPush(SqStack&S,SElemTypee){ if(S.top-S.base==S.stacksize)//棧滿returnERROR;

*S.top++=e; returnOK;}*S.top=e;S.top++;ABCtopbase(1)判斷是否棧空，若空則出錯(2)獲取棧頂元素e(3)棧頂指針減1順序棧出棧StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//?？誶eturnERROR;

e＝*--S.top; returnOK;}--S.top;e=*S.top;ABCtopbase判斷是否空棧，若空則返回錯誤否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //?？?/p>

e=*(S.top–1); returnOK;}e=*(S.top--);???ABCtopbase435612中到了12順序不能實(shí)現(xiàn)；135426可以實(shí)現(xiàn)。1.如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？練習(xí)練習(xí)Ａ．iＢ．n-iＣ．n-i+1Ｄ．不確定Ｃ2.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為練習(xí)Ａ．top不變Ｂ．top=0Ｃ．top++

Ｄ．top--D3.在一個具有n個單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理時，top的變化為b[0]t[0]t[1]b[1]0m-1V雙棧共享一個?？臻g優(yōu)點(diǎn)：互相調(diào)劑，靈活性強(qiáng)，減少溢出機(jī)會鏈棧的表示運(yùn)算是受限的單鏈表，只能在鏈表頭部進(jìn)行操作，故沒有必要附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStack;LinkStackS;datanext棧頂棧底∧S鏈棧的初始化voidInitStack(LinkStack&S){

S=NULL;}∧S判斷鏈棧是否為空StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturn

FALSE;

}

鏈棧進(jìn)棧StatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結(jié)點(diǎn)p

if(!p)exit(OVERFLOW);

p->data=e;p->next=S;S=p;

returnOK;

}ppep∧SeS鏈棧出棧StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}e=‘A’∧SApS∧S取鏈棧棧頂元素SElemTypeGetTop(LinkStackS){

if(S==NULL)

exit(1)；

elsereturnS–>data;}3.2棧的應(yīng)用例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）用棧暫存低位值例2：括號匹配的檢驗(yàn)用棧暫存左括號例3：表達(dá)式求值用棧暫存運(yùn)算符例4：迷宮求解用棧實(shí)現(xiàn)遞歸調(diào)用簡化了程序設(shè)計(jì)的問題表達(dá)式求值算術(shù)四則運(yùn)算規(guī)則(1)先乘除,后加減(2)從左算到右(3)先括號內(nèi),后括號外表達(dá)式常數(shù)標(biāo)識符操作數(shù)(operand)運(yùn)算符(operator)界限符(delimiter)算術(shù)邏輯關(guān)系括號結(jié)束符【算法思想】表達(dá)式求值——（1）初始化OPTR棧和OPND棧，將“#”壓入OPTR（2）依次讀入字符ch，循環(huán)執(zhí)行（3）至（5）（3）取出OPTR的棧頂元素，當(dāng)OPTR的棧頂元素和ch均為“#”時，表達(dá)式求值完畢，OPND棧頂元素為表達(dá)式的值設(shè)定兩棧：OPND-----操作數(shù)或運(yùn)算結(jié)果OPTR------運(yùn)算符（4）if(ch是操作數(shù))則ch進(jìn)OPND，讀入下一字符ch（5）else比較OPTR棧頂元素和ch的優(yōu)先級case‘<’:運(yùn)算符ch進(jìn)OPTR，讀入下一字符chcase‘=’:脫括號（彈出左括號），讀入下一字符chcase‘<’:棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)OPNDOperandTypeEvaluateExpression(){InitStack(OPND);ch=getchar();while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch,OP)){Push(OPND,ch);ch=getchar();}//ch不是運(yùn)算符則進(jìn)棧elseswitch(Precede(GetTop(OPTR),ch)){//比較優(yōu)先權(quán)case'<'://當(dāng)前字符ch壓入OPTR棧，讀入下一字符chPush(OPTR,ch);ch=getchar();break;case'>'://彈出OPTR棧頂?shù)倪\(yùn)算符運(yùn)算，并將運(yùn)算結(jié)果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;case'='://脫括號并接收下一字符Pop(OPTR,x);ch=getchar();break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpressionOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3.3棧與遞歸

遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己,則稱這個過程是遞歸的過程。以下三種情況常常用到遞歸方法遞歸定義的數(shù)學(xué)函數(shù)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)可遞歸求解的問題1.遞歸定義的數(shù)學(xué)函數(shù):階乘函數(shù):

2階Fibonaci數(shù)列:

樹

2.具有遞歸特性的數(shù)據(jù)結(jié)構(gòu):RootLchildRchild廣義表

A=(a,A)3.可遞歸求解的問題:迷宮問題Hanoi塔問題

分治法：對于一個較為復(fù)雜的問題，能夠分解成幾個相對簡單的且解法相同或類似的子問題來求解1、能將一個問題轉(zhuǎn)變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規(guī)律的2、可以通過上述轉(zhuǎn)化而使問題簡化3、必須有一個明確的遞歸出口，或稱遞歸的邊界求解遞歸的方法——分治法必備的三個條件分治法求解遞歸問題算法的一般形式：

voidp(參數(shù)表){if（遞歸結(jié)束條件）可直接求解步驟；-----基本項(xiàng)elsep（較小的參數(shù)）；------歸納項(xiàng)}longFact(longn){if(n==0)return1;//基本項(xiàng)

elsereturnn*Fact(n-1);//歸納項(xiàng)}返回2參數(shù)2計(jì)算2*Fact(1)返回1參數(shù)1計(jì)算1*Fact(0)返回1參數(shù)0直接定值=1參數(shù)傳遞遞歸調(diào)用結(jié)果返回回歸求值if(n==0)return1;elsereturnn*Fact(n-1);求解階乘n!的過程主程序main:Fact(4)返回24參數(shù)4計(jì)算4*Fact(3)返回6參數(shù)3計(jì)算3*Fact(2)設(shè)有一個遞歸算法如下:intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1}則計(jì)算X(X(8))時需要計(jì)算X函數(shù)

次.D練習(xí)A.8 B.9C.16 D.18在印度圣廟里，一塊黃銅板上插著三根寶石針。主神梵天在創(chuàng)造世界時，在其中一根針上穿好了由大到小的64片金片，這就是漢諾塔。僧侶不停移動這些金片，一次只移動一片，小片必在大片上面。當(dāng)所有的金片都移到另外一個針上時，世界將會滅亡。漢諾塔規(guī)則:(1)每次只能移動一個圓盤(2)圓盤可以插在A,B和C中的任一塔座上(3)任何時刻不可將較大圓盤壓在較小圓盤之上Hanoi塔問題ABCHanoi塔問題

n=1，則直接從A移到C。否則(1)用C柱做過渡，將A的(n-1)個移到B(2)將A最后一個直接移到C(3)用A做過渡，將B的(n-1)個移到C#include<iostream.h>intc=0;voidmove(charx,intn,charz){cout<<++c<<","<<n<<","<<x<<","<<z<<endl;}voidHanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);else{Hanoi(n-1,A,C,B);move(A,n,C);Hanoi(n-1,B,A,C);}}voidmain(){Hanoi(3,'a','b','c');}跟蹤程序，給出下列程序的運(yùn)行結(jié)果，以深刻地理解遞歸的調(diào)用和返回過程3,a,b,c遞歸調(diào)用樹2,a,c,b2,b,a,ca-3->c空間效率時間效率O(2n)與遞歸樹的結(jié)點(diǎn)數(shù)成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析1234f(1)=1f(1)+1+f(1)=3f(2)+1+f(2)=7f(3)+1+f(3)=15f(n)=2f(n-1)+1f(n-1)=2f(n-2)+1f(n-2)=2f(n-3)+1......f(3)=2f(2)+1f(2)=2f(1)+120f(n)=21f(n-1)+2021f(n-1)=22f(n-2)+2122f(n-2)=23f(n-3)+22......2n-3f(3)=2n-2f(2)+2n-32n-2f(2)=2n-1f(1)+2n-2f(n)=20+21+…+2n-2+2n-1f(1)=2n-1遞歸算法的效率分析64片金片移動次數(shù)：264-1=18446744073709551615

假如每秒鐘一次，共需多長時間呢？一年大約有31536926秒，移完這些金片需要５８００多億年世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅……!優(yōu)點(diǎn)：結(jié)構(gòu)清晰，程序易讀缺點(diǎn)：每次調(diào)用要生成工作記錄，保存狀態(tài)信息，入棧；返回時要出棧，恢復(fù)狀態(tài)信息。時間開銷大。遞歸的優(yōu)缺點(diǎn)遞歸非遞歸

隊(duì)列是一種先進(jìn)先出(FIFO)的線性表.它只允許在表的一端進(jìn)行插入,而在另一端刪除元素a1a2a3an...入隊(duì)列隊(duì)頭隊(duì)尾3.4隊(duì)列),,(21naaaq…=一、隊(duì)列定義a1a2a3an...隊(duì)頭隊(duì)尾出隊(duì)列),,(21naaaq…=設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過S，一個元素出棧后即進(jìn)入Q，若6個元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。（A）2（B）3（C）4（D）6練習(xí)B

(1)

InitQueue(&Q)//構(gòu)造空隊(duì)列(2)DestroyQueue(&Q)//銷毀隊(duì)列(3)ClearQueue(&S)//清空隊(duì)列(4)QueueEmpty(S)//判空.空—TRUE(5)QueueLength(Q)//取隊(duì)列長度(6)GetHead(Q,&e)//取隊(duì)頭元素,(7)EnQueue(&Q,e)//入隊(duì)列(8)DeQueue(&Q,&e)//出隊(duì)列隊(duì)列基本操作#defineM100//最大隊(duì)列長度typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間in