李春葆版数据结构课件

第3章栈和队列3.1栈3.2队列本章小结3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用例子3.1栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。3.1.1栈的定义栈顶栈底出栈进栈栈示意图例3.1设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba例3.2设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。例3.3已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。(A)i(B)n-i(C)n-i+1(D)不确定答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:p2=n-1,p3=n-2,…,pn=1推断出pi=n-i+1,所以本题答案为C。例3.4设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。(A)一定是2(B)一定是1(C)不可能是1(D)以上都不对答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。栈的几种基本运算如下:(1)初始化栈InitStack(&s):构造一个空栈s。(2)销毁栈ClearStack(&s):释放栈s占用的存储空间。(3)求栈的长度StackLength(s):返回栈s中的元素个数。(4)判断栈是否为空StackEmpty(s):若栈s为空,则返回真；否则返回假。(5)进栈Push(&S,e):将元素e插入到栈s中作为栈顶元素。(6)出栈Pop(&s,&e):从栈s中退出栈顶元素,并将其值赋给e。(7)取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。(8)显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。3.1.2栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:typedefstruct{ElemTypedata[MaxSize]；inttop；/*栈指针*/}SqStack；顺序栈进栈和出栈示意图在顺序栈中实现栈的基本运算算法:(1)初始化栈initStack(&s)建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s-top=-1;}(2)销毁栈ClearStack(&s)释放栈s占用的存储空间。对应算法如下:voidClearStack(SqStack*&s){free(s);}(3)求栈的长度StackLength(s)返回栈s中的元素个数,即栈指针加1的结果。对应算法如下:intStackLength(SqStack*s){return(s-top+1);}(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s-top==-1。对应算法如下:intStackEmpty(SqStack*s){return(s-top==-1);}(5)进栈Push(&s,e)在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e。对应算法如下:intPush(SqStack*&s,ElemTypee){if(s-top==MaxSize-1)return0;/*栈满的情况,即栈上溢出*/s-top++;s-data[s-top]=e;return1;}(6)出栈Pop(&s,&e)在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。对应算法如下:intPop(SqStack*&s,ElemType&e){if(s-top==-1)return0;/*栈为空的情况,即栈下溢出*/e=s-data[s-top];s-top--;return1;}(7)取栈顶元素GetTop(s)在栈不为空的条件下,将栈顶元素赋给e。对应算法如下:intGetTop(SqStack*s,ElemType&e){if(s-top==-1)return0;/*栈为空的情况,即栈下溢出*/e=s-data[s-top];return1;}(8)显示栈中元素DispStack(s)从栈顶到栈底顺序显示栈中所有元素。对应算法如下:voidDispStack(SqStack*s){inti;for(i=s-top;i=0;i--)printf(%c,s-data[i]);printf(\n);}3.1.3栈的链式存储结构及其基本运算的实现采用链式存储的栈称为链栈,这里采用单链表实现。链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、…、an。链栈示意图链栈中数据结点的类型LiStack定义如下:typedefstructlinknode{ElemTypedata;/*数据域*/structlinknode*next;/*指针域*/}LiStack;在链栈中,栈的基本运算算法如下:(1)初始化栈initStack(&s)建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下:voidInitStack(LiStack*&s){s=(LiStack*)malloc(sizeof(LiStack));s-next=NULL;}^s(2)销毁栈ClearStack(&s)释放栈s占用的全部存储空间。对应算法如下:voidClearStack(LiStack*&s){LiStack*p=s-next;while(p!=NULL){free(s);s=p;p=p-next;}}(3)求栈的长度StackLength(s)从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下:intStackLength(LiStack*s){inti=0;LiStack*p;p=s-next;while(p!=NULL){i++;p=p-next;}return(i);}(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s-next==NULL,即单链表中没有数据结点。对应算法如下:intStackEmpty(LiStack*s){return(s-next==NULL);}^s(5)进栈Push(&s,e)将新数据结点插入到头结点之后。对应算法如下:voidPush(LiStack*&s,ElemTypee){LiStack*p;p=(LiStack*)malloc(sizeof(LiStack));p-data=e;p-next=s-next;/*插入*p结点作为第一个数据结点*/s-next=p;}(6)出栈Pop(&s,&e)在栈不为空的条件下,将头结点后继数据结点的数据域赋给e,然后将其删除。对应算法如下:intPop(LiStack*&s,ElemType&e){LiStack*p;if(s-next==NULL)return0;/*栈空的情况*/p=s-next;/*p指向第一个数据结点*/e=p-data;s-next=p-next;free(p);return1;}(7)取栈顶元素GetTop(s)在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下:intGetTop(LiStack*s,ElemType&e){if(s-next==NULL)return0;/*栈空的情况*/e=s-next-data;return1;}(8)显示栈中元素DispStack(s)从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下:voidDispStack(LiStack*s){LiStack*p=s-next;while(p!=NULL){printf(%c,p-data);p=p-next;}printf(\n);}例3.5假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。解:设置一个括号栈,扫描表达式：遇到左括号(包括(、[和{)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。intcorrect(charexp[],intn){charst[MaxSize];inttop=-1,i=0,tag=1;while(in&&tag){if(exp[i]=='('||exp[i]=='['||exp[i]=='{')/*遇到'('、'['或'{',则将其入栈*/{top++;st[top]=exp[i];}if(exp[i]==‘)’)/*遇到‘)’,若栈顶是‘(’,则继续处理,否则以不配对返回*/if(st[top]=='(')top--;elsetag=0;if(exp[i]==‘]’)/*遇到‘]’,若栈顶是‘[’,则继续处理,否则以不配对返回*/if(st[top]=='[')top--;elsetag=0;if(exp[i]==‘}’)/*遇到‘}’,若栈顶是‘{’,则继续处理,否则以不配对返回*/if(st[top]=='{')top--;elsetag=0;i++;}/*表达式扫描完毕*/if(top-1)tag=0;/*若栈不空,则不配对*/return(tag);}3.1.4栈的应用例子1.表达式求值这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如：1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算xopy之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组str中,其后缀表达式存放在字符型数组exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:while(从exp读取字符ch,ch!='\0'){若ch为数字,将后续的