博客

在计算机中，数据的含义是极为文泛的，它包括数字、字符、字符串、图形、声音、表、文件等。

凡是可以输入到计算机中并可以被计算机程序进行处理的各种信息都可以称为数据。

早期的计算机，主要用于科学计算，所解决的问题一般是算法复杂但数据量少，结构简单，因此计算机科学主要研究程序及其算法。随着计算机技术的不断发展，应用领域的不断扩充，计算机更多地用于非数值计算——数据处理。由于数据处理技术的飞速发展，一门称为“数据结构”的新科学便应运而生了。

数据结构（

Data Structure


）是相互之间存在一种或多种特定关系的数据元素的集合

。数据结构是介于数学、计算机硬件、计算机软件之间的一门交叉学科，它主要研究数据的逻辑结构、物理结构以及对数据的操作。根据数据元素之间关系的不同特性，通常有下列四类基本结构：

①集合。结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

②线性结构。结构中的数据元素之间存在一个对一个的关系。

③树形结构。结构中的元素之间存在一个对多个的关系。

④图形结构或网状结构。结构中的元素之间存在多个对多个的关系。

由于“集合”是元素之间关系极为松散的一种结构，因此也可用其他结构来表示。

常见的数据结构有堆栈、队列、链表、树、图等。

一、椎栈概述

栈（

stack


）又叫堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作

进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

在日常生活中，有许多类似栈的例子，如刷洗盘子时，把洗净的盘子一个接一个地向上放（相当于进栈），取用盘子时，则从上面一个接一个地向下拿（相当于出栈）；又如向自动步枪的弹夹装子弹时，子弹被一个接一个地压入（相当于进栈），射击时总是后压入的先射出（相当于出栈）。

由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称作后进先出表（

Last In First Out,


简称


LIFO


）。

通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的元素，并用一个变量

t


指向当前栈顶

（如图

1-1


所示）。

假设栈中元素的上限为

m,


所有元素都具有同类型


stype


，则栈的定义可以描述如下：

const

t-1

……

m=

栈中元素的上限；

type

stack=array[1..m] of datatype;{


栈

的类型，

m


表示栈能够达到的最大深度

}

var

s:stack;                      {


定义


s


为栈


}

t:integer;{栈顶指针，

t


域用来存储栈顶元素所在单元的编号（即下标）

}

设一个栈为

T=(1,2,3,4),


栈


T


所对应的顺序存储结构如图


a


所示，若在


T


中插入一个元素


5


或删除一个元素，则分别对应的顺序存储结构如图


(b)


和


(c)


所示。

在栈的顺序存储结构中，为形象地使栈顶在上，栈底在下，所以采用的单元编号是向上递增的。

……

5

4

3

2

1

……

3

2

1

……

4

3

2

1

顺序栈的插入和删除示意图

二、栈的运算

栈的运算主要是插入和删除，除此之外，还有读取栈顶元素、置空栈和判断一个栈是否为空等。栈的运算都比较简单，具体列出如下：

1

．进栈算法

算法步骤为：

(1) 检查栈是否已满，若栈满，则进行“溢出”错误处理；否则执行步骤

(2)

(2) 将栈顶指针上移（即加

1


）；

(3) 将新元素赋给栈顶单元。

算法描述为：

过程

push(s,x,t)


——往栈


s


中插入一个值为


x


的元素

procedure push(var s:stack;x:datatype;var t:integer);

begin

if  t=m then writeln(‘overflow’)    {


上溢


}

else begin t:=t+1;s[t]:=x;end;      {x

入栈


}

end;

此算法中的第

(1)


步是必不可少的，例如，当你确信插入后不会造成溢出或者在调用此算法 之前已经判断栈未满时，则可省去此步。

2

．出栈算法

算法步骤为：

(1) 检查栈是否为空，若栈空，则进行“下溢”错误处理；否则执行步骤

(2)

(2) 将栈顶元素赋值给特定变参

x


（或者作为函数返回）；

(3) 将栈顶指针下移（即减

1


）。

算法描述为：

函数

pop(s,t)


——从栈中弹出一个元素

function pop(var s:stack;var t:integer):datatype;

begin

if t=0 then writeln(‘underflow’)     {


下溢


}

else begin pop:=s[t];t:=t-1;end;{


栈顶元素出栈


}

end;

此算法的第

(1)


步有时也可以省略，如当你确信不会发生下溢，或者调用此算法之前已经判定栈未空时就是如此。从出栈算法可以看出：原栈顶元素仍然存在（即没有被破坏），只是栈顶指针不指向它，而指向了它下面的元素。

3

．读取栈顶元素的算法

此算法很简单，只要将栈顶元素赋给指定变参或函数名即可。假定写成函数的形式，则为：

函数

top(s,t)


——读栈顶元素

function top(var s:stack;t:integer):datatype;

begin

if t=0 then writeln(‘stack empty’)

else pop:=s[t];                 {


返回栈顶元素


}

end;

注意：在这个算法中栈顶指针保持不变。

4.

置空栈算法

此算法也很简单，只要把栈顶指针置

0


即可。算法描述为：

procedure setnull(var s:stack;var t:integer);

begin

s[t]:=0;

end;

5.

判断一个栈是否为空栈的算法

此算法可用一个函数来描述，栈空时返回“真”值，非空时返回“假”值。

function empty(var s:stack, t:integer):bollean;

begin

