數(shù)據(jù)結構-棧和隊列-課件

第三章棧和隊列1ppt課件第三章棧和隊列本章學習兩種特殊的線性數(shù)據(jù)結構，它們特殊在定義的操作不同，即插入和刪除操作只能在線性表的兩端進行。

只能在一端進行的-----棧

分別在兩端進行的-----隊列2ppt課件重點

本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用。知識點

順序棧、鏈棧、循環(huán)隊列、鏈隊列

3ppt課件１.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的，那么使用時候的次序應是什么樣的？２.在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？

4ppt課件

棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結構．

棧必須按“后進先出”的規(guī)則進行操作，而隊列必須按“先進先出”的規(guī)則進行操作。

和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構。

5ppt課件

插入刪除

線性表：Insert(L,i,x)

Delete(L,i)

(1≤i≤n+1)

(1≤i≤n)

棧：Insert(L,n+1,x)

Delete(L,n)

隊列：Insert(L,n+1,x)

Delete(L,1)6ppt課件第三章棧和隊列

3.1棧1、棧（stack)：是一種特殊的線性表（數(shù)據(jù)元素之間的關系是線性關系），其插入、刪除只能在表的一端進行，另一端固定不動。棧頂（top)：插入、刪除的一端；

棧底（bottom)：固定不動的一端；

入棧（push)：又稱壓入，即插入一個元素；出棧（pop)：又稱彈出，即刪除一個元素；一、抽象數(shù)據(jù)類型棧的定義7ppt課件2、說明：設（a1,a2,a3,…,an）是一個棧

（a1,a2,...,ai-1,ai,ai+1,…,an）棧底棧頂進棧出棧1）表尾稱為棧頂，表頭稱為棧底，即a1為棧底元素，an為棧頂元素;

2）在表尾插入元素的操作稱進棧操作，在表頭刪除元素的操作稱為出棧操作;

3）元素按a1,a2,a3,…,an的次序進棧,第一個進棧的元素一定在棧底，最后一個進棧的元素一定在棧頂,第一個出棧的元素為棧頂元素；8ppt課件棧的示意圖棧特點：由于限制了插入刪除只能在一端進行，那么元素的操作順序有“先進后出”或“后進先出”的特點(LastInFirstout-LIFOFirstInLastout---FILO)第一個進棧的元素在棧底，最后一個進棧的元素在棧頂，第一個出棧的元素為棧頂元素，最后一個出棧的元素為棧底元素9ppt課件課堂練習假設有A，B,C,D四個元素；它們?nèi)霔４涡驗锳一＞B一＞C一＞D出棧次序任意，請問不可能得到下面哪些出棧序列？(1)ABCD

(2)DBCA

(3)CDBA(4)CBAD

(5)ACBD

(6)DBAC(7)ADCB

(8)CABD

10ppt課件3、棧的基本操作1）

初始化操作InitStack(&S)

功能：構造一個空棧S；

2）銷毀棧操作DestroyStack(&S)

功能：銷毀一個已存在的棧;

3）置空棧操作ClearStack(&S)

功能：將棧S置為空棧;

4）判空棧操作StackEmpty(S)

功能：若棧為空棧，返回TRUE，否則FALSE

5）取長度操作StackLength(S)

功能：返回棧S的元素個數(shù)

11ppt課件

6）取棧頂元素操作GetTop(S,&e)

功能：取棧頂元素，并用e返回;7）進棧操作Push(&S,e)

功能：元素e進棧;8）退棧操作Pop(&S,&e)

功能：棧頂元素退棧，并用e返回;7）棧遍歷StackTraverse(S)

功能：從棧底到棧頂依次調(diào)用函數(shù)visit().12ppt課件4、棧的ADT描述棧的抽象數(shù)據(jù)類型定義為：ADTStack{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,

i=1,2,...,n,n≥0}

數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,

i=2,...,n}

約定an端為棧頂,a1端為棧底?；静僮鳎?/p>

…….

}ADTStack

