数据结构3-栈与队列.ppt

* S3 §3.1 栈 第三章. 栈和队列 （Chapter 3. Stack and Queue) 栈（stack）是插入和删除操作受限的线性表，是一种后进先出（Last In First Out -- LIFO）的线性表。表头端称为栈底（bottom），表尾端称为栈顶（top），插入和删除都在栈顶进行。 bottom top S1 S2 S5 S6 S3 S4 S3 S3 S3 S3 S3 PUSH PUSH PUSH POP PUSH PUSH PUSH 栈的基本操作： INISTACK CLEAR GETTOP EMPTY PUSH POP 栈的实现： CONST maxlen = user_supply; TYPE stack = RECORD elem : ARRAY[1 .. maxlen] OF elemtype; top : 0 .. maxlen END; 顺序存储结构表示栈 FULL TYPE pointer = ↑ node; node = RECORD data : elemtype; next : pointer END; linkedstack = pointer; 链式存储结构表示栈----链栈（Linked_stack） 上溢（overflow）：若栈的容量已全部用完，再进行插入操作（PUSH），就会发生上溢错误。 下溢（underflow）：若栈已空，再进行删除操作（POP），就会发生下溢错误。 §3.2 栈的应用----表达式求值 任一表达式（expression）都是由操作数（operand）、操作符（operator）和界限符（delimiter）组成。 我们通常习惯使用中缀表达式（infix expression），但中缀表达式离不开括号（bracket)。若使用前缀表达式（prefix expression）或后缀表达式（ postfix expression）则不需要括号。利用栈，可以将中缀表达式变为前缀表达式或后缀表达式，再用栈进行运算即可得到表达式的值（value）。 §3.3 栈与递归 递归（recursive）：一个程序直接调用自己或通过其它程序调用自己就称为递归。根据调用关系可分为直接递归（direct recursive）和间接递归（indirect recursive ）。 第 一 次 上 机 作 业 输入表达式字符串，以“=”表示结束， 计算并输出表达式值。 操作数可以是整数或实数，操作符有 “+”、“-”、“*”、“/”、“^”（乘方）和 “sin( )”（正弦）、“cos( )”（余弦）、“log( )”（对数）、“ln( )”（自然对数）等函数。 栈在程序的过程或函数调用中的作用： 过程一 过程二 过程三 过程四 断 点 三 断 点 一 断 点 二 断点一 断点二 断点三 stack 调用子程序 返回断点 程序执行 递归是程序设计中一种强有力的工具。下面三种情况可用递归解决： 1、有些数学函数是递归定义的，对其求解可用递归； 2、有些数据结构具有递归特性，对其操作可用递归； 3、有些问题的解决方法用递归描述，对其求解也可用递归。 例： 求阶乘（factorial）： Fact(n) = 1 当 n = 0 n·Fact(n-1) 当 n 0 { FUNC Fact (n:integer); If n=0 Then Return (1) { 出口条件 } Else Return (n * Fact (n-1)) { 递归调用部分 } ENDF; 例： 河内塔（Hanoi Tower）问题求解： A B C A B C 如何解决这个问题呢？真伤脑筋啊！ 题目要求：1、将 n 个盘子从 A 柱移到 B 柱，C 柱可用； 2、每次只能移动一个盘子；