棧和隊(duì)列課件

棧隊(duì)列遞歸棧和隊(duì)列棧(Stack)定義:是限定僅在表尾進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端 稱為棧頂(top)，另一端 稱為棧底(bottom)特點(diǎn)：后進(jìn)先出(LIFO)a1topbottoman....進(jìn)棧

出棧棧的主要操作ADTStack{//對(duì)象由數(shù)據(jù)類型為StackData的元素構(gòu)成

intPush(stack*S,StackDatax);//進(jìn)棧

intPop(stack*S,StackData&x);//出棧

intGetTop(stack*S,StackData&x);//取棧頂

voidInitStack(stack*S);//置空棧

intStackEmpty(stack*S);//判?？辗?/p>

intStackFull(stack*S);//判棧滿否}棧的表示和實(shí)現(xiàn)順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個(gè)位置，

base為棧底指針，指向棧底的位置。base空棧a進(jìn)棧b進(jìn)棧aabtopbasetopbasetoptoptopabcdee進(jìn)棧abcdef進(jìn)棧溢出abde出棧cbasebasebasetop順序棧的類型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT10；typedefcharStackData;typedefstruct{ //順序棧定義

StackData*base;//棧底指針

StackData*top;//棧頂指針

intstacksize；//當(dāng)前已分配的存儲(chǔ)空間}SeqStack；判棧空intStackEmpty(SeqStack*S){ if(S->top==S->base)return1//判?？?空則返回1elsereturn0;//否則返回0

}判棧滿intStackFull(SeqStack*S){ if(S->top-S->base>=S->StackSize)return1

//判棧滿,滿則返回1 elsereturn0;//否則返回0}順序棧的基本運(yùn)算:初始化voidInitStack(SeqStack*S){//置空棧S->base=(StackData*)malloc(STACK_INIT_SIZE* sizeof(StackData));

if(!S->base)exit(OVERFLOW);S->top=S->base;S->stacksize=STACK_INIT_SIZE;Returnok;}入棧intPush(SeqStack*S,StackDatax){//插入元素x為新的棧頂元素

if(StackFull(S)){ S->base=(StackData*)malloc(S->base, (S->stacksize+STACKINCREMENT)* sizeof(StackData)); if(!S->base)exit(overflow); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT;//追加存儲(chǔ)空間} *(S->top)=x;

（S->top）++;Returnok}取棧頂元素intGettop(SeqStack*S,StackData&x){//若棧空返回0,否則棧頂元素讀到x并返回1

if(StackEmpty(S))return0; (S->top)--; x=*(S->top); return1;}出棧intpop(SeqStack*S,StackData&x){//若?？辗祷?,否則棧頂元素退出到x并返回1

if(StackEmpty(S))return0;

--(S->top); x=*(S->top);return1;}鏈?zhǔn)綏?棧的鏈接表示

鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作top鏈?zhǔn)綏?LinkStack)的定義typedefintStackData;typedefstructnode{

StackDatadata; //結(jié)點(diǎn)

structnode*link; //鏈指針}StackNode;typedefstruct{

StackNode*top;//棧頂指針}LinkStack;鏈?zhǔn)綏２僮鲗?shí)現(xiàn)初始化voidInitStack(LinkStack*S){S->top=NULL;}入棧intPush(LinkStack*S,StackDatax){

StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->link=S->top;S->top=p;return1;}判?？読ntStackEmpty(LinkStack*S){returnS->top==NULL;}出棧intPop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;

StackNode*p=S->top;

S->top=p->link;

x=p->data;free(p);return1;}取棧頂intGetTop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;x=S->top->data;return1;}置棧空intMakeEmpty(LinkStack*S){While(S->top!=NULL){ StackNode*p=S->top; S->top=S->top->link; free(p); }}棧的應(yīng)用舉例

數(shù)制轉(zhuǎn)換 行編輯程序 迷宮求解 表達(dá)式求值數(shù)制轉(zhuǎn)換

N=(Ndivd)×d+Nmodd

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

，其運(yùn)算過(guò)程如下：

NNdiv8Nmod8

13481684

16821 0

