《数据结构域算法设计Ch03 栈与队列3》由会员分享，可在线阅读，更多相关《数据结构域算法设计Ch03 栈与队列3（67页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 栈与队列,3.1 栈 3.2 栈的应用：递归 3.3 队列,2,栈可定义为只允许在表的末端进行插入和删除的线性表。 允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom) 特点先进后出 (FILO),3.1 栈 ( Stack ),一、栈的定义,3,template class Stack /栈的类定义 public:Stack() ; /构造函数virtual void Push(T x) = 0; /进栈virtual bool Pop(T /判栈满 ；,栈的抽象数据类型,4,#include #include const int stackIncreament
2、 = 20; /栈溢出时扩展空间的增量 template class SeqStack /顺序栈类定义 private: T *elements; /存放栈中元素的栈数组int top; /栈顶指针int maxSize; /栈最大容量void overflowProcess(); /栈的溢出处理,二、顺序栈,5,public:SeqStack(int sz=50); /构造函数SeqStack() delete elements; /析构函数void Push(T x); /进栈bool Pop(T,6,templateclass T SeqStackT:SeqStack(int sz) /
3、建立一个最大尺寸为sz的空栈，若分配不成功则错误处理。 top = -1; maxSize = sz;elements = new TmaxSize; /创建栈的数组空间assert(elements!NULL); /断言 ,7,top,空栈,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,8,9,栈的其他成员函数的实现,template void SeqStack:overflowProcess() /私有函数：当栈满则执行扩充栈存储空间处理 T *newArray = new TmaxSize+stackInc
4、reament; /创建更大的存储数组if (newArray=NULL) cerr“存储分配失败！”endl; exit(1); for (int i = 0; i link; delete p; ;,17,template void LinkedStack:Push( const T,18,template bool LinkedStack:Pop(T,19,template bool LinkedStack:getTop(T,20,template int LinkedStack:getSize() const LinkNode *ptop; int k=0;while(top!=NUL
5、L) top=top-link; k+; return k; ,21,21,四、栈的应用：表达式求值,一个表达式由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成。 算术表达式有三种表示： 中缀(infix)表示 ，如 A+B； 前缀(prefix)表示，如 ； 后缀(postfix)表示 ，如 ；,1.表达式,+AB,AB+,22,22,中缀表达式 a + b * ( c - d ) - e / f 后缀表达式 a b c d - * + e f / - 前缀表达式 - + a * b c d / e f,表达式示例,C+规定表达式中相邻两个操作符的计算次序为：,优先级高的先计算；优
6、先级相同的自左向右计算；当使用括号时从最内层括号开始计算；,23,23,一般表达式的操作符有4种类型 算术操作符：如双目操作符（+、-、*、/ 和%）以及单目操作符（-）。 关系操作符：包括=、。这些操作符主要用于比较。 逻辑操作符：如与(&)、或(|)、非(!)。 括号(和)：它们的作用是改变运算顺序。,24,24,先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。 如中缀表示 (A+B)*D-E/(F+A*D)+C，其转换为后缀表达式的过程如下：,中缀表达式转后缀表达式：,25,25,各个算术操作符的优先级,isp叫做栈内(in st
7、ack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。,2、利用栈将中缀表示转换为后缀表示,26,26,中缀表达式转换为后缀表达式的算法,操作符栈初始化，将结束符#进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch = #，同时栈顶的操作符也是#，停止循环。 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp： 若 icp(ch) isp(op)，令ch进栈，读入下一个字符ch
8、。 若 icp(ch) isp(op)，退栈并输出。 若 icp(ch) = isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。 算法结束，输出序列即为所需的后缀表达式。,27,27,28,28,29,29,void postfix ( ) SeqStack s;char ch#, ch1,op;s.Push(ch); cin.Get(ch);while ( s.IsEmpty()false)if ( isdigit(ch) ) coutisp(ch1) s.Push(ch); cin.Get(ch); else if ( icp(ch)isp(ch1) s.Pop(op);
9、 coutch, ch!#) switch(ch) case +: case-: case*; case/:DoOperator(ch); break；default: cin.putback(ch);cinnewOperand;AddOperand(newOperand);double result;s.Pop(result);cout“计算结果为：“resultendl; ,35,35,void Calculator:DoOperator(char op) /私有函数：取两个操作数，根据操作符op形成运算指令并计算; double left, right, value; bool resu
10、lt;result= Get2Operands(left,right); /取两个操作数;if (resulttrue) /如果操作数取成功，计算并进栈;switch (op) case+: valueleft+right; s.Push(value); break;case-: valueleft-right; s.Push(value); break;case*: valueleft*right; s.Push(value); break;case/: if (right0.0) /若除0，则报错，清栈; cerr”Divide by 0!”endl; Clear(); else value= left/right; s.Push(value)；break;else clear(); ;,