if s[t]=0

then empty:=true;

else empty:=false

end;

在上面栈的各种算法中，都不需要进行元素的比较和移动，所以其时间复杂性均为

O(1)


。


{



参见


G:\


信息


\pascal


讲义


\


关于时间复杂度


}

三、栈的应用

表达式的计算

1.

算述表达式的两种表示

通常书写的算术表达式是把运算符放在两个操作数

(


又叫运算对象或运算量


)


的中间


.


如对于


2+5*6,


乘法运算符”


*


”的两个操作数是它两边的


5


和


6;


加法运算符”


+


”的两个操作数


,


一个是它前面的


2,


另一个是它后面的


5*6


即


30.


我们把算术表达式的这种表示叫做中缀表达式


,


采用中缀表示的算术表达式简称中缀算术表达式


.

中缀表达式的计算必须按照以下三条规则进行

:

(1)

先算括号内


,


后算括号外


;

(2)

在无括号或同层括号内的情况下


,


先做乘除运算


,


后做加减运算


,


即乘除运算的优先级高于加减运算的优先级


(


假定我们只讨论这四种运算


);

(3)

同一优先级运算


,


从左向右依次进行


.

从这三条规则可以看出

,


在中缀表达式的计算过程中


,


即要考虑括号的作用


,


又要考虑运算符的优先级


,


还要考虑运算符出现的先后次序


.


通过计算机处理就比较麻烦了


,


因为计算机只能一个字符一个字符地扫描


,


要想得到哪一个运算符先算


,


就必须对整个中缀表达式扫描一遍


,


一个中缀表达式中有多少个运算符


,


原则上就得扫描多少遍才能计算完毕


,


这样就太浪费时间了。

波兰科学家卢卡谢维奇提出了算术表达式的后缀表示

,


又称逆波兰式


,


其

定义是把运算符放在两个运算对象的后面

.


采用后缀表示的算术表达式简称后缀算术表达式或后缀表达式

.在后缀表达式中

,


不存在括号


,


也不存在优先级的差别


,


计算过程完全按照运算符出现的先后次序进行


,


整个计算过程仅需一遍扫描便可完成

。例如

,


对于后缀表达式


12_4_-5_/,


其中”


_


”表示空格字符


,


因减法运算符在前


,


除法运算符在后


,


所以应先做减法


,


后做除法


;


减法的两个操作数是它前面的


12


和


4,


其中第一个数


12


是被减数


,


第二个数


4


是减数


;


除法的两个操作数是它前面的


12


减


4


的差


(


即


8)


和


5,


其中


8


是被除数


,5


是除数


.

中缀算术表达式转换成对应的后缀算术表达式的规则是

:


把每个运算符都移到它的两个运算对象的后面


,


然后删除掉所有的括号即可


.

例如

,


对于下列各中缀表达式


:

(1)3/5+6

(2)16-9*(4+3)

(3)2*(x+y)/(1-x)

(4)(25+x)*(a*(a+b)+b)

对应的后缀表达式分别为

:

(1)3_5_/6_+

(2)16_9_4_3_+*-

(3)2_x_y+*1_x_-/

(4)25_x_+a_a_b_+*b_+*

下面我们将讨论后缀表达式求值的算法

.


为了讨论方便


,


更好地突出本题的本质


,


不妨假定算术表达式中的每个操作数都是大于等于


0


的整数


,


并且算术表达式的语法都是正确的


,


因而不需要在算法中进行语法检查


.

设定一个栈

S1,


类型为


stack,


成分类型为实型


(real),


用它来存储运算的操作数


,


中间结果以及最后结果


.


作为此算法的输入


,


假定在一个字符型数组


A


中已存放着一个以


@


字符作为结束符的后缀算术表达式


,


并且该表达式中的每个操作数都是以空格字符结束的


.

此算法的基本思路是

:


从数组


A


中的第一个字符起扫描


,


若遇到的是数字字符


,


则就把以它开头的一组数字字符


(


直到遇到空格字符为止


)


转换成对应的数值


(


即一个操作数


)


后压入


S1


栈


;


若遇到的是运算符


,


则就从


S1


栈顶依次弹出两个操作数


,


进行相应的运算后


,


再把结果压入


S1


栈


;


继续扫描下一个字符并处理


,


直到遇到


@


字符为止


.


算法结束后


,S1


栈顶的值就是数组


A


中后缀算术表达式的计算结果


.


假定该结果由函数名带回


,


则算法描述为


:

