的数据结构第三章栈

第三章栈☞

3.1什么是栈3.2链栈

3.3栈的应用举例栈栈一、什么是栈栈：限定仅在一端进行插入或删除操作的线性表ana1a2……...栈底栈顶出栈(弹栈)进栈(压栈)栈s=(a1,a2,……,an)

a1为栈底元素

an为栈顶元素

不含元素的栈称空栈二、栈的特点根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

特点

：后进先出

也就是说，栈是一种后进先出的线性表，简称为LIFO(LastInFirstOut)表。例1：有一个栈，进栈序列为A、B、C，试给出所有可能的出栈序列。A进A出B进B出C进C出ABC不可能产生输出序列CABA进A出B进C进C出B出A进B进B出A出C进C出A进B进B出C进C出A出A进B进C进C出B出A出CBAACB

BACBCA例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？

43512不可能实现，主要是其中的12顺序不能实现

12345的输出可以实现，压入一个立即弹出一个即可三、栈的抽象数据类型ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an端为栈顶，a1端为栈底。基本操作：

InitStack(&S)//操作结果：构造一个空栈S。

DestroyStack(&S)

//操作结果：栈S被销毁。

ClearStack(&S)

//操作结果：将S清为空栈

StackEmpty(S)

//操作结果：若栈S为空栈，则返回TRUE，否则FALSE。

StackLength(S)

//操作结果：返回S的元素个数，即栈的长度。

GetTop(S,&e)

//操作结果：用e返回S的栈顶元素。

Push(&S,e)

//操作结果：插入元素e为新的栈顶元素。

Pop(&S,&e)

//操作结果：删除S的栈顶元素，并用e返回其值。}//ADTStack

3.1什么是栈

3.2链栈

3.3栈的应用举例栈栈

3.1什么是栈☞

3.2链栈

3.3栈的应用举例栈栈一、什么是链栈栈的链式存储结构简称为链栈。

注意链表中指针的方向是从栈顶到栈底

没有头结点？……栈顶指针S栈顶栈底ana1因为栈的所有操作在栈顶进行，所以可以不需要头结点,栈顶指针就相当于链表的头指针typedef???SElemType

//由实际需要决定typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*LStack;二、链栈的结构类型LStackS;//定义指向结点的指针sStatusInitStack(LStack&S)StatusGetTop(LStackS,SElemType&e)StatusPush(LStack&S,SElemTypee)StatusPop(LStack&S,SElemType&e)二、链栈的基本操作

(7链栈.cpp)

StatusInitStack(LStack&S){//构造一个空栈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栈的应用举例栈栈例二、括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（）］）均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：

[([][])]12345678分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;直到结束，也没有到来所“期待”的。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。4matching.cppstatusmatching(string&exp){intstate=1;//状态标志1表示正常0表示异常

while(i<=length(exp)&&state){switch(exp[i])//i表达式的第几个元素

{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;}例三、行编辑程序接受用户从终端输入的程序或数据，并存入用户的数据区。如果每接受一个字符即存入用户数据区，做法并不恰当。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，可用一个退格符“#”表示前一个字符无效；可用一个退行符“@”，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：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为全文结束符

{

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

{case‘#’:Pop(S,c);break;//仅当栈非空时退栈

case'@':ClearStack(S);break;//重置S为空栈

default

:Push(S,ch);break;