數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（第五版） 課件 第04章 棧

第4章棧第4章棧4.1棧的定義和操作4.2棧的存儲(chǔ)和實(shí)現(xiàn)4.2.1順序棧4.2.2鏈?zhǔn)綏?.3棧的應(yīng)用舉例4.3.1進(jìn)制轉(zhuǎn)換4.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴并求值4.3.3函數(shù)調(diào)用棧4.3.4非遞歸求解Hanoi問題4.3.5遞歸函數(shù)的展開分析2重難點(diǎn)棧和線性表、隊(duì)列的關(guān)系——操作受限的含義順序棧的定義及相關(guān)操作鏈?zhǔn)綏５亩x及相關(guān)操作利用棧的特點(diǎn)解決應(yīng)用問題中綴表達(dá)式轉(zhuǎn)后綴并求值函數(shù)調(diào)用及遞歸的本質(zhì)——系統(tǒng)棧(棧內(nèi)存區(qū)、棧幀)遞歸問題的非遞歸實(shí)現(xiàn)——使用自定義棧34.1棧的定義和操作棧(stack)的定義：棧是一個(gè)操作受限的線性表。棧是限制在表的一端進(jìn)行插入和刪除的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點(diǎn)：后進(jìn)先出(LIFO)或先進(jìn)后出(FILO)只在表的一端(棧頂)進(jìn)行插入和刪除操作4

topbottom4.1棧的定義和操作生活中的棧54.1棧的定義和操作棧的基本操作1．進(jìn)棧：intpush(&s,x)2．出棧：intpop(&s,&x)3．讀取棧頂元素：intreadTop(s,&x)4.判棧空：int

isSEmpty(s)5.

判棧滿：int

isSFull(s)6.顯示棧元素：voidshowStack(s)64.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序?！靡唤M地址連續(xù)的存儲(chǔ)單元(數(shù)組)依次存放從棧底到棧頂?shù)脑?，同時(shí)附設(shè)一個(gè)棧頂指針，用來指示棧頂元素在棧中的位置。7棧底(bottom)棧頂(top)棧底棧頂棧底棧頂4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧偽代碼4-1固定長度順序棧的定義和初始化8#defineN40typedef

struct{

ElemTypedata[N]; //data數(shù)組中存放進(jìn)棧元素

inttop;

//top指示棧頂元素的位置}SeqStack;

//定義順序棧的類型SeqStackvoidinit(SeqStack&s){

s.top=-1;

} //初始化順序棧為空intmain(){

SeqStackstack;//stack為局部變量，存放于棧內(nèi)存區(qū)

init(stack);

//...... //后續(xù)操作

return

0;}左側(cè)代碼中stack的內(nèi)存布局若將棧的空間置于堆內(nèi)存區(qū)topbottom4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧偽代碼4-2動(dòng)態(tài)分配順序棧的定義和初始化9#defineN40typedef

struct{

ElemType*pData;//pData所指數(shù)組中存放進(jìn)棧元素

int

stackSize;

//stackSize記錄pData所指數(shù)組的長度

int

top;

//top指示棧頂元素的位置}SeqStack;

//定義順序棧的類型SeqStackvoidinit(SeqStack&s){

//動(dòng)態(tài)分配pData所指的數(shù)組空間

s.pData=(ElemType*)malloc(sizeof(ElemType)*N);

s.stackSize=N; //當(dāng)前棧中數(shù)組的長度為N

s.top=-1;

//初始化順序棧為空}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧偽代碼4-2動(dòng)態(tài)分配順序棧的定義和初始化10intmain(){

//stack為局部變量，存放于棧內(nèi)存區(qū)

SeqStackstack;

//開辟空間并初始化順序棧stack為空

init(stack);

//......//后續(xù)操作

return

0;}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-3順序棧的判?？?1intisSEmpty(SeqStacks)//判斷順序棧s是否為空{(diào)

if(s.top==-1)

return

1; //棧為空，則返回1

else

return

0; //否則，返回0}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-4順序棧的判棧滿12intisSFull(SeqStacks)//判斷順序棧s是否為滿{

if(s.top==s.stackSize-1)

return

1; //棧為滿，則返回1

else

return

0; //否則，返回0}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-5順序棧的進(jìn)棧操作13//進(jìn)棧一個(gè)元素x到順序棧s中intpush(SeqStack&s,ElemTypex){

//如果棧已滿，則不能繼續(xù)進(jìn)棧

