数据结构-栈-(精选·公开·课件).ppt

栈 栈是一种线性表,对它的插入和删除都只能够在表的同一端进行。这一端叫做“栈顶”,另一端则叫做“栈底”。 外特性：后进先出(LIFO);先进后出 交卷子 KTV的“点歌单” 作用：保护现场 逻辑结构：只在一端操作的线性表 数组实现： 元素 int a[maxn]; 栈顶指针 t 栈的存储表示 顺序栈的数据结构表示 #define maxsize 栈的大小; struct stack1 { int a[stack_size]; int t; } stack1 s; 栈的基本操作 栈的基本操作 栈的练习试题 铁轨问题 例1：1,2,3,4,5 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2 思考? 输入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个位置，那么将整个序列分裂为2~i，1，i+1~n 两个部分。显然方法数为两个部分之积，如下： 典型试题 表达式求值1181 构造算符优先关系队列表 算法框架 示 例 算法框架 算法框架 等价表达式 明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？ 这个选择题中的每个表达式都满足下面的性质： 1．表达式只可能包含一个变量‘a’。 2．表达式中出现的数都是正整数，而且都小于10000。 3．表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符） 4．幂指数只可能是1到10之间的正整数（包括1和10）。 5． 表达式内部，头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子： ((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9…… 【输入文件】 输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2 = n = 26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……输入中的表达式，的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。 【输出文件】 输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。 【样例输入】 ( a + 1) ^2 3 (a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 【样例输出】 AC 【数据规模】 对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’； 对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。 对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。 分析 这道题目是要我们判断有哪些表达式和给出的表达式本质相同。最简单的想法是将每个表达式进行化简，但是通过仔细的读题，可以发现这是不可能的。因为这样的话涉及到多项式的加法、减法、乘法、幂运算。这在时间有限的考场上是几乎不可能写出来的。而且，也非常难以写对，时间效率也很难保证。 注意到数学里面的恒等式的性质，恒等式中代入任何值结果都应该是一样的。而非恒等的式子，结果相等的概率是非常非常小的。那么