13ppt課件二棧的存儲表示和操作的實現(xiàn)和線性表類似，棧也有兩種存儲表示，其順序存儲結構簡稱為順序棧。

和順序表類似，對順序棧也需要事先為它分配一個可以容納最多元素的存儲空間。14ppt課件順序存儲方式：同一般線性表的順序存儲結構完全相同。是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個稱為棧頂指針的變量指示。15ppt課件實際是棧中元素的個數(shù)順序棧類型的定義//結構定義：

typedefstruct{

ElemType*base;//存儲空間基址

inttop;

//棧頂指針

intstacksize;

//允許的最大存儲空間

}Stack;

棧頂指針總是指在棧頂元素的后面一個位置上16ppt課件top=0123450?？誸op123450進棧Atop出棧棧滿BCDEF設數(shù)組維數(shù)為stacksizetop=0,?？?，此時出棧，則下溢（underflow)top=stacksize,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptop17ppt課件特點：簡單、方便，但易產(chǎn)生溢出。上溢（Overflow)棧已經(jīng)滿，又要壓入元素；下溢（Underflow)棧已經(jīng)空，還要彈出元素；注：上溢是一種錯誤，使問題的處理無法進行下去；而下溢一般認為是一種結束條件，即問題處理結束。18ppt課件#defineSTACK_INIT_SIZE100//棧存儲空間的初始分配量#defineSTACKINCREMENT10//棧存儲空間的分配增量

typedefstruct{

SElemType*base;//?？臻g基址稱為棧底指針，指向棧底位置

SElemType*top//棧頂指針,約定棧頂指針指向棧頂元素的//下（后面）一個位置；

intstacksize;//當前分配的?？臻g大小//（以sizeof(SElemType)為單位）

}SqStack;//SqStack:：結構類型名順序棧的存儲表示19ppt課件

nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZE初始化操作圖示順序棧基本操作的算法

1）初始化操作InitStack_Sq(SqStack&S)

參數(shù)：S是存放棧的結構變量；功能：建一個空棧S；20ppt課件StatusInitStack_Sq(SqStack&S){

//構造一個空棧S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//為順序棧動態(tài)分配存儲空間

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}//InitStack_Sq21ppt課件StatusDetroyStack_Sq(SqStack&S){

If(!S.base)returnERROR;//若棧未建立（尚未分配?？臻g）

free(S.base);//回收?？臻g

S.base=S.top=null;

S.stacksize=0;

returnOK;}//DetroyStack_Sq2）銷毀棧操作DestroyStack_Sq(SqStack&S)

功能：銷毀一個已存在的棧;22ppt課件S.top=nullS.stacksizeS.base=null0

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE銷毀前銷毀后銷毀棧操作圖示23ppt課件3）置空棧操作ClearStack_Sq(SqStack&S)

功能：將棧S置為空棧算法

StatusClearStack_Sq(SqStack&S){

If(!S.base)returnERROR;//若棧未建立（尚未分

//配棧空間）

S.top=S.base;

returnOK;}//ClearStack_Sq24ppt課件

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE

nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a2a1置空棧操作圖示S.base=S.top表明棧為空置空前置空后25ppt課件StatusGetTop_Sq(SqStackS,SelemType&e){

//若棧不空，則用e返回S的棧頂元素，并返回//OK；否則返回ERROR

if(S.top==S.base)returnERROR;//若棧為空

e=*(S.top-1);

returnOK;

}//GetTop_Sq4）

取棧頂元素操作GetTop_Sq(SqStackS,SElemType&e)

功能：取棧頂元素，并用e返回;26ppt課件

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEean

取棧頂元素操作圖示27ppt課件5）進棧操作Push(SqStack&S,SElemTypee)

功能：元素e進棧;

進棧操作主要步驟：1）S是否已滿，若棧滿，重新分配存儲空間；2）將元素e寫入棧頂；3）修改棧頂指針，使棧頂指針指向棧頂元素的下（后面）一個位置；28ppt課件

