數(shù)據(jù)結(jié)構(gòu)第三章棧教材

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第1頁。23.1棧（Stack）3.2隊(duì)列（Queue）

第三章棧和隊(duì)列1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第2頁。31.

定義:3.1棧與線性表相同，仍為一對一(1:1)關(guān)系。用順序棧或鏈棧存儲均可，但以順序棧更常見只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序棧或鏈棧的存儲結(jié)構(gòu)有別而不同。3.存儲結(jié)構(gòu):4.運(yùn)算規(guī)則:5.實(shí)現(xiàn)方式:

2.邏輯結(jié)構(gòu):限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。即棧頂基本操作有：建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值，等等。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第3頁。4棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

/top;表頭(即a1端)稱為棧底/base例如：棧S=(a1,a2,a3,……….,an-1,an)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素想一想：要從棧中取出a1，應(yīng)當(dāng)如何操作？強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第4頁。5Q1：堆棧是什么？它與一般線性表有什么不同？

堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。

一般線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取

運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝插入=壓入=PUSH（an+1)“出”＝刪除=彈出=POP(an)數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第5頁。6a1a2……an順序棧Sai……Q2：順序表和順序棧的操作有何區(qū)別？表頭表尾低地址高地址寫入：S[i]=ai讀出：

e=S[i]壓入(PUSH):

S[top++]=an+1彈出(POP):e=S[--top]低地址高地址S[i]a1a2

aian……順序表S……

an+1以線性表

S=(a1,a2,….,an-1,an)為例棧底base棧頂top前提：一定要預(yù)設(shè)棧頂指針top棧頂top數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第6頁。7棧不存在的條件：base=NULL;棧為空的條件：base=top;棧滿的條件：top-base=stacksize;a1a2……an順序棧Sai……低地址高地址

an+1棧底base棧頂top數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第7頁。8向上生成：若入棧動作使地址向高端增長；向下生成：若入棧動作使地址向低端增長；Q3：什么叫“向上生成”的棧？“向下生成”又是何意？答：對于向上生成的堆棧:入?？谠E：堆棧指針top“先壓后加”

:

出棧口訣：堆棧指針top“先減后彈”

:

e=S[--top]S[top++]=an+1數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第8頁。9Q4：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；簡化了程序設(shè)計(jì)的問題。下面用4個例子來幫助理解堆棧：答：數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第9頁。10voidtest(int&sum){intx;scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}斷點(diǎn)地址入棧例1（嚴(yán)題集3.10③）閱讀下列遞歸過程，說明其功能。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入的數(shù)據(jù)

x1

最后才被累加程序功能：對鍵盤輸入數(shù)據(jù)求和，直到輸入0結(jié)束數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第10頁。11例2:一個棧的輸入序列為1,2,3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即；123132231213321②1入1出，2、3入，3、2出，即；③1、2入，2出，3入3出，即；④1、2入，2、1出，3入3出，即；⑤1、2、3入，3、2、1出，即；合計(jì)有5種可能性。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第11頁。12例3：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？答：43512思考：有無通用的判別原則？12345的輸出呢？不可能實(shí)現(xiàn)主要是其中的12順序不能實(shí)現(xiàn)12345可以實(shí)現(xiàn)每壓入一數(shù)便立即彈出即可。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第12頁。13例4：設(shè)依次進(jìn)入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bB）、C）討論：有無通用的判別原則？有！若輸入序列是…,Pj…Pk…Pi…(Pj<Pk<Pi)，一定不存在這樣的輸出序列

…,Pi…Pj…Pk…答：即對于輸入序列1，2，3，不存在輸出序列3，1，2A）、D）可以：不行：數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第13頁。14棧的抽象數(shù)據(jù)類型定義:(教材P44-45）ADTStack{數(shù)據(jù)對象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTStack入棧、本節(jié)重點(diǎn)：順序棧和鏈棧的基本操作出棧、建棧初始化、判斷棧滿或?？?、讀棧頂元素值等。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第14頁。15順序棧的存儲表示（教材P46)：

#defineSTACK-INIT-SIZE100

#defineSTACKINCREMENT

10

typedefstruct{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;動態(tài)數(shù)組//存儲空間初始分配量//存儲空間分配增量//棧的基址即棧底指針//棧頂指針//當(dāng)前分配的空間數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第15頁。16棧的存儲結(jié)構(gòu)順序棧棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為basetop進(jìn)棧A出棧棧滿CDEFtoptoptoptoptoptoptoptoptoptoptop棧空top123450?？誦asetopCA123450BDEFbaseB123450basetop實(shí)現(xiàn)：一維數(shù)組s[M]棧空:

棧滿:

s.top-s.base=M此時入棧則上溢（overflow)top=base此時出棧則下溢（underflow)數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第16頁。171.建棧(初始化):initstack(s)2.判?？?stackempty(s)voidinitstack(stack*s){s.top==s.base;}intstackempty(stack*s){if(s.top==s.base)return(1);/*若?？辗祷?*/elsereturn(0);/*否則返回0*/}3.判棧滿:stackfull(s)intstackfull(stack*s){if(s.top-s.base==stacksize)return(1);/*若棧滿返回1*/elsereturn(0);/*否則返回0*/}數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第17頁。18順序棧的入棧操作——例如用堆棧存放（A，B，C，D）AACBABAtop核心語句：top=L;

