第3章 栈和队列(学生)

2020年5月9日,陈正铭,数据结构,2020年5月9日,3.1栈3.2栈的应用3.3栈与递归3.4队列3.5队列的应用,教学内容,2020年5月9日,第3章栈和队列,掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程,教学目标,2020年5月9日,3.1栈,1.定义,只能在表的一端（栈顶）进行插入和删除运算的线性表,2020年5月9日,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则,4.运算规则,2020年5月9日,栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算栈与一般线性表的区别：仅在于运算规则不同,“进”压入=PUSH（)“出”弹出=POP(),栈与一般线性表的区别,2020年5月9日,“进”压入=PUSH（)“出”弹出=POP(),2020年5月9日,写入：vi=ai读出：x=vi,压入：PUSH(an+1)弹出：POP(x),前提：一定要预设栈顶指针top！,an+1,顺序栈与顺序表,2020年5月9日,顺序栈的表示,空栈base=top是栈空标志stacksize=4,top指示真正的栈顶元素之上的下标地址,栈满时的处理方法：1、报错,返回操作系统。2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。,2020年5月9日,#defineMAXSIZE100typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;,顺序栈的表示,2020年5月9日,构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错误,顺序栈初始化,s,(2)设置栈底和栈顶指针S.top=S.base;,(3)设置栈大小,2020年5月9日,StatusInitStack(SqStack,顺序栈初始化,2020年5月9日,判断顺序栈是否为空,boolStackEmpty(SqStackS)if(S.top=S.base)returntrue;elsereturnfalse;,求顺序栈的长度,intStackLength(SqStackS)returnS.topS.base;,2020年5月9日,StatusClearStack(SqStackS)if(S.base)S.top=S.base;returnOK;,清空顺序栈,2020年5月9日,StatusDestroyStack(SqStack,销毁顺序栈,2020年5月9日,(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1,顺序栈进栈,StatusPush(SqStack,*S.top=e;S.top+;,2020年5月9日,(1)判断是否栈空，若空则出错(2)获取栈顶元素e(3)栈顶指针减1,顺序栈出栈,StatusPop(SqStack,-S.top;e=*S.top;,2020年5月9日,判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素,取顺序栈栈顶元素,StatusGetTop(SqStackS,SElemType,e=*(S.top-);?,2020年5月9日,435612中到了12顺序不能实现；135426可以实现。,1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,练习(经验值200),2020年5月9日,双栈共享一个栈空间,优点：互相调剂，灵活性强，减少溢出机会,具体参考P71算法设计题（1）,2020年5月9日,链栈的表示,运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针,typedefstructStackNodeSElemTypedata;structStackNode*next;StackNode,*LinkStack;LinkStackS;,2020年5月9日,链栈的初始化,voidInitStack(LinkStack,判断链栈是否为空,StatusStackEmpty(LinkStackS)if(S=NULL)returnTRUE;elsereturnFALSE;,2020年5月9日,链栈进栈,e,S,StatusPush(LinkStack,2020年5月9日,链栈出栈,e=A,p,S,2020年5月9日,链栈出栈,StatusPop(LinkStack,e=A,S,2020年5月9日,取链栈栈顶元素,SElemTypeGetTop(LinkStackS)if(S=NULL)exit(ERROR)；elsereturnSdata;,2020年5月9日,3.2栈的应用,例1：数制转换（十转N）用栈暂存低位值例2：括号匹配的检验用栈暂存左括号例3：表达式求值（自学）用栈暂存运算符,简化了程序设计的问题,例1、数制转换算法基于原理：N=(Ndivd)d+Nmodd,例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202,计算顺序,输出顺序,voidconversion()InitStack(S);cinN;while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);cout,x,=,x,x,表3.1算符间的优先关系,2020年5月9日,【算法思想】,（1）初始化OPTR栈和OPND栈，将“#”压入OPTR（2）依次读入字符ch，循环执行（3）至（5）（3）取出OPTR的栈顶元素，当OPTR的栈顶元素和ch均为“#”时，表达式求值完毕，OPND栈顶元素为表达式的值,设定两栈：OPND-操作数或运算结果OPTR-运算符,（4）if(ch是操作数)则ch进OPND，读入下一字符ch,（5）else比较OPTR栈顶元素和ch的优先级,case:运算符ch进OPTR，读入下一字符ch,case=:脱括号（弹出左括号），读入下一字符ch,case:栈顶运算符退栈、计算，结果进OPND,2020年5月9日,北京林业大学信息学院,OperandTypeEvaluateExpression()InitStack(OPND);ch=getchar();while(ch!=#|GetTop(OPTR)!=#)if(!In(ch,OP)Push(OPND,ch);ch=getchar();/ch不是运算符则进栈elseswitch(Precede(GetTop(OPTR),ch)/比较优先权case:/弹出OPTR栈顶的运算符运算，并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;case=:/脱括号并接收下一字符Pop(OPTR,x);ch=getchar();break;/switch/whilereturnGetTop(OPND);/EvaluateExpression,2020年5月9日,2020年5月9日,3.3栈与递归,递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。,2020年5月9日,栈,递归与栈的关系,2020年5月9日,以下三种情况常常用到递归方法递归定义的数学函数具有递归特性的数据结构可递归求解的问题,2020年5月9日,1.递归定义的数学函数:,阶乘函数:,2阶Fibonaci数列:,2020年5月9日,树,2.具有递归特性的数据结构:,Root,Lchild,Rchild,广义表,A=(a,A),3.可递归求解的问题:,迷宫问题Hanoi塔问题,2020年5月9日,分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解,1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的2、可以通过上述转化而使问题简化3、必须有一个明确的递归出口，或称递归的边界,用分治法求解递归问题,必备的三个条件,2020年5月9日,分治法求解递归问题算法的一般形式：voidp(参数表)if（递归结束条件）可直接求解步骤；-基本项elsep（较小的参数）；-归纳项,longFact(longn)if(n=0)return1;/基本项elsereturnn*Fact(n-1);/归纳项,2020年5月9日,在印度圣庙里，一块黄铜板上插着三根宝石针。主神梵天在创造世界时，在其中一根针上穿好了由大到小的64片金片，这就是汉诺塔。僧侣不停移动这些金片，一次只移动一片，小片必在大片上面。当所有的金片都移到另外一个针上时，世界将会灭亡。,汉诺塔,2020年5月9日,规则:,(1)每次只能移动一个圆盘,(2)圆盘可以插在A,B和C中的任一塔座上,(3)任何时刻不可将较大圆盘压在较小圆盘之上,Hanoi塔问题,2020年5月9日,Hanoi塔问题,n=1，则直接从A移到C。否则,(1)用C柱做过渡，将A的(n-1)个移到B(2)将A最后一个直接移到C(3)用A做过渡，将B的(n-1)个移到C,2020年5月9日,#includeintc=0;voidmove(charx,intn,charz)cout+c,n,x,zlink；Btop=top-link;x=top-link；Cx=top;top=top-link；Dx=top-link；（5）设有一个递归算法如下intfact(intn)/n大于等于0if(n=0)return1;elsereturnn*fact(n-1);则计算fact(n)需要调用该函数的次数为（）。An+1Bn-1CnDn+2（6）栈在（）中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有,进阶任务2（完成每任务加经验值100）,（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A队列B栈C线性表D有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2B3C4D6（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。Atop不变Btop=0Ctop-Dtop+,进阶任务2（完成每任务加经验值100）,（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构B队列C.线性表的链式存储结构D.栈（11）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改（12）循环队列存储在数组A0.m中，则入队时的操作为（）A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1),进阶任务2（完成每任务加经验值100）,（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)%n=frontB.rear=frontCrear+1=frontD.(rear-l)%n=front（14）栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点（15）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分,2020年5月9日,（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈),算法设计题,进阶任务2（完成每任务加经验值200）,2020年5月9日,intIsHuiwen(char*t)/判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(/比较完毕均相等则返回1,任务：请同学们把本题用c语言程序实现，并在实验课验证之（经验值200）,2020年5月9日,（10）已知f为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的递归算法：求链表中的最大整数；求链表的结点个数；求所有整数的平均值。,算法设计题,进阶任务2（完成每子任务加经验值200）,2020年5月9日,voidmain()LinkListL;CreatList(L);coutnext)data;elseintmax=GetMax(p-next);returnp-data=max?p-data:max;,提示,2020年5月9日,intNum(ListNode*f)/递归算法:求链表中结点个数if(f=NULL)return0;/空表,返回0return1+Num(f-link);/否则,返回后继链表结点个数加1floatAvg