{14_3_20_5/*8_-+@}

function comp(A):real;

begin

setnull(S1)；

i:=1;

ch:=A[i];

while ch<>’@’  do

case ch of

‘0’..’9’:x:=0;

while ch<>‘ ’ do

begin

x:=x*10+ord(ch)-ord(‘0’)

i:=i+1;

ch:=A[i];

end;

‘+’:x:=pop(S1)+pop(S1);

‘-’:x:=pop(S1);

x:=pop(S1)-x;

‘*’:x:=pop(S1)*pop(S1);

‘/’:x:=pop(S1);

x:=pop(S1)/x

end

push(S1,x);

i:=i+1;

ch:=A[i];

return(pop(S1))

end;

此算法的运行时间主要花在扫描上

,


算法从头到尾扫描并处理数组


A


中字符


,


若后缀算术表达式由


n


个字符组成


,


则此算法的时间复杂性为


O(n).


此算法在运行时所占用的临时空间主要取决于


S1


栈的大小


,


显然


,


它的最大深度不会超过表达式操作数的个数


.


若操作数的个数为


m.


则此算法的时间复杂性为


O(m).

在这个算法中

,


若数组


A


的后缀表达式为


:

14_3_20_5/*8_-+@

则从第四个操作数开始

,


每处理一个操作数或运算符后


,S1


栈的状态如下图所示


:

S1

栈的数据变化

3

、把中缀表达式转 换成后缀表达式的算法

中缀算术表达式转换成对应的后缀算术表达式的规则是：把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。

将下列的中缀表达式改写成后缀表达式：

（

1


）


3/5+6

（

2


）


16-9*


（


4+3


）

（

3


）


2*


（


x+y


）


/(1-x)

（

4


）（


25+x


）


*(a*(a+b)+b)

结果为：

(1)

、


3_5_/6_+

(2)

、


16_9_4_3+*-

(3)

、


2_x_y+*1_x_-/

(4)

、


25_x+a_a_b_+*b_+*

两种表达式的异同：操作数出现的先后顺序没有变，只有运算符变了。根据中缀表达式的三条运算规则，有多少运算符就扫描多少遍就能确定每个运算符出现的先后顺序，从而得到后缀表达式。

怎么优化这个算法，减少扫描的次数，从而更快捷得到后缀表达式呢？

这要从中缀表达式运算符的优先级入手。

在中缀算术表达式中，设P1

和


P2


分别表示前后相邻出现的两个算符

，那么

P1


和


P2


之间的优先关系只能是下列两种情况之一：

P1<P2

表示


P1


落后于


P2


运算或者说


P2


优先于


P1


运算

P1>P2

表示


P1


优先于


P2


运算或者说


P2


落后于


P1


运算

根据中缀算术表达式运算的三条规则，相邻算符之间的优先关系下表所示。

P2 P1	+	–	*	/	(	)	@
+	>	>	<	<	<	>	>
–	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=
)	>	>	>	>		>	>
@	<	<	<	<	<		=

相邻算符优先关系表

分析：设以

@


字符结束的一个中缀算术表达式已存放在字符型数组


E


中，而转换后生成的后缀算术表达式用字符数组


A


来存放。在转换过程中需要使用一个栈，假定用


S2


表示，

用它来暂存不能立即送入数组

A


中的算符（这里暂且把运算符、左右圆括号和表达式结束符统称为算符）

，因此，

S2


栈的成分类型应为字符型，


S2


栈的最大深度不会超过中缀算术表达式中算符的个数。

当把中缀表达式转换成后缀表达式时，为了栈处理的方便，往往在栈底首先放入一个表达式结束符

@


，

并令它具有最低的优先级（即落后于其他任何算符），当栈处理结束时，会出现表达式最后的

@


字符同栈底的


@


字符相遇的情况，此时表明中缀表达式已经转换完毕，所以在表中把它们定义为“


=


”关系。在表达式处理中，有时还可能遇到右括号与栈顶的左括号比较优先关系的情况，所以必须对它们给予定义，由于它们在算术表达式中只能同时存在和消失，所以在表中也把它们定义为“


=


”关系。在表中还有三处空白，这是


P1


和


P2


算符不应该相遇的情况，若发生这种情况，则表明中缀算术表达式中有语法错误。

把中缀表达式转换成对应的后缀表达式的基本思路是：从数组

E


的第一个字符起扫描，当遇到的是数字字符时，就把以它开始的

一组数字字符（直到非数字字符为止）和附加的一个空格字符依次送入数组

A


；遇到的是算符时，

首先检查这它是否落后于栈顶算符的运算，若是，则表明栈顶算符的两个运算对象已经被送入到数组

A


中，应将栈顶算符退栈并送入数组


A


，

以此反复进行，直到不落后于栈顶算符为止，接着检查它是否优先于栈顶算符，若是，则表明它的第二个运算对象还没有被送入数组

A


中，所以应把它进栈，

否则表明该算符必然是右括号，栈顶算符必然是左括号，因该括号内的算符已处理完毕，所以应把左括号从栈顶退出；继续扫描和处理下一个字符，直到遇到结束符

@


后，再做必要的结束处理即可。

在这个算法中，若数组

E


中的中缀表达式为：

2 *

（（


8+7


）


/15


）


+9@

则每处理一个算符后，数组

A


和栈


S2


的状态如下图所示。

算法描述为：

procedure change(E,A)

begin

(1) setnull(S2);push(S2,’@’);

i:=1;{i

作为扫描数组


E


的指针


}

j:=1;{j

用来指示数组


A


中待写入字符的位置


}

ch:=E[i];{E

中第一个字符送给


ch}

(2)while ch<>’@’ do

(I) if ch in op1 then {op1

为数字字符的集合


}

(a)while ch in op1 do

A[j]:=ch ;j:=j+1;i:=i+1;ch:=E[i];

(b)A[j]:= ‘ ’;j:=j+1;

{


给


A


中的每个操作数后附加一个空格


}

(

Ⅱ


)if ch in op2 then {op2


为算符的集合


}

(a)w:=readtop(S2);

while precede(w,ch)=

’


>


’


do                          { [pri(:)’si:d]


较


…


优先


}

{precede

为比较两算符优先关系的函数


}

A[j]:=w;j:=j+1;pop(S2);w:=readtop(S2)

(b)if precede(w,ch)=’<’ then push(S2,ch)

else pop(S2);

(

Ⅲ


)i:=i+1;ch:=E[i];

(3)(I)w:=pop(S2);

while w<>’@’ do

A[j]:=w;j:=j+1;w:=pop(S2);

(

Ⅱ


) A[j]:=

‘@’

end;

{此算法的运行时间主要花在第（

2


）步上，如果单从这一步的


while


外循环来看，其时间复杂性为


O(n)


。那么循环体内的每一个


while


循环和


precede


函数是否会增加此算法的时间复杂性呢？

从第（

I


）步看，显然是不会的，因为每一次循环都 将顺序处理数组


E


中的下一个字符；从第（Ⅱ）步看，也是不会的，因为这里调用的


precede


函数实际上就是根据两个算符到上表中去查找其对应的优先关系，这种查找所需时间是固定的，它不随处理问题的规模（在此是指中缀算术表达式中包含字符的多少）而改变，在第（Ⅲ）步中出现的


while


循环在任何情况下都不会超过两次循环。因此，整个算法的时间复杂性为


O(n).

}

从上面算术表达式的计算过程可以看出，利用后缀表示和栈技术只需两遍扫描即可完成，其中第一遍是把算术表达式的中缀表示转换成对应的后缀表示，第二遍是根据后缀表示进行求值。显然它比直接利用中缀算术表达式进行计算的扫描次数要少得多，算法的复杂性和编程的复杂性大大降低。

例

1


计算后缀表达式

所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后，所有计算按运算符出现的顺序，严格地由左往右进行，不再考虑运算符的优先规则。例如，

5*


（


7-3


）


+9


对应的后缀表达式为


5.7.3.-*9.+@,


其中

“@”为后缀表达式的结束标记，“

.


”为操作数的结束符。

5.7.3.-*9.+

=5.4.*9.+

=20.9.+

=29

●输入数据

后缀表达式

A

●输出数据

表达式的值

算法分析

设后缀表达式为

A


，操作数和计算结果存放在栈


S


中，


S


的元素类型


datatype


为整型。计算过程如下：

由左向右处理

A


中的每一个字符。若遇到一个操作数，就送入栈


S


中保存；遇到一个操作符，就从栈中取出栈顶的两个操作数进行计算，然后将结果重新压入栈中。依次类推，直至表达式最后一个操作符处理完毕，这时的栈顶元素值即为计算结果。

参考程序

program aa;

const m=maxint;

type

stack=array[1..m] of integer;

var

s:stack;                                                  {


栈


S}

a:string;                                                  {


定义后缀表达式


}

t,i,j,k:integer;

{t

—栈顶指针；


i


—

后缀表达式的字符指针；

j,k


—操作数值


}

begin

read(a);

i:=1;t:=0;

while A[i]<>’@’ do

begin

case A[i] of

‘0’..’9’:begin

k:=0;

repeat                {


从后缀表达式中取出操作数


k}

k:=10*k+ord(A[i])-ord(‘0’);

i:=i+1;

until A[i]:=‘.’;

push(s,k,t);               {


操作数


k


压入栈中


}

end;{‘0’..’9’}

‘+’:push(s,pop(s,t)+pop(s,t),t);

‘-’:begin

j:=pop(s,t);

push(s,pop(s,t)-j,t);

end;{‘-’}

‘*’:push(s,pop(s,t)*pop(s,t),t);

‘/’:begin

j:=pop(s,t);

push(s,pop(s,t)div j,t);

end;{‘/’}

end;{case}

i:=i+1;

end;{while}

writeln(pop(s,t));

end.{main}

输出值为：

29

符

:ord(

‘A’)

为求字符


A


的


ASCII


码值，故其值为


65


。

例２、判断包含有括号

{,[,<,(,),>,],}


组成的字符串是否匹配。

如输入：

[bdw{*(ersfw)h<ipu>fdf}<a#/h>]fwy


，则显示匹配


(match)


。

如输入：

[fe(a-<4{trb>}ijk])


或


{a}[,


则显示不匹配


(mismatch)


。

即左右括号成对出现，并且顺序正确，叫作“匹配”。

算法分析：

用堆栈来解决此题。数组

s


作为堆栈，


t


为栈顶指针。当从字符串中读到一个左括号时，就将其压入堆栈。当读到一个右括号时，就从栈顶取出存储的左括号，与当前的右括号比较，是否匹配，如果匹配，就将这个左括号弹出堆栈；否则就显示不匹配。全部字符串读完后，再检查一下，堆栈中是否空，如果不空，表示有左括号无右括号与它匹配，显示不匹配。

参与程序：

program aa;

const m=100;

type

stack=array[1..m] of char;

var

s:stack;

a:string;

t,i:integer;

begin

t:=0;

i:=1;

read(a);

while (a[i]<>’@’) do

begin

case a[i] of

‘(‘,'[‘,'{‘,'<‘:begin

t:=t+1;

s[t]:=a[i];

end;

end;

if a[i]=’)’

then

begin

if s[t]='(‘ then t:=t-1

end;

if a[i]=’]’ then

begin

if s[t]='[‘ then t:=t-1

end;

if a[i]=’}’ then

begin

if s[t]='{‘ then t:=t-1

end;

if a[i]=’>’ then

begin

if s[t]='<‘ then t:=t-1

end;

i:=i+1;

end;

if t=0 then writeln(‘match’)

else writeln(‘mismatch’);

end.

例

3.


编写一个算法，对于给定的十进制正整数，打印出相应的八进制整数。

分析：把十进制正整数转换成对应的八进制整数采用逐次除

8


取余法，即用基数


8


不断地去除被转换的十进制正整数，直到商为


0


。设转换后得到的八进制整数为


k

mkm-1…

k

1k0(m

≥


0),


则第一次相除所得余数就是八进制整数的最低位


k

0,

第二次相除所得余数就是八进制的整数的次最低位


k

1,

依次类推，最后一次相除所得余数（

即商为

0


时的余数

）就是八进制整数的最高位

k

m。

例如，把十进制正整数

765


转换成对应的八进制整数的过程下图所示

设被转换的十进制正整数用

n


表示，每次整除


8


所得余数用


k


表示，若采用递归的方法来编写此题的算法，则具体步骤为：

(1) 用

8


对


n


作取余运算，将结果赋给


k;

(2) 用

8


去整除


n,


将结果仍赋给


n;

(3) 如果

n


不为


0


，则以


n


为实参调用本过程；

(4) 按域宽为

1


打印


k


的值。

用伪代码编写此递归过程的算法为：

transfer(n)

k:=n mod 8

n:=n div 8

if n<>0 then transfer(n)

write(k:1)

完整程序参考

:

program aa;

var

n:integer;

procedure transfer(n:integer);

var

k:integer;

begin

k:=n mod 8;

n:=n div 8;

if n<>0 then transfer(n);

write(k:1)

end;

begin

read(n);

transfer(n);

end.

计算机执行递归算法（包括递归过程和递归函数）时，是通过栈来实现的。具体地说，在运行开始时，首先为递归调用建立一个栈，该栈的成分类型（即元素类型）包括值参域、局部变量域和返回地址域；在每次执行递归调用语句或函数之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压入栈；在每次递归调用语句或函数执行结束后，又自动把栈顶各域的值分别赋给相应的值参和局部变量，以便使它们恢复为调用前的值，接着无条件转向（即返回）由返回地址域所指定的位置执行。

对于调用上面的递归过程来说，系统首先为后面的递归调用建立其成分类型包含值参

n


的域、局部变量


k


的域和返回地址的一个栈；在每次执行


transfer(n)


语句递归调用前，自动把


n


和


k


的当前值以及


write


语句的开始位置（即调用后的返回地址）压入栈；在每次执行到最后的


end


（即一次递归调用结束）后，又自动把栈顶的与


n


和


k


对应域的值分别赋给


n


和


k,


接着无条件转向


write


语句的开始位置，继续向下执行。

上面的分析说明了系统如何利用堆栈技术来进行递归处理的。下面我们将讨论如何模拟系统处理递归的方法把一个递归算法改写成一个非递归的算法，从而进一步加深对堆栈和递归这两个重要概念的理解和认识。

设

p


是一个递归算法，假定


p


中共有


m


个值参数和局部变量，共有


t


处递归调用


p


的过程语句或函数引用，则把


p


改写成一个非递归算法的一般规则为：

(1)

、定义一个栈


s


，用来保存每次递归调用前值参和局部变量的当前值以及调用后的返回地址，


s


栈中的成分类型应包含


m+1


个域，其中前


m


个域为值参和局部变量而设，后一个域为返回地址而设，


s


栈的深度应足够大，使得在递归调用中不会发生溢出；

(2)

、定义


t+2


个语句标号，其中用一个标号标在原算法中的第一条语句上，用另一个标号标在作返回处理的第一条语句上，其余


t


个标号作为


t


处递归调用的返回地址，分别标在相应的语句上；

(3)

、把每一个递归调用的语句或函数改写为：

(I)

、把值参和局部变量的当前值以及调用后的返回地址压入栈；

(Ⅱ)、把值参所对应的实在参数表达式的值赋给值参变量；

(Ⅲ)、无条件转向原算法的第一条语句；

(4)、在算法结尾之前增加返回处理，当栈非空时做：

(Ⅰ)、退栈；

(Ⅱ)、把原栈顶中前

m


个域的值分别赋给各对应的值参和局部变量；

(Ⅲ)、无条件转向由本次返回地址所指定的位置；

(5)、增设一个同

s


栈的成分类型相同的变量，作为进出栈的缓冲变量，对于递归函数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中所有函数名


,


待函数过程结束之前，再把这个变量的值赋给函数名返回；

(6)、在原算法的第一条语句之前，增加一条置栈空的语句；

(7)、对于递归函数而言，若某条赋值语句中包含有两处或多处（假定为

n


处，


n


≥


2


）递归调用，则应首先把它拆成


n


条赋值语句，使得每条赋值语句中只包含一处递归调用，同时对增加的


n-1


条语句赋值语句，要增设


n-1


个局部变量，然后再按照以上六条规则转换成非递归函数。

例4、给出按后缀表示法输入的一个算术表达式，表达式中只有26个大写英文字母和加减乘除四个运算符号，表达式的长度≤50,表达式以@号结束。编程求出它的等价中缀表表式。

输入：

通过文件输入后缀表达式，文件只有一行，就是后缀表达式。

输出：

输出它的等价中缀表达式。

样例：

输入：input.txt:                 输出:out.txt

AB+CD*EF-*/                (A+B)/(C*D*(E-F))

program aa;

type

link=^btree;

btree=record

info:char;

left,right:link;

end;

var

p,root:link;

str:string;

n,i:integer;

data:text;

procedure setbtree(var p:link);

begin

if n>=1 then begin

new(p);

p^.info:=str[n];

p^.right:=nil;p^.left:=nil;n:=n-1;

if p^.info in [‘+’,’-’,’*’,’/’] then

begin

setbtree(p^.right);

setbtree(p^.left);

end;

end;

end;

function btree_travel(p:link):string;

var a,b:string;

begin

if not (p^.info in [‘+’,’-’,’*’,’/’])  then btree_travel:=p^.info

else begin

a:=btree_travel(p^.left);b:=btree_travel(p^.right);

if (p^.info in [‘*’,’/’]) and (p^.left^.info in [‘+’,’-’]) then a:=’(’+a+’)’;

if (p^.info in [‘*’,’-’]) and (p^.right^.info in [‘+’,’-’]) then b:=’(’+b+’)’;

if (p^.info in [‘/’]) and (p^.right^.info in [‘+’,’-’,’*’,’/’]) then b:=’(’+b+’)’;

btree_travel:=a+p^.info+b;

end;

end;

begin

assign(data,’t5.txt’);reset(data);

read(data,str);close(data);n:=0;

for i:=1 to length(str) do

if (str[i]=’@’) and (n=0) then n:=i;

n:=n-1;

new(p);p^.info:=str[n];p^.left:=nil;p^.right:=nil;

root:=p;n:=n-1;

if root^.info in [‘+’,’-’,’*’,’/’] then

begin

setbtree(p^.right);

setbtree(p^.left);

end;

writeln(btree_travel(root));

end.

习题一

一、 单项选择题

1

、设栈的输入序列为


1


、


2


、


3


、……、


n


，输出序列为


a1


、


a2


、……、


an


，若存在


1


≤


k


≤


n,


使得


ak=n,


则当


k


≤


i


≤


n


时，


ai


为


(  )


。

A

．


n-i+1     B.n-(i-k)    C.


不确定

2.

设栈的输入序列是


(1


、


2


、


3


、


4)


，则


(  )


不可能是其出栈序列。

A.  1243    B.    2134    C.    1432    D.    4312    E.    3214

3.

已知一算术表达式的中缀形式为


A+B*

C﹣D/E ，其后缀形式为ABC*+DE/- ,其前缀形式为(  )

A. –A+B*C/DE    B. –A+B*CD/E  C. – + * ABC/DE  D. – + A*BC/DE

4.设栈的输入序列是1、2、…、n，若输出序列的第一个元素是n，则第i个元素是(  )

A．不确定  B.  n-i+1  C.  i   D.  n-i

5.当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行(    )语句修改top的指针。

A．inc(top) B.dec(top) C.top=0  D.top:=1

6.假定一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为(    ).

A.p^.next:=top;top:=top^.next

B.top:=p;p^.next:=top

C.p^.next:=top^.next;top^.next:=p

D.p^.next:=top;top:=p

7.假定一个链接的栈顶指针用top表示，当进行退栈时所进行的指针操作为（    ）。

A.top^.next:=top    B.top:=top^.data

C.top:=top^.next    D.top^.next:=top^.next^.next

8.若让元素1,2,3依次进栈，每个元素进栈后随时可以出栈，则出栈次序不可能出现(    )情况.

A.3,2,1    B.2,1,3    C.3,1,2    D.1,3,2

9. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是_________。

（1）A，B，C，D   （2）D，C，B，A  （3）A，C ，D，B  （4）D，A，B

解析：事实上，入栈和出栈操作是可以交替进行的。例如，若用I表示入栈，用O表示出栈，则下面的操作序列是合法的：I1，I2，O1，I3，O2，I4，O3，O4。而这一操作序列对本题的输入所得到的输出序列为B，C，D，A。

10.设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈，出栈顺序为b,d,c,f,e,a那么栈容量至少应该是（    ）

A.6 B.5 C.4 D.3 E.2

11.设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的有

（ ）。

A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g

D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a

12.以下哪一个不是栈的基本运算(  )

A)删除栈顶元素      B)删除栈底的元素