if(isSFull(s))

return

0; //進(jìn)棧失敗，返回0

//先讓s.top自增，再將進(jìn)棧元素存入s.top指示的位置

s.top=s.top+1;

s.pData[s.top]=x;

return

1; //進(jìn)棧成功，返回1}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-6順序棧的出棧操作14//從順序棧s中出棧一個(gè)元素給xintpop(SeqStack&s,ElemType&x){

if(isSEmpty(s))

//如果棧為空

return

0;

//出棧失敗

x=s.pData[s.top];

//通過x帶回出棧元素

s.top--;

//棧頂指針自增

return

1;

//出棧成功}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-7讀取順序棧的棧頂元素(棧中內(nèi)容、棧頂指針均不變)15//讀取順序棧s的棧頂元素給xintreadTop(SeqStacks,ElemType

&x){

if(s.top==-1)

//如果棧為空

return

0;

//讀取棧頂失敗

x=s.pData[s.top];

//通過x帶回棧頂元素

return

1;

//讀取棧頂成功}返回值一定是整型么？這份代碼是錯(cuò)誤的！DataTypereadTop(SeqStacks){

if(isEmpty(s)) //若棧空，則返回0

return

0;

else

//否則返回棧頂元素

return

s.data[s.top];}下面這種讀取棧頂元素的方法怎么樣？上面函數(shù)的調(diào)用形式：intstatus=readTop(stack,ret);4.2棧的存儲(chǔ)和實(shí)現(xiàn)——順序棧順序棧的基本操作偽代碼4-7讀取順序棧的棧頂元素(棧中內(nèi)容、棧頂指針均不變)16//讀取順序棧s的棧頂元素給*pxintreadTop(SeqStacks,ElemType*px){

if(s.top==-1)

//如果棧為空

return

0;

//讀取棧頂失敗

*px=s.pData[s.top];

//通過x帶回棧頂元素

return

1;

//讀取棧頂成功}上面函數(shù)的調(diào)用形式：intstatus=readTop(stack,&ret);4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏未a4-8鏈?zhǔn)綏５亩x及初始化17typedef

struct_StackNode{

ElemTypedata;

//數(shù)據(jù)域

struct_StackNode*next; //指針域}StackNode;

//定義鏈?zhǔn)綏５慕Y(jié)點(diǎn)類型StackNodetypedef

struct{

StackNode*top; //棧頂指針}LinkStack;

//定義鏈?zhǔn)綏５念愋蚅inkStackvoidinit(LinkStack&s){

s.top=NULL; //初始化鏈?zhǔn)綏榭諁4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏未a4-8鏈?zhǔn)綏５亩x及初始化18intmain(){

LinkStackstack; //stack為局部變量，存放于棧內(nèi)存區(qū)

init(stack);

//初始化鏈?zhǔn)綏tack為空

//...... //后續(xù)操作

return

0;}圖中的s為stack的引用，因此s.top即為stack.top。4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏ｆ準(zhǔn)綏５幕静僮鱾未a4-9鏈?zhǔn)綏５呐袟？?9intisSEmpty(LinkStacks) //判斷鏈?zhǔn)綏是否為空{(diào)

if(s.top==NULL)

return

1; //棧為空，則返回1

else

return

0; //否則，返回0}4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏ｆ準(zhǔn)綏５幕静僮鱾未a4-10鏈?zhǔn)綏５倪M(jìn)棧操作20voidpush(LinkStack&s,ElemTypex)//將元素x進(jìn)棧到s中{

StackNode*pNew;

//給待進(jìn)棧的新結(jié)點(diǎn)開辟空間

pNew=(StackNode*)malloc(sizeof(StackNode));

pNew->data=x;

//構(gòu)造待進(jìn)棧的新結(jié)點(diǎn)

pNew->next=s.top; //將新結(jié)點(diǎn)插入到原棧頂結(jié)點(diǎn)之前

s.top=pNew;

//新結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)}

∧s.topxpNew4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏ｆ準(zhǔn)綏５幕静僮鱾未a4-11鏈?zhǔn)綏５某鰲２僮?1//從棧s中出棧一個(gè)元素，將其賦值給xintpop(LinkStack&s,ElemType&x){

StackNode*p;

if(isSEmpty(s)) //如果棧為空

return

0;

//出棧失敗，返回0

p=s.top;

s.top=p->next; //設(shè)置新的棧頂結(jié)點(diǎn)