nn-1i-1i-20n+1nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEeanaiai-1a1anaiai-1a1S.topS.stacksizeS.baseSTACK_INIT_SIZE

e進棧前

e進棧后進棧操作圖示29ppt課件StatusPush(SqStack&S,SElemTypee){

//將元素e插入棧成為新的棧頂元素,要考慮上溢情況

if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;//元素e插入棧頂，修改棧頂指針

returnOK;}//Push進棧操作算法：30ppt課件StatusPop(SqStack&S,SElemType&e){

//若棧不空，則刪除S的棧頂元素，用e返回其值并返回OK

//否則返回ERROR

if(S.top==S.base)returnERROR;//?？眨祷谽RROR

e=*--S.top;//刪除棧頂元素，用e返回其值，并修

//改棧頂指針

returnOK;

}//Pop

6）出棧操作Pop(SqStack&S,SElemType&e)

功能：棧頂元素退棧，并用e返回;

31ppt課件S.topS.stacksizeS.base

nn-1i-1i-20anaiai-1a1STACK_INIT_SIZE出棧操作前nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a1出棧操作后ane出棧操作圖示32ppt課件鏈棧鏈棧即為棧的鏈式存儲結構。鏈棧的結點結構和單鏈表中的結點結構相同。由于棧只在棧頂作插入和刪除操作，因此鏈棧中不需要頭結點，但是鏈棧中指針的方向是從棧頂指向棧底的，這正好和單鏈表是相反的。

33ppt課件鏈棧中結點的定義：鏈棧結構定義：typedefstructLNode{ElemTypedata;structLNode*next;}*SLink;typedefstruct{SLinktop;//棧頂指針

intlength;//棧中元素個數(shù)}LStack;34ppt課件鏈棧的基本操作和順序棧操作基本相同，只需修改兩處：１．初始化時不需要maxsize的參數(shù)２．在進行入棧操作時不需要顧忌棧的空間是否已經(jīng)被填滿。

35ppt課件voidInitStack(LStack&S)

{

//構造一個空棧S

S.top=NULL;

//設棧頂指針的初值為空

S.length=0;

//空棧中元素個數(shù)為0

}//InitStack

36ppt課件voidPush(LStack&S,ElemTypee)

{

//在棧頂之上插入元素e為新的棧頂元素

p=(LNode*)malloc(sizeof(LNode);

//建新的結點

if(!p)exit(1);

//存儲分配失敗

p->data=e;

p->next=S.top;

//鏈接到原來的棧頂

S.top=p;

//移動棧頂指針

++S.length;

//棧的長度增1

}//Push

^…...棧底toptopxp37ppt課件boolPop(LStack&S,ElemType&e)

{

//若棧不空，則刪除S的棧頂元素，用e返回其值，

//并返回TRUE；否則返回FALSE

if(!S.top)

returnFALSE;

else

{

e=S.top->data;

//返回棧頂元素

q=S.top;

S.top=S.top->next;

//修改棧頂指針

--S.length;

//棧的長度減1

deleteq;

//釋放被刪除的結點空間

returnTRUE;

}

}//Poptop^…...棧底topq38ppt課件

小結

1.棧是限定僅能在表尾一端進行插入、刪除操作的線性表；2.棧的元素具有后進先出的特點；3.棧頂元素的位置由一個稱為棧頂指針的變量表示，進棧、出棧操作要修改棧頂指針；39ppt課件§3.2棧的應用舉例

NNdiv8Nmod8134816841682102125202輸出順序計算順序１．數(shù)制轉(zhuǎn)換十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：

N=(Ndivd)×d+Nmodd

(其中：div為整除運算，mod為求余運算)

例如：(1348)10=(2504)8

40ppt課件由上述求解過程可以看出，在計算過程中是從低位到高位順序產(chǎn)生八進制數(shù)的各個數(shù)位，而顯示時按照我們的習慣是高位在前，低位在后，即按從高位到低位的順序輸出,即后計算出的（高）位數(shù)先輸出，具有后進先出的特點，因此可將計算過程中得到的八進制數(shù)順序進棧，出棧序列打印輸出的就是對應的八進制數(shù)。41ppt課件3）算法voidconversion(){//對于輸入的任意一個非負十//進制整數(shù)，打印輸出與其等值的八進制數(shù)

InitStack(S);//建空棧

scanf(“%d”,N);//輸入一個非負十進制整數(shù)

while(N){//N不等于零，循環(huán)

Push(S,N%8);//N/8第一個余數(shù)進棧

N=N/8};//整除運算while(!StackEmpty){

//輸出存放在棧中的八進制數(shù)。

Pop(S,e);

Printf(“%d”,e);}}//conversion42ppt課件2表達式求值1）表達式的構成操作數(shù)+運算符+界符（如括號）2）表達式的求值：例5+6(1+2)-4按照四則運算法則，上述表達式的計算過程為：5+6(1+2)-4=5+63-4=5+18-4=23-4=19

表達式中運算符的運算順序為：+，，+，-如何確定運算符的運算順序？43ppt課件3）算符優(yōu)先關系表表達式中任何相鄰運算符1、2的優(yōu)先關系有：

1<2：1的優(yōu)先級低于2

1=2：1的優(yōu)先級等于2

1>2：1的優(yōu)先級高于2

由四則運算法則，可得到如下的算符優(yōu)先關系表：44ppt課件+

θ2θ1-*/()#+-*/()#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=算符間的優(yōu)先關系表注：

θ1

θ2是相鄰算符，θ1在左θ2在右45ppt課件4)

