数据结构清华大学严蔚敏ppt栈和队列课件.ppt

《数据结构清华大学严蔚敏ppt栈和队列课件.ppt》由会员分享，可在线阅读，更多相关《数据结构清华大学严蔚敏ppt栈和队列课件.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 栈和队列栈和队列 栈和队列是两种应用非常广泛的数据结构栈和队列是两种应用非常广泛的数据结构栈和队列是两种应用非常广泛的数据结构栈和队列是两种应用非常广泛的数据结构，它们都，它们都，它们都，它们都来自线性表数据结构，来自线性表数据结构，来自线性表数据结构，来自线性表数据结构，都是都是都是都是“操作受限操作受限操作受限操作受限”的线性表的线性表的线性表的线性表。栈在计算机的实现有多种方式：栈在计算机的实现有多种方式：栈在计算机的实现有多种方式：栈在计算机的实现有多种方式：硬堆栈硬堆栈硬堆栈硬堆栈：利用：利用：利用：利用CPUCPU中的某些寄存器组或类似的硬中的某些寄存器组或类似的硬中的

2、某些寄存器组或类似的硬中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，件或使用内存的特殊区域来实现。这类堆栈容量有限，件或使用内存的特殊区域来实现。这类堆栈容量有限，件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；但速度很快；但速度很快；但速度很快；软堆栈软堆栈软堆栈软堆栈：这类堆栈主要在内存中实现。堆栈容量：这类堆栈主要在内存中实现。堆栈容量：这类堆栈主要在内存中实现。堆栈容量：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有可以达到很大。在实现方式上，又有可以达到很大。在实现方式上，又有可以达到很大。在实现方式上，又有动态方式动态方式

3、动态方式动态方式和和和和静态静态静态静态方式方式方式方式两种。两种。两种。两种。本章将讨论栈和队列的基本概念本章将讨论栈和队列的基本概念本章将讨论栈和队列的基本概念本章将讨论栈和队列的基本概念、存储结构存储结构存储结构存储结构、基本基本基本基本操作以及这些操作的具体实现操作以及这些操作的具体实现操作以及这些操作的具体实现操作以及这些操作的具体实现。3.1 栈栈3.1.1 栈的基本概念栈的基本概念1 栈的概念栈的概念 栈栈(Stack)：是限制在表的一端进行插入和删除是限制在表的一端进行插入和删除是限制在表的一端进行插入和删除是限制在表的一端进行插入和删除操作的线性表。又称为后进先出操作的线性表

4、。又称为后进先出操作的线性表。又称为后进先出操作的线性表。又称为后进先出LIFOLIFO (Last In Last In First OutFirst Out)或先进后出或先进后出或先进后出或先进后出FILOFILO (First In Last OutFirst In Last Out)线性线性线性线性表。表。表。表。栈顶栈顶(Top)：允许进行插入、删除操作的一端，允许进行插入、删除操作的一端，允许进行插入、删除操作的一端，允许进行插入、删除操作的一端，又称为表尾。用栈顶指针又称为表尾。用栈顶指针又称为表尾。用栈顶指针又称为表尾。用栈顶指针(top)(top)来指示栈顶元素来指示栈顶元素

