栈与队列习题与答案(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); //申请新结点。假设有内存空间，否则系统给出出错信息。 s↑.data:=x; s↑.link:=p↑.link;//将s结点入队。 p↑.link:=s; p:=s; //尾指针p移至新的队尾。 ENDP;

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

// p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。

IF （p↑.link=p）THEN[writeln(“空队列”);return(0);]//带头结点的循环队列。 ELSE[s:=p↑.link↑.link; //找到队头元素。 p↑.link↑.link:=s↑.link; //删队头元素。 x:=s↑.data; //返回出队元素。

IF (p=s) THEN p:=p↑.link; //队列中只有一个结点，出队后成为空队列。 dispose(s); //回收出队元素所占存储空间。 ] ENDP;

[算法讨论]上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。 9、本题与上题本质上相同，现用类C语言编写入队和出队算法。 （1）void EnQueue (LinkedList rear, ElemType x)

// rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。 { s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间 s->data=x; s->next=rear->next; //将s结点链入队尾 rear->next=s; rear=s; //rear指向新队尾 }

（2）void DeQueue (LinkedList rear) // rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。

{ if (rear->next==rear) { printf(“队空\\n”); exit(0);} s=rear->next->next; //s指向队头元素，

rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”，s->data);

if (s==rear) rear=rear->next; //空队列 free(s); } 10、[题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。

（1）#define M 队列可能达到的最大长度 typedef struct { elemtp data[M]; int front,rear; } cycqueue;

（2）elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。

{ if (Q.front==Q.rear) {printf(“队列空”); exit(0);} Q.rear=(Q.rear-1+M)%M; //

修改队尾指针。

return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束

void enqueue (cycqueue Q, elemtp x)

// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);) Q.data[Q.front]=x; //x 入队列

Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。

11、参见9。

12、[题目分析] 双端队列示意图如下（设maxsize =12） 0 1 2 3 4 5 6 7 8 9 10 11

↑ ↑ end1 end2

用上述一维数组作存储结构，把它看作首尾相接的循环队列。可以在任一端（end1或end2）进行插入或删除。初始状态end1+1=end2被认为是队空状态；end1=end2被认为是队满状态。（左端队列）end1指向队尾元素的前一位置。end2指向（右端队列）队尾元素的后一位置。入队时判队满，出队（删除）时判队空。删除一个元素时，首先查找该元素，然后，从队尾将该元素前的元素依次向后或向前（视end1端或end2端而异）移动。 FUNC add (Qu:deque; var x:datatype;tag 0..1):integer;

//在双端队列Qu中插入元素x，若插入成功，返回插入元素在Qu中的下标；插入失败返回-1。tag=0表示在end1端插入；tag=1表示在end2端插入。 IF Qu.end1=Qu.end2 THEN [writeln(“队满”);return(-1);] CASE tag OF

0: //在end1端插入 [Qu.end1:=x; //插入x

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库栈与队列习题与答案(7)在线全文阅读。