算符優(yōu)先算法我們再來分析一下表達式5+4(1+2)-6

計算過程：

從左向右掃描表達式：遇操作數(shù)——保存；遇運算符號j——與前面的剛掃描過的運算符i比較若i<j則保存j，（因此已保存的運算符的優(yōu)先關系為1<2<3<4。。

）

若i>j

則說明i是已掃描的運算符中優(yōu)先級最高者，可進行運算；

若i=j則i為（，j為），說明括號內(nèi)的式子已計算完，需要消去括號；5+4(1+2)-6后面也許有優(yōu)先級更大的算符46ppt課件算法思想：

(1)設置兩個棧：運算符棧（OPTR)和操作數(shù)棧（OPND)(2)設置數(shù)據(jù)棧為空棧，表達式起始符“#”為算符棧的棧底元素。(3)自左向右，依次掃描表達式中的基本符號，若掃描的基本符號為操作數(shù)，則將操作數(shù)入OPND棧。(4)若基本符號為運算符，則和OPTR棧頂元素的優(yōu)先級比較（棧頂元素為C1,讀到的算符為C2）：（a）c1<c2，c2進棧，繼續(xù)掃描后續(xù)符號。（b）c1=c2，即”(“=“)”,括號內(nèi)的運算已經(jīng)結束，將c1出棧，放棄c2，繼續(xù)掃描。（c）c1>c2，c1出棧，從OPND棧取出兩個元素（a和b），按c1進行運算，并把運算結果放入OPND棧。(5)重復上述過程，直到表達式求值完畢（OPTR棧為空棧）47ppt課件表達式求值示意圖：5+6(1+2)-4topbaseOPTR棧#OPND棧topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptoptop23top-top4toptoptoptop19toptoptop5讀入表達式過程：+6×(1+2)-4#=191+2=36×3=185+18=2323-4=193.4棧的應用舉例48ppt課件在算符優(yōu)先算法中，建立了兩個工作棧。一個是OPTR棧，用以保存運算符,一個是OPND棧，用以保存操作數(shù)或運算結果。

