4-6 根据课文中给出的优先级 ，回答以下问题：
(1)在函数postfix中，如果表达式e含有n个运算符和分界符，那么栈中可能存入元素的最大个数是多少？
(2)如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，那么栈中可能存入元素的最大个数是多少？
(1)我想参考答案应该是错的。
题中的元算符指操作符，分界符在课文中有优先级定义么？
按照优先级表，从+，—开始往右依次进栈时，都不会导致退栈，一直到(，然后可以继续循环，如此可以保证最多的操作符进栈，一次进栈3个操作符和“(”，然后循环，但是(需要“）”对应，设有x个“(”，那么4x+3+x=n。x=(n-3)/5 那么最多进栈的操作符是 4(n-3)/5+3+1 1是指栈底的#
(2)括号深度最大6个，那么如果n足够大的话，最多存入的元素是
4*6+3再进来就是)了，要退栈。加上# 一共是28个。此时的n应该 >=33
如果n& lt;33的话，答案还是4(n-3)/5+3+1=4(n+2)/5
4-7 设表达式的中缀表示为a*x-b/x^2，试利用栈将它改为后缀表示ax*bx2^/-。写出转换过程中栈的变化。
4-9 假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
队空条件:length==0;
队满条件:length==maxsize;
4-10 假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写出此结构相应的插入和删除函数。
加入标志tag，则循环队列结构中不需要空一个元素位置了。front依然指向第一个元素前的队头
改写isEmpty()和isFull()
队空：front==rear&&tag==0
队满：front==rear&&tag==1
(1)在函数postfix中，如果表达式e含有n个运算符和分界符，那么栈中可能存入元素的最大个数是多少？
(2)如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，那么栈中可能存入元素的最大个数是多少？
(1)我想参考答案应该是错的。
题中的元算符指操作符，分界符在课文中有优先级定义么？
按照优先级表，从+，—开始往右依次进栈时，都不会导致退栈，一直到(，然后可以继续循环，如此可以保证最多的操作符进栈，一次进栈3个操作符和“(”，然后循环，但是(需要“）”对应，设有x个“(”，那么4x+3+x=n。x=(n-3)/5 那么最多进栈的操作符是 4(n-3)/5+3+1 1是指栈底的#
(2)括号深度最大6个，那么如果n足够大的话，最多存入的元素是
4*6+3再进来就是)了，要退栈。加上# 一共是28个。此时的n应该 >=33
如果n& lt;33的话，答案还是4(n-3)/5+3+1=4(n+2)/5
4-7 设表达式的中缀表示为a*x-b/x^2，试利用栈将它改为后缀表示ax*bx2^/-。写出转换过程中栈的变化。
步序 扫描项 类型项 动 作 栈变化 输出
0 '#'进栈 #
1 a 操作数 # a
2 * 操作符 isp* >icp#，进栈 #* a
3 x 操作数 #* ax
4 - 操作符 isp-< icp*，退栈 # ax*
isp- >icp#，进栈 #- ax*
5 b 操作数 #- ax*b
6 / 操作符 isp/ >icp-，进栈 #-/ ax*b
7 x 操作数 #-/ ax*bx
8 ^ 操作符 isp^ >icp/，进栈 #-/^ ax*bx
9 2 操作数 #-/^ ax*bx2
10 # 操作符 isp#< icp^,退栈, #-/ ax*bx2^
isp#< icp/,退栈, #- ax*bx2^/
isp#< icp-,退栈, # ax*bx2^/-
结束
4-9 假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
队空条件:length==0;
队满条件:length==maxsize;
template< class Type >void Queue< Type >::EnQueue(const Type& item){
//若队列不满，则将元素item插入该队列的队尾，否则出错处理.
assert(!isFull()); //假设isFull()函数已经能够正确判断
rear=(rear+1)%MaxSize; //对为指针加1
elements[rear]=item; //在队尾插入item
length++;
}
template< class Type >Type Queue< Type >::DeQueue(){
//若队列不空则函数返回该队列队头的元素的值，同时将该队头元素删除.
assert(!isEmpty()); //同样假设已经修正isEmpty()函数.
length--; //队列长度减1
return element[(rear-length)%MaxSize]; //返回原队头元素
}
4-10 假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写出此结构相应的插入和删除函数。
加入标志tag，则循环队列结构中不需要空一个元素位置了。front依然指向第一个元素前的队头
改写isEmpty()和isFull()
队空：front==rear&&tag==0
队满：front==rear&&tag==1
template< class Type >void Queue< Type >::EnQueue(const Type& item){
//若队列不满，则将元素item插入该队列的队尾，否则出错处理.
assert(!isFull()); //假设isFull()函数已经能够正确判断
rear=(rear+1)%MaxSize; //对为指针加1
elements[rear]=item; //在队尾插入item
tag=1; //队列不空
}
template< class Type >Type Queue< Type >::DeQueue(){
//若队列不空则函数返回该队列队头的元素的值，同时将该队头元素删除.
assert(!isEmpty()); //同样假设已经修正isEmpty()函数.
front=(front+1)%MaxSize; //队头往前移1
tag=0; //队列不满
return element[front]; //返回原队头元素
}
Comments (0)