C)判断栈是否为空    D)将栈置为空栈

13.设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是________。

(A){5，4，3，2，1}    (B){2，1}    (C){2，3}     (D){3，4}

14.已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；90在87后面；20在14后面；25在6前面；19在90后面。（        ）

A）20，6，8，51，90，25，14，19，87

B）51，6，19，20，14，8，87，90，25

C）19，20，90，8，6，25，51，14，87

D）6，25，51，8，20，19，90，87，14

E）25，6，8，51，87，90，19，14，20

15

．中缀表达式


A-(B/D)*E


的后缀形式是什么？

中缀形式：即一般情况下的表达式方式，将运算符写于参与运算的操作数的中间，操作数依原序列排列。后缀形式：式中不再引入括号，运算符放在参与运算的操作数之后，操作数的排列依原序列，所有计算按运算符出现的顺序，严格地由左而右进行

(


不再考虑运算符的优先规则


)


。所以利用堆栈的特性，可以得出本题的答案是


ABCD/+E*-


。

附：前缀就是运算符在两个操作数的前面

比如，

+ A B


属前缀

咱们平常使用的属中缀比如

A + B

后缀自然就是

A B +

设输入元素为

1


、


2


、


3


、


P


和


A


，输入次序为


123PA


，如下图所示，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？

