第3章栈和上机作业课件.ppt

第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) 初始化栈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: typedef struct ElemType dataMaxSize； int top；/*栈指针*/ SqStack；,在顺序栈中实现栈的基本运算算法: (1) 初始化栈initStack( ,顺序栈进栈和出栈示意图,(2) 销毁栈ClearStack( ,(3) 求栈的长度StackLength(s) 返回栈s中的元素个数,即栈指针加1的结果。对应算法如下: int StackLength(SqStack *s) return(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-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 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型LiStack定义如下: typedef struct linknode ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ LiStack;,在链栈中,栈的基本运算算法如下:(1) 初始化栈initStack(,(2) 销毁栈ClearStack(,(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) 进栈Push(,(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 编写一个算法判断输入的表达式中括号是否匹配（假设只有左、右圆括号）。解 :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. 表达式求值 这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。,在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如： 1+2*3 就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。,所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。 对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。,算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。 假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组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转换成后缀表达式postexpvoid 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 ): /*判定为右括号*/ 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表达式添加结束标识*/,下面对后缀表达式求值。在后缀表达式求值算法中要用到一个数值栈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; /*栈指针*/ st; /*定义数值栈*/ float d;char ch;int t=0; /*t作为postexp的下标*/ st.top=-1; ch=postexpt; t+;,while(ch!=0)/*postexp字符串未扫描完循环*/ switch (ch) case +: st.datast.top-1=st.datast.top-1+st.datast.top; st.top-;break; case -: st.datast.top-1=st.datast.top-1-st.datast.top; st.top-;break; case *: st.datast.top-1=st.datast.top-1*st.datast.top; st.top-;break;,case /: if (st.datast.top!=0)st.datast.top-1=st.datast.top-1/st.datast.top; else printf(nt除零错误!n);exit(0);/*异常退出*/ st.top-;break;,default: d=0; /*将数字字符转换成数值存放到d中*/ while(ch=0 ,上机时间,10月15日下午13:00到16:00 线性表综合实验10月24日上午3,4节 栈与队列实验10月31日上午3,4节 字串与递归实验11月19日下午13:00到16:00 树综合实验12月17日下午13:00到16:00 图综合实验,实验内容 1通讯录设计：设计一个班级同学的通讯录，要求如下：通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。程序主菜单包含以下几个功能：1 添加记录:通过键盘输入信息，添加一条通讯录记录。2 删除记录:通过键盘输入学号，删除该学号的记录。3 输出记录:输出通讯录全部记录。4 按姓名查找:通过键盘输入姓名，输出该同学的所有信息。5 保存记录:把通讯录中所有的记录保存到文件中。6 清空记录:删除通讯录中的全部记录，并删除文件。7 退出,提示：程序启动时应判断是否存在记录文件，如果存在，则读取每条记录到链表中。用户选择并完成主菜单某功能后，除了退出程序，应该返回主菜单。添加一条记录时，插入到链表的尾部。查找、删除记录时，如果该记录不存在，则应该输出不存在的提示。添加记录、删除记录时不需要写文件。保存记录时，用覆盖写文件的方法。（或者先删除原文件，再保存全部记录信息）各个功能模块写成函数，由主函数调用。,实验内容 2 求解迷宫问题 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。,