数据结构：栈.ppt
数据结构栈所有结点通过指针的链接而构成的线性表称为单链表。线性表（a1，a2，an，）的单链表可直观地画成：head是单链表的头指针，指向开始结点a1, an是终端结点，其指针域为空，不指向任何结点。一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。 head a1 a2 ai an 循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。 head 通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。 空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。 head 另一种方法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。 rear rear 双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。 双链表的结点形式为： 其中链域prior和next分别指向本结点的直接前趋和直接后继结点。 prior data next 如果循环链表的结点再采用双向指针，就成为双向循环链表。 head 堆栈简称为栈，是限定在表的一端进行插入或删除操作的线性表。 进行插入或删除操作的一端称为栈顶（top），另一端称为栈底（bottom）。 插入元素又称为入栈（push），删除元素操作称为出栈（pop）。 不含元素的栈称为空栈。 堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。 堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的 。设数组名为STACK，其下标的下界为1，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。本例中top=4 topADCB4753216STACK入栈的主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所指示下标值的位置上。设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下：void push (ST, int n, top, G) if (top=n) printf(“栈溢出!n”); /*显示栈满信息*/ else top=top+1; STtop=G; 出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定的变量为x，则出栈的函数如下： void pop (ST, int top, x) if (top=0) printf(“空栈!n”); /*栈为空显示相应的信息*/ else x=STtop; top=top-1; /*栈顶位置下移*/ A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C.a, e, d, c, b, f, g D.d, c, f, e, b, a, g E.g, e, f, d, c, b, a 链堆栈是栈的链式存储表示，它是只允许在表头进行插入和删除运算的单链表。它与普通的单链表没有什么不同，只是将头指针head改称为栈顶指针top。 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进制数。通过“除B取余法”来解决。 由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此可以用栈来解决。一个算术表达式，例如A+B，其中加号“+”称作运算符，而A，B称为运算数。 对于由两个运算数和一个运算符组成的表达式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。 计算机处理表达式时，常把运算符放在两个运算数的后面或前面。1. 把运算符放在两个运算数的后面，例如 AB+ ，称为后缀形式，也叫做波兰式 。2. 把运算符放在两个运算数的前面，例如 +AB，则称做前缀形式，也叫做逆波兰表达式。 表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3；后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，如：2 1 + 3 *；前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：* + 2 1 3。表达式的计算：由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算一个中缀表达式简单得多。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理；1、如果是运算数则直接放入后缀表达式；2、如果是左括号则直接入栈；3、如果是右括号，则把从栈顶直到对应左括号之间的运算符依次退栈，并清除对应的左括号；4、对于运算符，如果该运算符的优先级大于栈顶优先级，则直接入栈，若该运算符的优先级小于或等于栈顶运算符优先级，则先把栈顶运算符出栈，写入后缀表达式，然后该运算符再入栈；5、扫描完成后，取出栈中所有运算符，写入后缀表达式。a*(b+c)-d1）求输入串的逆序。2）从头到尾扫描表达式。3）假如是运算数，把它添加到输出串中。4）假如是右括号，将它入栈。5）假如是运算符，则i) 假如栈空，此运算符入栈。ii) 假如栈顶是右括号，此运算符入栈。iii) 假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。6）假如是左括号，栈中运算符逐个出栈并输出，直到遇到右括号。右括号出栈并丢弃。7）假如输入还未完毕，跳转到步骤2。8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9）求输出串的逆序。2*3/(2-1)+5*(4-1) )1-4(*5+)1-2(/3*2A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd原表达式的逆序是)1-4(*5+)1-2(/3*2+/*23-21*5-41 算术表达式的不同运算符有不同的运算优先顺序，如，在没有括号时，乘除运算（*或/）要比加减运算（+或-）优先进行。下面用一个简单的例子说明编译系统在处理算术表达式时，是如何应用堆栈这种数据结构的。 假定表达式的运算数都是使用单个字母表示的，式中无括号且只有加、减、乘、除4种运算，而没有更复杂的运算，例如表达式 X+Y*Z。 使用S1和S2两个堆栈，S1用于存储运算数，S2用于存储运算符。编译系统处理时，将表达式从左向右逐个扫视一遍，并根据不同情况按以下原则处理: 1) 若是运算数，则将其压入S1栈； 2) 若是运算符且S2栈是空栈则将其压入 S2栈； 3) 若是运算符且S2栈为非空栈，且此运算符的级别高于S2栈顶运算符的级别，则将此运算符压入S2栈； 4) 凡不属于上面三条的情况，则将S2的栈顶运算符与S1栈最上面的两个运算数出栈进行运算，并将运算结果压入S1栈。 图中每一步上面括号中的运算对象表示该步是按哪一条原则处理的。 (a) (b) (c) (d) (e) (f) (1) (2) (1) (3) (4) (4) S1 S2 S1 S2 S1 S2 S1 S2 S1 S2 S1 S2 X X + X Y + X Y + * XR1 + R2 Z 返回stack.instack.out输入一个中缀表达式,以#结束.求值.
