数据结构第3章解析.ppt

3.3 堆栈的应用—表达式计算 3.3.3 中缀表达式转换为后缀表达式 中缀表达式: a/(b-c)+d*e 后缀表达式: a b c - / d e * + a / b c - d + * e # 3.3 堆栈的应用—表达式计算 3.3.3 中缀表达式转换为后缀表达式 中缀表达式: a/(b-c)+d*e 后缀表达式: a b c - / d e * + a / b c - d + * e # 3.3 堆栈的应用—表达式计算 3.3.3 中缀表达式转换为后缀表达式 操作符 # ( */ +- ） icp 0 7 4 2 1 isp 0 1 5 3 7 扫描项 操 作 栈 输 出 #进栈（初始时） # a a输出 # a / icp(‘/’)isp(‘#’),’/’进栈 / # a ( icp(‘(‘)isp(‘/’), ‘(’进栈 ( /# a b b输出 ( / # ab - icp(‘-‘)isp(‘(‘), ‘-’进栈 - ( / # ab c c输出 - ( / # abc ) icp(‘)’)isp(‘-‘), ’-‘出栈输出 ( / # abc- icp(‘)’)==isp(‘(’), ’(’出栈但不输出 / # abc- + icp(‘+’)isp(‘/‘), ’/’出栈输出 # abc-/ icp(‘+’)isp(‘#’), ’+’进栈 + # abc-/ d d输出 + # abc-/d * icp(‘*’)isp(‘+’), ’*’进栈 * + # abc-/d e e输出 * + # abc-/de # 输出栈中剩余操作符。’*’ ,’+’出栈输出 # abc-/de*+ a/(b-c)+d*e 3.4 堆栈的应用—表达式计算 3.4.1 递归的概念 递归和递归定义 递归定义是一种直接或间接引用自身的定义方法。 课堂提要 第3章 堆栈和队列 3.1 堆栈 3.2 队列 3.3 表达式的计算 3.4 递归 3.4 堆栈的应用—表达式计算 3.4.1 递归的概念 斐波那契数列递归定义 斐波那契数列直接计算式 3.4 堆栈的应用—表达式计算 3.4.1 递归的概念 递归算法 一个递归算法是指直接或间接调用自身的算法 long Fib( long n）{ if(n=1) return n; else return Fib(n-2)+Fib(n-1); } 递归数据结构 使用递归方式定义的数据结构常称为递归数据结构 3.4 堆栈的应用—表达式计算 3.4.2 递归的实现 递归函数的性能 优点：程序结构简洁而清晰，易于正确性证明和算法分析。 缺点：既费时又费空间。 作业 P48 3-1, 3-3, 3-4 * 不懂什么意思？ 3.2 队列 3.2.2 队列的顺序表示 3. 顺序队列类 template class T class SeqQueue:public QueueT { public: SeqQueue(int mSize); ~SeqQueue(){ delete []q;} bool IsEmpty() const； bool IsFull() const； bool Front(T x)const; bool EnQueue(T x); bool DeQueue(); void Clear(){front=rear=0;} private: int front,rear; int maxSize; T *q; }; 0 f r 1 2 3 4 3.2 队列 3.2.2 队列的顺序表示 4. 动态一维数组描述顺序队列类 templateclas