Question

pascal数据结构

Answer 1

说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式：栈、队、链。
这一讲，我们就来谈谈“栈”。
“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢？
　　栈是只能在某一端插入和删除的特殊线性表。
　　用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。
　　栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。
　　一个栈可以用定长为Ｎ的数组Ｓ来表示，用一个栈指针TOP指向栈顶。若TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP<0时为下溢。栈指针在运算中永远指向栈顶（如图11.6所示）。
　　　　　　　　　

x x

top
top
top

原来状态 X进栈 TOP=TOP+1 退栈送X TOP=TOP- 1
　　　　　 表示处理前的栈指针
　　　　　 表示处理后的栈指针
　　 图11.6　栈
　　1、进栈（PUSH）算法
　　①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
　　②置TOP=TOP+1（栈指针加１，指向进栈地址）；
　　③S(TOP)=X，结束（X为新进栈的元素）；
　　（２）退栈（POP）算法
　　①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
　　②X=S(SOP)，（退栈后的元素赋给X）；
　　③TOP=TOP-1，结束（栈指针减１，指向栈顶）。
　　进栈、出栈的Pascal实现过程程序：
CONST
n=100;
TYPE
stack=ARRAY[1..n] OF integer;
PROCEDURE PUSH(VAR s:stack;VAR top,x:integer);{入栈}
BEGIN
IF top=n THEN writeln('overflow')
ELSE
BEGIN
top:=top+1;s[top]:=x;
END
END;
PROCEDURE POP(VAR s:stack;VAR y,top:integer);{出栈}
BEGIN
IF top=0 THEN writeln('underflow')
ELSE
BEGIN
y:=s[top];top:=top-1;
END
END;
　　对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。
　　栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。
　　源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句
　　X:＝4＋8×2－3; (式 11.1)
其正确的计算结果应该是１７，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为
　　X＝12×2－3＝24－3＝21
这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。
　　一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如：
　　运算符：×　÷　＋　－
　　优先数：２　２　１　１
　　（语句结束符“；”的优先数为零）
　　在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这样的规定，对式（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是：
　　①凡遇到操作数，一律进入操作数栈；
　　②当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作数栈，然后继续比较该运算符与栈顶元素的优先数。
　　例如式（11.1）中，当扫描到“＋”和“×”时都要将运算符入栈。扫描到操作数“２”时，两个栈的情况如图11.7(a)所示。接着扫描到“－”号， 其优先数小于乘号所以乘号退栈，并执行８×２，将结果１６再存入操作数栈，如图11.7(b)所示。再将“－”号的优先数与运算符栈的栈顶元素“＋”号的优先数相比较，两者相等，所以再将加号退栈，进行４＋１６，结果为２０，再入栈，如11.7(c) 所示，接着，由于运算栈已空，所以减号入栈。当扫描到“３”时，操作数入栈，如图11.7(d)所示。当扫描到“；”时，其优先数最低， 所以减号退栈并执行２０－３，结果为１７并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为１７，如图11.7(e)所示。
　　　　　　 　　　

(a) (b) (c) (d) (e)
图11.7 编译式(11.1)时栈的变化情况
例11.4　模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。
　　分析
　　建立两个栈，一个是操作数栈（number），一个是运算符栈（symbol），根据运算符的优先级对两个栈进行相应的操作。
源程序
program ex11_4;
const
max=100;
var
number:array[0..max] of integer;
symbol:array[1..max] of char;
s,t:string;
i,p,j,code:integer;
procedure push;{算符入栈运算}
begin
inc(p);symbol[p]:=s[i];
end;
procedure pop;{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算}
begin
dec(p);
case symbol[p+1] of
'+':inc(number[p],number[p+1]);
'-':dec(number[p],number[p+1]);
'*':number[p]:=number[p]*number[p+1];
'/':number[p]:=number[p] div number[p+1];
end;
end;
function can:boolean;{判断运算符的优先级别,建立标志函数}
begin
can:=true;
if (s[i] in ['+','-']) and (symbol[p]<>'(') then exit;
if (s[i] in ['*','/']) and (symbol[p] in ['*','/']) then exit;
can:=false;
end;
begin
write('String : '); readln(s); s:='('+s+')'; i:=1; p:=0;
while i<=length(s) do
begin
while s[i]='(' do {左括号处理]
begin
push; inc(i);
end;
j:=i;
repeat {取数入操作数栈}
inc(i);
until (s[i]<'0') or (s[i]>'9');
t:=copy(s,j,i-j); val(t,number[p],code);
repeat
if s[i]=')' then {右括号处理}
begin
while symbol[p]<>'(' do pop;
dec(p); number[p]:=number[p+1];
end
else
begin {根据标志函数值作运算符入栈或出栈运算处理}
while can do pop;
push;
end;
inc(i);
until (i>length(s)) or (s[i-1]<>')');
end;
write('Result=',number[0]);
readln;
end.