数据结构第3章.ppt

《数据结构第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构第3章.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 栈和队列栈和队列 3.1 3.1 3.1 3.1 栈栈栈栈 3.2 3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例 3.3 3.3 3.3 3.3 队列队列队列队列操作特殊的线性表操作特殊的线性表第三章首页上页下页退出 a1 进栈出栈的示意图：进栈出栈的示意图：进栈出栈的示意图：进栈出栈的示意图：a1 a1 a1 a2 a2 a2 a2.an an an an an an a2 a2 an a2 a1 a1 a1 a1 an a2.第三章首页上页下页退出3.1 3.1 3.1 3.1 栈栈栈栈 一、栈的特点：一、栈的特点：一、栈的特点：一、栈的特点：满足

2、满足先进后出，后进先出先进后出，后进先出先进后出，后进先出先进后出，后进先出的线性表。的线性表。二、二、二、二、ADTADT定义：定义：定义：定义：数据对象：数据对象：D=a i|a i ElemsSet,i=1,2,n,n0 数据关系：数据关系：R1=|a i-1,a i D,i=1,2,n an端端为栈顶，为栈顶，a a1 1端为栈底。端为栈底。基本操作：基本操作：Initstack(&S)初始化操作初始化操作；Destroystack(&S)销毁栈销毁栈 Stackempty(S)判栈空函数；判栈空函数；Push(&S,x)入栈操作；入栈操作；Pop(&S,&e)出栈函数；出栈函数；Ge

3、tTop(S,&e)取栈顶元素函数；取栈顶元素函数；Clearstack(&S)栈置空操作；栈置空操作；Stacklength(S)求当前栈中元素个数函数。求当前栈中元素个数函数。第三章首页上页下页退出、顺序结构、顺序结构、顺序结构、顺序结构：利用地址连续的存储单元依次存放自栈底到利用地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈顶的数据元素。type struct SElemType *base;SElemType *top;int stacksize;SqStack;、链式结构：、链式结构：、链式结构：、链式结构：与线性表类似。与线性表类似。三、栈的存储结构：三、栈的存储结构：三、栈

4、的存储结构：三、栈的存储结构：3.1 3.1 3.1 3.1 栈栈栈栈 a an n a a1 1 a an-1n-1S栈顶栈顶栈顶栈顶栈底栈底栈底栈底思思思思考考考考题题题题1、已知入栈序列为、已知入栈序列为XYZW，以下序列哪些是允许的出栈以下序列哪些是允许的出栈序列：序列：WZYX，XYZW，ZYXW，ZXYW。2、已知入栈序列为已知入栈序列为XYZ，现有两个单元的栈空间，问你现有两个单元的栈空间，问你能调度出多少种出栈序列。能调度出多少种出栈序列。第三章首页上页下页退出数制转换：数制转换：将十进制转化为任意进制将十进制转化为任意进制3.2 3.2 3.2 3.2 栈的应用举例栈的应用举

5、例栈的应用举例栈的应用举例void conversion()Initstack(S);scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;while(!Stackempty(S)Pop(S,e);Printf(“%d”,e);第三章首页上页下页退出括号匹配的检验括号匹配的检验 1.只有小括号的表达式只有小括号的表达式 2.包含有各种括号的表达式包含有各种括号的表达式行编辑程序行编辑程序3.2 3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例void Linedit()Initstack(S);ch=getchar();while(ch!=EO

6、F)while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);break;case:Clearstack(S);break;default:Push(S,ch);ch=getchar();Clearstack(S);if(ch!=EOF)ch=getchar();第三章首页上页下页退出迷宫求解：迷宫求解：这是栈的应用的典型例题。具体算法思想是：这是栈的应用的典型例题。具体算法思想是：3.2 3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例从演示过程可见：从演示过程可见：1从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果从入

7、口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；和往北方向，从一个走得通的方向继续往前直到出口为止；2如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探

8、过了，一直退到起始点都没有走通，那就说明这个迷宫根本不置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；通；3所谓所谓走不通走不通不单是指遇到不单是指遇到墙挡路墙挡路，还有，还有已经走过的路不能重复走第已经走过的路不能重复走第二次二次，它包括，它包括曾经走过而没有走通的路曾经走过而没有走通的路。显然为了保证在任何位置上都能沿原路退回，需要用一个显然为了保证在任何位置上都能沿原路退回，需要用一个后进先出后进先出的结构即的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入

9、口到出口的路径。入口到出口的路径。由此，求迷宫中一条路径的算法的基本思想是：由此，求迷宫中一条路径的算法的基本思想是：若当前位置若当前位置可通可通，则纳入，则纳入当前路径当前路径，并继续朝，并继续朝下一位置下一位置探索；探索；若当前位置若当前位置不可通不可通，则应顺着，则应顺着来的方向来的方向退回到退回到前一通道块前一通道块，然后朝，然后朝着除着除来向来向之外的其他方向继续探索；若该通道块的四周四个方块均之外的其他方向继续探索；若该通道块的四周四个方块均不可不可通通，则应从，则应从当前路径当前路径上删除该通道块。上删除该通道块。第三章首页上页下页退出3.2 3.2 3.2 3.2 栈的应用举例

