数据结构C／C+描述第章 栈和队列课件VIP

第3章栈和队列,1,PPT学习交流,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,栈和队列是两种常用的数据类型,2,PPT学习交流,3.1栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,3.1.1栈的定义及基本运算一、什么是栈,3,PPT学习交流,栈的示意图,出栈,进栈,栈的特点后进先出(LIFO表),第1个进栈的元素在栈底，最后一个进栈的元素在栈顶，第1个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素,二、栈的图示,4,PPT学习交流,（1）初始化操作InitStack(,三、栈的基本操作（1）,5,PPT学习交流,（5）进栈操作Push(,三、栈的基本操作（2）,6,PPT学习交流,栈的顺序存储结构，也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置，由一个称为栈顶指针的变量指示。,栈的顺序存贮结构也称为顺序栈。,一、栈的顺序存储结构及实现,3.1.2栈的顺序表示与实现,与线性表类似，栈也可以用顺序结构或链式结构存储。,7,PPT学习交流,SqStack:结构类型名；SqStack类型的变量是结构变量。base：称为栈底指针，始终指向栈底位置；top：称为栈顶指针，约定栈顶指针指向栈顶元素的下一个位置；Stacksize：用于存放当前已分配的栈的存储空间的大小；,#defineSTACK_INIT_SIZE100/栈存储空间的初始分配量#defineSTACKINCREMENT10/栈存储空间的分配增量typedefstructSElemType*base;/栈空间基址便于判断栈是否为空SElemType*top/栈顶指针intstacksize;/当前分配的栈空间大小/（以sizeof(SElemType)为单位）SqStack;,顺序栈的类型定义,8,PPT学习交流,空栈,A进栈,BCDE进栈，栈满,EDC出栈,顺序栈的操作示例P.58,9,PPT学习交流,顺序栈的图示,basetopstacksize,S,10,PPT学习交流,StatusInitStack(SqStack/InitStack_Sq,（1）初始化操作,顺序栈的基本操作的实现,11,PPT学习交流,StatusDetroyStack(SqStack/DetroyStack_Sq,（2）销毁栈操作,12,PPT学习交流,StatusClearStack(SqStack/ClearStack,（3）置空栈操作,13,PPT学习交流,StatusGetTop(SqStackS,SelemType/GetTop_Sq,（4）取栈顶元素操作GetTop,14,PPT学习交流,StatusPush(SqStack/Push,（5）进栈操作Push,15,PPT学习交流,StatusPop(SqStack,（6）出栈操作Pop,16,PPT学习交流,栈的链式存储结构，也称链栈，如右图所示：,3.1.3栈的链式表示及实现,17,PPT学习交流,链式栈图示,说明：1.链栈可用线性链表表示；2.链栈的栈顶指针就是链表的头指针；3.进栈操作(push)就是在该线性链表第一个元素结点之前插入一个新结点.4.出栈操作(pop)就是删除链表的第一个元素结点。,18,PPT学习交流,3.2栈的应用举例,例1数制转换我们学习过各种数制的转换问题。十-八进制转换十-二进制转换等。下面我们设计一程序,实现十-八进制数的自动转换。该程序功能为：对于输入的任意一个非负十进制数，显示输出与其等值的八进制数。,19,PPT学习交流,我们这里介绍的方法基于下列原理：N=(Ndiv8)108+Nmod8N：十进制数，div：整除运算，mod：求余运算；例：(1348)10=283+582+08+4=(2504)8NNdiv8Nmod8134816841682102125202,20,PPT学习交流,由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位。而显示时按照我们的习惯是从高位在前，低位在后，即按从高位到低位的顺序输出。即后计算出的（高）位数先输出，具有后进先出的特点。因此可将计算过程中得到的八进制数顺序进栈，按出栈序列打印输出的数，就是对应的八进制数。,21,PPT学习交流,例如：（1348)10=(2504)8其运算过程如下：NNdiv8Nmod8134816841682102125202,计算顺序,输出顺序,22,PPT学习交流,voidconversion()/输入任意一个非负十进制整数，输出与其等值的八进制数InitStack(S);/建空栈scanf(“%d”,23,PPT学习交流,例2括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或()均为不正确的格式。,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,24,PPT学习交流,分析可能出现的不匹配的情况:,到来的右括弧非所“期待”的;,例如：考虑下列括号序列：()12345678,到来的是“不速之客”;,直到结束，也没有到来所“期待”的括弧;,25,PPT学习交流,算法的设计思想：,（1）凡出现左括弧，则进栈；,（2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余error否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配error,（3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余error,26,PPT学习交流,Statusmatchpairs(SElemTypestr)SqStack*S;inttag=1;char*ch,e;/e存放出栈字符/tag=1表示表达式中括号正确配对，tag=0表示不配对InitStack(,27,PPT学习交流,/遇到)，或，弹出栈顶字符case):Pop(S,28,PPT学习交流,例3行编辑程序问题,如何实现？,是否每接受一个字符即存入存储器?,29,PPT学习交流,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区;并假设“#”为退格符,“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,30,PPT学习交流,假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outputchar(*s=#+);,则实际有效的是下列两行：while(*s)putchar(*s+);,31,PPT学习交流,while(ch!=EOF/从终端接收下一个字符,ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();,while(ch!=EOF)/EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,32,PPT学习交流,(1)问题的提出设计一个小计算器（程序），希望从键盘上输入一个算术表达式（由运算符操作数构成的字符串）后,在屏幕上显示表达式的求值结果。,例4表达式求值,33,PPT学习交流,(2)表达式的构成操作数+运算符+界符（如括号）(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,34,PPT学习交流,+,2,1,-,*,/,(,),#,+-*/()#,1递归算法：intfact(intn)/算法功能是求解并返回n的阶乘If（n=1）return（1）；elsereturn（n*fact(n-1)）；,40,PPT学习交流,例2编写求解Hanoi塔问题的递归算法有3个各为X，Y，Z的塔座，在X项上有n个大小不同，依小到大编号为1，2，n的圆盘。现要求将X上的n个圆盘移至Z上，并仍以同样顺序叠放，圆盘移动时必须遵守下列原则：（1）每次移动1个盘子；（2）圆盘可以放在X，Y，Z中的任一塔座上；（3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；,41,PPT学习交流,例:n=3时圆盘移动的过程如下图所示：,Y,X,Z,42,PPT学习交流,求解Hanoi塔问题的递归描述（定义）基本项：n=1时，将n号圆盘从X移至Z；递归项：n1时，将X上1n-1号圆盘移至Y；将X上的n号圆盘从X移至Z;将Y上1n-1号圆盘从Y移至Z;,将规模为n的问题的求解归结为规模为n-1的问题的求解,有了问题的递归定义，很容易写出对应的递归算法：,43,PPT学习交流,voidhanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大，且自上而下编号为1至n的n个圆盘按规则搬到/塔座z上，y可用作辅助塔座。/搬动操作move(x,n,z)可定义为(c是初值为0的全局变量，对搬动计数)：/printf(“%d.Movedisk%dfrom%cto%cn”,+c,n,x,z);if(n=1)move(x,1,z);/将编号为1的圆盘从x移动zelsehanoi(n-1,x,z,y);/将x上编号为1至n-1的圆盘移到y,z作辅助塔move(x,n,z);/将编号为n的圆盘从x移到zhanoi(n-1,y,x,z)；/将y上编号为1至n-1的圆盘移到z,x作辅助塔算法3.5Hanoi塔问题,44,PPT学习交流,3.4队列,3.4.1队列的定义及基本运算一什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表。,45,PPT学习交流,说明：设（a1,a2,a3,.,an）为一队列(1)表尾称作队尾，表头称为队头；(2)a1为队头元素，an为队尾元素；(3)在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；(4)元素按a1,a2,a3,.an顺序入队，第1个入队的元素为a1，最后一个入队的元素是an；第1个出队的元素为a1,最后一个出队的元素是an(5)队列具有先进先出的特点，所以又称为先进先出表（FIFO表）,46,PPT学习交流,二队列的基本操作（1）初始化操作InitQueue(/初始化时动态分配存储空间的基址intfront;/队头指针，指向队头元素intrear;/队尾指针，指向队尾元素的下一个位置SqQueue;,二、顺序队列的类型定义,50,PPT学习交流,顺序队列常常会出现“假溢出”现象，如图所示。虽然队列中还有一定的存储空间，但因为front指针与rear指针均向同一个方向移动，导致该队列不能再进行入队操作。,51,PPT学习交流,为了避免“假溢出”，可以这样规定，一旦rear指针（或front指针）指向了存储空间的末尾位置，如果此时再进行入队（或出队）操作，则将相应的指针平移到数组的起始位置，即是将队列假想为一个循环的环状空间，我们称之为循环队列。,52,PPT学习交流,三、循环队列操作图示,front,rear,空队front=rear是队空标志,3,1,2,0,MAXSIZE=4,53,PPT学习交流,front,rear,空队front=rear是队空标志,B,C,rear,front,3,1,2,0,MAXSIZE=4,A出队,三、循环队列操作图示,队列中含有3个元素，rear已经指向存储空间的末端，不能再向上移动,54,PPT学习交流,front,rear,空队front=rear是队空标志,C,rear,front,rear,front,3,1,2,0,MAXSIZE=4,B,C,B出队,三、循环队列操作图示,队列中含有2个元素,55,PPT学习交流,MAXSIZE=4,此刻rear已经指向存储空间的末端若再有元素进队列，则执行语句：rear=(rear+1)%MAXSIZE,三、循环队列操作图示,D元素进队列，执行：rear=(rear+1)%MAXSIZE经过计算，rear的值为0,56,PPT学习交流,front,rear,空队front=rear是队空标志,C,C,rear,front,rear,front,D,E,3,1,2,0,MAXSIZE=4,D,E进队,三、循环队列操作图示,Rear重新指向存储空间的起始位置，此刻队列仍有存储空间，可以进行进队操作,57,PPT学习交流,front,rear,空队front=rear是队空标志,C,C,rear,front,D,E,F,3,1,2,0,MAXSIZE=4,F进队，队满队满与队空条件混淆,E,D,三、循环队列操作图示,58,PPT学习交流,front,rear,空队front=rear是队空标志,C,rear,front,D,E,F,3,1,2,0,MAXSIZE=4,为了区分队满与队空，规定队满条件为：(rear+1)%MAXQSIZE=front所以队列中最多能包含的元素个数比实际空间少一个,队满,三、循环队列操作图示,59,PPT学习交流,出队时应先判-队是否空?队空条件：Q.rear=Q.front不空，则出队。进队时应先判-队是否满?队满条件：(Q.rear+1)%MAXQSIZE)=Q.front不满，则进队。,60,PPT学习交流,(1)初始化循环队,StatusInitQueue(SqQueue,四、循环队列基本操作的实现,Q.base=newQElemTypeMAXSIXE;,61,PPT学习交流,（2）进队操作,StatusEnSqQueue(SqQueue,再进队满（上溢）,再进队循环、满,再进队循环、不满,S进队,62,PPT学习交流,（3）出队操作P.76,StatusDeSqQueue(SqQueue,队空,63,PPT学习交流,3.4.3链队列队列的链式存储结构和实现,一、定义用链表表示的队列，称为链队列,空链队列,非空链队列,64,PPT学习交流,二、链队列的类型定义,typedefstructQNode/链队列结点的类型定义QElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstruct/链队列表头结点的类型定义QueuePtr*front;/队头指针，指向链表的头结点QueuePtr*rear;/队尾指针，指向队尾结点LinkQueue;,65,PPT学习交流,设Q为LinkQueue类型的变量，Q为链队列的表头结点，用于存储队列队头指针和队尾指针。,链队列的表头结点,链队列的头结点,空链队列,非空链队列,66,PPT学习交流,（1）初始化队操作：InitQueue(LinkQueue,三、链队列基本操作的算法,空链队列,67,PPT学习交流,销毁队操作：DestroyQueue(LinkQ