数据结构：栈.ppt

《数据结构：栈.ppt》由会员分享，可在线阅读，更多相关《数据结构：栈.ppt（30页珍藏版）》请在课桌文档上搜索。

1、数据结构,栈,单链表,所有结点通过指针的链接而构成的线性表称为单链表。线性表（a1，a2，an，）的单链表可直观地画成：head是单链表的头指针，指向开始结点a1,an是终端结点，其指针域为空，不指向任何结点。一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。,循环链表,循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。,1.带头指针的循环链表,通常在循环链表的表

2、头结点前面再加一个空结点,也叫空表头结点。表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。,2.带尾指针的循环链表,另一种方法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。,双链表,双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。双链表的结点形式为：其中链域prior和next分

3、别指向本结点的直接前趋和直接后继结点。,如果循环链表的结点再采用双向指针，就成为双向循环链表。,栈,堆栈(Stack),堆栈简称为栈，是限定在表的一端进行插入或删除操作的线性表。进行插入或删除操作的一端称为栈顶（top），另一端称为栈底（bottom）。插入元素又称为入栈（push），删除元素操作称为出栈（pop）。不含元素的栈称为空栈。堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。,堆栈的表示,堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的。设数组名为STACK，其下标的

4、下界为1，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。,本例中top=4,1.入栈（push）,入栈的主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所指示下标值的位置上。设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下：,入栈函数,void push(ST,int n,top,G)if(top=n)printf(“栈溢出!n”);/*显示栈满信息*/else top=top+1;STtop=G;,2.出栈（Pop）,出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定的变量为x

5、，则出栈的函数如下：,出栈函数,void pop(ST,int top,x)if(top=0)printf(“空栈!n”);/*栈为空显示相应的信息*/else x=STtop;top=top-1;/*栈顶位置下移*/,设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是【】,a,b,c,e,d,f,g b,c,a,f,e,g,d a,e,d,c,b,f,g d,c,f,e,b,a,g g,e,f,d,c,b,a,3.3.1 链堆栈,链堆栈是栈的链式存储表示，它是只允许在表头进行插入和删除运算的单链表。它与普通的单链表没有什么不同，只是将头指针head改称为

6、栈顶指针top。,链堆栈的入栈算法,在栈顶指针是top的链堆栈中插入一个值为x的结点的算法：void push(node*top,int x)node*s;s=(node*)malloc(sizeof(node);/*建立一个结点指针*/s-data=x;s-next=top;top=s;,链堆栈的出栈算法,int pop(node*top)int x;node*p;if(top=NULL)printf(“栈为空!n”);else x=top-data;p=top;top=top-next;free(p);return(x);,数制转换栈的应用,将一个非负的十进制整数N转换为另一个等价的B进制

7、数。通过“除B取余法”来解决。由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此可以用栈来解决。,2.堆栈在表达式计算中的应用,一个算术表达式，例如A+B，其中加号“+”称作运算符，而A，B称为运算数。对于由两个运算数和一个运算符组成的表达式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。计算机处理表达式时，常把运算符放在两个运算数的后面或前面。1.把运算符放在两个运算数的后面，例如 AB+，称为后缀形式，也叫做波兰式。2.把运算符放在两个运算数的前面，例如+AB，则称做前缀形式，也叫做逆波兰表达式。,栈的应用计算表达式的值,表达式的三种形式：中缀表达式：运算符

8、放在两个运算对象中间，如：(2+1)*3；后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，如：2 1+3*；前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：*+2 1 3。表达式的计算：由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算一个中缀表达式简单得多。,把中缀表达式转化为后缀表达式,从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理；1、如果是运算数则直接放入后缀表达式；2、如果是左括号则直接入栈；3、如果是右括号，则把从栈顶直到对应左括号之间的运算符依次退栈

9、，并清除对应的左括号；4、对于运算符，如果该运算符的优先级大于栈顶优先级，则直接入栈，若该运算符的优先级小于或等于栈顶运算符优先级，则先把栈顶运算符出栈，写入后缀表达式，然后该运算符再入栈；5、扫描完成后，取出栈中所有运算符，写入后缀表达式。a*(b+c)-d,把中缀表达式转化为前缀表达式,1）求输入串的逆序。2）从头到尾扫描表达式。3）假如是运算数，把它添加到输出串中。4）假如是右括号，将它入栈。5）假如是运算符，则i)假如栈空，此运算符入栈。ii)假如栈顶是右括号，此运算符入栈。iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5

10、。6）假如是左括号，栈中运算符逐个出栈并输出，直到遇到右括号。右括号出栈并丢弃。7）假如输入还未完毕，跳转到步骤2。8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9）求输出串的逆序。2*3/(2-1)+5*(4-1)1-4(*5+)1-2(/3*2,表达式a*(b+c)-d的后缀表达式是【】,abcd*+-abc+*d-abc*+d-+*abcd,假设我们要将表达式2*3/(2-1)+5*(4-1)转换成前缀形式,原表达式的逆序是)1-4(*5+)1-2(/3*2+/*23-21*5-41,算术表达式的不同运算符有不同的运算优先顺序，如，在没有括号时，乘除运算（*或/）要比加减运算

11、（+或-）优先进行。下面用一个简单的例子说明编译系统在处理算术表达式时，是如何应用堆栈这种数据结构的。假定表达式的运算数都是使用单个字母表示的，式中无括号且只有加、减、乘、除4种运算，而没有更复杂的运算，例如表达式 X+Y*Z。,使用S1和S2两个堆栈，S1用于存储运算数，S2用于存储运算符。编译系统处理时，将表达式从左向右逐个扫视一遍，并根据不同情况按以下原则处理:1)若是运算数，则将其压入S1栈；2)若是运算符且S2栈是空栈则将其压入 S2栈；3)若是运算符且S2栈为非空栈，且此运算符的级别高于S2栈顶运算符的级别，则将此运算符压入S2栈；4)凡不属于上面三条的情况，则将S2的栈顶运算符与S1栈最上面的两个运算数出栈进行运算，并将运算结果压入S1栈。,图中每一步上面括号中的运算对象表示该步是按哪一条原则处理的。,返回,stack.cpp,stack.instack.out输入一个中缀表达式,以#结束.求值.,