高级语言变量名的定义规则：以字母与数字的组合。

由于必须以字母开头，所以，第一个可能出现的字母是

p


，那么必然要求


123


已经先后入栈，这样便可得到以


P


开头的、并且


123


按逆序排列的


(


即


321)


、同时


A


位于


P


后任一位置的变量名序列。此外，还需要考虑以


A


开头的可能情况，这只有一种情形：


AP321


。所以


AP321


、


PA321


、


P3A21


、


P32A1


、


P321A


可以作为高级语言的变量名。

二、编程：

1

、阅读程序：

已知Ackerman函数的定义如下：

Akm(m,n)=

(1)

写出递归算法 。

(2)

写出非递归算法 。

(1)function akm(m,n:integer):integer;

Begin

If (m=0) then

Akm:=n+1

Else

If (n=0) then

Akm:=akm(m-1,1)

Else

Akm:=akm(m-1,akm(m,n-1));

End;

(2)function ackerman(m,n:integer):integer;

Var

I,j:initeger;

Akm:array[1..maxm,1..maxn] of integer;

Begin

Fillchar (akm,sizeof(akm),0);

For j:=0 to maxn-1 do

Akm[0,j]:=j+1;

For i:=1 to  m do

Begin

Akm[I,0]:=akm[i-1,1];

