栈与队列习题与答案(7)

scale=scale*10; scanf(“%c”,&x); } }//else

push(OPND,num); num=0.0;//数压入栈，下个数初始化 case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while（x！=‘$’）

printf(“后缀表达式的值为%f”,pop(OPND)); }//算法结束。

[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字

字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。 5、（1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} }

i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);} }//算法结束。

[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈

次数（题目中要求栈的初态和终态都为空），否则视为非法序列。 6、[题目分析]表达式中的括号有以下三对：‘（’、‘）’、‘[’、‘]’、‘{’、‘}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。

int Match(LinkedList la)

//算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对 {char s[]; //s为字符栈，容量足够大

p=la->link; //p为工作指针，指向待处理结点 StackInit(s); //初始化栈s

while (p!=la) //循环到头结点为止 {switch (p->ch)

{case ‘(’:push(s,p->ch); break;

case ‘)’:if(StackEmpty(s)||StackGetTop(s)!=‘(’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; case ‘[’:push(s,p->ch); break;

case ‘]’: if(StackEmpty(s)||StackGetTop(s)!=‘[’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; case ‘{’:push(s,p->ch); break;

case ‘}’: if(StackEmpty(s)||StackGetTop(s)!=‘{’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; } p

=p->link; 后移指针 }//while

if (StackEmpty(s)) {printf(“括号配对\\n”); return(1);} else{printf(“括号不配对\\n”); return(0);} }//算法match结束

[算法讨论]算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结论括号不配对。

7、[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1) int enqueue(stack s1,elemtp x)

//s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。

{if(top1==n && !Sempty(s2)) //top1是栈s1的栈顶指针，是全局变量。 {printf(“栈满”);return(0);} //s1满s2非空,这时s1不能再入栈。

if(top1==n && Sempty(s2)) //若s2为空，先将s1退栈,元素再压栈到s2。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}

PUSH(s1,x); return(1); //x入栈，实现了队列元素的入队。 }

(2) void dequeue(stack s2,s1)

//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。 {if(!Sempty(s2)) //栈s2不空，则直接出队。 {POP(s2,x); printf(“出队元素为”,x); } else //处理s2空栈。

if(Sempty(s1)) {printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。 else //先将栈s1倒入s2中，再作出队操作。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} POP(s2,x); //s2退栈相当队列出队。 printf(“出队元素”，x); }

}//结束算法dequue。 (3) int queue_empty()

//本算法判用栈s1和s2模拟的队列是否为空。

{if(Sempty(s1)&&Sempty(s2)) return(1);//队列空。 else return(0); //队列不空。 }

[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。 类似本题叙述的其它题的解答：

该题同上面题本质相同，只有叙述不同，请参考上题答案。

8、[题目分析]本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O（1），因此

我们用只设尾指针的循环链表来实现队列。

PROC addq(VAR p:linkedlist,x:elemtp);

//p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法是入队操作。 new(s); //申请新结点。假设有内存空间，否则 …… 此处隐藏：4273字，全部文档内容请下载后查看。喜欢就下载吧 ……