数据结构栈.ppt

栈,栈是一种线性表,对它的插入和删除都只能够在表的同一端进行。这一端叫做“栈顶”,另一端则叫做“栈底”。外特性：后进先出(LIFO);先进后出交卷子KTV的“点歌单”作用：保护现场逻辑结构：只在一端操作的线性表数组实现：元素 int amaxn;栈顶指针 t,栈的存储表示,顺序栈的数据结构表示#define maxsize 栈的大小;struct stack1 int astack_size;int t;stack1 s;,栈的基本操作,3,5,2,栈顶,一种“后进先出”的结构,加入一个数,4,取出栈顶元素,再取出栈顶元素,6,动画演示,栈的基本操作,栈的练习试题,例题：一个栈的输入顺序为1、2、3、4、5,下列序列中可能是栈的输出序列是()。(A)54312(B)2415(C)21543(D)1253例题：设有一个顺序栈S,元素S1,S2,S3,S4,S5,S6依次进栈,如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1,则顺序栈的容量至少应为多少？A)3 B)4 C)5 D)6例题：向顺序栈中压入新元素时,应当()。A先移动栈顶指针,再存入元素 B先存入元素,再移动栈顶指针 C先后次序无关紧要 D同时进行例题：某个车站呈狭长型，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”，假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（）A.1，2，3，4，5 B.1，2，4，5，7 C.1，3，5，4，6 D.1，3，5，6，7 E.1，3，6，5，7例题：表达式a*(b+c)-d的后缀表达式是：,铁轨问题,例1：1,2,3,4,5 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2,no;,yes;,yes;,yes;,思考?,输入1,2,n节火车厢,问有多少种出火车站的方法?只有1节车厢,显然只有1种方法,即1.有2节车厢,显然有2种出车厢的方法,12,21.有3节车厢,显然有5种出车厢的方法,123,132,213,231,321.有4节车厢,显然有14种出车厢的方法,1234，1324,2134，2314，3214，1243，1432，1342，2143，2431，2341，3421，3241，4321 n节车厢,有多少方法?,分析,设f(n)表示有n节车厢的出站的方法数那么,第1节车厢显然有进栈和不进栈两种方法.不进栈的方法为f(n-1)进栈的方法数,可以归结为元素1第i次出栈的所有可能性。元素1排列在第i个位置，那么将整个序列分裂为2i，1，i+1n 两个部分。显然方法数为两个部分之积，如下：,【问题描述】假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。【输入文件】输入文件stack.in包括一行数据，即表达式，【输出文件】输出文件stack.out包括一行，即“YES”或“NO”。【样例输入1】2*(x+y)/(1-x)【样例输出1】YES【样例输入2】(25+x)*(a*(a+b+b)【样例输出2】NO,表达式括号匹配1586,int main()char s;int t=0;cins;while(s!=)if(s=()t+;/入栈 if(s=)t-;/出栈 cins;if(t=0)coutYESendl;else coutNOendl;return 0;,Description：在算术表达式中,除了加、减、乘、除等运算外，往往还有括号。包括有大括号，中括号，小括号()，尖括号等。对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号-中括号-小括号-尖括号。例如，()，(),为一个合法的表达式，而()，(),都是非法的。Input：文件的第一行为一个整数n（1n100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。Output：在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。Sample Input 2()Sample Output YESNO,【培训试题】括号的匹配1091,典型试题,char a9=,(,),;cinst;x=true;k=0;len=st.length();for(j=0;jw)coutNOendl;x=false;break;else k+;ck=w;/入栈 else if(ck+w!=9)coutNOendl;x=false;break;else k-;/出栈 if(x=true)if(k=0)coutYESendl;else coutNOendl;,后缀表达式：12 2 5 4*+2/+5-,中缀表达式：12+(2+5*4)/2-5,1、操作数的先后顺序并没有发生变化；2、运算符的先后顺序发生了改变。,表达式求值1181,Description：由键盘输入一个算术表达式，该表达式由数字，加（+）、减（-）、乘（*）、求商（/）运算符及小括号组成。例如：6+8*（5-5*（26-1）/2+7）请编一程序，若输入的表达式的值。Input：输入一个算术表达式（表达式的长度小于255，输入数字的值=100）Output：计算表达式的其值（结果算出的保证都在longint的范围内）。Sample Input：16+8/3Sample Output：18,12+(2+5*4)/2-5,1,2,2,5,4,+,(,+,*,/,2,-,5,+,+(,+*,*),+),)=(,+/,+-,-,=,/-,(+,-,12 2 5 4*+2/+5-,1遍,构造算符优先关系队列表,算法框架,int compare_PRI(char a,char b)/优先级比较,a:符号栈顶,b:将入栈符号 if(a=(,示 例,以3*(7-2)为例,操作过程如下,构造操作符和操作数栈,算法框架,int cal(int a,char mark,int b)/计算函数 switch(mark)case+:return a+b;case-:return a-b;case*:return a*b;case/:return a/b;,算法框架,int main()int temp,num250,numtop=-1,marktop=0,k;char mark250;string s;cins;mark0=(;s+=);while(k=0)/若当前要处理字符是数字 temp=0;/将连续的数字字符转换成数压入数字栈 while(sk=0/输出栈底（也是栈顶）,方法二：用表达式树实现,int main()char st260;cinst;int len=strlen(st);couttree(st,0,len-1);return 0;,int poskh(char st,int right,int p)/寻找字符串left到right区间内与p位置的(匹配的)的位置 int t=1;/sp是一个(p+;/从下一个位置开始找 for(int i=p;i=right;i+)if(sti!=(,int findlow(char st,int left,int right)/寻找字符串left到right区间内最低优先级符号位置 int i,t=0,k=0;for(i=right;i=left;i-)/从右到左扫描,主要因为减号和除号如3-2-1 应是(3-2)-1 而不是3-(2-1).if(sti=A,int isnum(char st,int left,int right)/判断字符串left到right区间是否是一个数，是则返回数值，否则返回1 int data=0;for(int i=left;i=0,int tree(char st,int left,int right)int tmp,l1,l2,p;tmp=isnum(st,left,right);if(tmp!=-1)return tmp;/返回值 if(stleft=(,等价表达式,明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？,这个选择题中的每个表达式都满足下面的性质：1表达式只可能包含一个变量a。2表达式中出现的数都是正整数，而且都小于10000。3表达式中可以包括四种运算+（加），-（减），*（乘），（乘幂），以及小括号(，)。小括号的优先级最高，其次是，然后是*，最后是+和-。+和-的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符+，-，*，以及小括号(，)都是英文字符）4幂指数只可能是1到10之间的正整数（包括1和10）。5 表达式内部，头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子：(a1)2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1+(a-1)3，1109,【输入文件】输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2=n=26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D输入中的表达式，的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。【输出文件】输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。【样例输入】(a+1)23(a-1)2+4*aa+1+aa2+2*a*1+12+10-10+a-a【样例输出】AC【数据规模】对于30%的数据，表达式中只可能出现两种运算符+和-；对于其它的数据，四种运算符+，-，*，在表达式中都可能出现。对于全部的数据，表达式中都可能出现小括号(和)。,分析,这道题目是要我们判断有哪些表达式和给出的表达式本质相同。最简单的想法是将每个表达式进行化简，但是通过仔细的读题，可以发现这是不可能的。因为这样的话涉及到多项式的加法、减法、乘法、幂运算。这在时间有限的考场上是几乎不可能写出来的。而且，也非常难以写对，时间效率也很难保证。注意到数学里面的恒等式的性质，恒等式中代入任何值结果都应该是一样的。而非恒等的式子，结果相等的概率是非常非常小的。那么我们有了一种新的思路，就是每次随机一个a的取值，然后对于所有的表达式计算一次结果。看有多少个和原来的表达式计算出来的结果是一样的。如果只取一个a值进行计算，仍然有一定的概率出错。那么我们多随机几个数，就可以几乎保证正确了。,需要注意的方面,这里还有一个小问题，注意到表达式中可以连续的出现幂运算以及乘法运算。比如9910101010，如果直接用普通的整型计算会溢出。我们可以选一个大素数，每次进行一次运算，就对这个素数取一次余。而我们比较结果的时候就是比较两个表达式的结果对这个大素数取余的值是不是相同。算法流程是：随机取20个a值。将每个值代入每个表达式，计算表达式对于某大素数取余的结果。如果20个值均相同则认为两个式子恒等，否则不恒等。输出结果。,