212 5

20 2輸出順序計(jì)算順序voidconversion(){InitStack(S);scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion行編輯程序 在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。 設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū);并假設(shè)“#”為退格符，“@”為退行符。假設(shè)從終端接受兩行字符：

whli##ilr#e（s#*s)outcha@putchar(*s=#++);實(shí)際有效行為：

while(*s)putchar(*s++);VoidLineEdit(){ InitStack(s); ch=getchar(); while(ch!=EOF){//EOF為全文結(jié)束符

while(ch!=EOF&&ch!='\n'){

switch(ch){ case'#':Pop(S,c);break; case'@':ClearStack(S);break;

//重置S為空棧

default:Push(S,ch);break;

} ch=getchar();//從終端接收下一個(gè)字符

}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar(); }DestroyStack(s);}迷宮求解通常用的是“窮舉求解”的方法迷宮路徑算法的基本思想若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的 當(dāng)前位置；｝否則{ ………..

｝｝while(棧不空）；若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛ 刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？?｝限于二元運(yùn)算符的表達(dá)式定義:

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))

操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)Exp=S1+OP+S2前綴表示法OP

+S1+S2中綴表示法

S1+

OP

+S2后綴表示法

S1+S2+

OP表達(dá)式求值例如:Exp=a

b

+

(c

d/e)

f前綴式:+

ab

c/def中綴式:a

b

+

c

d/e

f后綴式:ab

cde/

f

