第三章栈和队列答案 选择题 B|2.1B|2.2A2.3B2.4D2. B|4.D5.D|6.c|7.D8.B 9.D10.D11D|12C13.B14.C|15B16.D17.B18.B19.B20.D 21.D22.D23.D|24.C25.A26.A27.D28.B29.BD30.c31.B32.c 33.1B33.2A33.3C33.4C33.5F34.C|35.C36.A37.AD 判断题 910.×11 12. 15.√|16×17√18 9√|20 部分答案解释如下 1、尾递归的消除就不需用栈 2、这个数是前序序列为1,2,3,,n,所能得到的不相似的二叉树的数目 三、填空题 1、操作受限(或限定仅在表尾进行插入和删除操作)后进先出 2、栈 4、23100CH 5、0n+1top[1]+1=top[2] 6、两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)。 7、(1)满(2)空(3)n(4)栈底(5)两栈顶指针相邻(即值之差的绝对值为1) 8、链式存储结构9、S×SS×S××10、data[++top]=x 11、23.12.3*2-4/34.5*7/++108.9/+(注:表达式中的点()表示将数隔开,如23.12.3 是三个数) 12、假溢出时大量移动数据元素 13、(M+1)MODN(M+1)%N:14、队列15、先进先出16、先进先出 17, s=(LinkedList)malloc(sizeof(LNode)): s->data=x: s->next=r->next: r->next=s 18、牺牲一个存储单元设标记 19、(TAIL+1)MODM= FRONT(数组下标0到M-1,若一定使用1到M,则取模为0者,值 改取M sq. front=(sg. front+1)%(M+1) return(sg. data(sg front (sg. rear+1)%(M+1)==sq. front 21、栈 22、(rear- front+m)%m 23、(R-P+N)%N 24、(1)a[i]或a[1](2)a[i](3)pop(s)或s[1] 25(1) PUSH (OPTR, w)(2) POP (OPTR )(3) PUSH (OPND, operate (a, theta, b)) 26、(1)T0(2)i0(4)topn(5)top+1(6)tue(7)i1(8)top-1(9 T+w[i](10) fal 四、应用题 栈是只准在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另 端叫栈底。最后插入的元素最先删除,故栈也称后进先出(LIFO)表。 2、队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删 除的一端叫队头。最先插入队的元素最先离开(删除),故队列也常称先进先出(FIFO)表。 3、用常规意义下顺序存储结构的一维数组表示队列,由于队列的性质(队尾插入和队 头删除),容易造成“假溢出”现象,即队尾已到达一维数组的髙下标,不能再插入,然而 队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把
第三章 栈和队列答案 一、选择题 1.B 2.1B 2.2A 2.3B 2.4D 2.5.C 3.B 4.D 5.D 6.C 7.D 8.B 9.D 10.D 11.D 12.C 13.B 14.C 15.B 16.D 17.B 18.B 19.B 20.D 21.D 22.D 23.D 24.C 25.A 26.A 27.D 28.B 29.BD 30.C 31.B 32.C 33.1B 33.2A 33.3C 33.4C 33.5F 34.C 35.C 36.A 37.AD 二、判断题 1.√ 2.√ 3. √ 4. √ 5.× 6.√ 7.√ 8. √ 9. √ 10.× 11. √ 12.× 13. × 14.× 15. √ 16.× 17.√ 18.× 19.√ 20. √ 部分答案解释如下。 1、 尾递归的消除就不需用栈 2、 这个数是前序序列为 1,2,3,…,n，所能得到的不相似的二叉树的数目。 三、填空题 1、操作受限（或限定仅在表尾进行插入和删除操作） 后进先出 2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top[1]+1=top[2] 6、两栈顶指针值相减的绝对值为 1（或两栈顶指针相邻）。 7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为 1） 8、链式存储结构 9、S×SS×S×× 10、data[++top]=x； 11、23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如 23.12.3 是三个数） 12、假溢出时大量移动数据元素。 13、(M+1) MOD N (M+1)% N； 14、队列 15、先进先出 16、先进先出 17、s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s； r=s； 18、牺牲一个存储单元 设标记 19、（TAIL+1）MOD M=FRONT (数组下标 0 到 M-1，若一定使用 1 到 M，则取模为 0 者，值 改取 M 20 、 sq.front=(sq.front+1)%(M+1) ； return(sq.data(sq.front)) ； (sq.rear+1)%(M+1)==sq.front； 21、栈 22、（rear-front+m）% m； 23、（R-P+N）% N； 24、（1）a[i]或 a[1] （2）a[i] （3）pop（s）或 s[1]； 25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b）） 26、（1）T>0（2）i0（4）top<n（5）top+1（6）true（7）i-1（8）top-1（9） T+w[i]（10）false 四、应用题 1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一 端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。 2、队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删 除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。 3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队 头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而 队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一
维数组看成首尾相接。在循环队列下,通常采用“牺牲一个存储单元”或“作标记”的方法 解决“队满”和“队空”的判定问题。 4、(1)通常有两条规则。第一是给定序列中S的个数和X的个数相等:第二是从给定 序列的开始,到给定序列中的任一位置,S的个数要大于或等于X的个数。 (2)可以得到相同的输出元素序列。例如,输入元素为A,B,C,则两个输入的合 法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC,我们使用本题约定 的S×S×S×操作序列;对于合法序列BAC,我们使用SS××S×操作序列。 5、三个: CDEBA, CDBEA, CDBAE 6、输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是12,前面 4个元素(4356)得到后,栈中元素剩12,且2在栈顶,不可能栈底元素1在栈顶元素2 之前出栈 得到135426的过程如下:1入栈并出栈,得到部分输出序列1:然后2和3入栈,3出 栈,部分输出序列变为:13:接着4和5入栈,5,4和2依次出栈,部分输出序列变为13542 最后6入栈并退栈,得最终结果135426 7、能得到出栈序列B、C、A、E、D,不能得到出栈序列D、B、A、C、E。其理由为:若 出栈序列以D开头,说明在D之前的入栈元素是A、B和C,三个元素中C是栈顶元素,B 和A不可能早于C出栈,故不可能得到D、B、A、C、E出栈序列 8、借助栈结构,n个入栈元素可得到1/(m+1)(2n)!/(n!*n!))种出栈序列。本题4 个元素,可有14种出栈序列,abcd和dcba就是其中两种。但dabc和adbc是不可能得到 的两种。 9、不能得到序列2, 4,6。栈可以用单链表实现,这就是链栈。由于栈只在栈顶 操作,所以链栈通常不设头结点 10、如果ip的情况,则 说明要将p压到p1之上,也就是在p出栈之后p才能出栈。这就说明,对于i<j<k,不可 能出现p<p<p的输出序列。换句话说,对于输入序列1,2,3,不可能出现3,1,2的输 出序列。 l1、(1)能得到325641。在123依次进栈后,3和2出栈,得部分输出序列32:然后4, 5入栈,5出栈,得部分出栈序列325:6入栈并出栈,得部分输出序列3256:最后退栈 直到栈空。得输出序列325641。其操作序列为 AAADDAADADDD。 (2)不能得到输出顺序为154623的序列。部分合法操作序列为 ADAAAADDAD,得到 部分输出序列1546后,栈中元素为23,3在栈顶,故不可能2先出栈,得不到输出序列154623 12、(1)一个函数在结束本函数之前,直接或间接调用函数自身,称为递归。例如,函 数f在执行中,又调用函数f自身,这称为直接递归;若函数f在执行中,调用函数g,而 g在执行中,又调用函数f,这称为间接递归。在实际应用中,多为直接递归,也常简称为 递归。 (2)递归程序的优点是程序结构简单、清晰,易证明其正确性。缺点是执行中占内 存空间较多,运行效率低 (3)递归程序执行中需借助栈这种数据结构来实现。 (4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本 项和归纳项组成。基本项是递归程序出口,即不再递归即可求出结果的部分:归纳项是将原 来问题化成简单的且与原来形式一样的问题,即向着“基本项”发展,最终“到达”基本项。 13、函数调用结東时vol=14。执行过程图示如下 vol(4) vol(4)=vol(3)+5 14 =vol(2)+3+5
维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法 解决“队满”和“队空”的判定问题。 4、（1）通常有两条规则。第一是给定序列中 S 的个数和 X 的个数相等；第二是从给定 序列的开始，到给定序列中的任一位置，S 的个数要大于或等于 X 的个数。 （2）可以得到相同的输出元素序列。例如，输入元素为 A，B，C，则两个输入的合 法序列 ABC 和 BAC 均可得到输出元素序列 ABC。对于合法序列 ABC，我们使用本题约定 的 S×S×S×操作序列；对于合法序列 BAC，我们使用 SS××S×操作序列。 5、三个：CDEBA，CDBEA，CDBAE 6、输入序列为 123456，不能得出 435612，其理由是，输出序列最后两元素是 12，前面 4 个元素（4356）得到后，栈中元素剩 12，且 2 在栈顶，不可能栈底元素 1 在栈顶元素 2 之前出栈。 得到 135426 的过程如下：1 入栈并出栈，得到部分输出序列 1；然后 2 和 3 入栈，3 出 栈，部分输出序列变为：13；接着 4 和 5 入栈，5，4 和 2 依次出栈，部分输出序列变为 13542； 最后 6 入栈并退栈，得最终结果 135426。 7、能得到出栈序列 B、C、A、E、D，不能得到出栈序列 D、B、A、C、E。其理由为：若 出栈序列以 D 开头，说明在 D 之前的入栈元素是 A、B 和 C，三个元素中 C 是栈顶元素，B 和 A 不可能早于 C 出栈，故不可能得到 D、B、A、C、E 出栈序列。 8、借助栈结构，n 个入栈元素可得到 1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题 4 个元素，可有 14 种出栈序列，abcd 和 dcba 就是其中两种。但 dabc 和 adbc 是不可能得到 的两种。 9、不能得到序列 2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶 操作，所以链栈通常不设头结点。 10、如果 ipj 的情况，则 说明要将 pj 压到 pi 之上，也就是在 pj 出栈之后 pi 才能出栈。这就说明，对于 i<j<k，不可 能出现 pj<pk<pi 的输出序列。换句话说，对于输入序列 1，2，3，不可能出现 3，1，2 的输 出序列。 11、（1）能得到 325641。在 123 依次进栈后，3 和 2 出栈，得部分输出序列 32；然后 4， 5 入栈，5 出栈，得部分出栈序列 325；6 入栈并出栈，得部分输出序列 3256；最后退栈， 直到栈空。得输出序列 325641。其操作序列为 AAADDAADADDD。 （2）不能得到输出顺序为 154623 的序列。部分合法操作序列为 ADAAAADDAD，得到 部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。 12、（1）一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函 数 f 在执行中，又调用函数 f 自身，这称为直接递归；若函数 f 在执行中，调用函数 g，而 g 在执行中，又调用函数 f，这称为间接递归。在实际应用中，多为直接递归，也常简称为 递归。 （2）递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内 存空间较多，运行效率低。 （3）递归程序执行中需借助栈这种数据结构来实现。 （4）递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本 项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原 来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。 13、函数调用结束时 vol=14。执行过程图示如下： vol（4） vol(4)=vol(3)+5 14 =vol(2)+3+5
vol(1)+4+3+5 vol(3)+5 =vol(0)+2+4+3+5 2+4+3+5 vol(2)+3 6 vol(1)+4 2 vol(0)+2 14、过程p递归调用自身时,过程p由内部定义的局部变量在p的2次调用期间,不占 同一数据区。每次调用都保留其数据区,这是递归定义所决定,用“递归工作栈”来实现。 15、设H为n个盘子的 Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z,可 借助钢针Y) 则Hn=2Hn1+1∥/先将n-1个盘子从X移到Y,第n个盘子移到Z,再将那n-1个 移到Z =2(2H-2+1)+1 =2H12+2 22(2H2-3+1)+2+1 =23H-3+22+2+1 =2kHnk+2k-1+2k-2+…+21+2 因为H1=1,所以原式H=2m1+2m2+…+21+202--1 故总盘数为n的 Hanoi塔的移动次数是2n-1。 16、运行结果为:1213121(注:运行结果是每行一个数,为节省篇幅, 到一行。) 17、两栈共享一向量空间(一维数组),栈底设在数组的两端,两栈顶相邻时为栈满 设共享数组为S[MAX],则一个栈顶指针为-1,另一个栈顶指针为MAX时,栈为空 用C写的入栈操作push(i,x)如下 const mAX=共享栈可能达到的最大容量 typedef struct node teletype s[MAX]: int top[2] int push (int i, elemtype x) //ds为容量有MAX个类型为 elemtype的元素的一维数组,由两个栈共享其空间 的值为0或1,x为类型为 elemtype的元素。本算法将x压入栈中。如压栈成功,返回1
=vol(1)+4+3+5 vol（3）+5 =vol(0)+2+4+3+5 9 =0+2+4+3+5 =14 vol（2）+3 6 vol（1）+4 2 vol（0）+2 0 14、过程 p 递归调用自身时，过程 p 由内部定义的局部变量在 p 的 2 次调用期间，不占 同一数据区。每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现。 15、设 Hn 为 n 个盘子的 Hanoi 塔的移动次数。(假定 n 个盘子从钢针 X 移到钢针 Z，可 借助钢针 Y) 则 Hn =2Hn-1+1 //先将 n-1 个盘子从 X 移到 Y，第 n 个盘子移到 Z，再将那 n-1 个 移到 Z =2（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22 +2+1 · · · = 2k Hn-k+2k-1 +2k-2 +…+21 +20 =2n-1 H1+2n-2+2n-3+…+21+20 因为 H1=1，所以原式 Hn=2n-1+2n-2+…+21+20=2n -1 故总盘数为 n 的 Hanoi 塔的移动次数是 2 n -1。 16、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放 到一行。） 17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。 设共享数组为 S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为 MAX 时，栈为空。 用 C 写的入栈操作 push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]； int top[2]； }anode； anode ds; int push(int i,elemtype x) //ds 为容量有 MAX 个类型为 elemtype 的元素的一维数组，由两个栈共享其空间。 i 的值为 0 或 1，x 为类型为 elemtype 的元素。本算法将 x 压入栈中。如压栈成功，返回 1；
否则,返回0 {if(ds.top[1]-ds.top[0]=1){ printf(“栈满Ⅶn”); return(0) switch (i) Icase 0: ds. s[++ds. toplill=x: break case ds. s[--ds. toplil]=x return(1);}/栈成功 18、本程序段查找栈S中有无整数为k的元素,如有,则删除。采用的办法使用另一个 栈T。在S栈元素退栈时,若退栈元素不是整数k,则压入T栈。遇整数k,k不入T栈, 然后将T栈元素全部退栈,并依次压入栈S中,实现了在S中删除整数k的目的。若S中 无整数k,则在S退成空栈后,再将T栈元素退栈,并依次压入S栈。直至T栈空。这后 种情况下S栈内容操作前后不变 19、中缀表达式8-(3+5)*(5-6/2)的后缀表达式是:835+562/-*- 栈的变化过程图略(请参见22题),表达式生成过程为 (1)835(2)835+562(3)835+562/-(4)835+562/-* 中缀表达式exp1转为后缀表达式exp2的规则如下: 设操作符栈s,初始为空栈后,压入优先级最低的操作符‘#’。对中缀表达式从左向右 扫描,遇操作数,直接写入exp2;若是操作符(记为w),分如下情况处理,直至表达式εxpl 扫描完毕。 (1)w为一般操作符(+’,’-,'*,”等),要与栈顶操作符比较优先级,若w优先 级高于栈顶操作符,则入栈;否则,栈顶运算符退栈到exp2,w再与新栈顶操作符作上述 比较处理,直至w入栈 (2)w为左括号((),w入栈。 (3)w为右括号()),操作符栈退栈并进入exp2,直到碰到左括号为止,左括号退 栈(不能进入exp2),右括号也丢掉,达到exp2中消除括号的目的 (4)w为‘#’,表示中缀表达式expl结束,操作符栈退栈到exp2,直至碰到‘#’, 退栈,整个操作结束 这里,再介绍一种简单方法。中缀表达式转为后缀表达式有三步:首先,将中缀表达 式中所有的子表达式按计算规则用嵌套括号括起来:接着,顺序将每对括号中的运算符移到 相应括号的后面:最后,删除所有括号 例如,将中缀表达式8(3+5)*(5-62)转为后缀表达式。按如上步骤 执行完上面第一步后为:(8-(3+5)*(5-(62)); 执行完上面第二步后为:(8(35)+(5(62)-)*) 执行完上面第三步后为:835+562/-* 可用类似方法将中缀表达式转为前缀表达式 20、中缀表达式转为后缀表达式的规则基本上与上面19题相同,不同之处是对运算符 *优先级的规定。在算术运算中,先乘除后加减,先括号内后括号外,相同级别的运算符按 从左到右的规则运算。而对*运算符,其优先级同常规理解,即高于加减乘除而小于左括
否则，返回 0。 {if（ds.top[1]-ds.top[0]==1）{printf（“栈满\n”）；return（0）；} switch（i） {case 0：ds.s[++ds.top[i]]=x；break； case 1：ds.s[--ds.top[i]]=x； return（1）；}//入栈成功。 } 18、本程序段查找栈 S 中有无整数为 k 的元素，如有，则删除。采用的办法使用另一个 栈 T。在 S 栈元素退栈时，若退栈元素不是整数 k，则压入 T 栈。遇整数 k，k 不入 T 栈， 然后将 T 栈元素全部退栈，并依次压入栈 S 中，实现了在 S 中删除整数 k 的目的。若 S 中 无整数 k，则在 S 退成空栈后，再将 T 栈元素退栈，并依次压入 S 栈。直至 T 栈空。这后 一种情况下 S 栈内容操作前后不变。 19、中缀表达式 8-(3+5)*(5-6/2）的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略（请参见 22 题），表达式生成过程为： 中缀表达式 exp1 转为后缀表达式 exp2 的规则如下： 设操作符栈 s，初始为空栈后，压入优先级最低的操作符‘#’。对中缀表达式从左向右 扫描，遇操作数，直接写入 exp2；若是操作符（记为 w），分如下情况处理，直至表达式 exp1 扫描完毕。 （1）w 为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若 w 优先 级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到 exp2，w 再与新栈顶操作符作上述 比较处理，直至 w 入栈。 （2）w 为左括号（’（’），w 入栈。 （3）w 为右括号（’）’），操作符栈退栈并进入 exp2，直到碰到左括号为止，左括号退 栈（不能进入 exp2），右括号也丢掉，达到 exp2 中消除括号的目的。 （4）w 为‘#’，表示中缀表达式 exp1 结束，操作符栈退栈到 exp2，直至碰到‘#’， 退栈，整个操作结束。 这里，再介绍一种简单方法。中缀表达式转为后缀表达式有三步：首先，将中缀表达 式中所有的子表达式按计算规则用嵌套括号括起来；接着，顺序将每对括号中的运算符移到 相应括号的后面；最后，删除所有括号。 例如，将中缀表达式 8-(3+5)*(5-6/2）转为后缀表达式。按如上步骤： 执行完上面第一步后为：(8-((3+5)*(5-(6/2))))； 执行完上面第二步后为：(8((35)+(5(62)/)-)*)- ； 执行完上面第三步后为：8 3 5 + 5 6 2 / - * - 。 可用类似方法将中缀表达式转为前缀表达式。 20、中缀表达式转为后缀表达式的规则基本上与上面 19 题相同，不同之处是对运算符 **优先级的规定。在算术运算中，先乘除后加减，先括号内后括号外，相同级别的运算符按 从左到右的规则运算。而对**运算符，其优先级同常规理解，即高于加减乘除而小于左括号。 （ 2） 8 3 5 + 5 6 2 # * # （ 3） 8 3 5 + 5 6 2 / - （ 4） 8 3 5 + 5 6 2 / - * - - # * （ / ） - - ） （ 1） 8 3 5 # （ + -
为了适应本题中“从右到左计算”的要求,规定栈顶运算符**的级别小于正从表达式中读出 的运算符**,即刚读出的运算符**级别高于栈顶运算符*,因此也入栈。 下面以A*B*C为例说明实现过程。 读入A,不是操作符,直接写入结果表达式。再读入*,这里规定在读入*后,不能立即 当乘号处理,要看下一个符号,若下个符号不是*,则前个*是乘号。这里因为下一个待读 符号也是*,故认为*是一个运算符,与运算符栈顶比较(运算符栈顶初始化后,首先压入 #’作为开始标志),其级别高于‘#’,入栈。再读入B,直接进入结果表达式。接着读入 *,与栈顶比较,均为*,我们规定,后读入的*级别高于栈顶的*,因此**入栈。接着读 入C,直接到结果表达式。现在的结果(后缀)表达式是ABC。最后读入‘#”,表示输入 表达式结束,这时运算符栈中从栈顶到栈底有两个**和一个‘#’。两个运算符*退栈至结果 表达式,结果表达式变为ABC**。运算符栈中只剩‘#’,退栈,运算结束 21、(1)sum=21。当ⅹ为局部变量时,每次递归调用,都要给局部变量分配存储单元,故ⅹ 数值4,9,6和2均保留,其递归过程示意图如下 sum(4) (x=4) sum(2)+9 (x=9) sum(0)+2 (x=2 (2)sum=8,当x为全局变量时,在程序的整个执行期间,x只占一个存储单元,先后读 入的4个数(4,9,6,2)仅最后一个起作用。当递归调用结束,逐层返回时sum=sum(n-1)+x表 达式中,x就是2,所以结果为sum=8。 2、设操作数栈是opnd,操作符栈是opt,对算术表达式A-B*C/D-E↑F求值,过程如下 d栈 optr|输入字符 主要操作 初 A-B*C/D-E t PUSH(OPTR, '#' A-B*C/D-E t PUSH(OPND, A) -B*C/D-E t PUSH(OPTR, '-' F# B*C/D-E PUSH (OPND, B)
为了适应本题中“从右到左计算”的要求，规定栈顶运算符**的级别小于正从表达式中读出 的运算符**，即刚读出的运算符**级别高于栈顶运算符**，因此也入栈。 下面以 A**B**C 为例说明实现过程。 读入 A，不是操作符，直接写入结果表达式。再读入*，这里规定在读入*后，不能立即 当乘号处理，要看下一个符号，若下个符号不是*，则前个*是乘号。这里因为下一个待读的 符号也是*，故认为**是一个运算符，与运算符栈顶比较（运算符栈顶初始化后，首先压入 ‘#’作为开始标志），其级别高于‘#’，入栈。再读入 B，直接进入结果表达式。接着读入 **，与栈顶比较，均为**，我们规定，后读入的**级别高于栈顶的**，因此**入栈。接着读 入 C，直接到结果表达式。现在的结果（后缀）表达式是 ABC。最后读入‘#’，表示输入 表达式结束，这时运算符栈中从栈顶到栈底有两个**和一个‘#’。两个运算符**退栈至结果 表达式，结果表达式变为 ABC****。运算符栈中只剩‘#’，退栈，运算结束。 21、（1）sum=21。当 x 为局部变量时，每次递归调用，都要给局部变量分配存储单元，故 x 数值 4，9，6 和 2 均保留，其递归过程示意图如下： sum（4） 21 sum（3）+4 （x=4） 17 sum（2）+9 （x=9） 8 sum（1）+6 （x=6） 2 sum（0）+2 （x=2） 0 (2) sum=8,当 x 为全局变量时，在程序的整个执行期间，x 只占一个存储单元，先后读 入的 4 个数(4,9,6,2),仅最后一个起作用。当递归调用结束，逐层返回时 sum:=sum(n-1)+x 表 达式中，x 就是 2，所以结果为 sum=8。 22、设操作数栈是 opnd，操作符栈是 optr，对算术表达式 A-B*C/D-E↑F 求值，过程如下： 步 骤 opnd 栈 optr 栈 输入字符 主要操作 初 始 # A-B*C/D-E ↑ F# PUSH(OPTR,’#’) 1 A # A-B*C/D-E ↑ F# PUSH(OPND,A) 2 A # - -B*C/D-E ↑ F# PUSH(OPTR,’-’) 3 AB # - B*C/D-E ↑ F# PUSH(OPND,B)
米C①DE|PUsH(OPTR,’*) F# C/E↑PusH(OPND,C 6AT(T=B*C)#-/ /D-E t PUSH(OPND, POP(OPND)*POP (OPND)) PUSH(OPTR,’/’) ATD D-E PUSH(OPND, D) 8AT(T=T/D)# t x=POP (OPND); y=POP (OPND) T(T=A-T) # PUSH (OPND, y/x) x=POP(OPND): y=POP(OPND) PUSH (OPND, y-x) PUSH(OPTR,’-’) E_↑|PUsH(OPND,E) t|PUSH(oPTR,“t 11 TEF F PUSH(OPND, F) 12|TE X=POP(OPND) Y=POP (OPND) TS(S=↑F)|# POP(OPTR) PUSH (OPND, y t x) x=POP(OPND) y=POP(OPND) R(R=T-S) POP(OPTR) PUSH(OPND, y-x) 步骤|栈S1 栈S2 「输入的算术表达式(按字符读入) A-B*C/D+E/FR B米C/D+E/F AB B*C/D+E/F& AR 一水 米C/D+E/F 一水 C/D+E/FR AT1(注:T1=B*C)歌/ /D+E/F& ATID D+E/F& AT2(注:T2=T1/) +E/FR T3(注:T=A-T2) T3E T3EF 12T(注:T=E/F) 24 XSXXXSSSXXSXXSXXSSSS
4 AB # - * *C/D-E ↑ F# PUSH(OPTR,’*’) 5 ABC # - * C/D-E ↑ F# PUSH(OPND,C) 6 AT(T=B*C) # - / /D-E ↑ F# PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) 7 ATD # - / D-E ↑ F# PUSH(OPND,D) 8 AT(T=T/D) T(T=A-T) # - # - -E ↑ F# x=POP(OPND);y=POP(OPND) PUSH(OPND,y/x); x=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 TE # - E ↑ F# PUSH(OPND,E) 10 TE # -↑ ↑ F# PUSH(OPTR, ‘↑’) 11 TEF # -↑ F # PUSH(OPND,F) 12 TE TS(S=E↑F) R(R=T-S) #- # # X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSH(OPND,y↑x) x=POP(OPND) y=POP(OPND) POP(OPTR) PUSH(OPND,y-x) 23、 步骤 栈 S1 栈 S2 输入的算术表达式（按字符读入） 初始 ® A-B*C/D+E/F® 1 A ® A-B*C/D+E/F® 2 A ®- -B*C/D+E/F® 3 AB ®- B*C/D+E/F® 4 AB ®-* *C/D+E/F® 5 ABC ®-* C/D+E/F® 6 AT1（注：T1=B*C） ®-/ /D+E/F® 7 AT1D ®-/ D+E/F® 8 AT2（注：T2=T1/D） T3 （注：T3=A-T2） ®- ®+ +E/F® 9 T3E ®+ E/F® 10 T3E ®+/ /F® 11 T3EF ®+/ F® 12 T3T4（注：T4=E/F） T5（注：T5= T3+ T4） ®+ ® ® 24、XSXXXSSSXXSXXSXXSSSS
25、S1和S2共享内存中一片连续空间(地址1到m),可以将S1和S2的栈底设在两端 两栈顶向共享空间的中心延伸,仅当两栈顶指针相邻(两栈顶指针值之差的绝对值等于1) 时,判断为栈满,当一个栈顶指针为0,另一个栈顶指针m+1时为两栈均空 26、设栈S1和栈S2共享向量[I.m],初始时,栈S1的栈顶指针topO]=0,栈S2的栈顶 指针top[1]=m+1,当topO=0为左栈空,top[=m+1为右栈空;当top0]=0并且top[]=m+1 时为全栈空。当top[-top[0]=1时为栈满。 27、(1)每个栈仅用一个顺序存储空间时,操作简便,但分配存储空间小了,容易产生溢出 分配空间大了,容易造成浪费,各栈不能共享空间 (2)多个栈共享一个顺序存储空间,充分利用了存储空间,只有在整个存储空间都用完 时才能产生溢出,其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有,则要移 动元素和修改相关的栈底和栈顶指针。当接近栈满时,查询空闲单元、移动元素和修改栈底 栈顶指针的操作频繁,计算复杂并且耗费时间。 (3)多个链栈一般不考虑栈的溢出(仅受用户内存空间限制),缺点是栈中元素要以指 针相链接,比顺序存储多占用了存储空间。 28、设topl和top2分别为栈1和2的栈顶指针 (1)入栈主要语句 if(top2-topl=1){ printf(“栈满Ⅶn”);exit(0);} casel:topl++; SPACE[top1]=x;//设x为入栈元素。 case2: top2-: SPACE[top2]=x 出栈主要语句 casel:if(topl=-1){ printf(“栈空Ⅶn”);exit(0) top1-: return( SPACE[opl+1])://返回出栈元素 case:if(top2=N) (printf(“栈空\n”);exit(0):} top2++; return( SPACE[op2-1]);/返回出栈元素 (2)栈满条件:top2-topl=1 栈空条件:topl=-1并且top2=N//topl=-1为左栈空,top2=N为右栈空 29、设顺序存储队列用一维数组q[m表示,其中m为队列中元素个数,队列中元素在向量 中的下标从0到m-1。设队头指针为 front,队尾指针是rear,约定 front指向队头元素的 前一位置,rear指向队尾元素。当 front等于-1时队空,rear等于m-1时为队满。由于队 列的性质(“删除”在队头而“插入”在队尾),所以当队尾指针rear等于m-1时,若 front 不等于-1,则队列中仍有空闲单元,所以队列并不是真满。这时若再有入队操作,会造成假 “溢出”。其解决办法有二,一是将队列元素向前“平移”(占用0至rear- front-1);二是 将队列看成首尾相连,即循环队列(0..m-1)。在循环队列下,仍定义 front=rear时为队空, 而判断队满则用两种办法,一是用“牺牲一个单元”,即rear+l= front(准确记是 (rear+1)%m= front,m是队列容量)时为队满。另一种解法是“设标记”方法,如设标记 tag,tag等于0情况下,若删除时导致 front=rear为队空;tag=1情况下,若因插入导致 front=rear则为队满 见上题29的解答。31、参见上面29题 、 typedef struct node elemtype elemcq[m;/m为队列最大可能的容量 int front, rear // front和rear分别为队头和队尾指针。 (1)初始状态
25、S1 和 S2 共享内存中一片连续空间（地址 1 到 m），可以将 S1 和 S2 的栈底设在两端， 两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于 1） 时，判断为栈满，当一个栈顶指针为 0，另一个栈顶指针 m+1 时为两栈均空。 26、设栈 S1 和栈 S2 共享向量 V[1..m]，初始时，栈 S1 的栈顶指针 top[0]=0，栈 S2 的栈顶 指针 top[1]=m+1，当 top[0]=0 为左栈空，top[1]=m+1 为右栈空；当 top[0]=0 并且 top[1]=m+1 时为全栈空。当 top[1]-top[0]=1 时为栈满。 27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出， 分配空间大了，容易造成浪费，各栈不能共享空间。 （2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完 时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移 动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底 栈顶指针的操作频繁，计算复杂并且耗费时间。 （3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指 针相链接，比顺序存储多占用了存储空间。 28、设 top1 和 top2 分别为栈 1 和 2 的栈顶指针 （1）入栈主要语句 if(top2-top1==1) {printf(“栈满\n”); exit(0);} case1:top1++；SPACE[top1]=x; //设 x 为入栈元素。 case2:top2--；SPACE[top2]=x; 出栈主要语句 case1：if（top1==-1） {printf（“栈空\n”）；exit（0）；} top1--；return（SPACE[top1+1]）； //返回出栈元素。 case2：if（top2==N）{printf（“栈空\n”）；exit（0）；} top2++；return（SPACE[top2-1]）； //返回出栈元素。 （2）栈满条件：top2-top1=1 栈空条件：top1=-1 并且 top2=N //top1=-1 为左栈空，top2=N 为右栈空 29、设顺序存储队列用一维数组 q[m]表示，其中 m 为队列中元素个数，队列中元素在向量 中的下标从 0 到 m-1。设队头指针为 front，队尾指针是 rear，约定 front 指向队头元素的 前一位置，rear 指向队尾元素。当 front 等于-1 时队空，rear 等于 m-1 时为队满。由于队 列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针 rear 等于 m-1 时，若 front 不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假 “溢出”。其解决办法有二，一是将队列元素向前“平移”（占用 0 至 rear-front-1）；二是 将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义 front=rear 时为队空， 而判断队满则用两种办法，一是用“牺牲一个单元”，即 rear+1=front（准确记是 （rear+1）%m=front，m 是队列容量）时为队满。另一种解法是“设标记”方法，如设标记 tag，tag 等于 0 情况下，若删除时导致 front=rear 为队空；tag=1 情况下，若因插入导致 front=rear 则为队满。 30、见上题 29 的解答。 31、参见上面 29 题。 32、typedef struct node {elemtype elemcq[m]; //m 为队列最大可能的容量。 int front ,rear; //front 和 rear 分别为队头和队尾指针。 }cqnode; cqnode cq; (1) 初始状态
cq. front=cq rear=0; (2)队列空 cq. front==cq. rear (3)队列满 (cq. rear+1)%==cq. front 33、栈的特点是后进先出,队列的特点是先进先出。初始时设栈s1和栈s2均为空 (1)用栈s1和s2模拟一个队列的输入:设sl和s2容量相等。分以下三种情况讨论: 若sl未满,则元素入sl栈;若s1满,s2空,则将sl全部元素退栈,再压栈入s2,之后 元素入s1栈:;若sl满,s2不空(已有出队列元素),则不能入队。 (2)用栈s1和s2模拟队列出队(删除):若栈s2不空,退栈,即是队列的出队;若s2 为空且s1不空,则将sl栈中全部元素退栈,并依次压入s2中,s2栈顶元素退栈,这就是 相当于队列的出队。若栈sl为空并且s2也为空,队列空,不能出队。 (3)判队空若栈s1为空并且s2也为空,才是队列空 讨论:s1和s2容量之和是队列的最大容量。其操作是,sl栈满后,全部退栈并压栈入 s2(设s1和s2容量相等)。再入栈sl直至sl满。这相当队列元素“入队”完毕。出队时, 2退栈完毕后,s1栈中元素依次退栈到s2,s2退栈完毕,相当于队列中全部元素出队。 在栈s2不空情况下,若要求入队操作,只要s1不满,就可压入s1中。若s1满和s2 不空状态下要求队列的入队时,按出错处理 4、(1)队空s. front=s.rear; /设s是 sequeuetp类型变量 (2)队满:(s.rear+1) MOD MAXSIZE=s. front/数组下标为0.. MAXSIZE-1 具体参见本章应用题第29题 35、 typedef struct lelemtp q[m] int front, count;// front是队首指针, count是队列中元素个数 I anode /定义类型标识符 (1)判空: int Empty( cqnode cq) //cq是 anode类型的变量 {if(cq. count==0) return(1): else return(0);//空队列} 入队: int EnQueue( anode cq, elemtp x) {if( coun t==m){ printf(“队满\n”):exit(0);} cq. g[(cg. front+count)%m]=x count++ return(1) //队列中元素个数增加1,入队成功 出队: int DeqUeue( anode cq) {if( count==0){ printf(“队空Ⅶn”); return(0) printf(“出队元素”,cq.q[cq. front]) x=cq. q[cg front] cq. front=(cq. front+1)‰;/)计算新的队头指针 return(x) (2)队列中能容纳的元素的个数为m。队头指针 front指向队头元素。 36、循环队列中元素个数为(REAR- FRONT+N)‰N。其中 FRONT是队首指针,指向队首元素的 前一位置:REAR是队尾指针,指向队尾元素;N是队列最大长度。 37、循环队列解决了用向量表示队列所出现的“假溢出”问题,但同时又出现了如何判断队 列的满与空问题。例如:在队列长10的循环队列中,若假定队头指针 front指向队头元素
cq.front=cq.rear=0; (2) 队列空 cq.front==cq.rear; (3) 队列满 (cq.rear+1)%m==cq.front; 33、栈的特点是后进先出，队列的特点是先进先出。初始时设栈 s1 和栈 s2 均为空。 （1）用栈 s1 和 s2 模拟一个队列的输入：设 s1 和 s2 容量相等。分以下三种情况讨论： 若 s1 未满，则元素入 s1 栈；若 s1 满，s2 空，则将 s1 全部元素退栈，再压栈入 s2，之后 元素入 s1 栈；若 s1 满，s2 不空（已有出队列元素），则不能入队。 （2）用栈 s1 和 s2 模拟队列出队（删除）：若栈 s2 不空，退栈，即是队列的出队；若 s2 为空且 s1 不空，则将 s1 栈中全部元素退栈，并依次压入 s2 中，s2 栈顶元素退栈，这就是 相当于队列的出队。若栈 s1 为空并且 s2 也为空，队列空，不能出队。 （3）判队空 若栈 s1 为空并且 s2 也为空，才是队列空。 讨论：s1 和 s2 容量之和是队列的最大容量。其操作是，s1 栈满后，全部退栈并压栈入 s2（设 s1 和 s2 容量相等）。再入栈 s1 直至 s1 满。这相当队列元素“入队”完毕。出队时， s2 退栈完毕后，s1 栈中元素依次退栈到 s2，s2 退栈完毕，相当于队列中全部元素出队。 在栈 s2 不空情况下，若要求入队操作，只要 s1 不满，就可压入 s1 中。若 s1 满和 s2 不空状态下要求队列的入队时，按出错处理。 34、（1）队空 s.front=s.rear； //设 s 是 sequeuetp 类型变量 （2）队满：（s.rear+1）MOD MAXSIZE=s.front //数组下标为 0.. MAXSIZE-1 具体参见本章应用题第 29 题 35、typedef struct {elemtp q[m]; int front,count; //front 是队首指针，count 是队列中元素个数。 }cqnode; //定义类型标识符。 (1)判空：int Empty(cqnode cq) //cq 是 cqnode 类型的变量 {if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x) {if(count==m){printf(“队满\n”)；exit(0); } cq.q[(cq.front+count)%m]=x; //x 入队 count++; return(1); //队列中元素个数增加 1,入队成功。 } 出队: int DelQueue(cqnode cq) {if (count==0){printf(“队空\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front]; cq.front=(cq.front+1)%m; //计算新的队头指针。 return(x) } (2) 队列中能容纳的元素的个数为 m。队头指针 front 指向队头元素。 36、循环队列中元素个数为（REAR-FRONT+N）%N。其中 FRONT 是队首指针，指向队首元素的 前一位置；REAR 是队尾指针，指向队尾元素；N 是队列最大长度。 37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队 列的满与空问题。例如：在队列长 10 的循环队列中，若假定队头指针 front 指向队头元素
的前一位置,而队尾指针指向队尾元素,则 front=3,rear=7的情况下,连续出队4个元素 则 front=rear为队空;如果连续入队6个元素,则 front=rear为队满。如何判断这种情 况下的队满与队空,一般采取牺牲一个单元的做法或设标记法。即假设 front=rear为队空, 而(rear+1)%表长= front为队满,或通过设标记tag。若tag=0, front==rear则为队空; 若tag=1,因入队而使得 front=rear,则为队满。 本题中队列尾指针rear,指向队尾元素的下一位置, listarray[rear]表示下一个入队 的元素。在这种情况下,我们可规定,队头指针 front指向队首元素。当 front=ear时为 队空,当(rear+1)‰n= front时为队满。出队操作(在队列不空情况下)队头指针是 front= ( front+1)‰n, 38、既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是 dbca 39、(1)4132 (2)4213 (3)4231 40、(1)队空的初始条件:f=r=0 (2)执行操作A后,r=3:∥/A表示三次入队操作 执行操作D后,f=1:/D表示一次出队操作 执行操作A后,r=0 执行操作D2后,f=3 执行操作A后,r=1 执行操作D后,f=5 执行操作A后,按溢出处理。因为执行A后,r=4,这时队满,若再执行A操作, 则出错 41.一般说,高级语言的变量名是以字母开头的字母数字序列。故本题答案是 AP321,PA321,P3A21,P32A1,P321A 五、算法设计题 1、[题目分析]两栈共享向量空间,将两栈栈底设在向量两端,初始时,s1栈顶指针为-1, s2栈顶为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向,迎面增长,栈顶指针指向栈顶 元素 # define maxsize两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int /假设元素类型为整型 typedef struct elemtp stack [maxsize];//栈空间 int top [2] //top为两个栈顶指针 Itk stk //s是如上定义的结构类型变量,为全局变量。 (1)入栈操作: int push(int i, int x) /入栈操作。i为栈号,i=0表示左边的栈s1,i=1表示右边的栈s2,x是入栈元素 入栈成功返回1,否则返回0 if(i<0i》1){ printf(“栈号输入不对”);exit(0);} if(s.top[1]-s.top[0]=1){ printf(“栈已满Ⅶn”); return(0);} Icase 0: s stack[++s top[o]]=x: return(1): break ase 1: s stack[--s top[1]]=x: return (1)
的前一位置，而队尾指针指向队尾元素，则 front=3，rear=7 的情况下，连续出队 4 个元素， 则 front==rear 为队空；如果连续入队 6 个元素，则 front==rear 为队满。如何判断这种情 况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设 front==rear 为队空， 而（rear+1）%表长==front 为队满，或通过设标记 tag。若 tag=0，front==rear 则为队空； 若 tag=1，因入队而使得 front==rear，则为队满。 本题中队列尾指针 rear，指向队尾元素的下一位置,listarray[rear]表示下一个入队 的元素。在这种情况下，我们可规定，队头指针 front 指向队首元素。当 front==rear 时为 队空，当（rear+1）%n=front 时为队满。出队操作（在队列不空情况下）队头指针是 front= （front+1）%n， 38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是 dbca。 39、（1）4132 （2）4213 （3）4231 40、（1）队空的初始条件：f=r=0； （2）执行操作 A 3 后，r=3；// A3 表示三次入队操作 执行操作 D 1 后，f=1；//D1 表示一次出队操作 执行操作 A 5 后，r=0； 执行操作 D 2 后，f=3； 执行操作 A 1 后，r=1； 执行操作 D 2 后，f=5； 执行操作 A 4 后，按溢出处理。因为执行 A 3 后，r=4，这时队满，若再执行 A 操作， 则出错。 41．一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。 五、算法设计题 1、[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1 栈顶指针为-1， s2 栈顶为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶 元素。 #define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int //假设元素类型为整型 typedef struct {elemtp stack[maxsize]; //栈空间 int top[2]; //top 为两个栈顶指针 }stk; stk s; //s 是如上定义的结构类型变量，为全局变量。 (1)入栈操作： int push(int i,int x) //入栈操作。i 为栈号，i=0 表示左边的栈 s1，i=1 表示右边的栈 s2，x 是入栈元素。 入栈成功返回 1，否则返回 0。 {if(i1){printf(“栈号输入不对”);exit(0);} if(s.top[1]-s.top[0]==1) {printf(“栈已满\n”);return(0);} switch(i) {case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1);
1//push (2)退栈操作 elemtp pop(int i) //退栈算法。i代表栈号,i=0时为s1栈,i=1时为s2栈。退栈成功返回退栈元素, 否则返回-1。 if(i<0‖|i》1){ printf(“栈号输入错误\n”):exit(0);} switch(i) case0:if(s.top[0]=-1){ printf(“栈空Ⅶn”): return(-1);} else return(s stack[s top[o]-]) case 1:if(s.top[1]= - mansize{ printf(“栈空n”); return(-1);} else return(s stack[s top[1]++]) }//算法结束 [算法讨论]请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图 略,sl栈是通常意乂下的栈,而s2栈入栈操作时,其栈顶指针左移(减1),退栈时,栈顶 指针右移(加1) 2、# define maxsize栈空间容量 void InOuts(int s[maxsize]) //s是元素为整数的栈,本算法进行入栈和退栈操作。 /top为栈顶指针,定义top=0时为栈空 for(i=1;i<=n;i++)//n个整数序列作处理。 scanf(“%d”,&x);//从键盘读入整数序列 if(x!=-1) //读入的整数不等于-1时入栈 if(top== maxsize-1){ printf(“栈满\n”) 0);} else s[+top]=x;//x入栈 else//读入的整数等于-1时退栈 if(top=0){ printf(“栈空Ⅶn”);exit(0);} else printf(“出栈元素 是%d\n”,s[top--]):}} }//算法结束。 、[题目分析]判断表达式中括号是否匹配,可通过栈,简单说是左括号时进栈,右括号时 退栈。退栈时,若栈顶元素是左括号,则新读入的右括号与栈顶左括号就可消去。如此下去 输入表达式结束时,栈为空则正确,否则括号不匹配。 int EXYX(char E[, int n /E是有n字符的字符数组,存放字符串表达式,以‘#’结束。本算法判断表达式中圆 括号是否匹配。 Ichar s[30] //s是一维数组,容量足够大,用作存放括号的栈 int top=0 //top用作栈顶指针。 s[op]=“# /‘#’先入栈,用于和表达式结束符号“#’匹配。 //字符数组E的工作指针 while(E[i]!=‘#’)//逐字符处理字符表达式的数组 switch([i] case‘(’:s[+top]=‘(’;i++; break case“)':if(s[top]==‘('{top-;i+; break;} else{ printf(“括号不配对”);exit(0)
} }//push （2） 退栈操作 elemtp pop(int i) //退栈算法。i 代表栈号，i=0 时为 s1 栈，i=1 时为 s2 栈。退栈成功返回退栈元素， 否则返回-1。 {if(i1){printf(“栈号输入错误\n”)；exit(0);} switch(i) {case 0: if(s.top[0]==-1) {printf(“栈空\n”)；return（-1）；} else return(s.stack[s.top[0]--]); case 1: if(s.top[1]==maxsize {printf(“栈空\n”); return(-1);} else return(s.stack[s.top[1]++]); } }//算法结束 [算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图 略，s1 栈是通常意义下的栈，而 s2 栈入栈操作时，其栈顶指针左移（减 1），退栈时，栈顶 指针右移（加 1）。 2、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top 为栈顶指针，定义 top=0 时为栈空。 for(i=1; i<=n; i++) //n 个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1 时入栈。 if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x 入栈。 else //读入的整数等于-1 时退栈。 {if(top==0){printf( “栈空 \n ” );exit(0);} else printf( “出栈元素 是%d\n”,s[top--])；}} }//算法结束。 3、[题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时 退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去， 输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E[],int n) //E[]是有 n 字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆 括号是否匹配。 {char s[30]; //s 是一维数组，容量足够大，用作存放括号的栈。 int top=0; //top 用作栈顶指针。 s[top]= ‘#’; //‘#’先入栈，用于和表达式结束符号‘#’匹配。 int i=0; //字符数组 E 的工作指针。 while(E[i]!= ‘#’) //逐字符处理字符表达式的数组。 switch(E[i]) {case‘(’: s[++top]=‘(’; i++ ; break ; case‘)’: if(s[top]==‘(’{top--; i++; break;} else{printf(“括号不配对”);exit(0);}