数据结构 | 每日一练（94）

1. 对下面过程写出调用 P(3)的运行结果。

PROCEDURE p（w：integer）;

BEGIN

IF w>0 THEN

BEGIN

p(w-1);

writeln(w);{输出 W}

p(w-1）

END；

END；

2. 用一个数组 S（设大小为 MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用 C 或 PASCAL 设计公用的入栈操作 push（i，x），其中 i 为 0 或 1，用于表示栈号，x 为入栈值。

正确答案

PS：||代表注释

1、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。）

2、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。用C写的入栈操作push（i，x）如下：

const MAX=共享栈可能达到的最大容量

typedef struct node

{elemtype s[MAX]；

int top[2]；

}anode；

anode ds;

int push( int i,elemtype x) //ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0。

{ if（ds.top[1]-ds.top[0]==1）{printf（“栈满\n”）； return（0）；}

switch（i）

{ case 0：ds.s[++ds.top[i]]=x； break；

case 1：ds.s[--ds.top[i]]=x；

return（1）；}//入栈成功。

}