x=p->data;

//用x帶回出棧元素的值

free(p);

//釋放原棧頂結(jié)點(diǎn)的空間

return

1;

//出棧成功，返回1}

∧s.top

p4.2棧的存儲(chǔ)和實(shí)現(xiàn)——鏈?zhǔn)綏ｆ準(zhǔn)綏５幕静僮鱾未a4-12顯示鏈?zhǔn)綏Ｖ械乃性?2voidshowLinkStack(LinkStacks)//顯示棧中所有元素{

StackNode*p;

if(s.top==NULL)

{

printf("當(dāng)前鏈?zhǔn)綏榭?！\n");

return;

}

for(p=s.top;p!=NULL;p=p->next)

{

printf("%s\t%s\t%c\t%d\t%.2f\n",

p->data.stuId,p->data.name,

p->data.gender,p->data.age,p->data.score);

}}假設(shè)棧中元素的類型為Student4.3棧的應(yīng)用舉例4.3.1進(jìn)制轉(zhuǎn)換4.3.2表達(dá)式轉(zhuǎn)換和求值中綴表達(dá)式轉(zhuǎn)后綴(運(yùn)算符棧)后綴表達(dá)式求值(運(yùn)算數(shù)棧)4.3.3函數(shù)調(diào)用棧4.3.4非遞歸求解Hanoi問題4.3.5遞歸函數(shù)的展開分析234.3.1進(jìn)制轉(zhuǎn)換

24商余數(shù)∴(138)10

=(10001010)24.3.1進(jìn)制轉(zhuǎn)換偽代碼4-13十進(jìn)制整數(shù)num，轉(zhuǎn)換為base進(jìn)制25voidconversion(intnum,intbase){

intx;

SeqStacks;

init(s); //初始化棧

while(num>0)

{

push(s,num%base); //除base取余

num=num/base; //將num更新為商

}

printf("轉(zhuǎn)換后的%d進(jìn)制值為：",base);

while(pop(s,x))//出棧成功，則執(zhí)行循環(huán)

{

charb=x>=10?x-10+'A':x+'0';

printf("%c",b);//出棧元素，轉(zhuǎn)成字符后，直接輸出

}}4.3.1進(jìn)制轉(zhuǎn)換——非負(fù)十進(jìn)制整數(shù)，轉(zhuǎn)為二進(jìn)制形式voiddec2binV1(intn){

SeqStacks;

int

e;

initSeqStack(s);

while(n) //依次進(jìn)棧，直到商為0

{

push(s,n%2);

n=n/2;

}

while(!isSEmpty(s)) //依次出棧，直到棧空

{

pop(s,e); //參數(shù)e為引用

printf("%d",e);

}}264.3.1進(jìn)制轉(zhuǎn)換——非負(fù)十進(jìn)制整數(shù)，轉(zhuǎn)為二進(jìn)制形式intdec2binV2(intn,intbin[]){

SeqStacks;

int

e,i=0;

initSeqStack(s);

while(n) //依次進(jìn)棧，直到商為0

{

push(s,n%2);

n=n/2;

}

while(!isEmpty(s)) //依次出棧，直到棧為空

{

pop(s,e);

bin[i++]=e; //printf("%d",e);

}

return

i;}274.3.1進(jìn)制轉(zhuǎn)換——非負(fù)十進(jìn)制整數(shù)，轉(zhuǎn)為任意進(jìn)制intdec2anyBase(intn,int

base,char

ret[]){

SeqStacks;

int

e,i=0;

initSeqStack(s);

while(n) //依次進(jìn)棧，直到商為0

{

push(s,n%base);

n=n/base;

}

while(!isEmpty(s)) //依次出棧，直到棧為空

{

pop(s,e);

//pop(s,&e);

ret[i++]=e<10?e+'0':e-10+'A';

}

return

i;}284.3.2表達(dá)式轉(zhuǎn)換和求值一個(gè)表達(dá)式由操作數(shù)(也稱運(yùn)算對(duì)象)、操作符

