米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) 初始状态