《第3章栈和上机作业》由会员分享，可在线阅读，更多相关《第3章栈和上机作业（56页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,3.1 栈,3.2 队列,3.3 本章小结,3.1.1 栈的定义 3.1.2 栈的顺序存储结构及 其基本运算实现 3.1.3 栈的链式存储结构及其 基本运算的实现 3.1.4 栈的应用例子,3.1 栈,栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,3.1.1 栈的定义,顺序栈进栈和出栈示意图,栈的几种基本运算如下: (1) 初始化栈Ini
2、tStack(&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 栈的顺序存储
3、结构及其基本运算实现 假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack: typedef struct ElemType dataMaxSize； int top； /*栈指针*/ SqStack；,在顺序栈中实现栈的基本运算算法: (1) 初始化栈initStack( ,顺序栈进栈和出栈示意图,(2) 销毁栈ClearStack( ,(3) 求栈的长度StackLength(s) 返回栈s中的元素个数,即栈指针加1的结果。对应算法如下: int StackLength(SqStack *s) return(
4、s-top+1); ,(4) 判断栈是否为空StackEmpty(s) 栈S为空的条件是s-top=-1。对应算法如下: int StackEmpty(SqStack *s) return(s-top=-1); ,(5) 进栈Push( ,(6) 出栈Pop( ,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将栈顶元素赋给e。对应算法如下: int GetTop(SqStack *s,ElemType ,(8) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应算法如下: void DispStack(SqStack *s) int i; for(i=s-
5、top;i=0;i-) printf(“%c “,s-datai); printf(“n“); ,例3.4 编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。 解 int symmetry(ElemType str) int i; ElemType e;SqStack *st; InitStack(st); For(i=0;stri!=0;i+); Push(st,stri); For(i=0;stri!=0;i+); Pop(st,e); if(stri!=e) Return(0); Return(1);,3.1.3 栈的链式存储结构及其基本运
6、算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型LiStack定义如下: typedef struct linknode ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ LiStack;,在链栈中,栈的基本运算算法如下: (1) 初始化栈initStack( ,(2) 销毁栈ClearS
7、tack( ,(3) 求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表,用n记录访问的数据结点个数,最后返回n值。对应算法如下: int StackLength(LiStack *s) int n=0; LiStack *p; p=s-next; while(p!=NULL) n+;p=p-next; return(n); ,(4) 判断栈是否为空StackEmpty(s) 栈S为空的条件是s-next=NULL,即单链表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) return(s-next=NULL); ,s,(5) 进栈Pus
8、h( ,(6) 出栈Pop( ,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下: int GetTop(LiStack *s,ElemType ,(8) 显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(“%c “,p-data); p=p-next; printf(“n“); ,例3.5 编写一个算法判断输入的表达式中括号是否匹配（
9、假设只有左、右圆括号）。 解 :int Match(char exp,int n) int i=0; char e;SqStack *st; InitStack(st); while(in) if(expi)=（; Push(st,expi); else if(expi=) if(GetTop(st,e)=1) if(e!=() return(0) else Pop(st,e); else return(0); i+; if(StackEmpty(st)=1) return(1); else Return(0);,3.1.4 栈的应用例子 1. 表达式求值 这里限定的表达式求值问题是:用户输入
10、一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。,在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如： 1+2*3 就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。,所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。 对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数
11、,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。,算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。 假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组exp中,其后缀表达式存放在字符型数组postexp中.在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:,while (从exp读取字符ch,ch!=0) 若ch为数字,将后续的所有数字均依次存放到pos
12、texp中,并以字符“#”标志数值串结束。 若ch为左括号“(”,则将此括号进栈到运算符栈op中。 若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。 若ch运算符优先级小于或等于op栈顶运算符的优先级(除栈顶运算符为“(”外),则依次出栈并存入到postexp中,然后将ch进栈。 ,中缀表达式后缀表达式,若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。,对于表达式“(56-20)/(4+2)”,其转换成后缀表达式的过程 如下：,将算术表达式exp转换
13、成后缀表达式postexp void trans(char exp, char postexp) struct char dataMaxSize;/*存放运算符*/ int top; /*栈指针*/ op; /*定义运算符栈*/ char ch; int i=0,t=0; /*i作为exp的下标,t作为postexp的下标*/ op.top=-1; ch=expi;i+;,while(ch!=0)/*exp表达式未扫描完时循环*/ switch(ch) case (: /*判定为左括号*/ op.top+; op.dataop.top=ch; break; case ): /*判定为右括号*/
14、 while (op.dataop.top!=() postexpt=op.dataop.top; op.top-; t+; op.top-; break;,case +: case -: /*判定为加或减号*/ while(op.top!=-1,case :break; /*过滤掉空格*/ default: while(ch=0 ,while (op.top!=-1) /*此时exp扫描完毕,栈不空时循环*/ postexpt=op.dataop.top; t+; op.top-; postexpt=0; /*给postexp表达式添加结束标识*/ ,下面对后缀表达式求值。在后缀表达式求值算
15、法中要用到一个数值栈st,该算法实现过程如下: 后缀表达式存放在字符型数组postexp中,从头开始依次扫描这个后缀表达式,当遇到运算数时,就把它插入到数值栈st中；当遇到运算符时,就执行两次退栈,并根据该运算符对退栈的数值进行相应的运算,再把结果入栈st。重复上述过程,直至后缀表达式postexp扫描完毕,此时数值栈st中栈顶的数值即为表达式的值。,while (从postexp读取字符ch,ch!=0) 若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。 若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。 若ch为“”,则从数值栈st中退栈两个运算数,相减后进栈st中。 若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。 若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中(若除数为零,则提示相应的错误信息)。 若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。,对后缀表达式求值,对于后缀表达式“56#20#-4#2#+/”的求值过程如下：,float compvalue(char postexp)/*计算后缀表达式的值*/ struct float dataMaxSize;/*存放数值*/ int top; /*
