《(6)--第3章 栈和队列-栈数据结构.ppt》由会员分享，可在线阅读，更多相关《(6)--第3章 栈和队列-栈数据结构.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、栈第3章 栈和队列1 1.栈和队列的定义和特点栈和队列的定义和特点2 2.栈的表示和操作的实现栈的表示和操作的实现3 3.栈的应用栈的应用4 4 队列的的表示和操作的实现队列的的表示和操作的实现5 5 队列的应用队列的应用教学内容端点端点1端点端点2线性表线性表栈 S=(a1 ,a2 ,a3 ,.,an-1,an)an称为栈顶元素a1称为栈底元素允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈。栈的删除操作通常称为退栈或出栈。栈的定义和特点1)定义用顺序栈或链栈存储均可，但以顺序栈更常见与线性表相同，仍为一对一关系只能在表
2、的一端（栈顶）进行插入和删除运算的线性表2)逻辑结构3)存储结构栈的定义和特点只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则4)运算规则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同5)实现方式数据对象:数据关系:ADT Stack 栈的抽象数据类型描述栈的抽象数据类型描述基本操作:InitStack(&s)：初始化栈。构造一个空栈s。StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。Push(&s,e)：进栈。将元素e插入到栈s中作为栈顶元素。Pop(&s,&e)：出栈。从栈s中退出栈顶元素，并将其值赋给e。GetTop(s,&e)：取栈
3、顶元素。返回当前的栈顶元素，并将其值赋给e。ADT Stack toptoptoptopAABABCABCDtoptoptoptopDABCCBAABAInitStack();Push(S,A);Push(S,B);Push(S,C);x=Pop(S);x=Pop(S);x=Pop(S);StackEmpty(S);Push 和和 Pop 可以穿插交替进行；可以穿插交替进行；按照操作系列按照操作系列(1)Push(S,A),Push(S,B),Push(S,C),Pop(S),Pop(S),Pop(S)堆栈输出是？堆栈输出是？(2)而而Push(S,A),Pop(S),Push(S,B),Pu
4、sh(S,C),Pop(S),Pop(S)堆栈输出是堆栈输出是?例例 如果三个字符按如果三个字符按ABC顺序压入堆栈顺序压入堆栈 ABC的所有排列都可能是出栈的序列吗？的所有排列都可能是出栈的序列吗？可以产生可以产生 CAB 这样的序列吗？这样的序列吗？CBAACBCAB已知入栈顺序是ABCD，若栈不空时，可以出栈，则出栈序列有哪些，有多少个？作答主观题2分设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。5 1 2 3 44 5 1 3 24 3 1 2 53 2 1 5 4ABC提交D单选题2分已知入栈顺序是1,2,3，n，若栈不空时，可以出栈，如何判断是
5、否为合法的出栈序列？作答判断规则是，每一位之后小于它的数都应该降序排列，且每一位都要满足。主观题2分若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为i n-in-i+1不确定ABCD提交单选题2分#define MAXSIZE 100/顺序栈存储空间的初始分配量typedef structSElemType *base;/栈底指针SElemType *top;/栈顶指针int stacksize;/栈可用最大容量SqStack;假设栈的元素个数最大不超过正整数MAXSIZE，所有的元素都具有同一数据类型SElemType。顺序栈表示空栈base=
6、top stacksize=4topAbasetopbaseABCDbasetop3120顺序栈的表示满栈top-base=stacksize stacksize=4topbaseABC进栈时top增1，出栈时top减1构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错误(2)设置栈底和栈顶指针 S.top=S.base;(3)设置栈大小顺序栈初始化Status InitStack(SqStack&S)S.base=new SElemTypeMAXSIZE；if(!S.base)return OVERFLOW;S.top=S.base;S.stackSize=MAXSIZE
7、;return OK;算法描述basestacksizetopsbool StackEmpty(SqStack S)if(S.top=S.base)return true;else return false;basetop3120顺序栈判空int StackLength(SqStack S)return S.top S.base;basetopAB求顺序栈的长度思路：(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1ABCtopbase顺序栈入栈栈满条件：S.top-S.base=S.stacksize Status Push(SqStack&S,SElemType e)if
8、(S.top-S.base=S.stacksize)/栈满 return ERROR;*S.top+=e;return OK;*S.top=e;S.top+;ABCtopbase算法描述(1)判断是否栈空，若空则出错(2)栈顶指针减1(3)获取栈顶元素eStatus Pop(SqStack&S,SElemType&e)if(S.top=S.base)/栈空 return ERROR;e*-S.top;return OK;-S.top;e=*S.top;ABCtopbase顺序栈出栈(1)判断是否空栈，若空则返回错误(2)否则通过栈顶指针获取栈顶元素Status GetTop(SqStack S
9、,SElemType&e)if(S.top=S.base)return ERROR;/栈空e=*(S.top 1);return OK;e=*(S.top-);?ABCtopbase取顺序栈栈顶元素是运算受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。链栈的表示 data next 栈顶栈顶栈底栈底 Sa1antypedef struct StackNode SElemType data;struct StackNode*next;StackNode,*LinkStack;LinkStack S;链栈的表示 data next 栈顶栈顶栈底栈底 Sa1an
10、void InitStack(LinkStack&S)S=NULL;S链栈的初始化Status StackEmpty(LinkStack S)if(S=NULL)return TRUE;else return FALSE;链栈判空Status Push(LinkStack&S,SElemType e)p=new StackNode;/生成新结点p if(!p)exit(OVERFLOW);p-data=e;p-next=S;S=p;return OK;p S链栈入栈eS SAe=AStatus Pop(LinkStack&S,SElemType&e)if(S=NULL)return ERROR
11、;e=S-data;p=S;S=S-next;delete p;return OK;pS链栈出栈SElemType GetTop(LinkStack S)if(S=NULL)exit(1)；else return Sdata;取链栈栈顶元素1）数制的转换2）括号的匹配3）表达式求值栈的应用表达式求值例如3*(7-2)#设定两栈：OPND-操作数或运算结果OPTR-运算符 初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作：l若ch不是运算符，则压入OPND栈，读入下
12、一字符ch；思路l若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理：若是小于，则ch压入OPTR栈，读入下一字符ch；若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈；若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于括号匹配成功，然后读入下一字符ch。OPND栈顶元素即为表达式求值结果，返回此元素。思路算法描述OperandType EvaluateExpression()InitStack(OPTR);Push(OPTR，#);InitStack(OPND);ch=getcha
13、r();while(ch!=#|GetTop(OPTR)!=#)if(!In(ch)Push(OPND,ch);ch=getchar();/ch不是运算符则进栈 else switch(Precede(GetTop(OPTR),ch)/比较优先权 算法描述case :/弹出OPTR栈顶的运算符运算，并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;case=:/脱括号并接收下一字符 Pop(OPTR,x);ch=getchar();break;/switch /while re
14、turn GetTop(OPND);/EvaluateExpressionOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3)#*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)表达式的三种标识方法：表达式的三种标识方法：设设 Exp=
15、S1+OP+S2则称则称 OP+S1+S2 为为前缀表示法前缀表示法 S1+OP+S2 为为中缀表示法中缀表示法 S1+S2+OP 为为后缀表示法后缀表示法 例如例如:Exp=a b+(c d/e)f前缀式前缀式:+a b c/d e f中缀式中缀式:a b+c d/e f后缀式后缀式:a b c d e/f +结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括弧信息，中缀式丢失了括弧信息，致使运算的次序不确定致使运算的次序不确定;4)前缀式的运算规则前缀式的运算规则为为:连续出现的两个操作数和在它们连续出现的两
16、个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最小表达式个最小表达式;5)后缀式的运算规则后缀式的运算规则为为:运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表达式的运算顺序表达式的运算顺序;每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式。表达式。表达式表达式a*(b+c)-d的后的后缀表达式是表达式是()。abcd*+-abc+*d-abc*+d-+*abcdABCD提交单选题2分如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符，再找操作数再找操作数例如：例如：a b
17、c d e/f +a bd/ec-d/e(c-d/e)fl如何从原表达式求得后缀式？如何从原表达式求得后缀式？每个运算符的运算次序要由每个运算符的运算次序要由它之后的一个运它之后的一个运算符算符来定，在后缀式中，优先数高的运算符领来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。先于优先数低的运算符。分析分析“原表达式原表达式”和和“后缀式后缀式”中的运算符中的运算符:原表达式原表达式:a+b c d/e f 后缀式后缀式:a b c +d e/f 从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1)设立设立操作数操作数栈；栈；2)设表达式的结束符为设表达式的结束符为“#”，予设予设运算符栈的运算符栈的栈底为栈底为“#”；3)若若当前字符当前字符是操作数是操作数，则则直接发送给后缀式直接发送给后缀式。4)若若当前当前运算符的运算符的优先数高优先数高于栈顶运算符，于栈顶运算符，则则进栈进栈；5)否则，退出栈顶运算符发送给后缀式否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符对它之前后的运算符起隔离作用起隔离作用，“)”可视为自相应左括弧开始的表达式的结可视为自相应左括弧开始的表达式的结束符。束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：