文档介绍：第3章栈和队列
§1 栈
§2 队列
本章小结
§ 栈的概述
§ 栈的顺序存储结构及其基本运算实现
§ 栈的链式存储结构及其基本运算实现
§ 栈的应用
§ 1 栈
§ 栈与递归的实现
堆栈在程序设计语言中的一项重要应用是实现递归。
递归的定义
在程序设计语言中,一个函数直接调用自己,或通过一系列的调用语句间接地调用自己的过程,称为递归。
若函数调用自身,称之为直接递归。
若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。
§ 栈与递归的实现
递归的作用
递归是程序设计中一个强有力的工具。帮助程序设计者解决复杂的问题,并精简程序结构。它的作用表现在:
第一,解决很多的数学问题。很多数学函数是递归定义的,比如阶乘、费氏级数、求最大公因子、组合公式等。
第二,有的数据结构,如二叉树、广义表等,结构本身就具备递归特性,对它们的操作就可以递归地描述。
第三,还有一类问题,本身并没有明显的递归结构,但使用递归求解可以简化算法。比如著名的汉诺塔问题、八皇后问题等。
递归的步骤
求解递归问题的步骤
(1)判断题意是否适合用递归来递解;
(2)决定递归结束的条件(Stopping Cases)
(3)决定递归执行部分(Recursive Stap)
递归模型—递归函数的算法格式
处理递归问题,常采用if语句来判断是否符合递归结束条件,算法格式如下:
if (符合递归结束条件)
返回答案;
else
调用递归程序; /*传递参数递减(增),表示更高一层的递归*/
递归出口
递归体
递归的执行过程—函数调用、信息传递
1. 普通函数的调用过程
在高级语言编制的程序中,调用函数和被调函数之间的链接和信息交换需要通过堆栈来进行。
系统将整个程序运行所需的数据空间安排在一个堆栈中。
通常,在一个函数的运行期间调用另一个函数时,在运行被调函数之前,系统先要完成三件事:1、将所有的实参、返回地址等信息传递给被调函数保存;2、为被调函数的局部变量分配存储区;3、将控制转移到被调函数的入口。
当执行完被调函数,在返回调用函数之前,系统也先要完成三件事:1、保存被调函数的计算结果;2、释放被调函数的数据区;3、依照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时,按照“后调用先返回”的原则,函数之间的信息传递和控制转移均通过堆栈来实现。
每当调用一个函数时,就在堆栈顶端为它分配一个存储区,保存其参数(实参、局部变量)和返回地址等信息;每当从一个函数退出时,就释放它的存储区,使得当前正在运行函数的数据区总是在栈顶。
最后被调用的函数,其相关的参数和返回地址等信息作为栈顶元素,我们称之为栈顶工作记录,因为是当前执行函数的工作记录,也称之为“活动记录”。指向活动记录的指针通常也被称为“环境指针。”
【】两个子函数first、second的嵌套调用
int first(int a, int b)
{ int i;
……
second(i);
2:……
}
int second(int d);
{ int x,y;
……
}
当前运行函数为second时,堆栈状态如右上图所示。工作记录的内容:返回地址(被调函数的下一语句,控制转移至调用函数)、实参、局部变量。
执行完最后调用的函数second后,栈顶记录被pop出去,控制转移至返回地址‘2’,接着执行first函数的其它语句。
执行完first函数语句,当前栈顶记录(first的记录)又被pop出去,控制转移至返回主函数地址‘1’,接着执行主函数中的其它语句。
2 i x y
1 m n i
……m n
……
(second工作记录)
(first 的记录)
栈顶
主函数工作区
2. 递归函数的调用过程
一个递归函数的嵌套过程类似于多个函数的嵌套调用。只是调用函数和被调函数均为同一个函数。唯一的不同点是其中的一个传入参数每次执行函数调用时都递减(增)。
这个传入参数可以表明递归函数运行的“层次”。
若调用递归函数的主函数为第0层,那么从主函数调用递归函数为进入第一层。从第i 层递归函数调用自身为进入第i+1层。反之,第i层函数执行完退回至i-1层。
系统也需要设立一个“递归工作栈”作为整个递归函数运行期间使用的数据区,不需用户自己管理,而由系统完成管理工作。
每一层递归函数所需信息也构成一个“工作记录”。最“高”层的工作记录就是栈顶的活动记录。指示活动记录的栈顶指针为“当前环境指针”。