順序棧入棧函數(shù)Push（）statusPush(ElemTypee){if(top-L>stacksize){追加存儲空間}elses[top++]=e;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第18頁。19順序棧出棧操作——例如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語句：Pop();順序棧出棧函數(shù)Pop()statusPop(){if(top=L){下溢}else{e=s[--top];return(e);}}Pop();Printf(Pop());數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第19頁。20鏈棧的入棧操作和出棧操作（教材省略）(1)鏈棧的構(gòu)造方式——以頭指針為棧頂，在頭指針處插入或刪除.Node*st,*p;intm=sizeof(Node);棧頂棧底棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來表示，用鏈?zhǔn)浇Y(jié)構(gòu)來表示的棧就是鏈棧sta1a2an-1annextdata鏈棧中每個結(jié)點(diǎn)由兩個域構(gòu)成：data域和next域，其定義為：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第20頁。21Push(SElemTypee){p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->next=st;st=p;}}

Status

Pop()

{if(st==NULL){下溢}else{e=st->data;p=st;st=st->next;

free(p);return(e);}}鏈棧入棧函數(shù)鏈棧出棧函數(shù)插入表頭從表頭刪除(2)操作由此可以看出：一個鏈棧由其棧頂指針唯一指定設(shè)st指向棧頂元素，則st

=NULL表示?？諗?shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第21頁。22鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；鏈棧一般不會出現(xiàn)棧滿情況，除非沒有空間導(dǎo)致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。采用鏈棧存儲方式的優(yōu)點(diǎn)是，可使多個棧共享空間；當(dāng)棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。幾點(diǎn)說明:數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第22頁。23棧的應(yīng)用--過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程3數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第23頁。24例1:數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——P48

設(shè)計(jì)思路：用棧暫存低位值例2：括號匹配的檢驗(yàn)————P49

設(shè)計(jì)思路：用棧暫存左括號例3：表達(dá)式求值—————P52

設(shè)計(jì)思路：用棧暫存運(yùn)算符例4：漢諾儀（Hanoi）塔———P55

設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第24頁。25例1:數(shù)制轉(zhuǎn)換

例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top723數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第25頁。26Voidconversion(){InitStack(S);//構(gòu)造空棧

scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(“%d”,e);}}//conversion數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第26頁。27例2:括號匹配的檢驗(yàn)

假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量（可理解為每個字符占用一個數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變量。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第27頁。28算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配3）表達(dá)式檢驗(yàn)結(jié)束時，若?？眨瑒t表明表達(dá)式中匹配正確否則表明“左括弧”有余數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第28頁。29Statusmatching(string&exp){

intstate=1;initstack(s);

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“){Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第29頁。30例3:行編輯程序功能:接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。思路:設(shè)立一個輸入緩沖區(qū)，接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶出錯，并在發(fā)現(xiàn)有誤時可以及時更正。舉例:‘#’:表示前一個字符無效；

‘@’：表示當(dāng)前行中的字符均無效。Whli##ilr#e(s#*s)outcha@putchar(*s=#++);While(*s)putchar(*s++);數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第30頁。31VoidLineEdit(){InitStack(S);//構(gòu)造空棧Sch=getchar();//從終端接收第一個字符

while(ch!=EOF){//EOF為全文結(jié)束符

while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,C);break;//僅當(dāng)棧非空時退棧

case‘@’:ClearStack(S);break;//重置S為空棧

default:Push(S,ch)break;}//有效字符進(jìn)棧，未考慮棧滿情形數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第31頁。32ch=getchar();//從終端接收下一個字符

}//將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)

ClearStack(S);

//重置S為空棧

if(ch!=EOF)ch=getchar();

}

DestroyStack(S);}//LineEdit數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第32頁。33例4

表達(dá)式求值(這是棧應(yīng)用的典型例子)這里，表達(dá)式求值的算法是“算符優(yōu)先法”.例如：3*（7–2）（1）要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：

a.從左算到右

b.

先乘除，后加減

c.

先括號內(nèi)，后括號外由此，此表達(dá)式的計(jì)算順序?yàn)椋?/p>

3*（7–2）=3*5=15數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第33頁。34（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對任意相繼出現(xiàn)的算符1和2

，都要比較優(yōu)先權(quán)關(guān)系算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見教材P53表3.1（是提供給計(jì)算機(jī)用的表?。┯杀砜煽闯?，右括號

)

和井號

#

作為2時級別最低；由c規(guī)則得出：*，/，+，-為1時的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號內(nèi)運(yùn)算，已算完?！?/p>

#

’=‘

#

’

表明表達(dá)式求值完畢。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第34頁。35（3）算法思想：設(shè)定兩棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if操作符<棧頂元素，則退棧、計(jì)算，結(jié)果壓入OPND棧；

操作符=棧頂元素且不為‘#’，脫括號（彈出左括號）；

操作符>棧頂元素，壓入OPTR棧。數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第35頁。36OPTROPNDINPUTOPERATE3*(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)數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第36頁。37StatusEvaluateExpression(OperandType&result){InitStack(OPND);Push(OPTR,’#’);InitStack(OPTR);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}

//不是運(yùn)算符則進(jìn)棧

else棧的應(yīng)用（表達(dá)式求值）算法描述數(shù)據(jù)結(jié)構(gòu)第三章棧教材全文共41頁，當(dāng)前為第37頁。38

switch(Precede(GetTop(OPTR),C)){case‘>’://棧頂元素優(yōu)先權(quán)