《《数据结构(C／C++描述)》-阮宏一-电子教案 第3章 栈和队列》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-阮宏一-电子教案 第3章 栈和队列（73页珍藏版）》请在金锄头文库上搜索。
1、中国水利水电出版社,1,第3章 栈和队列,中国水利水电出版社,2,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,栈和队列是两种常用的数据类型,中国水利水电出版社,3,3.1 栈,栈是限定仅能在表尾一端进行插入、 删除操作的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,3.1.1 栈的定义及基本运算 一、什么是栈,中国水利水电出版社,4,栈的示意图,出栈,进栈,栈的特点 后进先出 (LIFO表),第1个进栈的元素在栈底， 最后一个进栈的元素在栈顶， 第1个出栈的元素为栈顶元素， 最后一个出栈的元素为栈底元素,二、栈的图示,中国
2、水利水电出版社,5,（1）初始化操作 InitStack(,三、栈的基本操作（1）,中国水利水电出版社,6,（5）进栈操作 Push(,三、栈的基本操作 （2）,中国水利水电出版社,7,栈的顺序存储结构，也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置，由一个称为栈顶指针的变量指示 。,栈的顺序存贮结构也称为顺序栈。,一、栈的顺序存储结构及实现,3.1.2 栈的顺序表示与实现,与线性表类似，栈也可以用顺序结构或链式结构存储。,中国水利水电出版社,8,SqStack: 结构类型名； SqStack类型的变量是结构变量。 base： 称为栈底指针，始终指向栈底位置； top
3、： 称为栈顶指针，约定栈顶指针指向栈顶元素的下一个位置； Stacksize：用于存放当前已分配的栈的存储空间的大小；,#define STACK_INIT_SIZE 100 / 栈存储空间的初始分配量 #define STACKINCREMENT 10 / 栈存储空间的分配增量 typedef struct SElemType * base; / 栈空间基址便于判断栈是否为空 SElemType * top / 栈顶指针 int stacksize; / 当前分配的栈空间大小 /（以sizeof(SElemType)为单位） SqStack;,顺序栈的类型定义,中国水利水电出版社,9,空栈,
4、A 进栈,B C D E 进栈，栈满,E D C 出栈,顺序栈的操作示例P.58,中国水利水电出版社,10,顺序栈的图示,base top stacksize,S,中国水利水电出版社,11,Status InitStack (SqStack / InitStack_Sq,（1）初始化操作,顺序栈的基本操作的实现,中国水利水电出版社,12,Status DetroyStack ( SqStack / DetroyStack_Sq,（2） 销毁栈操作,中国水利水电出版社,13,Status ClearStack ( SqStack / ClearStack,（3）置空栈操作,中国水利水电出版社,1
5、4,Status GetTop (SqStack S, SelemType / GetTop_Sq,（4） 取栈顶元素操作 GetTop,中国水利水电出版社,15,Status Push (SqStack / Push,（5） 进栈操作 Push,中国水利水电出版社,16,Status Pop (SqStack ,（6） 出栈操作 Pop,中国水利水电出版社,17,栈的链式存储结构， 也称链栈， 如右图所示：,3.1.3 栈的链式表示及实现,中国水利水电出版社,18,链式栈图示,说明： 1. 链栈可用线性链表表示； 2. 链栈的栈顶指针就是链表的头指针； 3. 进栈操作(push)就是在该线性
6、链表第一个元素结点之前插入一个新结点. 4. 出栈操作(pop)就是删除链表的第一个元素结点。,中国水利水电出版社,19,3.2 栈的应用举例,例1 数制转换 我们学习过各种数制的转换问题。 十-八进制转换 十-二进制转换等。 下面我们设计一程序,实现十-八进制数的自动转换。该程序功能为： 对于输入的任意一个非负十进制数，显示输出与其等值的八进制数。,中国水利水电出版社,20,我们这里介绍的方法基于下列原理： N = (Ndiv8)10 8+N mod 8 N：十进制数，div：整除运算，mod：求余运算； 例：(1348)10 = 283+582+08+4 = (2504)8 N N div
7、 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,中国水利水电出版社,21,由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位。 而显示时按照我们的习惯是从高位在前，低位在后，即按从高位到低位的顺序输出。 即后计算出的（高）位数先输出，具有后进先出的特点。 因此可将计算过程中得到的八进制数顺序进栈，按出栈序列打印输出的数，就是对应的八进制数。,中国水利水电出版社,22,例如：（1348)10 = (2504)8 其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,
8、计算顺序,输出顺序,中国水利水电出版社,23,void conversion( ) / 输入任意一个非负十进制整数，输出与其等值的八进制数 InitStack(S); / 建空栈 scanf(“%d”, ,中国水利水电出版社,24,例2 括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 ( ) 均为不正确的格式。,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,中国水利水电出版社,25,分析可能出现的不匹配的情况:,到来的右括弧非所“期待”的;,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”;,直到结束
9、，也没有到来所“期待”的括弧;,中国水利水电出版社,26,算法的设计思想：,（1）凡出现左括弧，则进栈；,（2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余error 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配error,（3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余error,中国水利水电出版社,27,Status matchpairs(SElemType str) SqStack *S; int tag=1; char *ch,e; / e存放出栈字符 / tag=1表示表达式中括号正确配对，tag=0表示不配对 I
10、nitStack(,中国水利水电出版社,28,/遇到)， 或，弹出栈顶字符 case ): Pop(S, ,中国水利水电出版社,29,例3 行编辑程序问题,如何实现？,是否每接受一个字符即存入存储器 ?,中国水利水电出版社,30,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符,“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,中国水利水电出版社,31,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outputchar(*s=#+);,则实际有效的是下列两行： while
11、(*s) putchar(*s+);,中国水利水电出版社,32, while (ch != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar(); ,while (ch != EOF) / EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,中国水利水电出版社,33,(1) 问题的提出 设计一个小计算器（程序），希望从键盘上输入一个算术表达式（由运算符操作数构成的字符串）后,在屏幕上显示表达式的求值结果。,例4 表达式求值,中国水利水电出版社,34,(2) 表达式的构成 操作数+运算符+界符
12、（如括号） (3) 表达式的求值： 例 5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为： 5+6(1+2)-4=5+63-4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为： + ， ， +， - 如何确定运算符的运算顺序？,1,2,3,4,1,2,3,4,中国水利水电出版社,35,+,2,1,-,*,/,(,),#,+ - * / ( ) #, , , , , =, , =,(4) 算符间的优先关系表,注： 1 ,2 是相邻算符， 1在左， 2在右 12 表示1的优先权低于2 P.52,中国水利水电出版社,36,(5) 算符优先算法 分析表达式 5+4(1+2
13、)-6 计算过程：,从左向右扫描表达式： 遇操作数 进栈； 遇运算符号 j与前面的刚扫描过的运算符 i 比较 若 i j 则说明 i 是已扫描算符中优先级最高者， j 出栈，进行运算； 若 i = j 若 i 为（，j 为 ）， j 出栈，说明括号内的式子已计算完； 若 i 为 #，出栈，栈空，表达式计算完毕。,5+4 (1+2)- 6,进行运算的算符i是当前扫描过的运算符中优先级最高者，可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。,后面也许有优先级 更大的算符,中国水利水电出版社,37,建立两个工作栈。OPTR栈保存运算符；OPND栈-保存操作数或运算结果。算法3.3 operan
14、dType EvaluateExpression( ) / 算术表达式求值的算符优先算法。设OPTR和OPND / 分别为运算符栈和运算数栈，OP为运算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=getchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) / In(c, OP)是判断c 是否为运算符的函数 Push(OPND, c); c=getchar( ); / 不是运算符则进数据栈OPND else ,中国水利水电出版社,38,续 switch (Precede(GetTop(OPTR), c) case : / 栈顶算符优先权高, 出栈运算，并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression,中国水利水电出版社,39,3.3 栈与递归,1什么是递归 递归是一个很有用的工具，在数学和程序设计等许 多领域中都用到了递归。 递