10、栈的应用举例栈的应用举例栈的应用举例表达式求值表达式求值表达式求值表达式求值 1 1 1 1、比较优先级、比较优先级、比较优先级、比较优先级 存储存储 取括号取括号 运算运算 +-*/（）#+-*/(#=第三章首页上页下页退出3.2 3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例表达式求值表达式求值表达式求值表达式求值 2 2 2 2、算法思想：、算法思想：、算法思想：、算法思想：为实现算符优先法，可以使用两个工作栈。一个称做为实现算符优先法，可以使用两个工作栈。一个称做OPTROPTR，用以寄存运算符；另一个称做用以寄存运算符；另一个称做OPNDOPND，用以寄存操

11、作数或运算结果。用以寄存操作数或运算结果。基本思想：基本思想：1 1）首先置操作数栈为空栈，表达式起始符）首先置操作数栈为空栈，表达式起始符“#”为运算符栈为运算符栈的栈底元素；的栈底元素；2 2）依次读入表达式中每个字符，若是操作数则进）依次读入表达式中每个字符，若是操作数则进OPNDOPND栈，若栈，若是运算符，则和是运算符，则和OPTROPTR栈的栈顶运算符比较优先权后作相应操作，栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即直至整个表达式求值完毕（即OPTROPTR栈的栈顶元素和当前读入的字栈的栈顶元素和当前读入的字符为符为“#”）。）。第三章首页上页下页退出3.2

12、3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例表达式求值表达式求值表达式求值表达式求值 3 3 3 3、算法实现：、算法实现：、算法实现：、算法实现：例：例：3*3*（7-27-2）#Operandtype EvaluateExpress()Initstack(OPTR);Push(OPTR,#);Initstack(OPND);c=getchar();while(c!=#|Gettop(OPTR)!=#)if(!In(c,op)Push(OPND，c);c=getchar();else switch(Precede(Gettop(OPTR),c)case :Pop(

13、OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a theta b);break;return Gettop(OPND);第三章首页上页下页退出递归的实现递归的实现：递归算法实现必须使用栈。递归算法实现必须使用栈。Hanoi塔就是典型例子。塔就是典型例子。3.2 3.2 3.2 3.2 栈的应用举例栈的应用举例栈的应用举例栈的应用举例Void hanoi(int n,char x,char y char z)1if(n=1)2 move(x,1,z);3 else 4 hanoi(n-1,x,z,y);5 move(x,n,z);6

14、hanoi(n-1,y,x,z);7 8 9 一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于调调用函数和被调用函数是同一个函数用函数和被调用函数是同一个函数。为了保证。为了保证每一层的递归调用每一层的递归调用都是对都是对本层本层的数据进行操作，在执行递归函数的过程中需要一个的数据进行操作，在执行递归函数的过程中需要一个递归工作栈递归工作栈。它的作用是它的作用是:一、将递归调用时的实在参数和函数返回地址传递给下一层执一、将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数；二、保存本层的参数和局部变量，以便从下一层返

15、回时重行的递归函数；二、保存本层的参数和局部变量，以便从下一层返回时重新使用它们。新使用它们。递归过程执行过程中所占用的数据区，称之为递归工作栈。每一层的递归参数等数据合成一个记录，称之为递归工作记录。栈顶记录指示当前层的执行情况，称之为当前活动记录。递归工作栈的栈顶指针，称之为当前环境指针。第三章首页上页下页退出3.3 3.3 3.3 3.3 队列队列队列队列 一、队列的特点一、队列的特点一、队列的特点一、队列的特点：满足满足先进先出，后进后出先进先出，后进后出先进先出，后进后出先进先出，后进后出的线性表。的线性表。二、二、二、二、ADTADTADTADT定义：定义：定义：定义：数据对象：数

16、据对象：D=a i|a i ElemsSet,i=1,2,n,n=0 数据关系：数据关系：R1=|a i-1,a i D,i=1,2,n an端端为队列尾，为队列尾，a1端为队列头。端为队列头。基本操作：基本操作：Initqueue(&Q)Destroyqueue(&Q)Clearqueue(&Q)Queueempty(Q)Gethead(Q,&e)Queuelength(Q)Enqueue(&Q,e)Dequeue(&Q,&e)第三章首页上页下页退出3.3 3.3 3.3 3.3 队列队列队列队列 三、链队列的表示和实现：三、链队列的表示和实现：三、链队列的表示和实现：三、链队列的表示和实现

