第3章_栈和队列详解.ppt

第三章 栈和队列 3.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 3.1.2 栈的表示和实现 3.1.2 链栈 status ishs () { //判断输入串是否是回文数 InitStack(S); gets(str); i=j=0; while (str[i]){ if (str[i]!=‘ ’) { str1[j++]=str[i]; push(S,str[i]); } i++； } i=0; while (!StackEmpty(S)) { Pop(S,e); if (e!=str1[i++]) reture false } returen true } // ishs 算法中还调用了两个函数： precede( )的功能是判断两个运算符θ1和θ2的优先关系； operate( )的功能是求两数a和b作θ运算的结果。 OperandType EvaluationExpress() { InitStack (OPTR); Push(OPTR,’#’) InitStack (OPND); c=getchar(); while(c!=‘#’ || GetTop(OPTR!=‘#’)) { if(!In (c,OP))) //c不是运算符 { Push (OPND,c); c=getchar(); } else switch (Precede(GetTop(OPTR),c)) { case : Push(OPTR,c); c=getchar(); break; case =: Pop(OPTR,x); c=getchar(); break; case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push (OPND, Operate(a, theta,b)); break; } //switch } //while return(GetTop(OPND)); } 如何从后缀式求值？ 先找运算符， 再找操作数 中缀表达式转换成后缀表达式算法 3.3 栈与递归的实现 直接或间接地调用自身的算法称为递归算法 应用： 函数的递归定义 数据结构的递归定义 问题的递归求解 例1 阶乘函数 阶乘函数可递归地定义为： 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下： 例3-2 Hanoi塔问题 设A,B,C是3个塔座。在塔座A上有一叠共n个圆盘，这些圆盘自下而上由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：不允许较大的圆盘压在较小的圆盘之上； 规则3：可将圆盘移至A,B,C中任一塔座上。 递归小结 优点：易读、易写、易证明。 缺点：效率低——递归算法转换为非递归算法 递归中的重复子问题 3.4 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 链队列 结点定义 顺序队列—队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置 插入新的队尾元素，尾指针增1，rear = rear + 1， 删除队头元素，头指针增1， front = front + 1， 因此，在非空队列中，头指针始终指向队列头元素