5、来指示栈顶元素来指示栈顶元素。栈底栈底(Bottom)：是固定端，又称为表头。是固定端，又称为表头。是固定端，又称为表头。是固定端，又称为表头。空栈空栈：当表中没有元素时称为空栈。当表中没有元素时称为空栈。当表中没有元素时称为空栈。当表中没有元素时称为空栈。设栈设栈设栈设栈S=(aS=(a1 1，a a2 2，a an n)，则，则，则，则a a1 1称为栈底元素，称为栈底元素，称为栈底元素，称为栈底元素，a an n为栈顶元素，如为栈顶元素，如为栈顶元素，如为栈顶元素，如图图图图3-13-1所示。所示。所示。所示。栈中元素按栈中元素按栈中元素按栈中元素按a a1 1，a a2 2，a an

6、n的次的次的次的次序进栈，退栈的第一个元素应为栈顶序进栈，退栈的第一个元素应为栈顶序进栈，退栈的第一个元素应为栈顶序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原元素。即栈的修改是按后进先出的原元素。即栈的修改是按后进先出的原元素。即栈的修改是按后进先出的原则进行的。则进行的。则进行的。则进行的。图图3-1 顺序顺序栈示意图栈示意图a1a2aianbottomtop进栈（进栈（push）出栈出栈(pop)2 栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack数据对象：数据对象：D=ai|aiElemSet,i=1,2,n，n0 数据关系：数据关系：R=|ai-1，aiD

7、,i=2,3,n 基本操作：初始化、进栈、出栈、取栈顶元素等基本操作：初始化、进栈、出栈、取栈顶元素等 ADT Stack 栈的顺序存储结构简称为顺序栈，和线性表相类似，栈的顺序存储结构简称为顺序栈，和线性表相类似，栈的顺序存储结构简称为顺序栈，和线性表相类似，栈的顺序存储结构简称为顺序栈，和线性表相类似，用用用用一维数组一维数组一维数组一维数组来来来来存储栈存储栈存储栈存储栈。根据数组是否可以根据需要增大，。根据数组是否可以根据需要增大，。根据数组是否可以根据需要增大，。根据数组是否可以根据需要增大，又可分为又可分为又可分为又可分为静态顺序栈静态顺序栈静态顺序栈静态顺序栈和和和和动态顺序栈动

8、态顺序栈动态顺序栈动态顺序栈。静态顺序栈静态顺序栈静态顺序栈静态顺序栈实现简单，但不能根据需要增大栈的实现简单，但不能根据需要增大栈的实现简单，但不能根据需要增大栈的实现简单，但不能根据需要增大栈的存储空间；存储空间；存储空间；存储空间；动态顺序栈动态顺序栈动态顺序栈动态顺序栈可以根据需要增大栈的存储空间，但可以根据需要增大栈的存储空间，但可以根据需要增大栈的存储空间，但可以根据需要增大栈的存储空间，但实现稍为复杂。实现稍为复杂。实现稍为复杂。实现稍为复杂。3.1.2 栈的顺序存储表示栈的顺序存储表示 采用采用采用采用动态动态动态动态一维数组一维数组一维数组一维数组来来来来存储栈存储栈存储栈存

9、储栈。所谓动态，指的是栈。所谓动态，指的是栈。所谓动态，指的是栈。所谓动态，指的是栈的大小可以根据需要增加。的大小可以根据需要增加。的大小可以根据需要增加。的大小可以根据需要增加。用用用用bottombottom表示栈底指针，栈底固定不变的；栈表示栈底指针，栈底固定不变的；栈表示栈底指针，栈底固定不变的；栈表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用顶则随着进栈和退栈操作而变化。用顶则随着进栈和退栈操作而变化。用顶则随着进栈和退栈操作而变化。用toptop(称为栈顶称为栈顶称为栈顶称为栈顶指针指针指针指针)指示当前栈顶位置。指示当前栈顶位置。指示当前栈顶位置。指示当前栈顶位

10、置。用用用用top=bottomtop=bottom作为栈空的标记作为栈空的标记作为栈空的标记作为栈空的标记，每次，每次，每次，每次toptop指向指向指向指向栈顶数组中的下一个存储位置栈顶数组中的下一个存储位置栈顶数组中的下一个存储位置栈顶数组中的下一个存储位置。结点进栈结点进栈：首先将数据元素保存到栈顶首先将数据元素保存到栈顶首先将数据元素保存到栈顶首先将数据元素保存到栈顶(toptop所所所所指的当前位置指的当前位置指的当前位置指的当前位置)，然后执行，然后执行，然后执行，然后执行toptop加加加加1 1，使，使，使，使toptop指向栈顶指向栈顶指向栈顶指向栈顶的下一个存储位置的下一

11、个存储位置的下一个存储位置的下一个存储位置;3.1.2.1 栈的动态顺序存储表示栈的动态顺序存储表示 结点出栈结点出栈：首先执行首先执行首先执行首先执行toptop减减减减1 1，使，使，使，使toptop指向栈顶指向栈顶指向栈顶指向栈顶元素的存储位置，然后将栈顶元素取出元素的存储位置，然后将栈顶元素取出元素的存储位置，然后将栈顶元素取出元素的存储位置，然后将栈顶元素取出。图图图图3-23-2是一个动态栈的变化示意图是一个动态栈的变化示意图是一个动态栈的变化示意图是一个动态栈的变化示意图。图图3-2 (动态动态)堆栈变化示意图堆栈变化示意图空栈空栈bottomtop元素元素a进栈进栈botto

12、mtopa元素元素b，c进栈进栈bottomtopabc元素元素c退栈退栈bottomtopabbottomtopabdef元素元素d，e，f进栈进栈基本操作的实现基本操作的实现1 栈的类型定义栈的类型定义#define STACK_SIZE 100#define STACK_SIZE 100 /*/*栈初始向量大小栈初始向量大小栈初始向量大小栈初始向量大小 */#define STACKINCREMENT 10#define STACKINCREMENT 10 /*/*存储空间分存储空间分存储空间分存储空间分配增量配增量配增量配增量 */#typedef int ElemType;#type

13、def int ElemType;typedef struct sqstacktypedef struct sqstack ElemType *bottom;ElemType *bottom;/*/*栈不存在时值为栈不存在时值为栈不存在时值为栈不存在时值为NULL */NULL */ElemType *top;ElemType *top;/*/*栈顶指针栈顶指针栈顶指针栈顶指针 */int stacksize;int stacksize;/*/*当前已分配空间，以元素当前已分配空间，以元素当前已分配空间，以元素当前已分配空间，以元素为单位为单位为单位为单位 */SqStack;SqStack;

14、2 栈的初始化栈的初始化Status Init_Stack(void)Status Init_Stack(void)SqStack S;SqStack S;S.bottom=(ElemType S.bottom=(ElemType*)malloc(STACK_SIZE*)malloc(STACK_SIZE*sizeof(ElemType);*sizeof(ElemType);if(!S.bottom)return ERROR;if(!S.bottom)return ERROR;S.top=S.bottom;S.top=S.bottom;/*/*栈空时栈顶和栈底指针相栈空时栈顶和栈底指针相栈空时

15、栈顶和栈底指针相栈空时栈顶和栈底指针相同同同同 */S.stacksize=STACK_SIZE;S.stacksize=STACK_SIZE;return OK;return OK;3 压栈压栈(元素进栈元素进栈)Status push(SqStack S,ElemType e)Status push(SqStack S,ElemType e)if (S.top-S.bottom=S.stacksize-1)S.bottom=(ElemType*)realloc(S.S.bottom=(ElemType*)realloc(S.STACKINCREMENT+STACK_SIZE)STACKIN

16、CREMENT+STACK_SIZE)*sizeof(ElemType);*sizeof(ElemType);/*/*栈满，追加存储空栈满，追加存储空栈满，追加存储空栈满，追加存储空间间间间 */if(!S.bottom)return ERROR;if(!S.bottom)return ERROR;S.top=S.bottom+S.stacksize;S.top=S.bottom+S.stacksize;S.stacksize+=STACKINCREMENT;S.stacksize+=STACKINCREMENT;*S.top=e;S.top+;*S.top=e;S.top+;/*/*/*/*

17、栈顶指针加栈顶指针加栈顶指针加栈顶指针加1 1，e e成为新的成为新的成为新的成为新的栈顶栈顶栈顶栈顶*/return OK;return OK;4 弹栈弹栈(元素元素出栈出栈)Status pop(SqStack S,ElemType *e)Status pop(SqStack S,ElemType *e)/*/*弹出栈顶元素弹出栈顶元素弹出栈顶元素弹出栈顶元素*/if(S.top=S.bottom)if(S.top=S.bottom)return ERROR;return ERROR;/*/*栈空，返回失败标志栈空，返回失败标志栈空，返回失败标志栈空，返回失败标志 */S.top-;e=*

18、S.top;S.top-;e=*S.top;return OK;return OK;采用采用采用采用静态静态静态静态一维数组一维数组一维数组一维数组来来来来存储栈存储栈存储栈存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变栈底固定不变的，而栈顶则随着进栈和退栈操作变栈底固定不变的，而栈顶则随着进栈和退栈操作变栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，化的，化的，化的，栈底固定不变的；栈顶则随着进栈和退栈操作而栈底固定不变的；栈顶则随着进栈和退栈操作而栈底固定不变的；栈顶则随着进栈和退栈操作而栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量变化，用一个整型变量变化，用一

19、个整型变量变化，用一个整型变量toptop(称为栈顶指针称为栈顶指针称为栈顶指针称为栈顶指针)来指示当来指示当来指示当来指示当前栈顶位置。前栈顶位置。前栈顶位置。前栈顶位置。用用用用top=0top=0表示栈空的初始状态表示栈空的初始状态表示栈空的初始状态表示栈空的初始状态，每次，每次，每次，每次toptop指向栈指向栈指向栈指向栈顶在数组中的存储位置顶在数组中的存储位置顶在数组中的存储位置顶在数组中的存储位置。结点进栈结点进栈：首先执行首先执行首先执行首先执行toptop加加加加1 1，使，使，使，使toptop指向新的指向新的指向新的指向新的栈顶位置栈顶位置栈顶位置栈顶位置，然后将数据元素

20、保存到栈顶然后将数据元素保存到栈顶然后将数据元素保存到栈顶然后将数据元素保存到栈顶(toptop所指的所指的所指的所指的当前位置当前位置当前位置当前位置)。3.1.2.2 栈的静态顺序存储表示栈的静态顺序存储表示 结点出栈结点出栈：首先首先首先首先把把把把toptop指向的栈顶元素取出指向的栈顶元素取出指向的栈顶元素取出指向的栈顶元素取出，然然然然后执行后执行后执行后执行toptop减减减减1 1，使，使，使，使toptop指向新的栈顶位置指向新的栈顶位置指向新的栈顶位置指向新的栈顶位置。若栈的数组有若栈的数组有若栈的数组有若栈的数组有MaxsizeMaxsize个元素个元素个元素个元素，则，

21、则，则，则top=Maxsize-1top=Maxsize-1时栈满时栈满时栈满时栈满。图。图。图。图3-33-3是一个大小为是一个大小为是一个大小为是一个大小为5 5的栈的栈的栈的栈的变化示意图的变化示意图的变化示意图的变化示意图。图图3-3 静态静态堆栈变化示意图堆栈变化示意图空栈空栈bottomtopTop=11个元素进栈个元素进栈bottomtopaTop=33个元素进栈个元素进栈bottomtopabcTop=4栈满栈满bottomtopabedTop=2元素元素c进栈进栈bottomtopab基本操作的实现基本操作的实现1 栈的类型定义栈的类型定义#define MAX_STACK

22、_SIZE 100#define MAX_STACK_SIZE 100 /*/*栈向栈向栈向栈向量大小量大小量大小量大小 */#typedef int ElemType;#typedef int ElemType;typedef struct sqstacktypedef struct sqstack ElemType ElemType stack_arrayMAX_STACK_SIZE;stack_arrayMAX_STACK_SIZE;int top;int top;SqStack;SqStack;2 栈的初始化栈的初始化SqStack Init_Stack(void)SqStack In

23、it_Stack(void)SqStack S;SqStack S;S.bottom=S.top=0;return(S);S.bottom=S.top=0;return(S);3 压栈压栈(元素进栈元素进栈)Status push(SqStack S,ElemType e)Status push(SqStack S,ElemType e)/*/*/*/*使数据元素使数据元素使数据元素使数据元素e e进栈成为新的栈顶进栈成为新的栈顶进栈成为新的栈顶进栈成为新的栈顶 */if (S.top=MAX_STACK_SIZE-1)if (S.top=MAX_STACK_SIZE-1)return ERR

24、OR;return ERROR;/*/*栈满，返回错误标志栈满，返回错误标志栈满，返回错误标志栈满，返回错误标志 */S.top+;S.top+;/*/*/*/*栈顶指针加栈顶指针加栈顶指针加栈顶指针加1 1 */*/*/*/S.stack_arrayS.top=e ;S.stack_arrayS.top=e ;/*/*/*/*e e成为新的栈成为新的栈成为新的栈成为新的栈顶顶顶顶 */return OK;return OK;/*/*压栈成功压栈成功压栈成功压栈成功 */4 弹栈弹栈(元素元素出栈出栈)Status pop(SqStack S,ElemType *e)Status pop(Sq

25、Stack S,ElemType *e)/*/*弹出栈顶元素弹出栈顶元素弹出栈顶元素弹出栈顶元素*/if(S.top=0)if(S.top=0)return ERROR;return ERROR;/*/*栈空，返回错误标志栈空，返回错误标志栈空，返回错误标志栈空，返回错误标志 */*e=S.stack_arrayS.top;*e=S.stack_arrayS.top;S.top-;S.top-;return OK;return OK;当栈满时做进栈运算必定产生空间溢出，简称当栈满时做进栈运算必定产生空间溢出，简称当栈满时做进栈运算必定产生空间溢出，简称当栈满时做进栈运算必定产生空间溢出，简称“

26、上上上上溢溢溢溢”。上溢是一种出错状态，应设法避免。上溢是一种出错状态，应设法避免。上溢是一种出错状态，应设法避免。上溢是一种出错状态，应设法避免。当栈空时做退栈运算也将产生溢出，简称当栈空时做退栈运算也将产生溢出，简称当栈空时做退栈运算也将产生溢出，简称当栈空时做退栈运算也将产生溢出，简称“下溢下溢下溢下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终下溢则可能是正常现象，因为栈在使用时，其初态或终下溢则可能是正常现象，因为栈在使用时，其初态或终下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。态都是空栈，所以下溢常用来作为控制转移的条件。态

27、都是空栈，所以下溢常用来作为控制转移的条件。态都是空栈，所以下溢常用来作为控制转移的条件。1 栈的链式表示栈的链式表示 栈的栈的栈的栈的链式存储结构链式存储结构链式存储结构链式存储结构称为链栈，是运算受限的单链表。称为链栈，是运算受限的单链表。称为链栈，是运算受限的单链表。称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈其插入和删除操作只能在表头位置上进行。因此，链栈其插入和删除操作只能在表头位置上进行。因此，链栈其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针没有必要像单链表那样附加头结点，栈顶指针没有必要像单链表那样附加

28、头结点，栈顶指针没有必要像单链表那样附加头结点，栈顶指针toptop就是就是就是就是链表的头指针。图链表的头指针。图链表的头指针。图链表的头指针。图3-43-4是栈的链式存储表示形式是栈的链式存储表示形式是栈的链式存储表示形式是栈的链式存储表示形式。3.1.3 栈的链式存储表示栈的链式存储表示空栈空栈top 非空栈非空栈top a4 a3 a1 a2图图图图3-4 3-4 链链链链栈存储形式栈存储形式链栈的链栈的结点类型说明如下：结点类型说明如下：typedef struct Stack_Node ElemType data;struct Stack_Node *next;Stack_Node

29、;2 链栈基本操作的实现链栈基本操作的实现(1)栈的初始化栈的初始化Stack_Node Stack_Node *Init_Link_Stack(void)*Init_Link_Stack(void)Stack_Node Stack_Node *top;*top;top=(top=(Stack_Node Stack_Node *)malloc(sizeof()malloc(sizeof(Stack_Node Stack_Node););top-next=NULL;top-next=NULL;return(top);return(top);(2)压栈压栈(元素进栈元素进栈)Status push

30、(Status push(Stack_NodeStack_Node*top,ElemType *top,ElemType e)e)Stack_Node Stack_Node *p;*p;p=(p=(Stack_Node Stack_Node *)malloc(sizeof()malloc(sizeof(Stack_NodeStack_Node););if(!p)return ERROR;if(!p)return ERROR;/*/*申请新结点失败，返回错误标志申请新结点失败，返回错误标志申请新结点失败，返回错误标志申请新结点失败，返回错误标志*/p-data=e;p-data=e;p-next

31、=top-next ;p-next=top-next ;top-next=p;top-next=p;/*/*钩链钩链钩链钩链 */return OK;return OK;(3)弹栈弹栈(元素元素出栈出栈)Status pop(Status pop(Stack_Node Stack_Node *top,ElemType *top,ElemType*e)*e)/*/*/*/*将栈顶元素将栈顶元素将栈顶元素将栈顶元素出出出出栈栈栈栈 */Stack_Node *p;Stack_Node *p;ElemType e;ElemType e;if (top-next=NULL)if (top-next=N

32、ULL)return ERROR;return ERROR;/*/*栈空，返回错误标志栈空，返回错误标志栈空，返回错误标志栈空，返回错误标志 */p=top-next;e=p-data;p=top-next;e=p-data;/*/*/*/*取栈顶元取栈顶元取栈顶元取栈顶元素素素素 */top-next=p-next;top-next=p-next;/*/*/*/*修改栈顶指针修改栈顶指针修改栈顶指针修改栈顶指针 */free(p);free(p);return OK;return OK;3.2 栈的应用栈的应用 由于栈具有的由于栈具有的由于栈具有的由于栈具有的“后进先出后进先出后进先出后进先

33、出”的固有特性，因此，栈的固有特性，因此，栈的固有特性，因此，栈的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈成为程序设计中常用的工具和数据结构。以下是几个栈成为程序设计中常用的工具和数据结构。以下是几个栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。应用的例子。应用的例子。应用的例子。3.2.1 数制转换数制转换 十进制整数十进制整数十进制整数十进制整数NN向其它进制数向其它进制数向其它进制数向其它进制数d(d(二二二二、八八八八、十六十六十六十六)的转的转的转的转换是计算机实现计算的基本问题。换是计算机实现计算的基本问题。换是计算机实现计算的基本问题。换

34、是计算机实现计算的基本问题。转换法则转换法则转换法则转换法则：该转换法则对应于一个简单算法原理该转换法则对应于一个简单算法原理该转换法则对应于一个简单算法原理该转换法则对应于一个简单算法原理:n=(n div d)*d+n mod dn=(n div d)*d+n mod d 其中：其中：其中：其中：divdiv为整除运算为整除运算为整除运算为整除运算,modmod为求余运算为求余运算为求余运算为求余运算例如例如例如例如 (1348)1348)1010=(2504)=(2504)8 8，其运算过程如下：其运算过程如下：其运算过程如下：其运算过程如下：n n div 8 n mod 8n n d

35、iv 8 n mod 8 1348 168 4 1348 168 4 168 21 0 168 21 0 21 2 5 21 2 5 2 0 2 2 0 2 采用静态顺序栈方式实现采用静态顺序栈方式实现 void conversion(int n,int d)/*将将十进制整数十进制整数N转换为转换为d(2或或8)进制数进制数*/SqStack S;int k,*e;S=Init_Stack();while (n0)k=n%d;push(S,k);n=n/d;/*求出所有的余求出所有的余数，数，进栈进栈 */while (S.top!=0)/*栈不空时出栈，输出栈不空时出栈，输出 */pop(

36、S,e);printf(“%1d”,*e);3.2.2 括号匹配问题括号匹配问题 在文字处理软件或编译程序设计时，常常需要检在文字处理软件或编译程序设计时，常常需要检在文字处理软件或编译程序设计时，常常需要检在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配查一个字符串或一个表达式中的括号是否相匹配查一个字符串或一个表达式中的括号是否相匹配查一个字符串或一个表达式中的括号是否相匹配?匹配思想匹配思想：从左至右扫描一个字符串从左至右扫描一个字符串从左至右扫描一个字符串从左至右扫描一个字符串(或表达式或表达式或表达式或表达式)，则，则，则，则每个右括号将与最近遇到

37、的那个左括号相匹配每个右括号将与最近遇到的那个左括号相匹配每个右括号将与最近遇到的那个左括号相匹配每个右括号将与最近遇到的那个左括号相匹配。则可以。则可以。则可以。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。在从左至右扫描过程中把所遇到的左括号存放到堆栈中。在从左至右扫描过程中把所遇到的左括号存放到堆栈中。在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号每当遇到一个右括号时，就将它与栈顶的左括号每当遇到一个右括号时，就将它与栈顶的左括号每当遇到一个右括号时，就将它与栈顶的左括号(如果如果如果如果存在存在存在存在)相匹配，同时从栈顶删除该左

38、括号。相匹配，同时从栈顶删除该左括号。相匹配，同时从栈顶删除该左括号。相匹配，同时从栈顶删除该左括号。算法思想算法思想：设置一个栈，当读到左括号时，左括号进设置一个栈，当读到左括号时，左括号进设置一个栈，当读到左括号时，左括号进设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到栈。当读到右括号时，则从栈中弹出一个元素，与读到栈。当读到右括号时，则从栈中弹出一个元素，与读到栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配的左括号进行匹配，若匹配成功，继续读入；否则匹配的左括号进行匹配，若匹配成功，继续读入；否则匹配

39、的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回失败，返回失败，返回失败，返回FLASEFLASE。算法描述算法描述#define TRUE 0#define TRUE 0#define FLASE -1#define FLASE -1SqStack S;SqStack S;S=Init_Stack();S=Init_Stack();/*/*堆栈初始化堆栈初始化堆栈初始化堆栈初始化*/int Match_Brackets()int Match_Brackets()char ch,x;char ch,x;scanf(scanf(“%c%c”,&ch);,&ch);while(asc(c

40、h)!=13)while(asc(ch)!=13)if (ch=if (ch=()|(ch=)|(ch=)push(S)push(S,ch);,ch);else if (ch=else if (ch=)x=pop(S);x=pop(S);if(x!=if(x!=)printf(printf(“括号不匹配括号不匹配括号不匹配括号不匹配”););return FLASE ;return FLASE ;else if (ch=else if (ch=)x=pop(S);x=pop(S);if(x!=if(x!=()printf(printf(“(括号不匹配括号不匹配括号不匹配括号不匹配”););re

41、turn FLASE ;return FLASE ;if (S.top!=0)if (S.top!=0)printf(printf(“括号数量不匹配！括号数量不匹配！括号数量不匹配！括号数量不匹配！”););return FLASE ;return FLASE ;else return TRUE ;else return TRUE ;3.2.2 栈与递归调用的实现栈与递归调用的实现 栈的另一个重要应用是在程序设计语言中实现递归栈的另一个重要应用是在程序设计语言中实现递归栈的另一个重要应用是在程序设计语言中实现递归栈的另一个重要应用是在程序设计语言中实现递归调用。调用。调用。调用。递归调用递归调

42、用：一个函数一个函数一个函数一个函数(或过程或过程或过程或过程)直接或间接地调用直接或间接地调用直接或间接地调用直接或间接地调用自己本身，简称自己本身，简称自己本身，简称自己本身，简称递归递归递归递归(RecursiveRecursive)。递归递归递归递归是程序设计中的一个强有力的工具。因为递归是程序设计中的一个强有力的工具。因为递归是程序设计中的一个强有力的工具。因为递归是程序设计中的一个强有力的工具。因为递归函数结构清晰，程序易读，正确性很容易得到证明。函数结构清晰，程序易读，正确性很容易得到证明。函数结构清晰，程序易读，正确性很容易得到证明。函数结构清晰，程序易读，正确性很容易得到证明

43、。为了使递归调用不至于无终止地进行下去，实际上为了使递归调用不至于无终止地进行下去，实际上为了使递归调用不至于无终止地进行下去，实际上为了使递归调用不至于无终止地进行下去，实际上有效的递归调用函数有效的递归调用函数有效的递归调用函数有效的递归调用函数(或过程或过程或过程或过程)应包括两部分：应包括两部分：应包括两部分：应包括两部分：递推规则递推规则递推规则递推规则(方法方法方法方法)，终止条件终止条件终止条件终止条件。例如：求例如：求n!Fact(n)=1 当当n=0时时 终止条件终止条件n*fact(n-1)当当n0时时 递推规则递推规则 为保证递归调用正确执行，系统设立一个为保证递归调用正

44、确执行，系统设立一个“递归工递归工作栈作栈”，作为整个递归调用过程期间使用的数据存储区。，作为整个递归调用过程期间使用的数据存储区。每一层递归包含的信息如：每一层递归包含的信息如：参数参数、局部变量局部变量、上一上一层的返回地址构成层的返回地址构成一个一个“工作记录工作记录”。每进入一层递归，。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。就从栈顶弹出一个工作记录。从被调函数返回调用函数的一般步骤：从被调函数返回调用函数的一般步骤：(1)若栈为空，则执行正常返回。若栈为空，则执行正常返回。从栈顶弹出一个

45、工作记录。从栈顶弹出一个工作记录。将将“工作记录工作记录”中的参数值、局部变量值赋给相中的参数值、局部变量值赋给相应的变量；读取返回地址。应的变量；读取返回地址。将函数值赋给相应的变量。将函数值赋给相应的变量。(5)转移到返回地址。转移到返回地址。1 队列的基本概念队列的基本概念 队列队列队列队列(QueueQueue)：也是运算受限的线性表。是一种：也是运算受限的线性表。是一种：也是运算受限的线性表。是一种：也是运算受限的线性表。是一种先进先出先进先出先进先出先进先出(F First irst I In n F First irst OOut ut，简称，简称，简称，简称FIFOFIFO)的

46、线性的线性的线性的线性表。只允许在表的一端进行插入，而在另一端进行删除。表。只允许在表的一端进行插入，而在另一端进行删除。表。只允许在表的一端进行插入，而在另一端进行删除。表。只允许在表的一端进行插入，而在另一端进行删除。队首队首队首队首(frontfront)：允许进行删除的一端称为队首。：允许进行删除的一端称为队首。：允许进行删除的一端称为队首。：允许进行删除的一端称为队首。队尾队尾队尾队尾(rearrear)：允许进行插入的一端称为队尾。：允许进行插入的一端称为队尾。：允许进行插入的一端称为队尾。：允许进行插入的一端称为队尾。例如：排队购物。操作系统中的作业排队。先进入例如：排队购物。操

47、作系统中的作业排队。先进入例如：排队购物。操作系统中的作业排队。先进入例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。队列的成员总是先离开队列。队列的成员总是先离开队列。队列的成员总是先离开队列。3.3 队队 列列3.3.1 队列及其基本概念队列及其基本概念 队列中没有元素时称为空队列。在空队列中依次队列中没有元素时称为空队列。在空队列中依次队列中没有元素时称为空队列。在空队列中依次队列中没有元素时称为空队列。在空队列中依次加入元素加入元素加入元素加入元素a a1 1,a,a2 2,a,an n之后，之后，之后，之后，a a1 1是队首元素，是队首元素，是队首元素，是队首

48、元素，a an n是队是队是队是队尾元素。显然退出队列的次序也只能是尾元素。显然退出队列的次序也只能是尾元素。显然退出队列的次序也只能是尾元素。显然退出队列的次序也只能是a a1 1,a,a2 2,a,an n ，即队列的修改是依，即队列的修改是依，即队列的修改是依，即队列的修改是依先进先出先进先出先进先出先进先出的原则进行的，如图的原则进行的，如图的原则进行的，如图的原则进行的，如图3-53-5所示。所示。所示。所示。a1,a2,an出队出队入队入队队尾队尾队首队首图图3-5 队列示意图队列示意图2 队列的抽象数据类型定义队列的抽象数据类型定义ADT Queue数据对象：数据对象：D=ai|

49、aiElemSet,i=1,2,n,n=0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 约定约定a1端为队首，端为队首，an端为队尾。端为队尾。基本操作：基本操作：Create()：创建一个空队列：创建一个空队列；EmptyQue()：若队列为空：若队列为空，则返回则返回true，否则返否则返回回flase；InsertQue(x)：向队尾插入元素：向队尾插入元素x；DeleteQue(x)：删除队首元素：删除队首元素x；ADT Queue3.3.2 队列的顺序表示和实现队列的顺序表示和实现 利用利用一组连续的存储单元一组连续的存储单元(一维数组一维数组)依次存放从队依次存放从

50、队首到队尾的各个元素，称为首到队尾的各个元素，称为顺序队列顺序队列。对于队列，和顺序栈相类似，也有动态和静态之分。对于队列，和顺序栈相类似，也有动态和静态之分。本部分介绍的是本部分介绍的是静态顺序队列静态顺序队列，其类型定义如下：，其类型定义如下：#define MAX_QUEUE_SIZE 100typedef struct queue ElemType Queue_arrayMAX_QUEUE_SIZE;int front;int rear;SqQueue;3.3.2.1 队列的顺序队列的顺序存储结构存储结构 设立一个设立一个队首指针队首指针front，一个，一个队尾指针队尾指针rear，