17、：表示：表示：type struct QNode typedef struct QElemType data;QueuePtr front;struct Qnode *next;QueuePtr rear;Qnoode,*QueuePtr;LinkQueue;a a1 1 a an n a a2 2Q frontfront rearrear第三章首页上页下页退出四循环队列（顺序结构）四循环队列（顺序结构）四循环队列（顺序结构）四循环队列（顺序结构）3.3 3.3 3.3 3.3 队列队列队列队列 1 1 1 1、顺序结构的表示：、顺序结构的表示：、顺序结构的表示：、顺序结构的表示：用一维数组存

18、储队列。实现入列时在最后用一维数组存储队列。实现入列时在最后插入；出列时可删除队头元素，按线性表的操作方法从第二个元素插入；出列时可删除队头元素，按线性表的操作方法从第二个元素开始逐个前移，由于队列出列操作较频繁，因此这样的移动不是较开始逐个前移，由于队列出列操作较频繁，因此这样的移动不是较好的方法。由此改为指针移动。好的方法。由此改为指针移动。J 1 J 2 J 3 J 3 J 5 J 40123401234J1J2J301234J301234J4J5Q.frontQ.rear循环队列是队列的一种顺序存储表示。那么为什循环队列是队列的一种顺序存储表示。那么为什循环队列是队列的一种顺序存储表示

19、。那么为什循环队列是队列的一种顺序存储表示。那么为什么要称作么要称作么要称作么要称作 循环队列循环队列循环队列循环队列 而不说是而不说是而不说是而不说是 顺序队列顺序队列顺序队列顺序队列 呢？呢？呢？呢？这是由于队列操作（在队尾插入元素，而在队头删除元素）的特殊性造成的。这好比这是由于队列操作（在队尾插入元素，而在队头删除元素）的特殊性造成的。这好比我们在食堂排队买饭，因为柜台是固定位置不动的，则每次排头的人买完离开队伍之我们在食堂排队买饭，因为柜台是固定位置不动的，则每次排头的人买完离开队伍之后，后面的人依次往前后，后面的人依次往前 移动移动 一个位置，为了避免一个位置，为了避免 移动移动

20、可以改一种方式。让吃饭的可以改一种方式。让吃饭的人围着圆桌人围着圆桌 依次依次 入座，而食堂的师傅推着小车围着圆桌按先后落座的次序入座，而食堂的师傅推着小车围着圆桌按先后落座的次序 依次依次 卖卖饭，并假定饭，并假定 先来的先走先来的先走 。则就是。则就是 循环队列循环队列 的一种模拟。的一种模拟。第三章首页上页下页退出四循环队列（顺序结构）四循环队列（顺序结构）四循环队列（顺序结构）四循环队列（顺序结构）3.3 3.3 3.3 3.3 队列队列队列队列 2 2 2 2、队列的假溢出现象、队列的假溢出现象、队列的假溢出现象、队列的假溢出现象 避免假溢出：把队列设想为一个循环的表。避免假溢出：把

21、队列设想为一个循环的表。循环队列：即是队列的顺序循环队列：即是队列的顺序存储存储结构。结构。3 3 3 3、循环队列中当、循环队列中当、循环队列中当、循环队列中当Q.front=Q.rearQ.front=Q.rear是是是是“空空空空”还是还是还是还是“满满满满”？解决方法：解决方法：（1）设置标志域）设置标志域 （2）少用一个元素空间）少用一个元素空间 当当Q.front=(Q.rear+1)%MAXSIZE时为满时为满 当当Q.front=Q.rear时为空时为空 五队列的应用五队列的应用五队列的应用五队列的应用离散时间模拟离散时间模拟离散时间模拟离散时间模拟 银行业务模拟第三章首页上页

22、下页退出思考题：思考题：、一入栈序列为、一入栈序列为123456123456，能否得到，能否得到435612435612和和135426135426的出栈序列。的出栈序列。、写出判断一个表达式中开、闭括号是否配对出现、写出判断一个表达式中开、闭括号是否配对出现的算法。的算法。、设有一表达式为、设有一表达式为(a+b)/c+b*(e-f)*ga+b)/c+b*(e-f)*g，试写出试写出其前缀、中缀、后缀表示形式；并考虑采用此做为输其前缀、中缀、后缀表示形式；并考虑采用此做为输入形式时，能否优化表达式求值的算法。入形式时，能否优化表达式求值的算法。4 4、有一空间足够的静态存储队列共有、有一空间足够的静态存储队列共有1010个元素，出个元素，出列采用移动操作，现在进行列采用移动操作，现在进行3 3次出列，次出列，2 2次入列后再进次入列后再进行行2 2次出列，次出列，1 1次入列。问队列中的元素共移动了多少次入列。问队列中的元素共移动了多少次？次？