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

第三章棧?

3.1什么是棧3.2鏈棧

3.3棧的應(yīng)用舉例棧棧一、什么是棧棧：限定僅在一端進(jìn)行插入或刪除操作的線性表ana1a2……...棧底棧頂出棧(彈棧)進(jìn)棧(壓棧)棧s=(a1,a2,……,an)

a1為棧底元素

an為棧頂元素

不含元素的棧稱空棧二、棧的特點根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。

特點

：后進(jìn)先出

也就是說，棧是一種后進(jìn)先出的線性表，簡稱為LIFO(LastInFirstOut)表。例1：有一個棧，進(jìn)棧序列為A、B、C，試給出所有可能的出棧序列。A進(jìn)A出B進(jìn)B出C進(jìn)C出ABC不可能產(chǎn)生輸出序列CABA進(jìn)A出B進(jìn)C進(jìn)C出B出A進(jìn)B進(jìn)B出A出C進(jìn)C出A進(jìn)B進(jìn)B出C進(jìn)C出A出A進(jìn)B進(jìn)C進(jìn)C出B出A出CBAACB

BACBCA例2：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？

43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)

12345的輸出可以實現(xiàn)，壓入一個立即彈出一個即可三、棧的抽象數(shù)據(jù)類型ADTStack{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

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

InitStack(&S)//操作結(jié)果：構(gòu)造一個空棧S。

DestroyStack(&S)

//操作結(jié)果：棧S被銷毀。

ClearStack(&S)

//操作結(jié)果：將S清為空棧

StackEmpty(S)

//操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。

StackLength(S)

//操作結(jié)果：返回S的元素個數(shù)，即棧的長度。

GetTop(S,&e)

//操作結(jié)果：用e返回S的棧頂元素。

Push(&S,e)

//操作結(jié)果：插入元素e為新的棧頂元素。

Pop(&S,&e)

//操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}//ADTStack

3.1什么是棧

3.2鏈棧

3.3棧的應(yīng)用舉例棧棧

3.1什么是棧?

3.2鏈棧

3.3棧的應(yīng)用舉例棧棧一、什么是鏈棧棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈棧。

注意鏈表中指針的方向是從棧頂?shù)綏５?/p>

沒有頭結(jié)點？……棧頂指針S棧頂棧底ana1因為棧的所有操作在棧頂進(jìn)行，所以可以不需要頭結(jié)點,棧頂指針就相當(dāng)于鏈表的頭指針typedef???SElemType

//由實際需要決定typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*LStack;二、鏈棧的結(jié)構(gòu)類型LStackS;//定義指向結(jié)點的指針sStatusInitStack(LStack&S)StatusGetTop(LStackS,SElemType&e)StatusPush(LStack&S,SElemTypee)StatusPop(LStack&S,SElemType&e)二、鏈棧的基本操作

(7鏈棧.cpp)

StatusInitStack(LStack&S){//構(gòu)造一個空棧S

S=NULL;returnOK;}S……

S棧頂棧底ana1一個空的鏈棧什么樣？？？StatusGetTop(LStackS,SElemType&e){//

若棧不空，則用e返回S的棧頂元素，并返回OK,否則返回ERRORS96

if(！S)returnERROR;

e=S->data;returnOK;}StatusPush(LStack&S,SElemTypee)S96pe=22{//插入元素e為新的棧頂元素

LStackp;p=(LStack*)malloc(sizeof(SNode));if(!p)exit(OVERFLOW);p->data=e;p->next=S;S=p;returnOK;}StatusPop(LStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，

//并返回OK；否則返回ERROR}p2S96e=2

LStackp;if(!S)returnERROR;//

s是空棧

e=S->data;p=S;S=p->next;free(p);

returnOK;

3.1什么是棧

3.2順序棧

3.3鏈棧?3.4棧的應(yīng)用舉例棧棧例二、括號匹配的檢驗假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，即（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（）］）均為不正確的格式。檢驗括號是否匹配的方法可用"期待的急迫程度"這個概念來描述。例如考慮下列括號序列：

[([][])]12345678分析可能出現(xiàn)的不匹配的情況:到來的右括弧非是所“期待”的;到來的是“不速之客”;直到結(jié)束，也沒有到來所“期待”的。檢驗括號是否匹配的方法可用"期待的急迫程度"這個概念來描述。4matching.cppstatusmatching(string&exp){intstate=1;//狀態(tài)標(biāo)志1表示正常0表示異常

while(i<=length(exp)&&state){switch(exp[i])//i表達(dá)式的第幾個元素

{case“(":{Push(S,exp[i]);i++;break;}case“)”:{ if(!StackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0;}break;}……}//switch}//whileif(state&&StackEmpty(S))returnOK;elsereturnERROR;}例三、行編輯程序接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。如果每接受一個字符即存入用戶數(shù)據(jù)區(qū)，做法并不恰當(dāng)。較好的做法是，設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。例如，可用一個退格符“#”表示前一個字符無效；可用一個退行符“@”，表示當(dāng)前行中的字符均無效。例如，假設(shè)從終端接受了這樣兩行字符：whli##ilr#e（s#*s)while(*s)outcha@putchar(*s=#++);則實際有效的是下列兩行：while(*s)putchar(*s++);5lineEdit.cppvoid

LineEdit(){InitStack(S); ch=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;