数据结构PPT第三章.ppt

第三章 栈和队列 内容提要 栈 存储方式 基本操作 栈举例 队列 队列的存储方式 循环队列 3.1栈的概念 栈和队列也是线性表，其特殊性在于栈和队列是操作受限的线性表。 栈是限定仅在表尾进行插入或删除的线性表。表尾称为栈顶，表头称为栈底。 3.1.2栈的表示和实现 栈的存储分为顺序栈(P46)和链式栈两种 顺序栈是指栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附指针top指示栈顶元素在顺序栈中的位置 一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。 STACK_INIT_SIZE(存储空间初始分配量) STACKINCREMENT(存储空间分配增量) 堆栈的第二种表示方法 堆栈用数组进行表示 栈顶和栈底用整数而不是指针来表示 空栈: top=0; 满栈: top= Max (Max为数组长度上限) 链栈 用动态方式来存储栈可节省空间 采用链表存储的栈为链栈 链栈的类型定义如下： Typedef struct node { Elemtype data; //数据域； struct node * next; //指针域； }ListNode; Typedef ListNode * LinkStack; LinkStack top; //定义一个栈的栈顶指针变量 3.2栈的应用举例（一） 数制转换问题 3.2栈的应用举例（二） 迷宫求解 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。 为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。 回溯法的应用——马步问题 3.2栈的应用举例 表达式求值（算符优先的应用） 表达式的表示方法 波兰式 E = E1 E2θ 逆波兰式 E = θ E1 E2 E.G. (2+X*Y)/3 波兰式: ( 2 x y * + ) 3 / 逆波兰式: / ( + 2 * x y ) 3 N*((M+4)/2) 波兰式: N ( ( M 4 + ) 2 / ) * 逆波兰式: * N ( / ( + M 4 ) 2 ) 表达式求值（算符优先的应用） 3.3栈与递归 在程序中实现递归是栈的重要的运用之一 递归函数——一个直接调用自己或者通过一系列的调用语句间接调用自己的函数 函数调用前，系统完成三项工作： 将所有实参和返回地址等信息传递给被调用的函数保存 为被调用的函数的局部变量分配存储区 将控制转移到被调用函数的入口 子函数返回主函数之前，系统需要做的是： 保存子函数的计算结果 释放子函数的数据区 依照子函数保存的返回地址将控制转移到主函数 嵌套调用时按照后调用先返回的原则 系统将整个程序运行时需要的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区；每当一个函数退出时，释放它的存储区；当前运行的函数必须在栈顶 阶乘函数 已知F（n）函数（n为自然数）的定义如下： = 1 若n = 0 = n * F（n-1） 若n 0 程序如何编写？ 函数如何递归调用，如何返回？ 汉诺塔问题(Hanoi) 相传在某一座古庙有三根木桩，有24个铁盘从下到上，由大到小地全部放置在其中一个木桩上。庙中流传着一个传说：“如果有一天能把24个铁盘，从一根木桩移动到另一根木桩，且必须遵守如下这两个原则: 每天只能搬动1个铁盘，而且只能从最上面的铁盘开始搬动; 必须维持较小的铁盘在上方的原则。 当24个铁盘完全搬至另一个木桩时，世界就会永久和平”这就是著名的汉诺塔问题。 思考3个铁盘的操作步骤（P56），由此推广到n个铁盘 n个铁盘的操作过程 前n-1个盘从源桩x 搬到辅助桩y 第n个盘从源桩x搬到目标桩z 将前n-1个盘从辅助桩y搬到目标桩z 需要一个辅助桩y完成 3.4 队列 队列是只允许在一端进行插入，在另一端进行删除。 队列的存储方式 队列的存储方式有两种：用链表示的队列称为链队列。一个链队列需要两个分别指示队头和队尾的指针才能惟一确定。P61 空的链队列的判决条件为头指针和尾指针均指向头结点 单链队列的插入和删除的操作只需修改尾指针或头指针。 算法见P62 另一种存储方式为顺序存储 其他种类的队列结构 循环队列 队列元素用数组存储； Q.rear和Q.front均设为整数。 队列的应用——图形填充问题 上机操作 试写一个算法判断给定字符序列是否为回文（回文就是正读、反读均相同的字符序列） 思考 设一个顺序栈S，元素a1、a2、