For j:=1 to maxn-1 do

Akm[I,j]:=akm[i-1,akm[I,j-1]];

End;

Ackerman:=akm[m,n];

End;

2

、写出下列递归过程等价的非递归过程

procedure test(var sum:integer);

var a:integer;

begin

read(a)

；

if a=0 then sum:=1

else

begin

test(sum);

sum:=sum*a

end;

write(sum);

end;

此题的核心语句为

test(sum);

sum:=sum*a;

而

test


由于是递归调用实际上完成一个“多次读入


a


”的任务。只要


a<>0


就不停地读入，当


a=0


时，使


sum=1.


在通过不停地返回到上一层的调用过程实现把当前调用已经读入的全部


a


反向


(


与读入的顺序相反


)


逐个相乘。

由此可见，算法分成两部分：一部分是读入

a


并保存，另一部分是求出数


1


与当前已经读入所有


a


的反向相乘的乘积。

procedure test;

var stack:array[1..maxsize] of integer;

top,sum,a:integer;

begin

top:=0;

sum:=1;

read(a);

while a<>0 do

begin

top:=top+1;

stack[top]:=a;

read(a);

end;

write(sum);

while top<>0 do

begin

sum:=sum*stack[top];

top:=top-1;

write(sum);

end;

end;

从历届初赛可以看出，栈也是属于比较容易出题的知识点，选择题、解答题等题型都有可能出现。

