1、1ppt课件第三章第三章 栈和队列栈和队列 本章学习两种特殊的线性数据结构，它们特殊本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线在定义的操作不同，即插入和删除操作只能在线性表的两端进行。性表的两端进行。 只能在一端进行的只能在一端进行的- 栈栈 分别在两端进行的分别在两端进行的- 队列队列2ppt课件 重点本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。 知识点 顺序栈、链栈、循环队列、链队列3ppt课件. 你见过餐馆中一叠一叠的盘子吗？如果它 们是按1,2,n 的次序往上叠的，那么使用时候 的次序应是什么样的？. 在日常生活中，为了维
2、持正常的社会秩序 而出现的常见现象是什么？ 4ppt课件栈和队列是在程序设计中被广泛使用的两种线性数据结构栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。5ppt课件 插 入 删 除线性表： Insert(L,i,x) Delete(L,i) (1in+1) (1in)栈：Insert(L,n+1,x) Delete(L,n)队列：Insert(L,n+1,x) Delete(L,1)6ppt课件第三章第三章 栈和队列栈和队列 3.1 栈栈1 、栈（、栈（stack) ：是一种特殊的线
3、性表（数：是一种特殊的线性表（数据元素之间的关系是线性关系），据元素之间的关系是线性关系），其插入、其插入、删除只能在表的一端进行，另一端固定不动。删除只能在表的一端进行，另一端固定不动。栈顶（栈顶（top ) ：插入、删除的一端；：插入、删除的一端；栈底（栈底（bottom ) ：固定不动的一端；：固定不动的一端；入栈（入栈（push ) ：又称压入，即插入一个元素；：又称压入，即插入一个元素；出栈（出栈（pop) ：又称弹出，即删除一个元素；：又称弹出，即删除一个元素； 一、抽象数据类型栈的定义一、抽象数据类型栈的定义7ppt课件2 、说明：设（说明：设（a1, a2, a3, , an
4、） 是一个栈是一个栈 （a1, a2, . , ai -1, ai , ai+1, , an ）栈栈底底栈栈顶顶进栈进栈出栈出栈1）表尾称为栈顶，表头称为栈底）表尾称为栈顶，表头称为栈底 ，即，即a1为栈底元素，为栈底元素，an为栈顶元素为栈顶元素;2）在表尾插入元素的）在表尾插入元素的 操作称进栈操作，在表头删除元素的操作称为操作称进栈操作，在表头删除元素的操作称为出栈操作出栈操作;3）元素按）元素按a1, a2, a3, , an 的次序进栈的次序进栈, 第一个进栈的元素一定在第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈
5、顶元素；第一个出栈的元素为栈顶元素；8ppt课件栈的示意图栈的示意图栈特点：由于限制了插入删除只能在一端进行，那栈特点：由于限制了插入删除只能在一端进行，那么元素的操作顺序有么元素的操作顺序有“先进后出先进后出”或或“后进先出后进先出”的特点的特点(Last In First out-LIFO First In Last out -FILO ) 第一个进栈的元素在第一个进栈的元素在栈底，最后一个进栈栈底，最后一个进栈的元素在栈顶，第一的元素在栈顶，第一个出栈的元素为栈顶个出栈的元素为栈顶元素，最后一个出栈元素，最后一个出栈的元素为栈底元素的元素为栈底元素9ppt课件课堂练习课堂练习假设有假设有
6、A ， B , C , D 四个元素；它们入栈次四个元素；它们入栈次序为序为A一一 B 一一C 一一D 出栈次序任意，出栈次序任意，请问不可能得到下面哪些出栈序列？请问不可能得到下面哪些出栈序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D (5 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D 10ppt课件3 、 栈的基本操作栈的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：构造一个空栈功能：构造一个空栈S； 2） 销毁栈操作销毁栈操作Destro
7、yStack(&S) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈; 3） 置空栈操作置空栈操作ClearStack(&S) 功能：将栈功能：将栈S置为空栈置为空栈; 4）判空栈操作）判空栈操作StackEmpty(S) 功能：若栈为空栈，返回功能：若栈为空栈，返回TRUE，否则，否则FALSE 5）取长度操作）取长度操作StackLength(S) 功能：返回栈功能：返回栈S的元素个数的元素个数 11ppt课件 6）取栈顶元素操作）取栈顶元素操作GetTop(S, &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e 返回返回;7）进栈操作）进栈操作Push(&S, e)功能：元素功能
8、：元素e进栈进栈;8）退栈操作）退栈操作Pop(&S, &e) 功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e返回返回;7）栈遍历）栈遍历StackTraverse(S) 功能：从栈底到栈顶依次调用函数功能：从栈底到栈顶依次调用函数visit().12ppt课件4、栈的ADT描述栈的抽象数据类型定义为： ADT Stack 数据对象：Dai|aiElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1 , ai D, i=2,.,n 约定an端为栈顶,a1端为栈底。基本操作：基本操作：. ADT Stack 13ppt课件二 栈的存储表示和操作的实现和线性表类似，栈也有两
9、种存储表示，其顺序存储结构简称为顺序栈顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。 14ppt课件 顺序存储方式：顺序存储方式：同一般线性表的顺序存储结构同一般线性表的顺序存储结构完全相同。完全相同。是利用一组连续的内存单元依次存放是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素自栈底到栈顶的数据元素，栈顶元素的位置由一，栈顶元素的位置由一个称为栈顶指针的变量指示个称为栈顶指针的变量指示 。 15ppt课件实际是栈中元素的个数 顺序栈类型的定义 / 结构定义： typedef struct ElemType *base; / 存储空间基址 int to
10、p; / 栈顶指针 int stacksize; / 允许的最大存储空间 Stack; 栈顶指针总是指在栈顶元素的后面一个位置上 16ppt课件top=0123450栈空top123450进栈Atop出栈栈满BCDEF设数组维数为stacksizetop=0,栈空，此时出栈，则下溢（underflow)top= stacksize,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptop17ppt课件特点：简单、方便，但易产生溢出。特点：简单、方便，但易产生溢出。上溢（上溢（Overflow ) 栈已经满，又要压入元素；栈已经满，又要压入元素
11、； 下溢（下溢（Underflow ) 栈已经空，还要弹出元素；栈已经空，还要弹出元素；注：上溢是一种错误，使问题的处理无法进行下去；注：上溢是一种错误，使问题的处理无法进行下去；而下溢一般认为是一种结束条件，即问题处理结束。而下溢一般认为是一种结束条件，即问题处理结束。18ppt课件# #define STACK_INIT_SIZE 100define STACK_INIT_SIZE 100/栈存储空间的初始分配量栈存储空间的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10/ / 栈存储空间的分配增量栈存储空间的分配增量type
12、def structtypedef structSElemType SElemType * *base;base;/栈空间基址栈空间基址称为栈底指针，指向栈底位置称为栈底指针，指向栈底位置SElemType SElemType * *top top /栈顶指针栈顶指针, ,约定栈顶指针指向栈顶元素的约定栈顶指针指向栈顶元素的 /下（后面）一个位置；下（后面）一个位置； int stacksize; int stacksize; /当前分配的栈空间大小当前分配的栈空间大小 / /（以（以sizeof(SElemType)sizeof(SElemType)为单位为单位） SqStackSqStac
13、k;/ ;/ SqStack:：结构类型名结构类型名顺序栈的存储表示顺序栈的存储表示19ppt课件 n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作图示初始化操作图示顺序栈基本操作的算法顺序栈基本操作的算法1）初始化操作）初始化操作InitStack_Sq(SqStack &S) 参数：参数：S是存放栈的结构变量；是存放栈的结构变量； 功能：建一个空栈功能：建一个空栈S；20ppt课件Status InitStack_Sq(Sq
14、Stack &S) /构造一个空栈构造一个空栈S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /为顺序栈动态分配存储空间为顺序栈动态分配存储空间 if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitStack_Sq21ppt课件Status DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; /若
15、栈未建立（尚未分配栈空间）若栈未建立（尚未分配栈空间） free (S.base); / 回收栈空间回收栈空间 S.base = S.top = null; S.stacksize = 0; return OK; / DetroyStack_Sq2） 销毁栈操作销毁栈操作 DestroyStack_Sq(SqStack &SSqStack &S ) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈;22ppt课件S.top = nullS.top = nullS.stacksizeS.stacksizeS.base = nullS.base = null 0 0 n nn-1n-1i-1i-1
16、i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE 销毁前销毁前 销毁后销毁后销毁栈操作图示销毁栈操作图示23ppt课件3）置空栈操作置空栈操作ClearStack_Sq(SqStack &S) 功能：将栈功能：将栈S置为空栈置为空栈 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若栈未建立（尚未分若栈未建立（尚未
17、分 /配栈空间）配栈空间） S.top = S.base ; return OK; / ClearStack_Sq24ppt课件 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT
18、_SIZEa an na ai ia ai-1i-1a a2 2a a1 1置空栈操作图示置空栈操作图示S.base=S.topS.base=S.top表明栈为空表明栈为空置空前置空前置空后置空后25ppt课件Status GetTop_Sq(SqStack S, SelemType &e) / 若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回/OK；否则返回否则返回ERROR if (S.top= =S.base) return ERROR; /若栈为空若栈为空 e = * (S.top-1); return OK;/GetTop_Sq4） 取栈顶元素操作取栈顶元
19、素操作GetTop_Sq(SqStack S, SElemType &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e返回返回;26ppt课件 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an n 取栈顶元素操作图示取栈顶元素操作图示27ppt课件5）进栈操作进栈操作Push(SqStack &S, SElemType eSqStack &S, SElem
20、Type e) 功能：元素功能：元素e 进栈进栈; 进栈操作主要步骤：进栈操作主要步骤： 1）S是否已满，是否已满， 若若栈栈满，重新分配存储空间；满，重新分配存储空间； 2）将元素将元素e 写入栈顶；写入栈顶； 3）修改栈顶指针，使栈顶指针指向栈顶元素的）修改栈顶指针，使栈顶指针指向栈顶元素的下（后面）一个位置；下（后面）一个位置；28ppt课件 n nn-1n-1i-1i-1i-2i-2 0 0n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INI
21、T_SIZEe ea an na ai ia ai-1i-1a a1 1anana ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE e 进栈前进栈前 e 进栈后进栈后 进栈操作图示进栈操作图示29ppt课件Status Push(SqStack &S, SElemType e) /将元素将元素e插入栈成为新的栈顶元素插入栈成为新的栈顶元素,要考虑上溢情况要考虑上溢情况 if (S.top-S.base=S.stacksize) /栈满，追加存储空间栈满，追
22、加存储空间 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) sizeof(ElemType); if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /元素元素e 插入栈顶，修改栈顶指针插入栈顶，修改栈顶指针 return OK; /Push进栈操作算法：进栈操作算法：30ppt课件Status Pop(SqStack &S, SElemTy
23、pe &e) /若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e 返回其值并返回返回其值并返回OK /否则返回否则返回ERROR if (S.top= = S.base) return ERROR; /栈空，返回栈空，返回ERROR e = * -S.top; /删除栈顶元素，用删除栈顶元素，用e 返回其值，并修返回其值，并修 /改栈顶指针改栈顶指针 return OK; /Pop6）出）出栈操作栈操作Pop(SqStack &S, SElemType &e )功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e 返回返回;31ppt课件S.topS.topS.stacksize
24、S.stacksizeS.baseS.base n nn-1n-1i-1i-1i-2i-2 0 0a an na ai ia ai-1i-1a a1 1STACK_INIT_SIZESTACK_INIT_SIZE 出栈操作前出栈操作前n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a1 1 出栈操作后出栈操作后a an ne e出栈操作图示出栈操作图示32ppt课件链栈链栈即为栈的链式存储结构。 链栈
25、的结点结构和单链表中的结点结构相同。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但是链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。33ppt课件 链栈中结点的定义： 链栈结构定义：typedef struct LNode ElemType data; struct LNode *next;* SLink;typedef struct SLink top; /栈顶指针 int length; /栈中元素个数LStack;34ppt课件链栈的基本操作和顺序栈操作基本相同，只需修改两处：初始化时不需要maxsize的参数在进行入栈操作时不需要顾忌栈的空间是否已经被填满。35
26、ppt课件void InitStack ( LStack &S ) / 构造一个空栈构造一个空栈 SS.top = NULL; / 设栈顶指针的初值为空S.length = 0; / 空栈中元素个数为0 / InitStack 36ppt课件void Push ( LStack &S, ElemType e )/ 在栈顶之上插入元素在栈顶之上插入元素 e 为新的栈顶元素为新的栈顶元素p = (LNode *)malloc(sizeof(LNode); / 建新的结点if(!p) exit(1);/ 存储分配失败p - data = e;p - next = S.top;/ 链接到原来的栈顶S.
27、top = p; / 移动栈顶指针+S.length; / 栈的长度增1 / Push .栈底toptopxp37ppt课件bool Pop ( LStack &S, ElemType &e ) / 若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用 e 返回其值，返回其值，/ 并返回并返回 TRUE；否则返回；否则返回 FALSEif ( !S.top )return FALSE; else e = S.top - data; / 返回栈顶元素 q = S.top; S.top = S.top - next;/ 修改栈顶指针 -S.length; / 栈的长度减1 delete
28、q; / 释放被删除的结点空间 return TRUE; / Pop top .栈底topq38ppt课件 小小 结结 1.栈是限定仅能在表尾一端进行插入、 删除操作的线性表；2. 栈的元素具有后进先出的特点；3. 栈顶元素的位置由一个称为栈顶指针的变量表示，进栈、出栈操作要修改栈顶指针；39ppt课件3.2 栈的应用举例栈的应用举例 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2输出顺序输出顺序计算顺序计算顺序数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N = (N d
29、iv d)d + N mod d (其中：div 为整除运算，mod 为求余运算)例如：(1348)10 = (2504)8 40ppt课件 由上述求解过程可以看出，在计算过程中是从低由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是高位在前，低位在后，即按时按照我们的习惯是高位在前，低位在后，即按从高位到低位的顺序输出从高位到低位的顺序输出, 即后计算出的（高）位即后计算出的（高）位数先输出，具有数先输出，具有后进先出后进先出的特点，因此可将计算的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈
30、序列打印过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。输出的就是对应的八进制数。41ppt课件3） 算法算法void conversion( ) /对于输入的任意一个非负十对于输入的任意一个非负十/进制整数，打印输出与其等值的八进制数进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈建空栈 scanf(“%d”, N); /输入一个输入一个非负十进制整数非负十进制整数 while(N) / N不等于零不等于零，循环，循环 Push(S, N % 8); / N/8第一个余数进栈第一个余数进栈 N=N/8 ; /整除运算整除运算 while(! St
31、ackEmpty) /输出存放在栈中的八进制数。输出存放在栈中的八进制数。 Pop(S, e); Printf(“%d”, e); /conversion42ppt课件 2 表达式求值表达式求值1） 表达式的构成表达式的构成 操作数操作数+运算符运算符+界符（如括号）界符（如括号）2） 表达式的求值：表达式的求值： 例例 5+6 (1+2)- 4 按照四则运算法则，上述表达式的计算过程为：按照四则运算法则，上述表达式的计算过程为： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为：表达式中运算符的运算顺序为： + ， ， +， -如何确
32、定运算符的运算顺序？如何确定运算符的运算顺序？43ppt课件3） 算符优先关系表算符优先关系表 表达式中任何相邻运算符表达式中任何相邻运算符 1、 2的优先关系有：的优先关系有： 1 2： 1的优先级高于的优先级高于 2 由四则运算法则，可得到如下的算符优先关系表：由四则运算法则，可得到如下的算符优先关系表：44ppt课件+ 21- -* */ /( () )# #+ - + - * * / ( ) # / ( ) # = = = 算符间的优先关系表算符间的优先关系表注：注： 1 2是相邻算符，是相邻算符，1在左在左 2在右在右45ppt课件4) 算符优先算法算符优先算法 我们再来分析一下表达
33、式我们再来分析一下表达式5+4 (1+2)- 6 计算过程：计算过程： 从左向右扫描表达式：从左向右扫描表达式： 遇操作数遇操作数保存；保存；遇运算符号遇运算符号 j与前面的刚扫描过的运算符与前面的刚扫描过的运算符 i比较比较 若若 i j 则保存则保存 j，（，（ 因此已保存的运算符的优先关系为因此已保存的运算符的优先关系为 1 2 3 j 则说明则说明 i是已扫描的运算符中优先级最高者，可进行运算；是已扫描的运算符中优先级最高者，可进行运算； 若若 i = j 则则 i为（，为（， j 为为 ），说明括号内的式子已计算完，需要消去括），说明括号内的式子已计算完，需要消去括号；号； 5+4
34、(1+2)- 6后面也许有优先后面也许有优先级更大的算符级更大的算符46ppt课件算法思想：(1) 设置两个栈：运算符栈（OPTR)和操作数栈（OPND)(2)设置数据栈为空栈，表达式起始符“#”为算符栈的栈底元素。(3)自左向右，依次扫描表达式中的基本符号，若扫描的基本符号为操作数，则将操作数入OPND栈。(4)若基本符号为运算符，则和OPTR栈顶元素的优先级比较（栈顶元素为C1,读到的算符为C2）： （a）c1c2，c1出栈，从OPND栈取出两个元素（a和b），按c1进行运算，并把运算结果放入OPND栈。(5)重复上述过程，直到表达式求值完毕（OPTR栈为空栈）47ppt课件表达式求值示意
35、图：表达式求值示意图：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR栈栈# #OPNDOPND栈栈toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptopto
36、ptoptop5 5读入表达式过程：读入表达式过程： + +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+18=235+18=2323-4=1923-4=193.4 栈的应用举例栈的应用举例48ppt课件 在算符优先算法中，建立了两个工作栈。一个是在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存栈，用以保存运算符运算符,一个是一个是OPND栈，用以保存操作数或运算结果。栈，用以保存操作数或运算结果。 operandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设算术表达式求值的算符优先
37、算法。设OPTR和和OPND分别为运算符栈分别为运算符栈和运算数栈，和运算数栈，OP为运算符集合。为运算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是运算符则进栈不是运算符则进栈,In(c, OP)判断判断c是否是运算符的函数是否是运算符的函数 else 49ppt课件续续 switch (Precede(GetTop(OPTR), c) case
38、 : /新输入的算符新输入的算符c优先级低，即栈顶算符优先权优先级低，即栈顶算符优先权 /高高,出栈并将运算结果入栈出栈并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression50ppt课件3括弧匹配检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均
39、为错误的匹配。问题：如何检验一个给定表达式中的括弧是否正确匹配？解决办法：用期待的急迫程度这个概念来描述。 51ppt课件 对于后出现的左括号,它等待与其匹配的右括号出 现的急迫心情要比先出现的左括号高,也就是说,对 左括号来说,后出现的比先出现的优先等待检测. 对右括号来说,每个出现的右括号要去找在它之前最后出现的那个左括号去匹配.52ppt课件例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8显然,必须将先后出现的左括号依次保存,为了反映这个优先程度,保存左括号的结构应该使用栈 对于出现的右括号来说,只要栈顶元素相匹配即可.如果栈顶的左括号正好和它匹配,就可将它从栈顶删除.53
40、ppt课件什么样的情况是“不匹配”的情况呢？1和栈顶的左括弧不相匹配；2栈中并没有左括弧等在那里；3栈中还有左括弧没有等到和它相匹配的右括弧。54ppt课件Bool match()InitStack(S); /初始化栈初始化栈 ch=getchar(); /接收第一个括号接收第一个括号 while(ch!=#) /不是结束符不是结束符 if(ch=(|ch=) /左括号时进栈左括号时进栈 push(S,ch); /if else if(ch=) /) 时检测匹配时检测匹配 if(!StackEmpty(S) gettop(S,e); /取栈顶元素取栈顶元素 if(e=() /匹配成功匹配成功
41、pop(S); /if else return false; /匹配失败匹配失败 /if /elseElse /时检测匹配时检测匹配 if(!StackEmpty(S) gettop(S,e); /取栈顶元素取栈顶元素 if(e=) /匹配成功匹配成功 pop(S); /if else return false; /匹配失败匹配失败 /if /else ch=getchar();/whileIf(!StackEmpty(S) return false; /栈中还有没有匹配栈中还有没有匹配 /成功的左括号成功的左括号 else return true;/match算法实现算法实现55ppt课件4
42、.迷宫求解问题计算机解迷宫时，通常用的是“穷举求解穷举求解”的方法. 1进入迷宫之后，不管在迷宫的哪一个位置上，都先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通； 56ppt课件为了保证在任何位置上都能沿原路退回，需要用 一个“后进先出”的结构即栈来保存从入口到当前 位置的路径。并且在走出出口之后
43、，栈中保存的 正是一条从入口到出口的路径。57ppt课件算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 58ppt课件伪码算法 ：设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方
44、向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)； 没有路径存在59ppt课件3.3 栈与递归 由上看到：应用中如果处理数据处理过程具有后由上看到：应用中如果处理数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下进先出的特性，可利用栈来实现数据处理过程。下面我们将看到可以用栈来实现递归。面我们将看到可以用栈来实现递归。1什么是递归什么是递归 递归是一个很有用的工具，在数学和程序设计等许多递归是一个很有用的工具，在数学和程
45、序设计等许多领域中都用到了递归。递归定义：简单地说，一个领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念用自己定义自己的概念,称为递归定义。称为递归定义。例例 n!= 1 2 3 4 (n-1) n n!递归定义递归定义 n!= 1 当当 n=0时时 n!= n (n-1)! 当当n 0时时用(n-1)!定义n!60ppt课件栈与递归2.递归函数递归函数：一个直接调用自己或通过一系列调用：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。间接调用自己的函数称为递归函数。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己直接调用自
46、己B间接调用自己间接调用自己61ppt课件栈与递归递归是程序设计中的有用工具，下面举例说明递归算法的编写递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。和执行过程。2递归算法的编写递归算法的编写1）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法 问题的递归描述（定义）问题的递归描述（定义） 递归定义包括两项递归定义包括两项 基本项（终止项）基本项（终止项）：描述递归终止时问题的求解；：描述递归终止时问题的求解； 递归项：递归项：将问题分解为与原问题性质相同，但规模较小将问题分解为与
47、原问题性质相同，但规模较小 的问题；的问题； 62ppt课件栈与递归栈与递归例例1 编写求解编写求解 阶乘阶乘n! 的递归算法的递归算法首先给出阶乘首先给出阶乘n! 的递归定义的递归定义 n!的递归定义的递归定义 基本项：基本项： n!=1 当当 n=1 递归项：递归项： n!=n (n-1)! 当当 n 1 有了问题的递归定义，很容易写出对应的递归算法：有了问题的递归定义，很容易写出对应的递归算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的阶乘的阶乘 If（n=1） return（1）；）； Else return（n*fact (n-1)）；）；/fa
48、ct 63ppt课件栈与递归栈与递归例例2. 编写求解编写求解Hanoi塔问题的递归算法塔问题的递归算法 有三个各为有三个各为X，Y，Z的塔座，在的塔座，在X项有项有n个大小不个大小不同，依小到大编号为同，依小到大编号为1，2n的圆盘。的圆盘。 现要求将现要求将X上上的的n个圆盘移至个圆盘移至Z上，并仍以同样顺序叠放，上，并仍以同样顺序叠放， 圆盘移动圆盘移动时必须遵守下列原则：时必须遵守下列原则：1）每次移动一个盘子；）每次移动一个盘子；2）圆盘可以放在）圆盘可以放在X，Y，Z中的任一塔座上；中的任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；）任何时刻都不能将较大的圆盘压放在
49、较小圆盘之上；例例 n=3时圆盘移动的过程如下图所示时圆盘移动的过程如下图所示：64ppt课件abc321 11213121栈与递归栈与递归Y YX XZ Z65ppt课件栈与递归栈与递归首先给出求解首先给出求解Hanoi塔问题塔问题 的递归描述（定义）的递归描述（定义） 基本项：基本项： n=1时，将时，将n号圆盘从号圆盘从X移至移至Z； 递归项：递归项： n1时，时， 将将X上上1n-1号圆盘移至号圆盘移至Y； 将将X上的上的n号圆盘从号圆盘从X移至移至Z; 将将Y上上1n-1号圆盘从号圆盘从Y移至移至Z; 将规模为将规模为n n的的问题的求解归问题的求解归结为规模为结为规模为n-n-1
50、1的问题的求的问题的求解解有了问题的递归定义，很容易写出对应的递归有了问题的递归定义，很容易写出对应的递归算法：算法：66ppt课件void hanoi (int n, char x, char y, char z) /将塔座将塔座x上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1至至n的的n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z上，上，y可用作辅助塔座。可用作辅助塔座。 if (n= =1) move(x,1,z); /将编号为将编号为1的圆盘从的圆盘从x移动移动z else hanoi(n-1, x, z, y); /将将x上编号为上编号为1至至n-1的圆盘移到的圆盘