+表達(dá)式標(biāo)識(shí)方法b-ca/*def*+后綴表達(dá)式求值先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f從原表達(dá)式求得后綴式方法設(shè)立暫存運(yùn)算符的棧;設(shè)表達(dá)式的結(jié)束符為“#”,予設(shè)運(yùn)算符棧的棧底為“#”若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;否則，退出棧頂運(yùn)算符發(fā)送給后綴式;“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”為自左括弧開(kāi)始的表達(dá)式的結(jié)束符。隊(duì)列定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱為對(duì)頭(front)。特點(diǎn)：先進(jìn)先出(FIFO)

a1，a2，a3，…，an出隊(duì)列入隊(duì)列隊(duì)頭隊(duì)尾鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎炬滉?duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。datanextfrontreardatanextfrontrearfrontrearx^元素x入隊(duì)frontrearx^y^元素y入隊(duì)frontrearx^^y元素x出隊(duì)frontrear^空隊(duì)列^frontrearNULL空隊(duì)列鏈?zhǔn)疥?duì)列的定義typedefintQueueData;typedefstructnode{

QueueDatadata; //隊(duì)列結(jié)點(diǎn)數(shù)據(jù)

structnode*link;//結(jié)點(diǎn)鏈指針}QueueNode;typedefstruct{

QueueNode*rear,*front;}LinkQueue;鏈隊(duì)列的主要操作初始化voidInitQueue(LinkQueue*Q){Q->rear=Q->front=NULL;}隊(duì)空intQueueEmpty(LinkQueue*Q){returnQ->front==NULL;}取隊(duì)頭元素intGetFront(LinkQueue*Q,QueueData&x){if(QueueEmpty(Q))return0; x=Q->front->data;return1; }入隊(duì)intEnQueue(LinkQueue*Q,QueueDatax){

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));p->data=x;p->link=NULL;if(Q->front==NULL)

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

Q->front=Q->rear=p;elseQ->rear->link=p;//入隊(duì)

Q->rear=p;return1;}出隊(duì)intDeQueue(LinkQueue*Q,QueueData&x){//刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值

if(QueueEmpty(Q))return0; //判隊(duì)空

QueueNode*p=Q->front; x=p->data; //保存隊(duì)頭的值

Q->front=Q->front->link; //新隊(duì)頭

free(p);return1; }循環(huán)隊(duì)列(CircularQueue)順序隊(duì)列—隊(duì)列的順序存儲(chǔ)表示。用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。插入新的隊(duì)尾元素，尾指針增1，rear=rear+1，刪除隊(duì)頭元素，頭指針增1，front=front+1，因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出解決辦法：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，形成循環(huán)(環(huán)形)隊(duì)列隊(duì)列的進(jìn)隊(duì)和出隊(duì)frontrear空隊(duì)列frontrearA,B,C,D進(jìn)隊(duì)ABCDfrontrearA,B出隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出循環(huán)隊(duì)列(CircularQueue)隊(duì)頭、隊(duì)尾指針加1，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxsize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxsize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxsize==front;

01234567循環(huán)隊(duì)列frontrearMaxsize-101234567frontBCDrear一般情況AC01234567隊(duì)滿frontrearDEFGABCH01234567rear空隊(duì)列frontC01234567隊(duì)滿(正確)frontrearDEFGABC#defineMAXSIZE100Typedefstruct{ QueueData*data; intfront; intrear;}SeqQueue循環(huán)隊(duì)列的類型定義循環(huán)隊(duì)列操作的實(shí)現(xiàn)

初始化隊(duì)列voidInitQueue(SeqQueue*Q){//構(gòu)造空隊(duì)列Q->data=(QueueData*)malloc(MAXSIZE*sizeof(QueueData));If(!Q->data)exit(OVERFLOW);Q->rear=Q->front=0;Returnok}判隊(duì)空intQueueEmpty(SeqQueue*Q){returnQ->rear==Q->front;}判隊(duì)滿intQueueFull(SeqQueue*Q){return(Q->rear+1)%QueueSize==Q->front;}入隊(duì)intEnQueue(SeqQueue*Q,QueueDatax){if(QueueFull(Q))return0;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;return1;}出隊(duì)intDeQueue(SeqQueue*Q,QueueData&x){if(QueueEmpty(Q))return0; x=Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return1;}取隊(duì)頭intGetFront(SeqQueue*Q,QueueData&x){if(QueueEmpty(Q))return0;x=Q->data[(Q->front+1)%MAXSIZE];return1;}隊(duì)列應(yīng)用舉例—打印二項(xiàng)展開(kāi)式(a+b)i的系數(shù)楊輝三角形(Pascal’striangle)分析第i行元素與第i+1行元素的關(guān)系目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)從第i行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)voidYANGVI(intn){

Queueq;//隊(duì)列初始化q.MakeEmpty();

q.EnQueue(1);q.EnQueue(1);//預(yù)放入第一行的兩個(gè)系數(shù)

ints=0;for(inti=1;i<=n;i++){//逐行處理

cout<<endl; q.EnQueue(0); for(intj=1;j<=i+2;j++){//處理第i行的i+2個(gè)系數(shù)

intt=q.DeQueue();//讀取系數(shù)

q.EnQueue(s+t);//計(jì)算下一行系數(shù)，并進(jìn)隊(duì)列

s=t;if(j!=i+2)cout<<s<<‘’;//打印一個(gè)系數(shù)，第i+2個(gè)為0 }}}優(yōu)先級(jí)隊(duì)列(PriorityQueue)優(yōu)先級(jí)隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素例如下表：任務(wù)的優(yōu)先權(quán)及執(zhí)行順序的關(guān)系數(shù)字越小，優(yōu)先權(quán)越高#include<assert.h>#include<iostream.h>$include<stdlib.h>constint

maxPQSize=50;//缺省元素個(gè)數(shù)template<classType>class

PQueue

{public:

PQueue();

~PQueue(){delete[]pqelements;}

voidPQInsert(constType&

item);

Type

PQRemove();

優(yōu)先隊(duì)列的類定義

voidmakeEmpty(){

count=-1;}

int

IsEmpty()const{returncount==

-1;}

intIsFull

()const{returncount==maxPQSize;}

int

Length()const{returncount;}/

/優(yōu)先級(jí)隊(duì)列元素個(gè)數(shù)private:

Type*pqelements;

//存放數(shù)組（優(yōu)先級(jí)隊(duì)列數(shù)組）

int

count;

//隊(duì)列元素計(jì)數(shù)

}template<classType>PQueue<Type>::PQueue():count(-1){

pqelements=newType[maxPQSize];

assert(pqelements!=0);//分配斷言}template<classType>voidPQueue<Type>::PQInsert(constType&item){

assert(!IsFull()); //判隊(duì)滿斷言

count++；pqelements[count]=item; }優(yōu)先級(jí)隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)template<classType>TypePQueue<Type>::PQRemove(){

assert(!IsEmpty()); //判隊(duì)空斷言

Typemin=pqelements[0]; intminindex=0;

for(inti=1;i<count;i++)//尋找最小元素

if(pqelements[i]<min)//存于min {min=pqelements[i];minindex=i;}

pqelements[minindex]=pqelements[count-1];

//用最后一個(gè)元素填補(bǔ)要取走的最小值元素

count--;//優(yōu)先級(jí)隊(duì)列中元素個(gè)數(shù)減一

returnmin;}遞歸定義

若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的； 若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱這個(gè)過(guò)程是遞歸的過(guò)程。三種遞歸情況

定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的定義是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){

if(n==0)return1;

elsereturnn*Factorial(n-1);}例1.階乘函數(shù)求解階乘n!的過(guò)程主程序

main:fact(4)參數(shù)4計(jì)算4*fact(3)

返回24參數(shù)3計(jì)算3*fact(2)

返回6參數(shù)2計(jì)算2*fact(1)

返回2參數(shù)1計(jì)算1*fact(0)

返回1參數(shù)0直接定值=1

返回1參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值例2.計(jì)算斐波那契數(shù)列函數(shù)Fib(n)的定義遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

數(shù)據(jù)結(jié)構(gòu)是遞歸的有若干結(jié)點(diǎn)的單鏈表

例如單鏈表結(jié)構(gòu)f

f

只有一個(gè)結(jié)點(diǎn)的單鏈表例1.搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值voidSearch(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elseSearch(f->link);}fffff

a0a1a2a3a4遞歸找鏈尾例2.在鏈表中尋找等于給定值的結(jié)點(diǎn),并打印其數(shù)值

void

Search(ListNode*f,ListData&

x){

if(f!=NULL)

if(f->data==x)

printf(“%d\n”,

f->data);

else

Search(f->link,x);

}ffff

遞歸找含x值的結(jié)點(diǎn)x

例如，漢諾塔(TowerofHanoi)問(wèn)題的解法：如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：

①用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤子移到B柱上：

②將A柱上最后一個(gè)盤子直接移到C柱上；

③用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤子移到C柱上。問(wèn)題的解法是遞歸的算法#include<iostream.h>#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){

//解決漢諾塔問(wèn)題的算法

if(n==1)printf("move%s",A,"to%s,C); else{Hanoi(n-1,A,C,B);

printf("move%s",A,"to%s,C);Hanoi(n-1,B,A,C);}}遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過(guò)程為外部調(diào)用；遞歸過(guò)程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)

longFactorial(longn){

inttemp;

if(n==0)return1;elsetemp=n*Factorial(n-1);

RetLoc2

returntemp;

}voidmain(){ int

n;

n=Factorial(4);

RetLoc1

}

計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1參數(shù)返回地址返回時(shí)的指令RetLoc1return4*6//返回24

RetLoc2return3*2//返回6

RetLoc2return1//返回1

RetLoc2return1*1//返回1

RetLoc2return2*1//返回2

遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5斐波那契數(shù)列的遞歸調(diào)用樹(shù)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)

棧結(jié)點(diǎn)ntagtag=1,向左遞歸；tag=2,向右遞歸Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)

213141n=1sum=0+1223141n=2-23141n=0sum=1+03241n=3-2

41n=1sum=1+142

n=4-2

Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)

2142n=1sum=2+12242n=2-242n=0sum=3+0

longFibnacci(longn){ Stack<Node>S;Node*w;longsum=0;

//反復(fù)執(zhí)行直到所有終端結(jié)點(diǎn)數(shù)據(jù)累加完

do{ while(n>1){

w->n=n;w->tag=1;S.push(w);n--;}//向左遞歸到底,邊走邊進(jìn)棧

sum=sum+n; //執(zhí)行求和

while(!S.IsEmpty()){ w=S.getTop();S.Pop(); if(w->tag==1){//改為向右遞歸