深度优先搜索.ppt

《深度优先搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈与递归例0-1：输入一个正整数n，求n的阶乘varn:integer;functionfac(n:integer):longint;beginifn=0thenfac:=1elsefac:=n*fac(n-1);end;beginreadln(n);writeln(fac(n));end.要理解递归，首先应了解一种数据结构：堆栈（简称栈）的概念。栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈；从一个栈删除元素又称作

2、出栈或退栈。栈指针top123Init初始化栈Procedureinit;Begintop:=0;End;栈指针top123Push入栈Procedurepush(x:integer);Begintop:=top+1;ifisfull=falsethenStack[top]:=x;elsewriteln(‘stackfull’);End;栈指针top123Isfull判栈满Functionisfull;Beginiftop=n+1then;isfull:=true;elseisfull:=false;End;n+1栈指针top123Gettop

3、取栈顶元素Functiongettop:integerBegingettop:=stack[top];End;栈指针top123Push出栈Procedurepop;Beginifisempty=truethenwrite(‘stackempty’)elsetop:=top–1;End;栈空栈指针top123Isempty判栈空Functionisempty;Beginiftop=0then;isempty:=true;elseisempty:=false;End;0例0-2：输入n个整数，并逆序输出（栈实现）。输入样例：3123输出样例：32

4、1constmaxn=20;varstack:array[1..maxn]ofinteger;top:integer;n,i,x:integer;procedureinit;begintop:=0;end;functionisfull:boolean;beginiftop=n+1thenisfull:=trueelseisfull:=false;end;functionisempty:boolean;beginiftop=0thenisempty:=trueelseisempty:=false;end;procedurepush(x:integ

5、er);begintop:=top+1;ifisfull=truethenwriteln('StackFull')elsestack[top]:=x;end;functiongettop:integer;begingettop:=stack[top];end;procedurepop;beginifisempty=truethenwriteln('StackEmpty')elsetop:=top-1;end;beginreadln(n);fori:=1tondobeginread(x);push(x);end;whileisempty<>tru

6、edobeginwrite(gettop,'');pop;end;end.编译器处理函数调用时，就是使用栈来保存数据的。当主调函数调用另一个函数时，编译器将主调函数的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。Function函数1:integer;Begin函数2；End;函数1调用函数2系统栈中的变化（入栈）当进行被调函数时，编译器将栈中的实参数据弹出，赋值给函数的形参。在被调用函数执行期间，还可利用栈来保存函数执行时的局部变量。当被调用函数准备返回时，系统将弹出栈中所有当前函数压入栈中的值，这时，栈指针移动到被调用

7、函数刚开始执行时的位置。接着被调用函数返回，系统从栈中弹出返回地址，主调函数就可以继续执行了。函数2返回至函数1系统栈中的变化（出栈）回到阶乘的递归算法上来。假设要计算5的阶乘，通过前面设计的递归程序执行过程如下。首先，在主函数中调用fact(5)函数，将返回地址、参数、局部变量压入堆栈。在fact()函数中，判断n的值若不为0，则递归调用fact(4)，这时将函数的返回地址和参数压入堆栈。程序继续递归调用时，将fact(3)、fact(2)、fact(1)逐步压入堆栈当调用fact(0)时，达到阶乘递归算法的结束条件，这时结束fact(0)函

8、数调用，从堆栈中弹出该层的相关数据，并返回函数的结果1。这时栈顶中保存的将是fact(1)中的相关数据当递归函数逐层返回时，栈中压入的数据将逐步弹出，