第3章栈和上机作业

第3章栈和队列3.1栈3.2队列3.3本章小结3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用例子3.1栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。3.1.1栈的定义图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)顺序栈进栈和出栈示意图栈的几种基本运算如下:(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.4编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。解intsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;InitStack(st);For(i=0;str[i]!=‘\0’;i++);Push(st,str[i]);For(i=0;str[i]!=‘\0’;i++);{Pop(st,e);if(str[i]!=e)Return(0);}Return(1);}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;*q=s-next;while(q!=NULL){free(p);p=q;q=p-next;}free(p);}(3)求栈的长度StackLength(s)从第一个数据结点开始扫描单链表,用n记录访问的数据结点个数,最后返回n值。对应算法如下:intStackLength(LiStack*s){intn=0;LiStack*p;p=s-next;while(p!=NULL){n++;p=p-next;}return(n);}(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编写一个算法判断输入的表达式中括号是否匹配（假设只有左、右圆括号）。解:intMatch(charexp[],intn){inti=0;chare;SqStack*st;InitStack(st);while(in){if(exp[i])==‘（’;Push(st,exp[i]);elseif(exp[i]==‘)’){if(GetTop(st,e)==1){if(e!=‘(’)return(0)elsePop(st,e);}elsereturn(0);}i++;}if(StackEmpty(st)==1)return(1);elseReturn(0);}3.1.4栈的应用例子1.表达式求值这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如：1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算xopy之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组exp中,其后缀表达式存放在字符型数组postexp中.在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:while(从exp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#”标志数值串结束。若ch为左括号“(”,则将此括号进栈到运算符栈op中。若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。若ch运算符优先级小于或等于op栈顶运算符的优先级(除栈顶运算符为“(”外),则依次出栈并存入到postexp中,然后将ch进栈。}中缀表达式后缀表达式若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。对于表达式“(56-20)/(4+2)”,其转换成后缀表达式的过程如下：exp操作过程oppostexp(56-20)/(4+2)遇到ch为“(”,将此括号进栈op。(56-20)/(4+2)遇到ch为数字,将56存入postexp中,并插入一个字符“#”。(56#-20)/(4+2)遇到ch为“-”,由于op中“(”以前没有字符,则直接将ch进栈op中。(-56#20)/(4+2)遇到ch为数字,将20#存入数组exp中。(-56#20#exp操作过程oppostexp)/(4+2)遇到ch为“)”,则将栈op中“(”以前的字符依次出栈并存入postexp中,然后将“(”删除。56#20#-/(4+2)遇到ch为“/”,将将ch进栈op中。/56#20#-(4+2)遇到ch为“(”,将此括号进栈op中。/(56#20#-4+2)遇