数据结构 第三章栈队列

《数据结构 第三章栈队列》由会员分享，可在线阅读，更多相关《数据结构 第三章栈队列（95页珍藏版）》请在文档大全上搜索。

1、第三章第三章 栈和队列栈和队列 本章介绍在程序设计中常用的两种数据结构本章介绍在程序设计中常用的两种数据结构 栈和队列栈和队列 第三章第三章 栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 栈的应用举例栈的应用举例 3.3 3.3 栈与递归栈与递归 3.4 3.4 队列队列 3.1 3.1 栈栈3.13.1 .1 .1 栈的概念栈的概念3.13.1 .2 .2 栈的顺序存储和实现栈的顺序存储和实现3.13.1 .3 .3 栈的链式存储和实现栈的链式存储和实现3.1 栈栈栈是限定仅能在表尾一端进行插入、删除操作的线性表栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1, a2, .

2、, ai -1, ai , ai+1, , an ）插入插入删除删除3.1.1栈的定义和抽象数据类型栈的定义和抽象数据类型一一 什么是栈什么是栈说明：设（说明：设（a1, a2, a3, , an ） 是一个栈是一个栈 1）表尾称为栈顶，表头称为栈底）表尾称为栈顶，表头称为栈底 ，即，即a1为栈底元素，为栈底元素，an为为 栈顶元素；栈顶元素； 2）在表尾插入元素的）在表尾插入元素的 操作称进栈操作，在表尾删除元素操作称进栈操作，在表尾删除元素 的操作称为出栈操作的操作称为出栈操作; 3）元素按）元素按a1, a2, a3, , an 的次序进栈的次序进栈, 第一个进栈的元素第一个进栈的元素

3、一定在栈底，最后一个进栈的元素一定在栈顶一定在栈底，最后一个进栈的元素一定在栈顶, 第一个第一个 出栈的元素为栈顶元素；出栈的元素为栈顶元素； 4）栈的元素具有后进先出的特点）栈的元素具有后进先出的特点,所以栈又称为后进先出所以栈又称为后进先出 表（表（LIFO表）；表）； 5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称）由于进栈、出栈操作总是在栈顶一端进行，通常设置称 为栈顶指针的变量为栈顶指针的变量(Top)指示栈顶的位置。指示栈顶的位置。栈栈底底栈栈顶顶（a1, a2, . , ai -1, ai , ai+1, , an ）进栈进栈出栈出栈栈的示意图栈的示意图出栈出栈进栈进栈栈的

4、特点栈的特点后进先出后进先出第一个进栈的元素在栈底，第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素最后一个出栈的元素为栈底元素栈顶栈顶栈底栈底a an na a2 2a a1 1二二 栈的基本操作栈的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：构造一个空栈功能：构造一个空栈S； 2） 销毁栈操作销毁栈操作DestroyStack(&S) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈; 3） 置空栈操作置空栈操作ClearStack(&S) 功能：将栈功

