栈与队列1.pptVIP

type link = ^node; node = record data: datatype; next: link; end;var hs: link; 讨论 表达式计算3×5+（6-8/4)×7 【问题分析】 为了便于计算需要设计两个栈： 操作数栈 操作符栈 例表达式计算 计算表达式3×5+（6-8/4)×7的值。 从左向右扫描表达式 遇到运算数形成数值送到操作数栈 遇到运算符 1）如果运算优先级大于操作符栈顶元素直接进栈 2）如果运算优先级小于或等于栈顶元素，则依次做两次弹出操作数栈顶元素，然后弹出操作符栈顶元素，再计算并将结果放入操作数栈，直到当前运算符优先级大于操作符栈顶元素为止，并将当前运算符入栈。 4. 左括号直接进操作符栈 5. 右括号则依次弹出操作符和操作数栈中的元素计算并将结果放回操作数栈，直到遇到第一个左括号为止。 实战演练 【问题描述】栈 解法二——计算Catalan数 对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 链表存储的队列的操作 判空 function qempty(f:link): boolean; begin if f = nil then qempty := true else qempty := false; end; 链表存储的队列的操作的实现 入队 procedure qadd(x: datatype;f,r:link); begin new(p); p^.data := x; p^.next := nil; if qempty(f) then begin f := p; r := p; end else begin r^.next := p; r := p; end end; 链表存储的队列的操作的实现 出队 function qdel(f:link): …; begin if qempty(f) then begin writeln(empty); halt; end else begin p := f; f := p^.next; qdel := p^.data; dispose(p); end; end; 链表存储的队列的操作的实现 清空队列 procedure qsetnull(f,r:link); begin while f nil do begin p := f; f := p^.next; dispose(p); end; r := nil; end; 顺序队列的“假溢出”现象 循环队列 f=r=m f=r r=r mod m+1 f=f mod m+1 S:=1; For i:=1 to n do s:=s*(2*n-i+1) div I; S:=s div (n+1) 计算Catalan数的程序实现： 总结： Catalan数是比较复杂的递推公式，针对上述题目需要将问题抽象，揭示事物间的关系，运用组合分析的手段寻求内在的规律，建立数学模型。 队列的概念和特征 队列也是一种特殊的线性表，对它的插入和删除都限制在表的两端进行。 在队列中，最先插入的元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。 F队首 初始时f=r=0。 R队尾 队列的顺序存储结构 type queue = record data: array[1..n] of datatype; f, r: integer; end; Var q: queue; 队列的链式存储结构 type link = ^node; node = record data: datatype; next: link; end; var f, r: link; ^ f …… r 队列的基本操作 判断队列是否为空 qempty 入队 qadd 出队 qdel 清空队列 qsetnull r