数据结构-清华大学-殷人昆-03

第3章栈、队列与数组清华大学计算机系殷人昆数据结构课件第三章栈、队列和数组如此巧妙存取如此规整的栈和队列110-2栈表达式求值队列递归多维数组特殊矩阵的压缩存储稀疏矩阵第三章栈、队列与数组110-3只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出(LIFO)栈的主要操作进栈Push(S,x)退栈Pop(S,&x)看栈顶getTop(S,&x)置空栈initStack(S)判栈空，判栈满栈(Stack)退栈进栈a0an-1an-2topbottom110-4栈的数组表示—顺序栈0123456789StackSize-1top(栈空)elem#defineInitSize100#defineIncreament20typedefcharSElemType;typedefstruct{//顺序栈定义SElemType*elem;//栈数组inttop,maxSize;//栈顶指针及栈大小}SeqStack;110-5voidInitStack(SeqStack&S){//初始化S.elem=newSElemType[InitSize];if(S.elem==NULL){printf(“存储分配失败!\n”);exit(1);}S.top=-1;S.maxSize=InitSize;}boolStackEmpty(SeqStack&S){//判断栈是否空？空则返回1，否则返回0returnS.top==-1;}110-6boolStackFull(SeqStack&S){//判断栈是否满？满则返回1，否则返回0returnS.top==S.maxSize-1;}voidPush(SeqStack&S,SElemTypex){//若栈满返回0,否则新元素x进栈并返回1if(StackFull(S))OverFlow(S);//栈满溢出处理S.top++;S.elem[S.top]=x;//加入新元素}110-7voidOverFlow(SeqStack&S){//栈满处理intnewSize=S.maxSize+Increment;SElemType*newS=newSElemType[newSize];if(newS==NULL){printf(“数组创建失败!\n”);exit(1);}for(inti=0;i=S.top;i++)newS[i]=S.elem[i];//向新数组传送数据delete[]S.elem;//释放老数组S.elem=newS;//新数组作为栈数组S.maxSize=newSize;//新数组大小}//栈顶指针不变110-8top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c110-9topc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop栈顶指针指示实际栈顶位置即最后加入新元素的位置110-10boolPop(SeqStack&S,SElemType&x){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))return0;x=S.elem[S.top];S.top--;return1;}boolgetTop(SeqStack&S,SElemType&x){//若栈空返回0,否则栈顶元素读到x并返回1if(StackEmpty(S))return0;x=S.elem[S.top];return1;}110-11top栈的链接表示—链式栈顺序栈有栈满问题，一旦栈满需要做溢出处理，扩充栈空间，时间和空间开销较大。链式栈无栈满问题，只要存储空间还有就可扩充。链式栈的栈顶在链头，插入与删除仅在栈顶处执行。链式栈适合于多栈操作，无需大量移动存储。本课件所述的链式栈无头结点，与教材有不同。110-12链式栈的结构定义typedefintSElemType;//每个栈元素的数据类型typedefstructLinkNode{//栈元素结点定义SElemTypedata;//结点数据structLinkNode*link;//结点链接指针}*LinkStack;//链式栈voidInitStack(LinkStack&S){//栈初始化S=NULL;//栈顶(链头)指针置空}110-13boolStackEmpty(LinkStack&S){//判栈空否returnS==NULL;}voidPush(LinkStack&S,SElemTypex){//进栈LinkNode*p=newLinkNode;if(p==NULL){printf(“结点创建失败!\n”);exit(1);}p-data=x;//结点赋值p-link=S;S=p;//链入栈顶}110-14boolPop(LinkStack&S,SElemType&x){//退栈if(StackEmpty(S))return0;LinkNode*p=S;x=p-data;S=S-link;//摘下原栈顶deletep;return1;//释放原栈顶结点}boolGetTop(LinkStack&S,SElemType&x){//看栈顶元素if(StackEmpty(S))return0;x=S-data;return1;}110-15“混洗”原意是重新洗牌。用在本领域，问题的提法是：当进栈元素的编号为1,2,…,n时，可能的出栈序列有多少种？当进栈序列为1,2时，可能的出栈序列有2种：1,2（进1出1进2出2）和2,1（进1进2出2出1）；当进栈序列为1,2,3时，可能的出栈序列有5种：1,2,3（进1出1进2出2进3出3）1,3,2（进1出1进2进3出3出2）2,1,3（进1进2出2出1进3出3）栈的混洗110-162,3,1（进1进2出2进3出3出1）3,2,1（进1进2进3出3出2出1）注意，3,1,2是不可能的出栈序列，因为若3第1个出栈，栈内一定是1压在2的下面，1不可能先于2出栈。一般情形如何呢？若设进栈序列为1,2,…,n，可能的出栈序列有mn种，则n=0时，m0=1:出栈序列为{}。n=1时，m1=1:出栈序列为{1}。n=2时，m2=2：110-17①出栈序列中1在首位，1左侧有0个数，右侧有1个数，有m0*m1=1种出栈序列：{1,2}②出栈序列中1在末位，1左侧有1个数，右侧有0个数，有m1*m0=1种出栈序列：{2,1}。可能出栈序列有m0*m1+m1*m0=2种。n=3时，m3=5:①出栈序列中1在首位，1左侧有0个数，右侧有2个数，有m0*m2=2种出栈序列：{1,2,3}和{1,3,2}。110-18②出栈序列中1在第2位，1左侧1个数，右侧1个数，有m1*m1=1种出栈序列：{2,1,3}。③出栈序列中1在第3位。1左侧2个数，右侧0个数，有m2*m0=2种出栈序列：{2,3,1}和{3,2,1}。可能的出栈序列有m0*m2+m1*m1+m2*m0=2+1+2=5种。n=4，m4=14:①出栈序列中1在第1位。1左侧0个数，右侧3个数，有m0*m3=5种出栈序列：110-19{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,3,2}。③出栈序列中1在第2位。1左侧1个数，右侧2个数，有m1*m2=2种出栈序列：{2,1,3,4},{2,1,4,3}。④出栈序列中1在第3位。1左侧2个数，右侧1个数，有m2*m1=2种出栈序列：{2,3,1,4},{3,2,1,4}。⑤出栈序列中1在第4位。1左侧3个数，右侧0个数，有m3*m0=5种出栈序列：{2,3,4,1},{2,4,3,1},{3,2,4,1},{3,4,2,1},{4,3,2,1}。110-20可能出栈序列m0*m3+m1*m2+m2*m1+m3*m0=5+2+2+5=14种。一般地，有n个元素按序号1,2,…,n进栈，轮流让1在出栈序列的第1,第2,…第n位，则可能的出栈序列数为：推导结果为：-100121101****ninnninimmmmmmmmC210111*nnniininmm110-21例题：元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A．3B．4C．5D．6解答：选B。如果d在出栈序列中排在开头，a,b,c必须在d出栈前压在栈内，d出栈后它们才可出栈，出栈顺序必须是c,b,a。e可夹在它们之间进栈和出栈。因此，以d开头的出栈序列只可能是d,e,c,b,ad,c,e,b,ad,c,b,e,ad,c,b,a,e110-22表达式求值表达式求值是一种典型的栈的应用。一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。算术表达式有三种表示：中缀(infix)表示操作数操作符操作数，如A+B；前缀(prefix)表示操作符操作数操作数，如+AB；后缀(postfix)表示操作数操作数操作符，如AB+；110-23中缀表达式a+b*(c-d)-e/f后缀表达式abcd-*+ef/-表达式中相邻两个操作符的计算次序为：a)优先级高的先计算；b)优先级相同的自左向右计算；c)当使用括号时从最内层括号开始计算。当使用中缀表达式计算时，需要同时使用两个栈辅助求值；而使用后缀表达式求值，则只需要一个栈，相对简单一些。表达式事例110-24rst1rst2rst3rst4rst5rst6应用后缀表示计算表达式的值从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。计算例abcd-*+ef^g/-abcd-*+ef^g/-110-26通过后缀表示计算表达式值的过程顺序扫描表达式的每一项，根据它的类型做如下相应操作：a)若该项是操作数，则将其压栈；b)若该项是操作符op，则连续从栈中退出两个操作数Y和X，形成运算指令XopY，并将计算结果重新压栈。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。举例abcd-*+ef^g/-110-27步输入类型动作栈内容1置空栈空2a操作数进栈a3b操作数进栈ab4c操作数进栈abc5d操作数进栈abcd6-操作符d、c退栈,计算c-d,结果r1进栈abr17*操作符r1、b退栈,计算b*r1,结果r2进栈ar28+操作符r2、a退栈,计算a+r2,结果r3进栈r3110-28步输入类型动作栈内容9e操作数进栈r3e10f操作数进栈r3ef11^操作符f、e退栈,计算e^f,结果r4进栈r3r412g操作数进栈r3r4g13/操作符g、r4退栈,计算r4/g,结果r5进栈r3r514-操作符r5、r3退栈,计算r3-r5,结果r6进栈r6110-29利用栈将中缀表示转换为后缀表示使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。为了实现这种转换，需要考虑各操作符的优先级。C/C++中操作符的优先级优先级1234567操作符单目-,!*,/,%+,-,=,,===,!=&&||110-30各个算术操作符的优先级isp叫做栈内(instackpriority)优先数icp叫做栈外(incomingpriority)优先数。操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。在把中缀表达式转换为后缀表达式的过程中，需要检查算术运算符的优先级，以实现运算规则。操作符ch#(^*,/,%+,-)isp(栈内)017538icp(栈外)086421110-31中缀表达式转换为后缀表达式的算法操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。重复