数据结构：栈的原理与应用.ppt

第1页,数据结构,栈的原理与应用,第2页,主要内容,栈的定义 顺序栈 链栈 栈的应用举例 课堂作业,第3页,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,1. 什么是栈,一、栈的定义,第4页,第一个进栈的元素在栈底， 最后一个进栈的元素在栈顶， 不含元素的栈称为空栈。,出栈 Pop,进栈 Push,栈顶,栈底,2、栈的逻辑结构,top,bottom,空栈,top,bottom,第5页,bottom,bottom,A,A,B,C,D,E,A,B,栈操作图示,A进栈,B C D E 进栈,E D C 出栈,C,D,E,栈的特点 后进先出LIFO,3、入栈与出栈,第6页,4、 栈的基本操作,初始化 IniStack(S): 构造一个空栈S，准备存放数据； 进栈操作 Push(S,x)： 将数据元素x插入栈S，使x成为S的栈顶元素； 出栈操作 Pop(S)： 当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素； 取栈顶元素 GetTop(S)： 当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变； 判栈空 EmptyStack(S)： 若S为空栈则该函数值为1，否则为0。,第7页,栈属于加了限制条件的线性结构； 栈是后进先出的线性表； 进栈和出栈只能从栈的一个端点进行； 栈中的元素个数可以是0，此时是空栈； 栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个； 每个栈中的元素的类型相同.,5、栈的特性,第8页,思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。,CBA,ACB,ABC,CAB,BAC,BCA,第9页,如果是4个元素，那么它 不可能的出栈序列有哪些？,可能的出栈序列： 1243 1324 1342 2134 2143 2314 2431 3241 3214 3421 4321,不可能出现的出栈序列： 2413 3124 3412 4123 4231 4213 4312,第10页,用一个一维数组和一个整型变量来实现。,struct stack datatype arraymaxlen; int top; ,栈数组 arraymaxlen 用来存放栈中所有元素； 整型变量top的整数值表示栈顶元素在数组array中的位置，也称为栈顶指针。,二、栈的顺序存储结构,第11页,约定栈顶指针指向 向栈顶元素的位置,顺序栈的图示,栈空：,栈满：,Top=-1,Top=maxlen-1,二、栈的顺序存储结构（续）,第12页,1 ) 初始化栈 viod initstack(struct stack s ) s.top=-1; ,二、栈的顺序存储结构（续）,第13页,2 ) 进栈操作 viod Push ( struct stack s, datatype x ) s.top=s.top+1; s.arraytop=x； ,第14页,3）出栈操作 int pop( struct stack s ) return(arrays.top) ; s.top- ; ,第15页,栈在运算过程中可能发生“溢出”现象： 上溢 下溢,二、栈的顺序存储结构（续）,第16页,顺序栈的不足： 存在栈满以后就不能再进栈的问题 （这是因为用了定长的数组存储栈的元素） 解决方法： 使用链式存储结构。,二、栈的顺序存储结构（续）,第17页,三 、栈的链式存储和实现 栈的链式存储结构，也称链栈。其各结点的结构与单链表中的结点结构完全相同。如图所示：,在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法,结点结构定义： Typedef struct node elemtype data; struct node *next; node,*pointer;,第18页,(1) 初始化栈 Void initstack（pointer s） s=null; ,三 、栈的链式存储和实现（续）,第19页,进栈前 进栈后,(2) 进栈,第20页,进栈算法 Void push(pointer s,datatype x) p= (pointer *) malloc ( sizeof (node ); p-data=x; p-next=s-next; s-next=p; ,第21页,出栈前 出栈后,(3) 出栈,第22页,出栈算法,Datatype pop ( pointer s ) if (s-next=null) return(null); else p=s-next; x=p-data; s-next=p-next; free(p); return(x); ,第23页,四、栈的应用举例,实现数制转换 表达式求值,第24页,十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,数制转换,第25页,（2）算术表达式求值,中缀式求值的算法 运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一： 1 2 1的优先权高于2,第26页,操作符优先级表,第27页,求表达式算法,算法需两个栈。一个是运算符栈(OPTR) ；另一个是操作数或运算结果栈(OPND) 。算法的基本思想是： （1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符#压入运算符栈中成为其栈底。 （2）从左向右依次读出表达式中的每一个字符， 若为操作数，则将其压入操作数栈中，接着读出下一个字符； 若为运算符，则和运算符栈的栈顶运算符比较优先权： 如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符； 如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）； 如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。,第28页,例如：表达式3*(7-2),求值过程如下表：,第29页,五、课堂作业：迷宫问题,有一个迷宫，一个老鼠从入口进来，在迷宫里找出一个出口。,第30页,迷宫,出口,入口,白色表示通路，红色的表示墙,第31页,解题