(也稱運(yùn)算符)和分界符(括號(hào))組成。算術(shù)表達(dá)式舉例：(a+b)*(c–d)–d/e29a+b左操作數(shù)右操作數(shù)雙目運(yùn)算符運(yùn)算規(guī)則：先算乘除，后算加減；先算括號(hào)內(nèi)，后算括號(hào)外；從左到右，依次計(jì)算。4.3.2表達(dá)式轉(zhuǎn)換和求值算術(shù)表達(dá)式的三種表示形式：中綴(infix)表達(dá)式<操作數(shù)><操作符><操作數(shù)>，如A+B前綴(prefix)表達(dá)式<操作符><操作數(shù)><操作數(shù)>，如+AB運(yùn)算符放在操作數(shù)的前面，又稱為波蘭式后綴(postfix)表達(dá)式<操作數(shù)><操作數(shù)><操作符>，如AB+運(yùn)算符放在操作數(shù)的后面，又稱為逆波蘭式304.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴中綴表達(dá)式：(a+b)*(c–d)–e/f等價(jià)的后綴表達(dá)式：ab+cd–*ef/–等價(jià)的前綴表達(dá)式：–*+ab–cd/ef后綴和前綴表達(dá)式的共同特點(diǎn)是：表達(dá)式中沒有括號(hào)，運(yùn)算符不存在優(yōu)先級(jí)的差別。314.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴中綴表達(dá)式(6+22)/4-(17-(9-4))/332對(duì)應(yīng)的后綴表達(dá)式622+4/1794--3/-如果沒有括號(hào)，運(yùn)算順序?qū)⑼耆煌?+22/4-17-9-4/36+22/4-17-9-4/3對(duì)應(yīng)的后綴表達(dá)式6224/

+

17

-

9

-

4

3

/

-4.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴中綴表達(dá)式(6+22)/4-(17-(9-4))/333對(duì)應(yīng)的后綴表達(dá)式622+4/1794--3/-如果沒有括號(hào)，運(yùn)算順序?qū)⑼耆煌?+22/4-17-9-4/36+22/4-17-9-4/3對(duì)應(yīng)的后綴表達(dá)式6224/

+

17

-

9

-

4

3

/

-4.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴中綴表達(dá)式轉(zhuǎn)后綴的過程從左向右掃描中綴表達(dá)式；遇到運(yùn)算對(duì)象時(shí)，直接輸出到后綴表達(dá)式遇到運(yùn)算符時(shí)，和棧頂運(yùn)算符比較優(yōu)先級(jí)棧為空，當(dāng)前運(yùn)算符進(jìn)棧；棧頂為左括號(hào)，當(dāng)前運(yùn)算符進(jìn)棧；棧頂運(yùn)算符優(yōu)先級(jí)低，當(dāng)前運(yùn)算符進(jìn)棧；棧頂運(yùn)算符優(yōu)先級(jí)較高或相等，應(yīng)一直出棧并輸出，直到棧為空或棧頂運(yùn)算符的優(yōu)先級(jí)較低，然后再將當(dāng)前運(yùn)算符進(jìn)棧。中綴表達(dá)式：(6+22)/4–(17–(9–4))/3后綴表達(dá)式：34543210622+4/1794––3/–(6+22)/4–(17–(9–4))/3遇到運(yùn)算符為右括號(hào)時(shí)一直出棧并輸出，直到左括號(hào)出棧并丟棄；運(yùn)算符棧4.3.2表達(dá)式轉(zhuǎn)換和求值——中綴表達(dá)式轉(zhuǎn)后綴3552+94–*183/–52①5+2=7794②9–4=55③7*5=3535183④18/3=6629⑤35-6=29運(yùn)算數(shù)棧出棧運(yùn)算時(shí)，先出棧的元素放后面，后出棧的元素放前面。4.3.2表達(dá)式轉(zhuǎn)換和求值——后綴表達(dá)式求值后綴表達(dá)式求值的過程從左向右掃描后綴表達(dá)式；遇到運(yùn)算對(duì)象時(shí)，直接進(jìn)棧遇到運(yùn)算符時(shí)，就出棧兩個(gè)操作數(shù)進(jìn)行計(jì)算3652+94-*183/-94-751833567*183/-=183/-=35-===29該后綴表達(dá)式對(duì)應(yīng)的中綴表達(dá)式(5+2)*(9–4)–18/3*/-后綴表達(dá)式：4.3.3函數(shù)調(diào)用棧374.3.3函數(shù)調(diào)用?！瘮?shù)的遞歸調(diào)用為什么使用遞歸調(diào)用使用遞歸編寫程序，使許多復(fù)雜的問題大大簡化。遞歸是程序設(shè)計(jì)中的一個(gè)強(qiáng)有力的工具。以下三種情況常用到遞歸問題的定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的384.3.3函數(shù)調(diào)用棧——遞歸調(diào)用工作棧函數(shù)的調(diào)用和返回，導(dǎo)致棧內(nèi)存中棧幀的變化遞歸——函數(shù)自己調(diào)用自己每次調(diào)用自己，都跳轉(zhuǎn)到同一份代碼的開頭；每個(gè)棧幀中，記錄不同的執(zhí)行現(xiàn)場。394.3.4非遞歸求解Hanoi問題——尾遞歸和非尾遞歸兩種方法求n的階乘如果函數(shù)中所有的遞歸調(diào)用都在函數(shù)末尾，則稱這種情況為尾遞歸。尾遞歸一般很容易改寫為非遞歸形式，即改用循環(huán)來實(shí)現(xiàn)。40intfac(intn){

if(n==0||n==1)

return

1;

returnn*fac(n-1);}intfac(intn){

inti,ret=1;

for(i=1;i<=n;i++)

ret*=i;

returnret;}偽代碼4-14遞歸求n的階乘偽代碼4-15用循環(huán)求n的階乘

