《数据结构域算法设计chapter2.4-2.5栈与队列》由会员分享，可在线阅读，更多相关《数据结构域算法设计chapter2.4-2.5栈与队列（111页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法2.4-2.5 2.4-2.5 栈与队列栈与队列主要内容 2.4 2.4 栈栈 2.5 队列第2章 线性表栈与队列 栈和队列是在程序设计中被广泛使用的两种线 性数据结构。 与线性表相比，它们的插入和删除操作受更多 的约束和限定，故又称为限定性的线性表结构 。第2章 线性表栈栈：限定仅只能在末端进行插入和删除的线性表。栈顶：允许插入和删除的一端。栈底：不允许插入和删除的一端。时间有序表：先进后出（FILO) /后进先出（LIFO）an-1 an-2 a1 a0bottomtop退栈（弹出）进栈（压入）第2章 线性表栈的基本操作 Clear()清空栈。 IsEmpty(
2、)判断栈是否为空。 Push(T item)将元素item放到栈的顶部。 Pop(Tst=new TMaxStackSize;top=-1;第2章 线性表进栈操作0 1 2 maxSize-1topba0 1 2 maxSize-1topbactemplate bool ArrayStack:Push(const T item ) if(IsFull() coutbool ArrayStack:Pop(T private: T data;Node * link; 第2章 线性表第2章 线性表链式栈的进栈操作template LinkedStack p-data=x; p-link=top; t
3、op=p; return *this; topdata link data linkitemtop第2章 线性表data linktopx = Atemplate LinkedStack Node *p=top;top = top -link; delete p;return *this; 链式栈的出栈操作链式栈的清空操作template void LinkStack:MakeEmpty() /同析构函数Node *next;while(top)next=top-link;delete top;top=next; 第2章 线性表栈的应用 数制转换 括号匹配 回文游戏 表达式计算 计算中缀表带式
4、的值 中缀、后缀表达式转换 匹配程序分隔符 递归第2章 线性表将一个非负十进制整数转换成八进制数并输出。例 把十进制数159转换成八进制数。数制转换toptop7top73top732(159)10=(237)81598198 28 02 3 7 余 7余 3余 2第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 11匹配情况：左括号4 右括号8左括号1 右括号11算法：从左向右扫描字符串，(1)如果是左括号，就把它的位置编码压入栈中(2)如果是右括号，则与栈顶的位置编码所指的左括号匹配。第2章
5、线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 111第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 111第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 111第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10
6、 1114第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1114第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1114第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1114第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4
7、5 6 7 8 9 10 11144出栈8 4 匹配第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1118 4 匹配第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1118 4 匹配第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1118 4 匹配第2章 线性表括号匹配匹配一个字符串中的左、右括号
8、。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 1118 4 匹配1出栈11 1 匹配第2章 线性表括号匹配匹配一个字符串中的左、右括号。如( a * ( b + c ) + d )字符位置 1 2 3 4 5 6 7 8 9 10 118 4 匹配11 1 匹配第2章 线性表算法思想： 读入字符串； 去掉空格（原串）； 压入栈； 原串字符与出栈字符依次比较； 若不等，非回文； 若直到栈空都相等，回文。回文游戏（顺读与逆读字符 串一样（不含空格）第2章 线性表表达式计算 表达式都由操作数（也称运算对象）、操作符（也成运算符）和 分界符组成。 算
9、术表达式三种表示： （1）中缀(infix)表示： 例如A+B （2）前缀(prefix)表示： 例如+ AB （3）后缀(postfix)表示： 例如AB +第2章 线性表中缀表示 平时所用的表达式都是中缀表示。如A+B*(C-D)-E/F 中缀表示中有操作符的优先级问题，并可以加括号 改变运算顺序。 用中缀表示求解表达式的值需要利用两个栈来实现 ，一个暂存操作数，另一个暂存操作符。第2章 线性表计算中缀表达式算法思想设置两个工作栈 运算符栈OPTR，运算符栈的栈底为表达式的起始符#。 操作数栈OPND，操作数栈为空栈。第2章 线性表计算中缀表达式算法思想设isp(.)代表栈内优先级,icp
10、(.)代表栈外优先级依次读入表达式中的每个字符,若是 操作数,则进OPND栈； 运算符s1，则和OPTR中的栈顶元素s2做比较再操作。若icp(s1)isp(s2)，则运算符入栈；若icp(s1)，连续从栈中退出两个操作数Y 和X，形 成运算指令 XY,并将结果重新压入栈中。 当扫描完表达式后，栈顶存放的就是计算结果。第2章 线性表计算后缀表达式的值 A B C D - * + E F / -R1 R4R2R3R5等价于：A+B*(C-D)-E/F第2章 线性表用后缀表达式计算的步骤步 扫描项项类型动作 栈中内容1 置空栈 空 2Aoperand进栈 A 3Boperand进栈 A B 4Co
11、perand进栈 A B C 5Doperand进栈 A B C D 6-operator D和C退栈,计算C-D,结果R1进栈 A B R1 7*operand R1和B退栈,计算B*R1,结果R2进栈 A R28 + operand R2和A退栈,计算A+R2,结果R3进栈 R39 E operand进栈 R3 E10 F operand进栈 R3 E F11 / operand F和E退栈,计算E/F,结果R4进栈 R3 R412 - operand R4和R3退栈,计算R3-R4,结果R5进栈 R5A B C D - * + E F / -中缀向后缀转换 扫描中缀表达式， 操作数直接输
12、出； 操作符放到(操作符)栈中。 如：A+B*(C-D)-E/F 应转换为ABCD-*+EF/-算法过程算法过程? ?第2章 线性表a=b+(c-d)*(e-f); g10=h i9 +(j+k)*l; while( m1时 把上面n-1个圆盘从A移到B 然后将n号盘从A移到C 将n-1个盘从B移到C。即把解n个圆盘的Hanoi问题转化为解n-1个圆盘的Hanoi问 题,依次,直至转化成只有一个圆盘的Hanoi问题。ABC递归与循环 递归函数可以使用循环来实现。 函数Power()可以用另一种方法来实现：double nonRecPower(double x, unsigned int n)double result=1;for(result=x;n1;-n)result*=x;return result;第2章 线性表尾部递归 尾部递归的特点 在每个函数的实现的末尾只使用一个递归调用 例如：void tail(int i) if(i0) cout0;i-) couti“ ”; 第2章 线性表非尾部递归 例如：将输入行以相反的顺序打印出来。void reverse() char ch;cin.get(ch);if(c
