数据结构第三章栈和队列.ppt
第三章 栈和队列,3.1 栈,3.2 栈的应用举例,3.3 栈与递归的实现,3.4 队列,作业,实验,3.1 栈,栈的定义,栈的存储方法,栈的基本操作,栈的定义,栈是限制在表的一端进行插入和删除的线性表。,允许插入、删除的这一端称为栈顶.,另一个固定端称为栈底。,a1,a2,a3,top,（Last In First Out），简称 LIFO表。,a1,a2,a3,top,有三个元素，进栈的顺序是a1、a2、a3,当需要出栈时其出栈顺序为a3、a2、a1,所以栈又称为后进先出的线性表,进栈,出栈,栈的基本操作,栈的初始化,判栈空,入栈,出栈,读栈顶元素,栈使用不同的存储方式，同一操作会有不同的方法步骤。,由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。,栈的存储,顺序栈,链式栈,顺序栈,利用顺序存储方式实现的栈称为顺序栈。,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，,同时附设指针top指示栈顶元素在顺序栈中的位置。,top,base,top,base,top,base,top,base,为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。,设定两个常量：,STACK_INIT_SIZE存储空间初始分配量STACKINCREMENT存储空间分配增量,顺序栈的定义,typedef struct SElemType*base;SElemType*top;int stacksize;SqStack;,stacksize指示栈的当前可使用的最大容量。,#define STACK_INIT_SIZE 100#define STACKINCREMENT 10,top,base,base为栈底指针，top为栈顶指针，baseNULL，则栈结构不存在topbase 表示栈空,top,base,top,base,top,base,顺序栈的基本操作:,构造一个空栈S,Status InitStack(SqStack,取栈顶元素,Status GetTop(SqStack S,SElemType,插入,Status Push(SqStack,删除栈顶,Status Pop(SqStack,链式栈,data,next,：,栈顶,栈底,S,3.2 栈的应用举例,3.2.1 数制转换,十进制数N和其他d进制数的转换。,N=(N div d)d+N mod d,整除,求余,原理：,(1348)10=(2504)8,运算过程：,上面的例子即为：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。,算出来的八进制在输出之前放哪呢？按照上述计算过程得到的八进制数的顺序是：,4,0,5,2,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);,用数组实现不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。,3.2.2 括号匹配的检验,(),(),(),(),检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,如：,(1)第一个符号进栈。(2)第二个符号(与栈顶元素比较，如果匹配，删除栈顶，并且该符号不入栈。如此类推。,3.2.3 行编辑程序,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。,如：,当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“”，以表示当前行中的字符均无效。,如,从键盘输入了这样两行字符：,whi#ilr#e(s#*s)outchaputchar(*s=#+);,则实际有效的是：,while(*s)putchar(*s+);,算法见P50,3.2.4 迷宫求解,求迷宫中从入口到出口的所有路径。,入口,出口,一条通道上同一空白方块不能走两次。,为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。即栈。,求迷宫中一条从入口到出口的路径的算法描述：,设定当前位置的初值为入口位置：,do若当前位置可通，则 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东邻方块为新 的当前位置；,否则，若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置；若栈不空，则重新测试新的 栈顶位置，直至找到一个可通的相邻块或出栈至栈空;while（栈不空）;,3.2.5 表达式求值,表达式是由运算对象、运算符、括号组成的有意义的式子。,运算符从运算对象的个数上分，有单目运算符和双目运算符；,从运算类型上分，有算术运算、关系运算、逻辑运算。,在此仅限于讨论只含二目运算符的算术表达式。,4+2*3-10/5,c,栈的一个重要应用是在程序设计语言中实现递归过程。,现实中，有许多实际问题是递归定义的，这时用递归方法可以使许多问题的结果大大简化。,3.3 栈与递归,以 n!为例：,fact(n)=,1 n=0/*递归终止条件*/,n*fact(n-1)n0/*递归步骤*/,int fact(int n)if(n=0)return 1;else return(n*fact(n-1);,3!,递归函数都有一个终止递归的条件，如上例n=0时，将不再继续递归下去。,递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已，自己调用自己。,fibonacci数列,fibonacci(0)=0fibonacci(1)=1fibonacci(2)=1fibonacci(3)=2fibonacci(4)=3fibonacci(5)=5fibonacci(n)=fibonacci(n-1)+fibonacci(n-2),斐波那契数列,int fib(n)if(n=0)return 0;if(n=1)return 1;else return fib(n-1)+fib(n-2);,在1202年，Fibonacci注意到了一个兔子的繁殖问题，他假设一开始有一只公的兔子与一只母的兔子刚出生，每只兔子再经过一个月後就有繁殖能力，而兔子的怀孕期是一个月，而一旦母兔子拥有繁殖能力时，它每个月都会生产，而且生出来的兔子是一公一母，最後一个条件是，兔子不会死掉。在这种理想状况下，问题来了：经过一年（十二个月）後，总共有几对兔子？,3.4 队列,插入在表一端进行，而删除在表的另一端进行，把允许插入的一端叫队尾(rear)，把允许删除的一端叫队头(front)。,队列是“先进先出”FIFO(First In First Out)的数据结构.,队列也是一种运算受限制的线性表，所以又叫先进先出表。,在队列上进行的基本操作有：,队列初始化,入队,出队,读队头元素,判队空,队列的存储实现及运算实现,与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。,链队列,构造一个空链队列,Status InitQueue(LinkQueue,销毁链队列,Status DestroyQueue(LinkQueue,插入元素为Q的新的队尾元素,Status EnQueue(LinkQueue,若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR。,Status Dequeue(LinkQueue,循环队列队列的顺序表示和实现,在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。,为了在C语言中描述方便起见，我们约定：,初始化建空队列时，令frontrear0。,每当删除队列头元素时，头指针增1。,在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。,Q.front=Q.rear,是“空”还是“满”,有两种处理方法：,define MAXQSIZE 100type struct QElemType*base;int front;int rear;SqQueue;,构造一个空循环队列,Status InitQueue(SqQueue,返回Q的元素，即队列的长度,int QueueLength(SqQueue Q)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;,插入元素e为Q的新的队尾元素,Status EnQueue(SqQueue,若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR,Status DeQueue(SqQueue,作业,一、选择题,1、栈和队列的共同点是_A）都是先进后出 B）都是先进先出C）只允许在端点处插入和删除元素 D）没有共同点,2、判定一个顺序栈为（元素最多为StackSize个）空的条件为_A）S.top=0 B）S.top!=0 C）S.top!=StackSize D）S.top=StackSize,3、将递归算法转换为对应的非递归算法时，通常需要使用_保存中间结果。A）队列 B）栈 C）链表 D）树,4、设循环队列中数组的下标是0N-1，其头尾指针分别为f和r，则其元素个数为_。A）rf B）rf1 C）（rf）N1 D）（rfN）N,5、判定一个循环队列Q（存放元素位置0QueueSize-1）队满的条件是_A）Q.front=Q.rear B）Q.front+1=Q.rearC）Q.front=(Q.rear+1)%QueueSize D）Q.rear=(Q.front+1)%QueueSize,6、栈结构通常采用的两种存储结构是_。A）顺序存储结构和链表存储结构 B）散列方式和索引方式C）链表存储结构和数组 D）线性链表结构和非线性存储结构,7、在栈操作中，输入序列为（A，B，C，D），不可能得到的输出数列是_A）（A，B，C，D）B）（D，C，B，A）C）（A，C，D，B）D）（C，A，B，D）,8、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行_。A）xHS；HSHSnext；B）HSHSnext；xHSdata；C）xHSdata；HSHSnext；D）SnextHS；HSHSnext；,二、简答题,1、链栈中为何不设置头结点？,三、递归专题,1 若n0,n*Fact(n-1)若n1,Fact（n）=,1、阶乘函数,（1）写出递归算法（2）写出非递归算法,2、试将下列递归过程改写为非递归过程。void test(int,3、已知Ackermann函数定义如下：,写出计算Ack(m,n)的递归算法。,4、设a是含有n个分量的整数数组，写出求n个整数之和的递归定义_，写出求n个整数之积的递归定义_。,5、将下列递推过程改写为递归过程void ditui(int n)int i;i=n;while(i1)printf(i-);,