4.3.4非遞歸求解Hanoi問題——尾遞歸和非尾遞歸兩種方法求斐波那契(Fibonacci)數(shù)列41int

fibV1(intn){

if(n<=1)

return

1;

return

fibV1(n-1)+fibV1(n-2);}偽代碼4-16末尾遞歸調(diào)用自己兩次int

fibV2(intn,intnum1,intnum2){

if(n<=1)

returnnum2;

return

fibV2(n-1,num2,num1+num2);}偽代碼4-17末尾遞歸調(diào)用自己一次

求斐波那契(Fibonacci)數(shù)列的函數(shù)，也可以僅用循環(huán)，即可實(shí)現(xiàn)非遞歸。4.3.4非遞歸求解Hanoi問題——尾遞歸和非尾遞歸斐波那契(Fibonacci)數(shù)列遞歸調(diào)用的示意圖42fib(3)fib(4)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)＋＋＋＋101211310源桿中間桿(臨時(shí)桿)目標(biāo)桿4.3.4非遞歸求解Hanoi問題——非尾遞歸(必須用棧)Hanoi問題源桿上有n個(gè)盤子(順序：大的在下，小的在上)n個(gè)盤子要全部移動(dòng)到目標(biāo)桿上移動(dòng)過程中始終保證大的盤子在下，小的盤子在上每次只能移動(dòng)一個(gè)盤子，移動(dòng)過程中能借助臨時(shí)桿求盤子的移動(dòng)順序。434.3.4非遞歸求解Hanoi問題——非尾遞歸(必須用棧)偽代碼4-18遞歸求解Hanoi問題44voidhanoi(intn,charx,chary,charz){

static

ints=1;

if(n==1)//如果只有一個(gè)盤子

printf("第%d步：%c-->%c\n",s++,x,z);

else

{

//先移動(dòng)上面的n-1個(gè)盤子到中間桿

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

//再移動(dòng)最下面的那個(gè)盤子到目標(biāo)桿

printf("第%d步：%c-->%c\n",s++,x,z);

//最后將n-1個(gè)盤子從中間桿移動(dòng)到目標(biāo)桿

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

}}4.3.4非遞歸求解Hanoi問題——非尾遞歸(必須用棧)454.3.4非遞歸求解Hanoi問題——非尾遞歸(必須用棧)464.3.5遞歸函數(shù)的展開分析程序4-2遞歸函數(shù)recursion()47#include<stdio.h>void

recursion(){

charc=getchar();

putchar(c);

if(c!='*')

recursion();

putchar(c);}intmain(){

recursion();

return

0;}//若輸入為ABC*，請(qǐng)分析并寫出輸出結(jié)果。4.3.5遞歸函數(shù)的展開分析48補(bǔ)充：表達(dá)式中括號(hào)匹配的檢驗(yàn)括號(hào)配對(duì)的三種失配情況：當(dāng)掃描到右括號(hào)時(shí)，棧為空——無左括號(hào)相配；棧不為空，但右括號(hào)與當(dāng)前棧頂元素不配對(duì)；掃描結(jié)束，但棧不空——有剩余左括號(hào)未匹配完。49補(bǔ)充：表達(dá)式中括號(hào)匹配的檢驗(yàn)括號(hào)匹配的過程50(…{…}…)…[…{…(…)...

[…]