教察 栈和队列 程序设计—数据结构 基本概念及应用 3.3栈与递归的实现 1、递归定义 直接或间接地调用自身的函数，称为递归函数。如右 图所示，递归表现为：在该函数的所有可能执行路径中， 开始 存在一条由于调用自身或其它函数所导致的环路路径：为 确保函数最终在有限的时间内执行完毕，必须在环路中存 在一个出口，即当某种条件成立时，不必执行环路，而直 形成 接执行一条通向结束的非环路线。 了环 2、递归应用 结 1)递归应用类型 ·递归定义的数学问题 ·具有递归特性的数据结构，其操作可以递归地表示 ·其它一些问题 2)递归应用的特点 对于一个问题，当问题规模很大时，往往难于直接求解，此时： ·将大问题分解成若干小问题 ·考虑如何利用这些小问题的解构成大问题的解 ·避免陷入考虑如何求解小问题 这种分解、合成的方法就是递归求解中的递归方法： 另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件， 给出此时的直接求解方法。 3)递归应用举例 Hanoi塔问题 3、递归的实现 1)系统的处理 (1)调用前 现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。 (2)调用后 保存计算结果，释放被调函数的数据区，控制转移回调用处。 2)实现——栈 “后调用先返回”。系统利用递归工作栈记录各层调用的现场信息。 3.4队列的基本概念 3.4.1队列的抽象数据类型定义 1、队列的逻辑特征 1)先进先出的线性表 2)队头：允许删除的一端：队尾：允许插入的一端 3)应用举例：操作系统的作业排队 2、队列的抽象数据类型定义ADT Queue ADT Queue 文档编号 完成时间 完成人张昱 修改时间 第6页程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 6 页 3.3 栈与递归的实现 1、递归定义 直接或间接地调用自身的函数，称为递归函数。如右 图所示，递归表现为：在该函数的所有可能执行路径中， 存在一条由于调用自身或其它函数所导致的环路路径；为 确保函数最终在有限的时间内执行完毕，必须在环路中存 在一个出口，即当某种条件成立时，不必执行环路，而直 接执行一条通向结束的非环路线。 2、递归应用 1) 递归应用类型 ·递归定义的数学问题 ·具有递归特性的数据结构，其操作可以递归地表示 ·其它一些问题 2) 递归应用的特点 对于一个问题，当问题规模很大时，往往难于直接求解，此时： ·将大问题分解成若干小问题 ·考虑如何利用这些小问题的解构成大问题的解 ·避免陷入考虑如何求解小问题 这种分解、合成的方法就是递归求解中的递归方法； 另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件， 给出此时的直接求解方法。 3) 递归应用举例 Hanoi 塔问题 3、递归的实现 1) 系统的处理 (1) 调用前 现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。 (2) 调用后 保存计算结果，释放被调函数的数据区，控制转移回调用处。 2) 实现——栈 “后调用先返回”。系统利用递归工作栈记录各层调用的现场信息。 3.4 队列的基本概念 3.4.1 队列的抽象数据类型定义 1、队列的逻辑特征 1) 先进先出的线性表 2) 队头：允许删除的一端；队尾：允许插入的一端 3) 应用举例：操作系统的作业排队 2、队列的抽象数据类型定义 ADT Queue ADT Queue{ 开始 结束 形成 了环