《栈和队列栈》PPT课件.ppt

1、带头结点的单链表为空的判定条件是（哈尔滨工业大学）A.H=NULLB.H-next=NULLC.H-next=HD.H!=NULL,2、将图中S结点加到P所指结点之后，其语句是：(浙江大学)A.s-next=p+1 p-next=sB.(*p).next=s(*s).next=(*p).nextC.s-next=p-next p-next=s-nextD.s-next=p-next p-next=s,3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）线性表采用顺序储存，必须占用一片连续的存储单元线性表采用顺序储存，便于进行插入和删除操作线性表采用链式储存，不必占用一片连续的储存单元线性表采用链式储存，便于插入和删除操作4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学）A 顺序表B 双向链表C 单链表,5.线性表的逻辑顺序和物理顺序总是一致的这种说法A 正确 B 不正确6.线性表若是采用链式存储，要求内存中可用存储单元的地址A 必须连续 B 部分地址必须连续C 一定是不连续的 D 连续不连续都可以7.非空循环单链表L的尾结点P满足A.p-next=NULLB.p=NULLC.p-next=LD.p=L,本章小结线性表的顺序表示与链式表示:从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1),结论,在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储总之，两种情况各有优缺点，应看具体情况进行讨论。,第3章 栈和队列,3.1 栈,3.2 队列,本章小结,栈和队列的逻辑结构和物理结构，以及他们之间的相互关系定义与之相适应的算法设计相应的算法分析算法的效率,3.1 栈3.1.1 栈的定义3.1.2 栈的顺序存储结构及其基本运算的实现3.1.3 栈的链式存储结构及其基本运算的实现3.1.4 栈的应用例子,栈是一种操作受限的线性表。栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。,3.1.1 栈的定义,栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。数据的插入操作通常称为进栈或入栈,数据的删除操作通常称为退栈或出栈。,栈顶top,栈底botton,出栈,进栈,栈示意图,栈是一种限制存取点的线性结构，即只允许在栈顶进行出栈和入栈的操作。所以，栈还叫做“后进先出”表,例3.1 设一个栈的输入序列为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.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学),A 23415B 54132C 23145D 15432,答案：B,例3.3 设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。,顺序栈进栈和出栈示意图,TOP 栈指针代表的是物理位序 dataMaxSize栈空 TOP=-1栈满 TOP=MaxSize-1 思考：如何表示栈顶元素?,栈的几种基本运算如下:初始化栈InitStack():构造一个空栈s。进栈Push(s,e):将元素e插入到栈s中作为栈顶元素(3)求栈的长度StackLength(s):返回栈s中的元素个数。(4)判断栈是否为空StackEmpty(s):若栈s为空,则返回1；否则返回0。,(5)出栈Pop(s,&e):从栈s中退出栈顶元素,并将其值赋给e。(6)取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。(7)显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。(8)销毁栈ClearStack(s):释放栈s占用的存储空间。,3.1.2 栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:typedef struct ElemType dataMaxSize；int top；/*栈指针*/SqStack；,在顺序栈中实现栈的基本运算算法:(1)初始化栈initStack()建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:SqStack*InitStack(void)s=(SqStack*)malloc(sizeof(SqStack);s-top=-1;return s;,(2)进栈Push(s,e)算法思想：若栈满返回 0；在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e，返回1。int Push(SqStack*s,ElemType e)if(s-top=MaxSize-1)return 0;/*栈满的情况,即栈上溢出*/s-top+;s-datas-top=e;return 1;,A b c d e,(3)显示栈中元素DispStack(s)从栈顶到栈底顺序显示栈中所有元素。对应算法如下:void DispStack(SqStack*s)int i;for(i=s-top;i=0;i-)printf(%c,s-datai);printf(n);,(4)求栈的长度StackLength(s)返回栈s中的元素个数,即栈指针加1的结果。对应算法如下:int StackLength(SqStack*s)return(s-top+1);,(5)判断栈是否为空StackEmpty(s)栈S为空的条件是s-top=-1。对应算法如下:int StackEmpty(SqStack*s)return(s-top=-1);,(6)出栈Pop(s,(7)取栈顶元素GetTop(s,(8)销毁栈ClearStack(,编写一个程序exam3-1，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能,初始化栈s;判断栈s是否非空;依次进栈元素a,b,c,d,e;判断栈s是否非空;输出栈的长度;输出从栈顶到栈底元素;输出出栈序列;判断栈s是否为空;释放栈.,3.1.3 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型LiStack定义如下:typedef struct linknode ElemType data;/*数据域*/struct linknode*next;/*指针域*/LiStack;,在链栈中,栈的基本运算算法如下:(1)初始化栈initStack(,(2)进栈Push(,(3)求栈的长度StackLength(s)从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下:int StackLength(LiStack*s)int i=0;LiStack*p;p=s-next;while(p!=NULL)i+;p=p-next;return(i);,(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s-next=NULL,即单链表中没有数据结点。对应算法如下:int StackEmpty(LiStack*s)return(s-next=NULL);,s,(5)显示栈中元素DispStack(s)从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下:void DispStack(LiStack*s)LiStack*p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);,(6)出栈Pop(,(7)取栈顶元素GetTop(s)在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下:int GetTop(LiStack*s,ElemType,(8)销毁栈ClearStack(,编写一个程序exam3-2，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能,初始化链栈s;判断链栈s是否非空;依次进链栈元素a,b,c,d,e;判断链栈s是否非空;输出链栈的长度;输出从栈顶到栈底元素;输出出链栈序列;判断链栈s是否为空;释放链栈.,exam3-3 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。,解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,int correct(LiStack*,3.1.4 栈的应用例子 1.exam3-4表达式求值 这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。,在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如：1+2*3 就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。,所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。,算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组str中,其后缀表达式存放在字符型数组exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组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)”,其转换成后缀表达式的过程 如下：,将算术表达式str转换成后缀表达式expvoid trans(char str,char exp)structchar dataMaxSize;/*存放运算符*/int top;/*栈指针*/op;/*定义运算符栈*/char ch;int i=0,t=0;/*t作为exp的下标,i作为str的下标*/op.top=-1;ch=stri;i+;,while(ch!=0)/*str表达式未扫描完时循环*/switch(ch)case(:/*判定为左括号*/op.top+;op.dataop.top=ch;break;case):/*判定为右括号*/while(op.dataop.top!=()expt=op.dataop.top;op.top-;t+;op.top-;break;case+:case-:/*判定为加或减号*/while(op.top!=-1,case*:case/:/*判定为*或/号*/while(op.dataop.top=*|op.dataop.top=/)expt=op.dataop.top;op.top-;t+;op.top+;op.dataop.top=ch;break;case:break;/*过滤掉空格*/default:while(ch=0,while(op.top!=-1)/*此时str扫描完毕,栈不空时循环*/expt=op.dataop.top;t+;op.top-;expt=0;/*给exp表达式添加结束标识*/,下面对后缀表达式求值。在后缀表达式求值算法中要用到一个数值栈st,该算法实现过程如下:后缀表达式存放在字符型数组exp中,从头开始依次扫描这个后缀表达式,当遇到运算数时,就把它插入到数值栈st中；当遇到运算符时,就执行两次退栈,并根据该运算符对退栈的数值进行相应的运算,再把结果入栈st。重复上述过程,直至后缀表达式exp扫描完毕,此时数值栈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 exp)/*计算后缀表达式的值*/struct float dataMaxSize;/*存放数值*/int top;/*栈指针*/st;/*定义数值栈*/float d;char ch;int t=0;/*t作为exp的下标*/st.top=-1;ch=expt;t+;while(ch!=0)/*exp字符串未扫描完时循环*/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,2.求解迷宫问题 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。,为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下:int mgM+1N+1=/*M=10,N=10*/1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;,对于迷宫中的每个方块,有上下左右四个方块相邻,如图3.4所示,第i行第j列的当前方块的位置为(i,j),规定上方方块为方位0,顺时针方向递增编号。在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中,为此,将栈定义为:struct int i;/*当前方块的行号*/int j;/*当前方块的列号*/int di;/*di是下一可走方位的方位号*/StackMaxSize;/*定义栈*/int top=-1;/*初始化栈指针*/,求解迷宫(1,1)到(M-2,N-2)路径的过程是:先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中方块即为路径。否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。,void mgpath()/*路径为:(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+;/*初始方块进栈*/Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while(top-1)/*栈不空时循环*/i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if(i=M-2,find=0;while(di4,if(find=1)/*找到了下一个可走方块*/Stacktop.di=di;/*修改原栈顶元素的di值*/top+;/*下一个可走方块进栈*/Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;mgij=-1;/*避免重复走到该方块*/else/*没有路径可走,则退栈*/mgStacktop.iStacktop.j=0;/*让该位置变为其他路径可走方块*/top-;printf(没有可走路径!n);,