昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 本节内容 1.栈的链式存储结构及实现 2.栈的应用

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 定义 栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。

栈的链式存储结构及实现 定义 示意图： 对于链栈来说： 1.不需要头结点 2.不存在栈满的情况 3.top=NULL，为空栈 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 定义 示意图： 对于链栈来说： 1.不需要头结点 2.不存在栈满的情况 3.top=NULL，为空栈

栈的链式存储结构及实现 链栈的结构代码 /* 链栈结构 */ typedef struct StackNode { 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 链栈的结构代码 /* 链栈结构 */ typedef struct StackNode { SElemType data; struct StackNode *next; }StackNode,*LinkStackPtr; typedef struct LinkStackPtr top; int count; }LinkStack;

栈的链式存储结构及实现 进栈（push）操作 /* 插入元素e为新的栈顶元素 */ 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 进栈（push）操作 /* 插入元素e为新的栈顶元素 */ Status Push(LinkStack *S,SElemType e) { LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top;/* 把当前的栈顶元素赋值给新结点的直接后继*/ S->top=s; /* 将新的结点s赋值给栈顶指针*/ S->count++; return OK; } 演示：

栈的链式存储结构及实现 出栈（pop）操作 /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 出栈（pop）操作 /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p; if(StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top; /* 将栈顶结点赋值给p*/ S->top=S->top->next; /* 使得栈顶指针下移一位，指向后一结点 */ free(p); /* 释放结点p */ S->count--; return OK; } 演示：

栈的链式存储结构及实现 注意 1.使用过程中元素的个数变化不可预料，有时很小，有时非常大，那么最好用链栈 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的链式存储结构及实现 注意 1.使用过程中元素的个数变化不可预料，有时很小，有时非常大，那么最好用链栈 2.如果它的变化在可控的范围内，建议用顺序栈

栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 迭代的方法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 迭代的方法： int _tmain(int argc, _TCHAR* argv[]) { unsigned int i; unsigned int n = 16; //求16的阶乘 unsigned int nResult = 1; for (i=1;i<=n;i++) nResult = nResult*i; printf("%d!=%d \n",i,nResult); } return 0;

栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 递归的方法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 递归的方法： unsigned int Factorial(unsigned int n) { unsigned int nRet; nRet = 1; if(n>1) nRet = n*Factorial(n-1); } printf("%d!=%d \n",n,nRet); return nRet;

栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 递归的方法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用1—递归 先来看一个经典的递归的例子：求n! 递归的方法： int _tmain(int argc, _TCHAR* argv[]) { Factorial(16); return 0; }

栈的应用 应用1—递归 递归的定义: 一个直接调用自己或间接调用自己的函数成为递归函数 注意： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用1—递归 递归的定义: 一个直接调用自己或间接调用自己的函数成为递归函数 注意： 必须有退出条件，让递归退出，是函数不再调用自身。 优点： 是代码简洁，更易理解 缺点： 1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间 2.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出

栈的应用 应用2—四则运算表达式 标准的四则运算： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用2—四则运算表达式 标准的四则运算： 当一级运算（加减）和二级运算（乘除）同时出现在一个式子中时，它们的运算顺序是先乘除，后加减，如果有括号就先算括号内后算括号外，同一级运算顺序是从左到右，这样的运算叫四则运算。 比如：99+（88-11）×5+66÷2 1.先要算88-11=77 2.再算77×5=385 3.99+385=484 4. 66÷2=33 5.484+33=517 这样存在的问题： 1.要考虑括号 2.要考虑优先级 3.计算的顺序和运算符出现的位置不一样

栈的应用 应用2—四则运算表达式 后缀表达式： 定义： 举例： 99+（88-11）×5+66÷2 后缀表达式为： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用2—四则运算表达式 后缀表达式： 可以实现所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运 算符的优先级和括号） 定义： 一种不需要括号的把所有的运算符号放到要运算数字后面的表达式 举例： 99+（88-11）×5+66÷2 后缀表达式为： 99 88 11 - 5 × + 66 2 ÷ + 演示后缀表达式计算过程：

栈的应用 应用2—四则运算表达式 中缀表达式转后缀表达式： 规则： 2.遇到数字，输出，成为后缀表达式的一部分 演示过程： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 栈的应用 应用2—四则运算表达式 中缀表达式转后缀表达式： 可以实现所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运 算符的优先级和括号） 规则： 1.从左到右遍历中缀表达式的每个数字和符号 2.遇到数字，输出，成为后缀表达式的一部分 3.遇到符号，判断其与栈顶符号的优先级，不高于栈顶符号，栈顶符号依次出栈，并将当前符号进栈 4.遇到右括号依次弹出栈里的元素，直到弹出左括号 5.当栈变为空时，输出的结果即为后缀表达式 演示过程：