第1章--栈(C++版).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 栈,栈是只能在某一端插入和删除的特殊线性表。,用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。,栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（,PUSH,），删除则称为退栈（,POP,）。栈也称为后进先出表（,LIFO,表）。,一个栈可以用定长为的数组来表示，用一个栈指针,TOP,指向栈顶。若,TOP,0,，表示栈空，,TOP=N,时栈满。进栈时,TOP,加。退栈时,TOP,减。当,TOP0,时为下溢。栈指针在运算中永远指向栈顶。,1,、进栈（,PUSH,）算法,若,TOP,时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作,）；,TOP+,（栈指针加，指向进栈地址）；,STOP=X,，结束（,X,为新进栈的元素）；,2,、退栈（,POP,）算法,若,TOP0,，则给出下溢信息，作出错处理,(,退栈前先检查是否已为空栈，空则下溢；不空则作,),；,X=STOP,，（退栈后的元素赋给,X,）；,TOP-,，结束（栈指针减，指向栈顶）。,进栈、出栈的,c+,实现过程程序：,#define n 100,void push(int s,int*top,int,*x)/,入栈,if(*top=n)printf(overflow,);,else (*top)+;s*top=*x;,void pop(int s,int*y,int,*top)/,出栈,if(*top=0)printf(underflow,);,else *y=s*top;(*top)-;,对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。,堆栈的数组模拟,十进制数,N,和其它,d,进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：,N=(N/d)d,N%d,（其中,/,为整除运算，,%,为求余运算）。,例如：,(1348),10,(2504),8,运算过程如下：,N,N/8,N%8,9413,N,N/8,N%8,1348,168,4,168,21,0,21,2,5,2,0,2,1,、填空：,(9413)10=()8=()16=()2,2,、数制转化程序,#include,#include,using namespace std;,#define size 100,int,asize+1,n,d,i=0,j;,main(),coutn;,coutd;,do,a+i=n%d,;,n=n/d,;,while(n,!=0);,for(j=i;j=1;j-)coutaj,;,return 0;,3,、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。,如果进站的车厢序列为,123,，则可能的出站车厢序列是什么？,如果进站的车厢序列为,123456,，问能否得到,135426,和,435612,的出站序列。,【例,1,】括号的匹配（表达式的合法性检查）,【问题描述,】,假设一个表达式有英文字母（小写）、运算符（,+,，,，,*,，,/,）和左右小（圆）括号构成，以“,”,作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“,YES”,；否则返回“,NO”,。假设表达式长度小于,255,，左圆括号少于,20,个。,【算法分析,】,假设输入的字符串存储在,c,中（,char c256,）。,我们可以定义一个栈：,char smaxn+1;,int,top;,用它来存放表达式中从左往右的左圆括号（,maxn,=20,）。,算法的思路为：顺序（从左往右）扫描表达式的每个字符,ci,，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“,NO”,；否则表示匹配，返回“,YES”,。,#include,#include,using namespace std;,#define maxn,20,char c256;,bool judge(char,c256),int,top=0,i=0;,while(ci,!=),if(ci,=()top+;,if(ci,=),if(top0)top-;,else return 0;,i+;,if(top!=0)return 0;/,检测栈是否为空。不空则说明有未匹配的括号,else return 1;,main(),scanf(%s,c,);,if(judge(c)printf(YES,);,else printf(NO,);,return 0;,【例,2,】编程求一个后缀表达式的值,【问题描述,】,从键盘读入一个后缀表达式（字符串），只含有,0-9,组成的运算数及加（,+,）、减（,）、乘（,*,）、除（,/,）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以,作为结束标志。,【算法分析,】,后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。,比如，,169*(4+3),转换成后缀表达式为：,16943+*,，在字符数组,A,中的形式为：,栈中的变化情况：,运行结果：,-47,#include,#include,#include,#include,using namespace std;,int,stack101;,char s256;,int comp(char,s256),int,i=0,top=0,x,y;,while(i=strlen(s)-2),switch(si,),case+:stack-top+=stacktop+1;break;,case-:stack-top-=stacktop+1;break;,case*:stack-top*=stacktop+1;break;,case/:stack-top/=stacktop+1;break;,default:x=0;while(si!=)x=x*10+si+-0;stack+top,=x;break;,i+;,/while,return stacktop,;,main(),printf(input a string(_over,):);,gets(s,);,printf(result=%d,comp(s,);,return 0;,【例,3,】车厢调度,【问题描述,】,有一个火车站，铁路如图所示，,每辆火车从,A,驶入，再从,B,方向驶出，同时它的车厢可以重新组合。假设从,A,方向驶来的火车有,n,节（,n=1000,），分别按照顺序编号为,1,，,2,，,3,，,，,n,。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到,B,处的铁轨上。另外假定车站,C,可以停放任意多节车厢。但是一旦进入车站,C,，它就不能再回到,A,方向的铁轨上了，并且一旦当它进入,B,方向的铁轨，它就不能再回到车站,C,。,负责车厢调度的工作人员需要知道能否使它以,a1,a2,an,的顺序从,B,方向驶出，请来判断能否得到指定的车厢顺序。,【输入,】,输入文件的第一行为一个整数,n,，其中,n=1000,，表示有,n,节车厢，第二行为,n,个数字，表示指定的车厢顺序。,【输出,】,如果可以得到指定的车厢顺序，则输出一个字符串,”,YES”,，否则输出”,NO”,（注意要大写，不包含引号）。,【输入样例,】,5,5 4 3 2 1,【输出样例,】,YES,分析：,该题就是前面思考题的一部分。车站,C,相当于一个栈。我们用模拟法来做，假设我们已经处理了前,i-1,节从,B,方向驶出的车厢，我们现在要让,ai,驶出。若,ai,不在车站,C,中，我们就让若干车厢从,A,方向驶入车站,C,，直到,ai,驶入，再将它从,B,方向驶出；若,ai,在车站,C,中，如果它是车站,C,中停在最前面的，则将它从,B,方向驶出，否则原问题无解。,如样例中，出栈序列是,3 5 4 2 1,，模拟过程如下：,一开始栈为空,由于,3,不在栈中，就需要把,1,2,3,依次进栈，再出栈，这样符合出栈序列第一个数是,3,，当前栈为,1,2,第,2,个出栈的是,5,5,不在栈中，则就把,4,5,压栈，再出栈就可以得到,5,，此时栈为,1,2,，,4,第,3,个出栈的是,4,，正好是栈顶元素，直接出栈，栈变为,1,2,第,4,个出栈的是,2,，正好是栈顶元素，直接出栈，栈变为,2,第,5,个出栈的是,1,，正好是栈顶元素，直接出栈，栈变为,在模拟过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况，所以该方案可行。,【参考程序,】,#include,#include,#include,using namespace std;,const int,N=1010;,int stackN,aN;int top,n,;,int,main(),cin n;,for(int i=1;i ai;,top=0;,for(int i=1,cur=1;i=n;+i)/cur,为当前要从,A,方向驶入的车厢号,while(cur=ai),stack+top=cur+;,if(stacktop=ai,),-top;,else,cout NO endl,;,return 0;,cout YES()(),()(),()()(),()()(),【输出标例,】,YES,YES,YES,YES,NO,4,、计算,(calc.cpp,),【问题描述,】,小明在你的帮助下，破密了,Ferrari,设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“,(”,，“,)”,，“,0-9”,，“,+”,，“,-”,，“,*”,，“,/”,，“,”,求出的值就是密码。小明数学学得不好，还需你帮他的忙。,(“/”,用整数除法,),【输入,】,输入文件,calc.in,共,1,行，为一个算式。,【输出,】,输出文件,calc.out,共,1,行，就是密码。,【输入样例,】,calc,.in,1+(3+2)*(72+6*9)/(2),【输出样例,】,calc,.out,258,【限制,】,100%,的数据满足：算式长度,=30,其中所有数据在,231-1,的范围内。,5,、车厢调度,(train.cpp,),【问题描述,】,有一个火车站，铁路如图所示，,每辆火车从,A,驶入，再从,B,方向驶出，同时它的车厢可以重新组合。假设从,A,方向驶来的火车有,n,节（,n=1000,），分别按照顺序编号为,1,，,2,，,3,，,，,n,。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到,B,处的铁轨上。另外假定车站,C,可以停放任意多节车厢。但是一旦进入车站,C,，它就不能再回到,A,方向的铁轨上了，并且一旦当它进入,B,方向的铁轨，它就不能再回到车站,C,。,负责车厢调度的工作人员需要知道能否使它以,a1,a2,an,的顺序从,B,方向驶出，请来判断能否得到指定的车厢顺序。,【输入,】,train.in,输入文件的第一行为一个整数,n,，其中,n=1000,，表示有,n,节车厢，第二行为,n,个数字，表示指定的车厢顺序。,【输出,】,train.out,如果可以得到指定的车厢顺序，则输出一个字符串”,YES”,，否则输出”,NO”,（注意要大写，不包含引号）。,【输入样例,】,5,5 4 3 2 1,【输出样例,】,YES,6,、中缀表达式值,(Expr.cpp,),【问题描述,】,输入一个中缀表达式（由,0-9,组成的运算数、加,+,减,乘,*,除,/,四种运算符、左右小括号组成。注意“,”,也可作为负数的标志，表达式以“,”,作为结束符），判断表达式是否合法，如果不合法，请输出“,NO”,；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。,注意：必须用栈操作，不能直接输出表达式的值。如果再考虑是实数运算呢？,【输入文件,】,Expr,.in,输入文件的第一行为一个以,结束的字符串。,【输出文件,】,Expr,.,out,如果表达式不合法，请输出“,NO”,，要求大写。,如果表达式合法，请输出计算结果。,【输入样例,】,1,289,【输出样例,】,8,