2

、背包问题

问题：假设有

n


件质量分配为


w1


，


w2


，


…


，


wn


的物品和一个最多能装载总质量为


T


的背包，能否从这


n


件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即


wi1+wi2+…+wik=T


。若能，则背包问题有解，否则无解。

算法思想：首先将

n


件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。

若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。

具体实现：设用数组

weight[1..N]


，


stack[1,N]


分别存放物品重量和已经装入背包（栈）的物品序号，


MaxW


表示背包的最大装载量。每进栈一个物品，就从


MaxW


中减去该物品的质量


,


设


i


为待选物品序号


,


若


MaxW-weight[i]>=0


，则该物品可选；若


MaxW-weight[i] < 0


，则该物品不可选


,


且若


i>n


，则需退栈，若此时栈空，则说明无解。

用

Pascal


实现的参考函数：

Function knapstack(n,MaxW,weight);

begin

top:=0; i:=1; {i

为待选物品序号


}

while (MaxW>0) and ( i < = n ) do

begin

if (MaxW-weight[i]>=0) and  ( i < = n ) then

begin top:=top+1; stack[top]:=i;MaxW=MaxW-weight[i] end;

{


第


i


件物品装入背包


}

if MaxW=0 then return(true)

else begin

if (i=n) and (top>0) then {


背包内有不合适物品


}

begin  {


取栈顶物品，恢复


MaxW


的值


}

i:=stack[top]; top:=top-1;MaxW=MaxW+weight[i];

if top>0 then begin

i:=stack[top]; top:=top-1;MaxW=MaxW+weight[i];

end;

end;

i:=i+1;

end;

end;

return(false) {


问题无解


}

end;

3

、假设一个算术表达式中可包含三种括号：圆括号“


(


”和“


)


”；方括号“


[


”和“


]


”以及花括号“


{



”和“


}


”，且这三种括号可按任意的次序嵌套使用，试利用栈的运算，判别给定的表达式中所含括号是否正确配对出现。

分析：如果括号只有一种，比如说是“

(


”和“


)


”，则判断是否正确匹配可以这样进行：

用一个计数器

T


来记录左括号与右括号比较的情况，初始时


T=0


，表达式从左向右扫描，如果遇到左括号则


T


←


T+1


，遇到右括号则


T


←


T-1


，中间如果出现


T<0


的情况，说明右括号的个数大于左括号的个数，匹配出错；扫描结束时，如果


T<>0


，说明左右括号的个数不相等，匹配出错。

但本题的括号有三种，这里用栈可以较好地解决，方法如下：

(1)

将“