5、能：将栈S置为空栈置为空栈; 4） 取栈顶元素操作取栈顶元素操作GetTop(S, &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e 返回返回; 5）进栈操作）进栈操作Push(&S, e) 功能：元素功能：元素e进栈进栈; 6）退栈操作）退栈操作Pop(&S, &e) 功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e返回返回; 7）判空操作）判空操作StackEmpty(S) 功能：若栈功能：若栈S为空，则返回为空，则返回True，否则返回否则返回False;toptopbasebasebasebasetoptopbasebasetoptopbasebasetoptopA AA AB

6、 BC CD DE EA AB B 栈操作图示栈操作图示空栈空栈 A A进栈进栈 B C D E B C D E 进栈进栈E D C E D C 出栈出栈 栈的顺序存储结构也是利用一组连续的内存单元栈的顺序存储结构也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示置由一个称为栈顶指针的变量指示 。 栈的顺序存贮结构也称为顺序栈。栈的顺序存贮结构也称为顺序栈。3.1.2 栈的顺序存储和实现栈的顺序存储和实现 与线性表类似，栈也可以用顺序结构或链式结构存储。与线性表类似，栈也可以用顺序结构或链式结构存储。

7、一、栈的顺序存储结构一、栈的顺序存储结构 1 顺序存储结构顺序存储结构SqStack：结构类型名；结构类型名；SqStack类型的变量是结构变量，它的三个域类型的变量是结构变量，它的三个域 分别是：分别是： base：称为栈底指针，指向栈底位置；称为栈底指针，指向栈底位置； top： 称为栈顶指针，约定栈顶指针指向栈顶元素的下（后面）一称为栈顶指针，约定栈顶指针指向栈顶元素的下（后面）一 个位置；个位置； Stacksize：用于存放当前分配（存放用于存放当前分配（存放栈栈元素）的存储空间的大小；元素）的存储空间的大小；# #define STACK_INIT_SIZE 100 / defin

8、e STACK_INIT_SIZE 100 / 栈存储空间的初始分配量栈存储空间的初始分配量# #define STACKINCREMENT 10 / define STACKINCREMENT 10 / 栈存储空间的分配增量栈存储空间的分配增量typedeftypedef structstruct SElemTypeSElemType * *base; /base; /栈空间基址栈空间基址SElemTypeSElemType * *top /top /栈顶指针栈顶指针intint stacksizestacksize; /; /当前分配的栈空间大小当前分配的栈空间大小 / /（以（以size

9、of(SElemTypesizeof(SElemType) )为单位）为单位） SqStackSqStack; ;2 顺序栈的类型定义顺序栈的类型定义3 顺序栈的图示顺序栈的图示a 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 0当栈用顺序结构存储时，当栈用顺序结构存储时，栈的基本操作如建空栈、栈的基本操作如建空栈、进栈、出栈等操作如何实现？进栈、出栈等操作如何实现？二二 顺

10、序栈基本操作的算法顺序栈基本操作的算法1）初始化操作）初始化操作InitStack_Sq(SqStack &S) 参数：参数：S是存放栈的结构变量；是存放栈的结构变量； 功能：建一个空栈功能：建一个空栈S； 算法算法Status InitStack_Sq(SqStack &S) /构造一个空栈构造一个空栈S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /为顺序栈动态分配存储空间为顺序栈动态分配存储空间 if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.top=S.b

11、ase; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作图示初始化操作图示 初始化操作图示初始化操作图示算法算法Status DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若栈未建立（尚未分配栈空间）若栈未建立（尚未分配栈空间） free (S.base

12、); / 回收栈空间回收栈空间 S.base = S.top = null; S.stacksize = 0; return OK;/ DetroyStack_Sq2） 销毁栈操作销毁栈操作 DestroyStack_Sq(SqStackSqStack &S &S ) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈;S.top =nullS.top =nullS.stacksizeS.stacksizeS.base =nullS.base =null 0 0 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.top

13、S.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE 销毁前 销毁后销毁栈操作图示3）置空栈操作置空栈操作ClearStack_Sq(SqStack &S) 功能：将栈功能：将栈S置为空栈置为空栈 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若栈未建立（尚未分配栈空间）若栈未建立（尚未分配栈空间） S.top = S.base ; return OK; / ClearStack_Sq n nn-1n-1i-1i-1i

14、-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_SIZEa an na ai ia ai-1i-1a a2 2a a1 1置空栈操作图示置空栈操作图示S.base=S.topS.base=S.top表明栈为空

15、表明栈为空置空前置空前置空后置空后 算法算法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） 取栈顶元素操作取栈顶元素操作GetTop_Sq(SqStack S, SElemType &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e返回返回; n nn-1n-1i-1i-1i-

16、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 取栈顶元素操作图示取栈顶元素操作图示n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 15）进栈操作进栈操作Push(SqS

17、tackSqStack &S, &S, SElemTypeSElemType e e) 功能：元素功能：元素e 进栈进栈; 进栈操作主要步骤：进栈操作主要步骤： 1）S是否已满，是否已满， 若若栈栈满，重新分配存储空间；满，重新分配存储空间； 2）将元素将元素e 写入栈顶；写入栈顶； 3）修改栈顶指针，使栈顶指针指向栈顶元素）修改栈顶指针，使栈顶指针指向栈顶元素 的下（后面）一个位置；的下（后面）一个位置； 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.base

18、S.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 1a an na ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE e 进栈前进栈前 e 进栈后进栈后 进栈操作图示进栈操作图示进栈操作算法：进栈操作算法：Status Push(SqStack &S, SElemType e) /将元素将元素e插入栈成为新的栈顶元素插入栈成为新的栈顶元素 if (S.top-S.base=S.s

19、tacksize) /栈满，追加存储空间栈满，追加存储空间 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;/Push6）出）出栈操作栈操作Pop(SqStack &S,

20、SElemType &e )功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e 返回返回;出栈操作基本步骤出栈操作基本步骤算法算法Status Pop(SqStack &S, SElemType &e) /若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e 返回其值，并返回返回其值，并返回OK； /否则返回否则返回ERROR if (S.top= = S.base) return ERROR; /栈空，返回栈空，返回ERROR e = * -S.top; /删除栈顶元素，用删除栈顶元素，用e 返回其值，并修改栈顶指针返回其值，并修改栈顶指针 return OK;/PopS.top

21、S.topS.stacksizeS.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-1n-1a ai ia ai-1i-1a a1 1e ea an n 栈的链式存

22、储结构，也称链栈，栈的链式存储结构，也称链栈，如图所示：如图所示：Data nextData nextS S栈顶栈顶栈底栈底a an-1n-1a a1 1a an n3.1.3 3.1.3 栈的链式存储和实现栈的链式存储和实现说明说明 1）链式栈可用线性链表表示；）链式栈可用线性链表表示； 2）链式栈的栈顶指针就是链表的头指针；）链式栈的栈顶指针就是链表的头指针； 3）进栈操作就是在该线性链表第一个元素）进栈操作就是在该线性链表第一个元素 结点之前插入一个新结点，出栈操作就是结点之前插入一个新结点，出栈操作就是 删除链表的第一个元素结点。删除链表的第一个元素结点。 在前面学习了线性链表的插入删

23、除操作在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈算法，不难写出链式栈初始化、进栈、出栈等操作的算法。大家不妨试一试。等操作的算法。大家不妨试一试。链式栈图示链式栈图示Data nextData nextS S栈顶栈顶栈底栈底a an-1n-1a a1 1a an n 小小 结结 1 栈是限定仅能在表尾一端进行插入、删除栈是限定仅能在表尾一端进行插入、删除 操作的线性表；操作的线性表； 2 栈的元素具有后进先出的特点；栈的元素具有后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的变栈顶元素的位置由一个称为栈顶指针的变 指示，进栈、出栈操作要修改栈顶指针；指示，

24、进栈、出栈操作要修改栈顶指针； 3.2 3.2 栈的应用举例栈的应用举例 栈结构具有后进先出的特征，使栈成为程序设计中的有栈结构具有后进先出的特征，使栈成为程序设计中的有用工具，本节介绍栈的几个简单应用的实例。用工具，本节介绍栈的几个简单应用的实例。例例1 1 数制转换数制转换 1 1）问题）问题 在计算机基础课中，我们学习过各种数制的转换问在计算机基础课中，我们学习过各种数制的转换问题。十题。十八进制转换、十八进制转换、十二进制转换等。下面我们二进制转换等。下面我们设计一程序实现十进制数到八进制数的自动转换。即该程设计一程序实现十进制数到八进制数的自动转换。即该程序功能为：对于输入的任意一个

25、非负十进制数，显示输出序功能为：对于输入的任意一个非负十进制数，显示输出与其等值的八进制数。与其等值的八进制数。 2 2） 求解方法求解方法 这个问题的求解方法有很多，我们这里介绍的方法基于这个问题的求解方法有很多，我们这里介绍的方法基于下列原理：下列原理： N = (Ndiv8)10 8+N mod 8 N：十进制数，十进制数，div：整除运算，整除运算，mod：求余运算；求余运算； (1348)10 = 2 83+5 82+0 8+4 = (2504)8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 由上述求解过程可以看出，在计算过程

26、中是从低位到高位由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是从顺序产生八进制数的各个数位，而显示时按照我们的习惯是从高位在前，低位在后，即按从高位到低位的顺序输出高位在前，低位在后，即按从高位到低位的顺序输出, , 即后计即后计算出的（高）位数先输出，具有后进先出的特点，因此可将计算出的（高）位数先输出，具有后进先出的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈序列打印输出的就是算过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。对应的八进制数。3 3）算法算法void conversion( ) /对于输入的

27、任意一个非负十进制整数，打印输出与其等值的八进制数对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈建空栈 scanf(“%d”, N); /输入一个输入一个非负十进制整数非负十进制整数 while(N) / N不等于零不等于零循环循环 Push(S, N % 8); / N/8第一个余数进栈第一个余数进栈 N=N/8; /整除运算整除运算 while(! StackEmpty) /输出存放在栈中的八制数位。输出存放在栈中的八制数位。 Pop(S, e); Printf(“%d”, e); /conversion 算法算法3.1例例2 括号匹配的

28、检验括号匹配的检验假设在表达式中假设在表达式中（）或（）或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或）或 （）（）)均为不正确的格式。均为不正确的格式。算法的设计思想：算法的设计思想：1 1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；2 2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空 若栈空，则表明该若栈空，则表明该“右括弧右括弧”多余，多余， 否则和栈顶元素比较，否则和栈顶元素比较， 若相匹配，则若相匹配，则“左括弧出栈左括弧出栈” ” ， 否则表明不匹配。否则表明不匹配。3 3）表达式检验结束时，）表达式检验结束时， 若栈空，则表明表达式中匹配正确

29、，若栈空，则表明表达式中匹配正确， 否则表明否则表明“左括弧左括弧”有余。有余。出口例例3 3 迷宫求解迷宫求解入口入口求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：若当前位置若当前位置“可通可通”，则纳入路径，继续前进，则纳入路径，继续前进; ;若当前位置若当前位置“不可通不可通”，则后退，换方向继续探索，则后退，换方向继续探索;若四周若四周“均无通路均无通路”，则将当前位置从路径中删除出，则将当前位置从路径中删除出去。去。设定初值为入口位置设定初值为入口位置, ,以正东为起始方向以正东为起始方向； dodo if( if(当前位置可通当前位置可通) ) 则将当前位置插入栈顶；则将

30、当前位置插入栈顶； if(if(该位置是出口位置该位置是出口位置) ) exit(0)exit(0)； else else 按顺时针下一方向为新的当前位置；按顺时针下一方向为新的当前位置； elseelse* * while(while(栈不空）；栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。else * if if( (栈不空栈不空&栈顶位置尚有其他方向未被探索栈顶位置尚有其他方向未被探索) ) 新的当前位置为新的当前位置为: : 沿顺时针方向旋转沿顺时针方向旋转 找到的栈顶位置的下一相邻块；找到

31、的栈顶位置的下一相邻块； if if( (栈不空栈不空&栈顶位置的四周均不可通栈顶位置的四周均不可通) ) 删去栈顶位置；删去栈顶位置；/ / 从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空； /else例例4 表达式求值表达式求值1）问题的提出）问题的提出 假若我们想在计算机上设计一个小计算器（程序），其假若我们想在计算机上设计一个小计算器（程序），其功能为：从键盘上输入一个算术表达式（由运算符操作数构成功能为：从键盘上输入一个算术表达式（由运算符操作数

32、构成的字符串）的字符串）,在屏幕上显示输出表达式的求值结果。在屏幕上显示输出表达式的求值结果。 显然这个小计算器程序应该对你键入的表达式进行求值。显然这个小计算器程序应该对你键入的表达式进行求值。在该程序中如何对键入的表达式求值呢？在该程序中如何对键入的表达式求值呢？ 又如，高级语言中都有表达式，例赋值语句：变量又如，高级语言中都有表达式，例赋值语句：变量=表达表达式；该语句的执行过程为：先求出表达式的值，式；该语句的执行过程为：先求出表达式的值， 然后将其值然后将其值赋给赋值号左边的变量。这个表达式的值是如何求出的？赋给赋值号左边的变量。这个表达式的值是如何求出的？ 下面我们就来设计一个表达

33、式求值算法。下面我们就来设计一个表达式求值算法。2 2）表达式的构成）表达式的构成 操作数操作数+ +运算符运算符+ +界限符（如括号）界限符（如括号）3 3）表达式的求值：）表达式的求值： 例例 5+6 5+6 (1+2)- 4(1+2)- 4 按照四则运算法则，上述表达式的计算过程为：按照四则运算法则，上述表达式的计算过程为： 5+ 6 5+ 6 (1+2)- 4=5+6 (1+2)- 4=5+6 3-4 = 5+18-4= 23-4=193-4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为：表达式中运算符的运算顺序为： + + ， ， + +， - - ， 如何确定运算

34、符的运算顺序？如何确定运算符的运算顺序？1 12 23 34 41 12 23 34 44） 算符优先关系表算符优先关系表 表达式中任何相邻运算符表达式中任何相邻运算符 1、 2的优先关系有：的优先关系有： 1 2： 1的优先级高于的优先级高于 2 由四则运算法则，可得到如下的算符优先关系表：由四则运算法则，可得到如下的算符优先关系表：+ 21 - -* */ /( () )# #+ - + - * * / ( ) # / ( ) # = = = 算符间的优先关系表算符间的优先关系表注：注： 1 2是相邻算符，是相邻算符， 1在左，在左， 2在右在右5 5 ) ) 算符优先算法算符优先算法 我

35、们再来分析一下表达式我们再来分析一下表达式5+45+4 (1+2)-6 (1+2)-6 计算过程：计算过程： 从左向右扫描表达式：从左向右扫描表达式： 遇操作数遇操作数保存；保存； 遇运算符号遇运算符号 j与前面的刚扫描过的运算符与前面的刚扫描过的运算符 i比较比较 若若 i j 则保存则保存 j，（，（ 因此已保存的运算符的优先关系为因此已保存的运算符的优先关系为 1 2 3 j 则说明则说明 i是已扫描的运算符中优先级最高者，可进行运算；是已扫描的运算符中优先级最高者，可进行运算； 若若 i = j 则则 i为（，为（， j 为为 ），说明括号内的式子已计算完，需要消去括号；），说明括号内

36、的式子已计算完，需要消去括号； 5+4 (1+2)- 6我们可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。我们可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。后面也许有优先级后面也许有优先级更大的算符更大的算符表达式求值示意图：表达式求值示意图：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR栈栈# #OPNDOPND栈栈toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3

37、toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5读入表达式过程：读入表达式过程：+ +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+18=235+18=2323-4=1923-4=19 在算符优先算法中，建立了两个工作栈。一个是在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符栈，用以保存运算符一个是一个是OPND

38、栈，用以保存操作数或运算结果。栈，用以保存操作数或运算结果。 operandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设算术表达式求值的算符优先算法。设OPTR和和OPND分别为运算符栈和分别为运算符栈和 /运算数栈，运算数栈，OP为运算符集合。为运算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是运算符则

39、进栈不是运算符则进栈 else / In(c, OP)判断判断c是否是否 /是运算符的函数是运算符的函数 续续 switch (Precede(GetTop(OPTR), c) case : /新输入的算符新输入的算符c优先级低，即栈顶算符优先权高，优先级低，即栈顶算符优先权高， /出栈并将运算结果入栈出栈并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND);/EvaluateEx

40、pression第三章第三章 习题一习题一习题五习题五1 P21-23 1 P21-23 3.1, 3.2, 3.7 3.1, 3.2, 3.72 2 编编写链式栈进栈、出栈操作的算法，并画出链式栈进栈操作写链式栈进栈、出栈操作的算法，并画出链式栈进栈操作前、进栈操作后的图示前、进栈操作后的图示 习题取自习题取自数据结构题集数据结构题集 C C语言版语言版 严尉敏等编严尉敏等编 清华大学出版社清华大学出版社3.3 栈与递归栈与递归 由上看到：应用中如果处理数据处理过程具有后进先出的特性，可由上看到：应用中如果处理数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下面我们将看到可以用栈

41、来实现递归。利用栈来实现数据处理过程。下面我们将看到可以用栈来实现递归。1什么是递归什么是递归 递归是一个很有用的工具，在数学和程序设计等许多领域中都用到递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。了递归。递归定义：简单地说，一个用自己定义自己的概念递归定义：简单地说，一个用自己定义自己的概念,称为递归定义。称为递归定义。例例 n!= 1 2 3 4 (n-1) n n!递归定义递归定义 n!= 1 当当 n=1时时 n!= n (n-1)! 当当n 1时时用用(n-1)!(n-1)!定义定义n!n!2 递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称递归函

42、数：一个直接调用自己或通过一系列调用间接调用自己的函数称 为递归函数。为递归函数。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己直接调用自己B间接调用自己间接调用自己递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。2递归算法的编写递归算法的编写1）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法 问题的递归描述（定义）问题的递归描述（定义） 递归定义包括两项递归定义包括两项 基本

43、项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小的问题；递归项：将问题分解为与原问题性质相同，但规模较小的问题； 例例 n!的递归定义的递归定义 基本项：基本项： n!=1 当当 n=1 递归项：递归项： n!=n (n-1)! 当当 n 1用用(n-1)!(n-1)!定义定义n!n!例例1 编写求解编写求解 阶乘阶乘n! 的递归算法的递归算法首先给出阶乘首先给出阶乘n! 的递归定义的递归定义 n!的递归定义的递归定义 基本项：基本项： n!=1 当当 n=1 递归项：递归项： n!=n (n-1)! 当当

44、n 1 有了问题的递归定义，很容易写出对应的递归算法：有了问题的递归定义，很容易写出对应的递归算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的阶乘的阶乘 if（n=1） return（1）；）； else return（n*fact (n-1)）；）；/fact 例例2. 编写求解编写求解Hanci塔问题的递归算法塔问题的递归算法 有三个各为有三个各为X，Y，Z的塔座，在的塔座，在X项有项有n个大小不同，依个大小不同，依小到大编号为小到大编号为1，2n的圆盘。的圆盘。 现要求将现要求将X上的上的n个圆盘移个圆盘移至至Z上，并仍以同样顺序叠放，上，并仍以同样

45、顺序叠放， 圆盘移动时必须遵守下列原圆盘移动时必须遵守下列原则：则：1）每次移动一个盘子；）每次移动一个盘子；2）圆盘可以放在）圆盘可以放在X，Y，Z中的中的任一塔座上；任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；）任何时刻都不能将较大的圆盘压放在较小圆盘之上；例例 n=3时时圆盘移动的过程如下图所示圆盘移动的过程如下图所示：a ab bc c3 32 21 1 1 11 12 21 13 31 12 21 1Y YX XZ Z首先给出首先给出求解求解Hanci塔问题塔问题 的递归描述（定义）的递归描述（定义） 基本项：基本项： n=1时，将时，将n号圆盘从号圆盘从X移至移至

46、Z； 递归项：递归项： n1时，时， 将将X上上1n-1号圆盘移至号圆盘移至Y； 将将X上的上的n号圆盘从号圆盘从X移至移至Z; 将将Y上上1n-1号圆盘从号圆盘从Y移至移至Z; 将规模为将规模为n n的问题的问题的求解归结为规模的求解归结为规模为为n-1n-1的问题的求的问题的求解解有了问题的递归定义，很容易写出对应的递归算法：有了问题的递归定义，很容易写出对应的递归算法：void hanoi (int n, char x, char y, char z) /将塔座将塔座x上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1至至n的的n个圆盘按规则搬到个圆盘按规则搬到 /塔座塔

47、座z上，上，y可用作辅助塔座。可用作辅助塔座。 /搬动操作搬动操作move(x, n, z),将编号为将编号为 n的圆盘从的圆盘从x移到移到z /printf(“%d Move disk %di from %c to %cn”, +c, n, x, z); if (n= =1) move(x,1,z); /将编号为将编号为1的圆盘从的圆盘从x移动移动z else hanoi(n-1, x, z, y); /将将x上编号为上编号为1至至n-1的圆盘移到的圆盘移到y, z作辅助塔作辅助塔 move(x, n, z); /将编号为将编号为 n的圆盘从的圆盘从x移到移到z hanoi(n-1, y,

48、x, z)； /将将y上编号为上编号为1至至n-1的圆盘移到的圆盘移到z，x作辅助塔作辅助塔 算法算法3.5 Hanci塔问题塔问题 3 递归函数的实现递归函数的实现 在递归函数的执行中，在递归函数的执行中， 需多次自己调用自己，递归函数是如何执行的？需多次自己调用自己，递归函数是如何执行的？先看一般函数的调用机制如何实现的。先看一般函数的调用机制如何实现的。 A( )A( )B( );B( ); C( )C( ) B( )B( )C( );C( ); 调用调用调用调用返回返回返回返回函数调用顺序函数调用顺序 A B CA B C函数返回顺序函数返回顺序 C B AC B A后调用的函数先返回

49、后调用的函数先返回 函数调用机制可通过栈来实现函数调用机制可通过栈来实现我们看一下我们看一下n=3 n=3 阶乘函数阶乘函数fact(n)fact(n)的执行过程的执行过程Main( ) Main( ) intint n=3,y; n=3,y;L y= fact(n);L y= fact(n); 调调用用调用调用调调用用int fact (n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=3n=3int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-

50、1)）；）；/factn=2n=2int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=1n=1L 3L 3L1 1L1 1L1 2L1 2返返回回1 1返回返回2 2返返回回6 6返回地址返回地址 实参实参 注意递归调用中注意递归调用中 栈的变化栈的变化 3.4 3.4 队列队列3.43.4 .1 .1 队列队列的概念的概念3.43.4 .2 .2 循环队列循环队列 队列队列的顺序存储和实现的顺序存储和实现3.43.4 .3 .3 队列队列的链式存储和实现的链式存储和实现学习要点学习要点1 1

51、理解掌握队列的结构特征和操作特点；理解掌握队列的结构特征和操作特点；2 2 掌握队列的顺序存储结构和链式存储结构，及如何用掌握队列的顺序存储结构和链式存储结构，及如何用C C语言描述语言描述 它们的类型定义；它们的类型定义；3 3 掌握在两种存储结构下，队列的基本操作的算法；重点掌握掌握在两种存储结构下，队列的基本操作的算法；重点掌握 循环队列的入队、出队算法，循环队列队空、队满的判别条件；循环队列的入队、出队算法，循环队列队空、队满的判别条件；4 4 理解队列先进先出的特点及在程序设计中的应用；理解队列先进先出的特点及在程序设计中的应用；基本内容基本内容1 1 队列的概念，队列的基本操作；队

52、列的概念，队列的基本操作；2 2 队列的两类存储结构和它们的类型定义；队列的两类存储结构和它们的类型定义；3 3 在队列的存储结构下，队列的基本操作的算法；在队列的存储结构下，队列的基本操作的算法；4 4 队列在程序设计中的应用。队列在程序设计中的应用。3 34 4 队列队列3.4.1队列的定义和抽象数据类型队列的定义和抽象数据类型一一 什么是队列什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线队列是限定仅能在表头进行删除，表尾进行插入的线性表性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入删除删除说明：设（说明：设（a1,a2 , a3 , .

53、, an ）为一队列为一队列 1）表尾称作队尾，表头称为队头；）表尾称作队尾，表头称为队头； 2）a1为队头元素，为队头元素，an为队尾元素；为队尾元素； 3）在表尾插入元素操作，称为入队操作；在表头删除元素）在表尾插入元素操作，称为入队操作；在表头删除元素 的操作，称为出队操作；的操作，称为出队操作； 4）元素按）元素按a1,a2, a3, . an 顺序入队，第一个入队的元素为顺序入队，第一个入队的元素为a1 最后一个入队的元素是最后一个入队的元素是an 第一个出队的元素为第一个出队的元素为a1 ； 5）队列具有先进先出的特点，所以又称为先进先出表队列具有先进先出的特点，所以又称为先进先出

54、表 （FIFO表）表） a a1 1 a a2 2 a a3 3 a an n入队列入队列队队头头队队尾尾出队列出队列队列的示意图队列的示意图队列的特点队列的特点先进先出先进先出第一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素 队列类似于日常的排队，新来的人站在队尾，队头的队列类似于日常的排队，新来的人站在队尾，队头的人进行事务处理后离队。人进行事务处理后离队。 队列通常设置两个变量分别指示队头元素位置和队尾队列通常设置两个变量分别

55、指示队头元素位置和队尾元素的位置，这两个变量分别称为队头指针、队尾指针；元素的位置，这两个变量分别称为队头指针、队尾指针；二二 队列的基本操作队列的基本操作1）初始化操作）初始化操作InitQueue( &Q) 功能：构造一个空队列功能：构造一个空队列Q；2）销毁操作销毁操作DestroyQueue( &Q) 功能：销毁已存在队列功能：销毁已存在队列Q；3）置空操作置空操作ClearQueue(&Q) 功能：功能： 将队列将队列Q置为空队列置为空队列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若队列功能：若队列Q为空，则返回为空，则返回True，否则返回否则返回False；5）

56、取队头元素操作取队头元素操作GetHead(Q,&e) 功能：取队头元素，并用功能：取队头元素，并用e返回；返回；6）入队操作入队操作EnQueue( &Q, e ) 功能：将元素功能：将元素e插入插入Q的队尾；的队尾；7）出队操作）出队操作DeQueue( &Q, &e) 功能：若队列不空，则删除功能：若队列不空，则删除Q的队头元素，用的队头元素，用e返回其值，并返回返回其值，并返回OK，否则返回否则返回ERROR；3.4.2 循环队列循环队列队列的顺序存储和实现队列的顺序存储和实现一一 队列的顺序存贮结构队列的顺序存贮结构 1 队列的顺序存贮结构队列的顺序存贮结构 和顺序栈类似，在队列的顺

57、序存贮结构中除了和顺序栈类似，在队列的顺序存贮结构中除了用一组连续存储单元依次存储从队头到队尾的数据用一组连续存储单元依次存储从队头到队尾的数据元素外，还需附加两个变量，一个称为队头指针，元素外，还需附加两个变量，一个称为队头指针，指示队头元素的位置；一个称为队尾指针，指示队指示队头元素的位置；一个称为队尾指针，指示队尾元素的位置。尾元素的位置。Q.rearQ.rearQ.frontQ.frontJ1J1J2J2J3J3队列的顺序存贮结构图示队列的顺序存贮结构图示MAXSIZE：最大队列空间，可根据实际应用确定；最大队列空间，可根据实际应用确定； SqQueue：结构类型名；结构类型名； Sq

58、Queue 类型的变量是结构变量。它的三个域分别是：类型的变量是结构变量。它的三个域分别是： base：队列存储空间基址；队列存储空间基址； front：队头指针，若队列不空，指向队头元素；队头指针，若队列不空，指向队头元素； rear：队尾指针，若队列不空，指向队尾元素的下一位置；队尾指针，若队列不空，指向队尾元素的下一位置；# #define MAXSIZE 100 / define MAXSIZE 100 / 最大队列长度最大队列长度typedeftypedef structstruct QElemTypeQElemType * *base; /base; /初始化时动态分配初始化时动态

59、分配存储空间的基址存储空间的基址 intint front; / front; /队头指针，指向队头元素队头指针，指向队头元素 intint rear; / rear; /队尾指针，指向队尾元素的下一个位置队尾指针，指向队尾元素的下一个位置 SqQueueSqQueue; ;2顺序队列的类型定义顺序队列的类型定义Q.rearQ.rearQ.frontQ.frontJ1J1J2J2J3J3Q.rearQ.rearQ.frontQ.frontJ3J3（a)a)空队列空队列(b)J1,J2(b)J1,J2和和J3J3相继入队列相继入队列(c)J1(c)J1和和J2J2相相继出队继出队( (d)J4,

60、J5d)J4,J5和和J6J6相继入相继入队之后队之后, ,J3J3出队出队Q.rearQ.rearQ.frontQ.front0 01 12 23 34 45 5队头指针队尾指针和队列中元素之间的关系图示队头指针队尾指针和队列中元素之间的关系图示 设设Q为为SqQueue类型的变量，用于存储队列。设为队列类型的变量，用于存储队列。设为队列Q分配空间大小分配空间大小为为MAXSIZE=6，初始建队时，令初始建队时，令Q.front=Q.rear=0;Q.rearQ.rearQ.frontQ.frontJ6J6J5J5J4J43 . 循环队列循环队列 从图从图示示（d）中可看出，当中可看出，当J

61、6 入队后入队后, 队尾指针队尾指针Q.rear越界，不可能再插入新的队尾元素，但是另一方面，队列的越界，不可能再插入新的队尾元素，但是另一方面，队列的实际可用空间并未占满。一个巧妙的办法是，将顺序队列设实际可用空间并未占满。一个巧妙的办法是，将顺序队列设想为首尾相连的环状空间，如图，当想为首尾相连的环状空间，如图，当Q.rear 值超出队列空间值超出队列空间的最大位置时，令的最大位置时，令Q.rear= 0 (通过模运算），通过模运算）， 使队列空间使队列空间能能“循环循环”使用。这种循环使用空间的队列称为循环队列。使用。这种循环使用空间的队列称为循环队列。Q.rearQ.rearQ.fro

62、ntQ.front5 54 43 32 21 10 0 循环队列图示循环队列图示Q.rearQ.rearQ.frontQ.frontJ6J6J5J5J4J4Q.frontQ.frontJ6J6J4J4J5J54 43 35 52 20 01 14队空队满的判别队空队满的判别问题：如何判断循环队列队空、队满？问题：如何判断循环队列队空、队满？1）在（）在（a）状态下状态下,J4, J5, J6依次出队，队列状依次出队，队列状态如图（态如图（b），），这时有这时有Q.front=Q.rear;2）在（在（a ）状态下，状态下，J7, J8, J9依次入队，队列依次入队，队列状态如图（状态如图（c）

63、，），这时也有这时也有Q.front=Q.rear; 由此仅凭等式由此仅凭等式Q.front=Q.rear; 是否成立，是否成立，无法判断队列是空还是满。无法判断队列是空还是满。Q.frontQ.frontQ.rearQ.rear ( (a)a)( (b)b)队空队空( (c)c)队满队满Q.frontQ.frontQ.rearQ.rearJ6J6J4J4J5J54 43 35 52 20 01 1J6J6J4J4J5J54 43 35 52 20 01 1J6J6J4J4J5J54 43 35 52 20 01 1J9J8J7Q.frontQ.frontQ.rearQ.rear有两种方法：有

64、两种方法： 1）另设一个标志位以区分队空、队满。）另设一个标志位以区分队空、队满。 2）少用一个存储单元，即当队列达到图）少用一个存储单元，即当队列达到图 （d ）所示状态时，我们就认为队列已满，所示状态时，我们就认为队列已满，这时的条件是这时的条件是Q.front=Q.rear+1;如何判断循环队列如何判断循环队列队空、队满？队空、队满？Q.rearQ.rearQ.frontQ.front（d d）J6J6J4J4J5J54 43 35 52 20 01 1J8J75 5循环队列的类型定义循环队列的类型定义# #define MAXSIZE 100 / define MAXSIZE 100

65、/ 最大队列长度最大队列长度typedeftypedef structstruct QElemTypeQElemType * *base; /base; /初始化时动态分配初始化时动态分配存储空间的基址存储空间的基址 intint front; / front; /队头指针，指向队头元素队头指针，指向队头元素 intint rear; / rear; /队尾指针，指向队尾元素的下一个位置队尾指针，指向队尾元素的下一个位置 SqQueueSqQueue; ;MAXSIZE：最大队列空间，可根据实际应用确定；最大队列空间，可根据实际应用确定；SqQueue：结构类型名；结构类型名； SqQueue

66、 类型的变量是结构变量。它的三个域分别是：类型的变量是结构变量。它的三个域分别是： base：队列存储空间基址；队列存储空间基址； front：队头指针，若队列不空，指向队头元素；当队头指针，若队列不空，指向队头元素；当front=MAXSIZE时，时， 置置front=0 rear：队尾指针，若队列不空，指向队尾元素的下一位置；队尾指针，若队列不空，指向队尾元素的下一位置； 当当rear=MAXSIZE时，时， 置置rear=0只是称为指针，只是称为指针，实现时不一定用实现时不一定用指针变量指针变量 设设Q为为SqQueue类型的变量，用于存储队列。设为队列类型的变量，用于存储队列。设为队列Q分配空间大小为分配空间大小为MAXSIZE=6，初始建队时，令初始建队时，令Q.front=Q.rear=0;Q.frontQ.frontQ.rearQ.rearQ.baseQ.base实际上，实际上，Q.frontQ.front=0,=0,Q.rearQ.rear=0=0，用箭头指用箭头指示只是为了直观示只是为了直观4 43 35 52 20 01 11）初始化操作）初始化操作InitQueu