资源描述：
《栈和队列课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列重庆一中葛静栈外特性：后进先出(LIFO)交卷子KTV的“点歌单”作用：保护现场逻辑结构：只在一端操作的线性表数组实现：元素stack:array[1..maxn]ofinteger栈顶指针top栈的存储表示顺序栈的数据结构表示constmaxsize=栈的大小;typesqstktp=recordelem:array[1..stack_size]ofelemtp;top:0..maxsize;end链栈lnkstack=^nodenode=recordelem:elemtp;top:lnkstack;end;栈的基本操作funcpush(vars:s
2、qstktp;x:elemtp):boolean;beginiftop=stack_sizethenreturn(false);{栈满}elsebegins.top:=s.top+1;s.elem[s.top]:=x;return(true);end;endf;funcpop(vars:sqstktp;):elemtp;beginifs.top=0thenreturn(NULL){栈空}elsebegins.top:=s.top-1;return(s.elem[s.top+1]);end;endf;铁轨问题例1：1,2,3,4,5例2：5,4,3,2,1例3：3,2
3、,4,5,1例4：3,1,4,5,2no;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节车厢显然有进栈和不进栈两种方
4、法.不进栈的方法为f(n-1)进栈的方法数,可以归结为元素1第i次出栈的所有可能性。元素1排列在第i个位置，那么将整个序列分裂为2~i，1，i+1~n两个部分。显然方法数为两个部分之积，如下：h(1)=1卡特兰数：中文:卡特兰数令h(0)=1,h(1)＝1,catalan数满足递归式：h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)h(0)(其中n>=2)另类递归式：h(n)=((4*n-6)/(n))*h(n-1);该递推关系的解为：h(n)=C(2n,n)/(n+1)(n=1,2,3,...)典型试题问题:算术达式求值输入一个表达式
5、，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数，输入以@结束。构造算符优先关系队列表+-*/()@+-*/()@>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=示例以3*(5-2)+7@为例,操作过程如下,构造操作符和操作数栈算法框架Functionexp_reduced:oprandtype;inistack(optr);push(optr,’@’);inistack(opnd)read(w);whilenot((w=‘@’)and(gettop(optr)=‘@’))doIfnotwinopthe
6、n[push(opnd,w);read(w)]elsecasepredede(gettop(optr),w)of‘<‘:[push(optr,w);read(w)];‘=‘:[x:=pop(optr);read(w)];‘>‘:[theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b))];endcreturn(gettop(opnd))endF等价表达式明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选
7、项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。这个选择题中的每个表达式都满足下面的性质：1． 表达式只可能包含一个变量‘a’。2． 表达式中出现的数都是正整数，而且都小于10000。3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）4． 幂指
