信管软件11级数据结构课程设计(9)

修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

40 回文判断

[问题描述]

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

[实现提示]

首先，序列1进栈，然后序列1出栈并与序列2比较。

[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。

41 商品货架管理

[问题描述]

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。 上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。

[基本要求]

针对一种特定商品，实现上述管理过程。

[实现提示]

用栈模拟货架和周转空间。

[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。

42 括号匹配的检验

[问题描述]

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或

[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8

当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程