第三章栈和队列详解.ppt

栈 队列 递归第三章栈和队列*;栈 ( Stack )定义:是;栈的抽象数据类型定义为： AD;template class;栈的表示和实现顺序栈：栈的顺序;toptopabcdee 进栈;顺序栈的定义及存储表示#def;初始化操作参数：S是存放栈的结;取栈顶操作功能：取栈顶元素，并;进栈操作Push功能：元素e进;出栈操作Pop功能：栈顶元素退;#include asser;Type Pop ( ); ;template class;template class;程序中定义多个栈（1）定义共享;(2)共享进栈算法 void ;(3)共享出栈算法 int ;链式栈:栈的链接表示 链式栈无;*链式栈 (LinkedSta;*链式栈 (LinkedSta;*链式栈 (LinkedSta;*链式栈 (LinkedSta;template class;template class;template class;template class;栈的应用举例 数制转换 行编辑;数制转换十进制数转换为八进制数;void conversion;行编辑程序 在用户输入一行的过;Void LineEdit();将从栈底到栈顶的字符传送至调用;迷宫求解通常用的是“穷举求解”;迷宫路径算法的基本思想若当前位;设定当前位置的初值为入口位置；;否则 {若栈不空且栈顶位置尚有;typedef struct ;do { if (Pass(;else { if (!St;限于二元运算符的表达式定义: ;例如: Exp = a ;表达式的中缀表示 ;C++中操作符的优先级 优先级;一般表达式的操作符有4种类型：;后缀表示法计算表达式的值从左向;通过后缀表示计算表达式值的过程;无标题;无标题;void Calculator;利用栈将中缀表示转换为后缀表示;算符间优先级＋ － ;各个算术操作符的优先级isp叫;从中缀式求得后缀式方法设立暂存;void postfix ( ;为实现算符优先算法，在这里用了;例如：表达式3*(7-2),求;为使两个算符比较方便,给算符设;算符比较算法char Prec;switch(c2){ ca;OperandType Eva;case ‘=‘://脱括号 ;队列定义:只允许在表的一端进行;链队列：队列的链式表示链队列中;frontrearx^元素x入;typedef struct ;Status InitQueu;Status DestroyQ;Status EnQueue_;Status DeQueue_;template class;template class;int IsEmpty ( );template class;template class;循环队列 (Circular ;队列的进队和出队frontre;循环队列 (Circular rontBC;#define MAXSIZ;Status EnQueue_;Status DeQueue_;#include asser;int DeQueue ( );template class;template class;队列应用举例 —打印二项展开式;分析第 i 行元素与第 i+1;从第 i 行数据计算并存放第 ;void YANGHUI ( ;优先级队列 (Priority;#include asser;void makeEmpty ;template class;template class;离散事件模拟日常生活中排队活动;思路：为求平均时间要知道每个客;银行客户的离散事件驱动模拟程序;具体实现：1.算法中处理的主要;2.模拟程序的另一种数据结构是;3.每个队列的队头是正在办理事;主要操作的实现：设第一个客户进;银行事件驱动模拟程序算法:Ev;void CustomerAr;Void CustomerDe;void Bank_Simul;递 归定义 若一个对象部分地;定义是递归的求解阶乘函数的递归;求解阶乘 n! 的过程主程序 ;例2.计算斐波那契数列函数Fi;数据结构是递归的有若干结点的单;例1.搜索链表最后一个结点并打;例2.在链表中寻找等于给定值的;例如，汉诺塔(Tower of;*;Void hanoi(int ;#include iostr;递归过程与递归工作栈递归过程在;递归工作栈每一次递归调用时，需;函数递归时的活动记录……………;long Factorial ;计算Fact时活动记录的内容递;递归过程改为非递归过程递归过程;计算斐波那契数列的函数Fib(;斐波那契数列的递归调用树Fib;Fib(1)Fib(0)Fib;Fib(1)Fib(0)Fib;Fib(1)Fib(0)Fib;long Fibn