operandTypeEvaluateExpression(){

//算術表達式求值的算符優(yōu)先算法。設OPTR和OPND分別為運算符棧和運算數(shù)棧，OP為運算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=qetchar();While(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push(OPND,c);c=getchar()}

//不是運算符則進棧,In(c,OP)判斷c是否是運算符的函數(shù)

else

49ppt課件續(xù)switch(Precede(GetTop(OPTR),c){case<://新輸入的算符c優(yōu)先級高，c進棧Push(OPTR,c);c=getchar();break;case=://脫括號并接收下一字符Pop(OPTR,x);c=getchar();break;case>://新輸入的算符c優(yōu)先級低，即棧頂算符優(yōu)先權

//高,出棧并將運算結果入棧OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression50ppt課件3．括弧匹配檢驗

假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（［］（））或［（［］［］）］等為正確的匹配，［（]）或（［］（）或(())）均為錯誤的匹配。

問題：如何檢驗一個給定表達式中的括弧是否正確匹配？

解決辦法：用"期待的急迫程度"這個概念來描述。

51ppt課件

對于后出現(xiàn)的左括號,它等待與其匹配的右括號出現(xiàn)的急迫心情要比先出現(xiàn)的左括號高,也就是說,對左括號來說,后出現(xiàn)的比先出現(xiàn)的優(yōu)先等待檢測.

對右括號來說,每個出現(xiàn)的右括號要去找在它之前最后出現(xiàn)的那個左括號去匹配.52ppt課件例如考慮下列括號序列：

[([][])]

12345678

顯然,必須將先后出現(xiàn)的左括號依次保存,為了反映這個優(yōu)先程度,保存左括號的結構應該使用棧

對于出現(xiàn)的右括號來說,只要棧頂元素相匹配即可.如果棧頂?shù)淖罄ㄌ栒煤退ヅ?就可將它從棧頂刪除.53ppt課件什么樣的情況是“不匹配”的情況呢？1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?．棧中并沒有左括弧等在那里；3．棧中還有左括弧沒有等到和它相匹配的右括弧。54ppt課件Boolmatch(){InitStack(S);//初始化棧

ch=getchar();//接收第一個括號

while(ch!=‘#’)//不是結束符

{if(ch==‘(‘||ch==‘[‘)//左括號時進棧

{push(S,ch);}//ifelseif(ch==‘)’)//‘)’時檢測匹配

{if(!StackEmpty(S)){gettop(S,e);//取棧頂元素

if(e==‘(‘)//匹配成功

{pop(S);}//ifelsereturnfalse;//匹配失敗

}//if}//elseElse//’]’時檢測匹配{if(!StackEmpty(S)){gettop(S,e);//取棧頂元素

if(e==‘[‘)//匹配成功

{pop(S);}//ifelsereturnfalse;//匹配失敗

}//if}//elsech=getchar();}//whileIf(!StackEmpty(S))returnfalse;//棧中還有沒有匹配

//成功的左括號

elsereturntrue;}//match算法實現(xiàn)55ppt課件4.迷宮求解問題

計算機解迷宮時，通常用的是“窮舉求解”的方法.1．進入迷宮之后，不管在迷宮的哪一個位置上，都先往東走，如果走得通就繼續(xù)往東走，如果在某個位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個走得通的方向繼續(xù)往前直到出口為止；2．如果某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方向再試，如果這個位置已經(jīng)沒有方向可試了就再退一步，如果所有已經(jīng)走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通；56ppt課件

為了保證在任何位置上都能沿原路退回，需要用一個“后進先出”的結構即棧來保存從入口到當前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。

57ppt課件算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。58ppt課件偽碼算法：設定當前位置的初值為入口位置；

do{

若當前位置可通，

則{

將當前位置插入棧頂；//納入路徑

若該位置是出口位置，則算法結束；

否則切換當前位置的東鄰方塊為新的當前位置；

}

否則

{

若棧不空且棧頂位置尚有其他方向未被探索，

則設定新的當前位置為:沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通，

則{刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？?；

}

}

}while(棧不空)；

沒有路徑存在59ppt課件3.3棧與遞歸由上看到：應用中如果處理數(shù)據(jù)處理過程具有后進先出的特性，可利用棧來實現(xiàn)數(shù)據(jù)處理過程。下面我們將看到可以用棧來實現(xiàn)遞歸。1．什么是遞歸遞歸是一個很有用的工具，在數(shù)學和程序設計等許多領域中都用到了遞歸。遞歸定義：簡單地說，一個用自己定義自己的概念,稱為遞歸定義。例

n!=1234(n-1)nn!遞歸定義n!=1當n=0時n!=n(n-1)!當n>0時用(n-1)!定義n!60ppt課件棧與遞歸2.遞歸函數(shù)：一個直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。

A（

）{

…

A();

…}B(){C(){

…

…

C();B();

…

…

}}A直接調(diào)用自己B間接調(diào)用自己61ppt課件棧與遞歸遞歸是程序設計中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。2．遞歸算法的編寫1）將問題用遞歸的方式描述（定義）2）根據(jù)問題的遞歸描述（定義）編寫遞歸算法

問題的遞歸描述（定義）遞歸定義包括兩項

基本項（終止項）：描述遞歸終止時問題的求解；

遞歸項：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題；

62ppt課件棧與遞歸例1

編寫求解階乘n!

的遞歸算法首先給出階乘n!

的遞歸定義

n!的遞歸定義基本項：n!=1當n=1遞歸項：n!=n(n-1)!

當n>1有了問題的遞歸定義，很容易寫出對應的遞歸算法：intfact(intn){//算法功能是求解并返回n的階乘If（n=1）return（1）；Elsereturn（n*fact(n-1)）；}//fact

63ppt課件棧與遞歸例2.編寫求解Hanoi塔問題的遞歸算法有三個各為X，Y，Z的塔座，在X項有n個大小不同，依小到大編號為1，2…n的圓盤。

現(xiàn)要求將X上的n個圓盤移至Z上，并仍以同樣順序疊放，

圓盤移動時必須遵守下列原則：1）每次移動一個盤子；2）圓盤可以放在X，Y，Z中的任一塔座上；3）任何時刻都不能將較大的圓盤壓放在較小圓盤之上；例

n=3時圓盤移動的過程如下圖所示：64ppt課件abc32111213121棧與遞歸YXZ65ppt課件棧與遞歸首先給出求解Hanoi塔問題

的遞歸描述（定義）

基本項：n=1時，將n號圓盤從X移至Z；遞歸項：n>1時，將X上1——n-1號圓盤移至Y；將X上的n號圓盤從X移至Z;將Y上1——n-1號圓盤從Y移至Z;

將規(guī)模為n的問題的求解歸結為規(guī)模為n-1的問題的求解有了問題的遞歸定義，很容易寫出對應的遞歸算法：66ppt課件voidhanoi(intn,charx,chary,charz)//將塔座x上按直徑由小到大且自上而下編號為1至n的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。{

if(n==1)

move(x,1,z);//將編號為1的圓盤從x移動z

else{

hanoi(n-1,x,z,y);//將x上編號為1至n-1的圓盤移到y(tǒng),z作輔助塔

move(x,n,z);//將編號為n的圓盤從x移到z

hanoi(n-1,y,x,z)；

//將y上編號為1至n-1的圓盤移到z，x作輔助塔

}

}

67ppt課件棧與遞歸3遞歸函數(shù)的實現(xiàn)先看一般函數(shù)的調(diào)用機制如何實現(xiàn)的。

A(){…B();…}C(){……}B(){…C();…}調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序ABC函數(shù)返回順序CBA后調(diào)用的函數(shù)先返回

函數(shù)調(diào)用機制可通過棧來實現(xiàn)計算機正是利用棧來實現(xiàn)函數(shù)的調(diào)用和返回的68ppt課件棧與遞歸我們看一下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)）；}//factn=3intfact(intn){

If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}//factn=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)返回地址實參

注意遞歸調(diào)用中棧的變化69ppt課件2、隊列的特點：由于限制了插入、刪除分別在兩端進行，那么元素的操作順序有“先進先出”或“后進后出”的特點（FirstInFirstOut--FIFOLastInLastOut--LILO）1、隊列（Queue)：是一種特殊的線性表(數(shù)據(jù)元之間的關系是線性關系.其插入、刪除分別在表的兩端進行，一端只能插入、另一端只能刪除。)隊首（front)：進行刪除的一端；隊尾（rear)：進行插入的一端；入隊：在隊尾插入一個元素；出隊：在隊首刪除一個元素；§3.4隊列3.4.1抽象數(shù)據(jù)類型隊列的定義70ppt課件

a1a2a3an入隊列隊頭隊尾出隊列隊列的示意圖隊列的特點先進先出第一個入隊的元素在隊頭，

最后一個入隊的元素在隊尾，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素隊列類似于日常的排隊，新來的人站在隊尾，隊頭的人進行事務處理后離隊。隊列通常設置兩個變量分別指示隊頭元素位置和隊尾元素的位置，這兩個變量分別稱為隊頭指針、隊尾指針；71ppt課件2.隊列的基本操作1）初始化操作InitQueue(&Q)

功能：構造一個空隊列Q；

2）銷毀操作DestroyQueue(&Q)

功能：銷毀已存在隊列Q；

3）置空操作ClearQueue(&Q)功能：將隊列Q置為空隊列；4）判空操作QueueEmpty(Q)功能：若隊列Q為空，則返回True，否則返回False；72ppt課件5）取隊頭元素操作GetHead(Q,&e)

功能：取隊頭元素，并用e返回；

6）入隊操作EnQueue(&Q,e)

功能：將元素e插入Q的隊尾；

7）出隊操作DeQueue(&Q,&e)

功能：若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK，否則返回ERROR；73ppt課件隊列的抽象數(shù)據(jù)類型定義：

ADTQueue{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet, i=1,2,...,n,n≥0}

數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1端為隊列頭，an端為隊列尾

74ppt課件基本操作：

InitQueue(&Q) DestroyQueue(&Q) ClearQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) DeQueue(&Q,&e) QueueTraverse(Q,visit())}ADTQueue75ppt課件3.隊列ADT應用舉例打印機隊列管理：在一臺打印機共享使用時，任何時刻它只能處理一個用戶的打印請求。打印任務的組織就用一個隊列來組織（先請求的，先處理）。當用戶發(fā)出打印請求時，把打印任務入隊；當打印機空閑時，從打印隊列中出隊一個任務；當打印機阻塞時,系統(tǒng)管理員可以清空隊列.76ppt課件1、存儲方式：同一般線性表的順序存儲結構完全相同。但是由于在兩端操作，設兩個指示器，(rear和front）分別指示隊列的尾和首。特別約定:頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一位置！空隊列：rear=front=0入隊：rear=rear+1出隊：front=front+1隊列空：front=rear3.4.2隊列的順序存儲結構77ppt課件特點:簡單,方便,但是易產(chǎn)生假溢出.78ppt課件只是稱為指針，實現(xiàn)時不一定用指針變量79ppt課件2.隊列的簡單操作的實現(xiàn)(1）初始化Q.front=Q.rear=0;(2）入隊Q.base[Q.rear]＝e;Q.rear++;(3）出隊Q.front++;(4）判空Q.front==Q.rear;(5）求隊長Q.rear-Q.front80ppt課件思考：順序隊列存在的問題及解決方案

可以看出：當入隊一個元素時，可能會出現(xiàn)假溢出現(xiàn)象.即：空間并沒有使用完，但不能入隊！解決的辦法：(1）平移，一旦發(fā)生假溢出，把隊列中所有元素移到隊列開頭．效率低．

(2）使用動態(tài)數(shù)組，當產(chǎn)生假溢出或真溢出時，都重新分配一個更大的空間．（不可?。?3）使用環(huán)數(shù)組，即將順序存儲的空間視為一個環(huán)空間。81ppt課件3.4.3循環(huán)隊列存儲結構及操作實現(xiàn)

方式：將順序隊列臆造為一個環(huán)狀的空間，如圖所示，稱之為循環(huán)隊列.指針和隊列元素之間的關系不變這種循環(huán)的圈只是一種邏輯上的圈,在物理上還是一組連續(xù)的存儲單元,仍可利用數(shù)組實現(xiàn).82ppt課件1.存儲結構及操作實現(xiàn)

循環(huán)隊列可充分利用空間，但仍存在問題：我們知道：隊列為空時front=rear右圖中，繼續(xù)入隊a7,a8，則front=rear即：隊列為空或隊列為滿時，都是front=rear，如何區(qū)分？83ppt課件兩種方法1.設置標志位以區(qū)別隊列是“空”還是“滿”因出隊而相等，則為空；因入隊而相等，則為滿；2.少用一個元素的空間，約定rear+1=front時，就認為隊滿．84ppt課件2.循環(huán)隊列存儲結構及操作實現(xiàn)

#defineMAXSIZE100//最大隊列長度

typedefstruct{

QElemType*base;//初始化時動態(tài)分配//存儲空間的基址

intfront;//隊頭指針，指向隊頭元素

intrear;//隊尾指針，指向隊尾元素的下//一個位置}SqQueue;85ppt課件

1）初始化操作InitQueue_Sq(SqQueue&Q)

參數(shù)：Q是存放隊列的結構變量；功能：建一個空隊列Q；

循環(huán)隊列的基本操作算法Q.frontQ.rear540312建一個空隊列Q86ppt課件StatusInitQueue_Sq(SqQueue&Q){

//構造一個空隊列QQ.base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!Q.base)exit(OVERFLOW);

//存儲分配失敗

Q.front=Q.rear=0;(什么意思？)

ReturnOK;

}//InitQueue_Sq算法：87ppt課件2)入隊操作EnQueue_Sq(SqQueue&Q,QElemTypee)

功能：將元素e插入隊尾；入隊操作主要步驟：1）Q是否已滿，若滿，返回ERROR；否則轉(zhuǎn)2）；2）將元素e寫入隊尾；3）修改隊尾指針，使隊尾指針指向隊尾元素的下一個位置；Q.frontQ.rear540312J1J3J2eQ.frontQ.rear540312J1J3J2元素e入隊前元素e入隊后88ppt課件StatusEnQueue_Sq(SqQueue&Q,QElemTypee)

//將元素e插入隊尾

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;//將元素e插入隊尾Q.rear=(Q.rear+1)%MAXSIZE;

//修改隊尾指針

returnOK;}//EnQueue_Sq入隊操作算法

89ppt課件3)出隊操作DeQueue_Sq(SqQueue&Q,QElemType&e)功能：刪除隊頭元素，用e返回其值;出隊操作主要步驟：1）Q是否為空，若空，返回ERROR；否則轉(zhuǎn)2）；2）將隊頭元素賦值給e；3）修改隊頭指針，刪除隊頭元素；Q.frontQ.rear540312J1J3J2Q.frontQ.rear540312J1J3J2出隊操作前出隊操作后eJ190ppt課件StatusDeQueue_Sq(SqQueue&Q,QElemType&e)

//刪除隊頭元素，用e返回其值,并返回OK；否

//則返回ERROR

if((Q.rear==Q.front)returnERROR;

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;//修改隊頭指針

returnOK;

}//EnQueue_Sq出隊操作算法

91ppt課件§3.4.4鏈式隊列的表示和實現(xiàn)1、存儲方式：同一般線性表的單鏈式存儲結構完全相同。但是由于插入、刪除在兩端進行，需要兩個指針front、rear分別指向隊列的兩端。有兩種不同的鏈法：哪個好?92ppt課件入隊都很容易，但是出隊差別很大！!

應該用第1種鏈法。為了處理空隊列，可以加上頭結點。2、特點：沒有假溢出，提高了空間利用率。只有系統(tǒng)沒有空間了，才會溢出；93ppt課件2.鏈式存儲結構。頭結點^…...front隊頭隊尾rear設隊首、隊尾指針front和rear,front指向頭結點，rear指向隊尾94ppt課件frontrearx入隊^xfrontreary入隊x^yfrontrearx出隊x^yfrontrear空隊^frontreary出隊^95ppt課