(


”，“


[


”，“


{



”定为左括号，“


)


”，“


]


”，“


}


”定为右括号，建一个栈来存放左括号，初始时，栈为空；

(2)

从左向右扫描表达式，如果是左括号，则将其压入栈中；如果是右括号则

（

a


）栈顶是与该右括号匹配的左括号，则将它们消去，重复


(2)

（

b


）栈顶的左括号与该右括号不匹配，则匹配错误；

(3)

扫描结束时，若栈非空，则匹配错误。

4

计算四个数：由键盘输入正整数


A


，


B


，


C


，


D(1<=A


，


B


，


C


，


D<=10)


；然后按如下形式排列：

A

□


B


□


C


□


D=24


；在四个数字之间的□处填上加，减，乘，除四种运算之一


(


不含括号


)


，输出所有满足条件的计算式子。若不能满足条件，则打印“


NORESULT!


“。

分析：

A


，


B


，


C


，


D


四个数的位置已经固定，因此只需将


+


，


–


，


*


，


/


四种运算符依次放入三个□中，穷举所有可能的情况，再计算表达式的值即可。

5

、问题描述：编号为


1


，


2


，……，


n


的


n


辆列车顺序进入一个栈式结构的站台。试给出这


n


辆列车开出车站的所有可能次序。

var

s:array[1..100]of integer;

a:array[1..100]of integer;

i,j,k,l,m,n:integer;

procedure serch(k{n},m{a},i{s}:integer);

var j,temp:integer;

begin

if m=n then begin

for j:=1 to n do write(output,a[j],’ ‘);

writeln;

exit;

end;{full}

if k<>n+1 then begin temp:=s[i+1];

s[i+1]:=k;

serch(k+1,m,i+1);

s[i+1]:=temp;end;{in}

if i<>0 then begin

temp:=a[m+1];

a[m+1]:=s[i];

serch(k,m+1,i-1);

a[m+1]:=temp;

end;{out}

end;

begin

assign(input,’d:\work.in’);

reset(input);

assign(output,’d:\work.out’);

rewrite(output);

read(input,n);

serch(1,0,0);

close(input);

close(output);

end.

习题二

一、选择题

1

、栈的特点是（  ）

A

先进先出


B


先进后出

2

、一个栈的进栈序列是


a,b,c,d,e,


则栈的不可能的输出序列是（   ）

A

、


edcba    B


、


ecba    C


、


dceab    D


、


abcde

3

、若已知一个栈的进栈序列是


1


，


2


，


3


，…，


n


，其输出序列为


P1,P2,p3

,…,Pn,若P1=n,则Pi(1≤i<n)为(    )

A.i    B.n=i    C.n-i+1    D.不确定

解：当P1=n，即n是最先出栈的，根据栈的原理，n必定是最后出栈，那么输入顺序必定是1,2,3,…,n,则出栈的序列是n,…,3,2,1。本题答案是C。

4

、若已知一个栈的进栈序列是


1,2,3

,…,n,其输出序列为P1,P2,p3,…,Pn, 若Pn=n,则Pi(1≤i<n)为(    )

A.i    B.n=i    C.n-i+1    D.不确定

解  当Pn=n,也就是n最后出栈，前面1～n-1的元素可以任意进栈出栈。本题答案是D。

5、若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1=3，则P2为（    ）

A.可能是2  B. 不一定是2  C.可能是1  D.一定是1

解：当P1=3，表示3最先出栈，前面1、2应在栈中，此时若出栈操作，则P2应为2，此时若进栈操作如4进栈（栈中元素为1、2、4），P2就不一定是2。本题答案为A。

6、若已知一个栈的进栈序列P1,P2,P3,…,Pn,输出序列是1,2,3,…,n。若P3=1，则P1为(    )

A、可能是2  B、一定是2  C、不可能是2  D、不可能是3

解  由于输出序列是1,2,3,…,n。P3=1最先出栈，则P1，P2在栈中，此时若出栈操作，表示

P2为2，此时若为进栈操作，表示P1和都不可能是2，因此，P1不可能是2。本题答案为C。

7、若已知一个栈的进栈序列P1,P2,P3,…,Pn,输出序列是1,2,3,…,n。若Pn=1,则Pi(1≤i<n)为（    ）

A、n-i+1  B.n-i  C.i  D.有多种可能

解  由于输出序列是1,2,3,…,n。Pn=1最先出栈，则P1,P2,P3,…,Pn-1在栈中，即出栈序

二应为Pn,Pn-1,…,P3,P2,P1对应1,2,3,…,n，即Pi为n-i+1。

二、简答题

为什么说栈是一种先进先出表？

栈是一种线性表，最后插进栈中的那个元素总是最先从栈中移出，所以说栈是一种先进先出表。

三、算法设计题

1、编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转

分析：假定彩顺序栈结构，利用两个临时栈st1和st2。先将st栈中内容移到st1栈中(即从st栈中逐一出栈元素并进栈到st1中)，再将st1栈中内容移到st2栈中，最后将st2栈中内容移到st栈中，这样st栈中的内容进行了逆转 。

2、编写一个算法，利用栈的基本运算返回指定栈中栈底元素。

分析：假定彩顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中元素，最后一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元互素。

3、在栈顶指针为HS的链栈中，编写算法计算该链栈中结点个数.

分析：假设链栈不带头结点，求链栈结点个数就是扫描链表。