数据结构第3章课件 中国石油大学(华东)

1,栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形优先级队列,第三章栈与队列,2,3.1.1栈的定义只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO),3.1栈(Stack),退栈,进栈,a0,an-1,an-2,top,基于数组的存储表示实现的栈称为顺序栈，基于链表的存储表示实现的栈称为链式栈。,3,classSeqStack/顺序栈类定义private:int*elements;/栈元素存放数组inttop;/栈顶指针intmaxSize;/栈最大容量,栈的数组存储表示顺序栈,4,voidoverflowProcess();/栈的溢出处理public:SeqStack(intsz=50);/构造函数SeqStack()deleteelements;/析构函数voidPush(int,顺序栈的构造函数,#include#includeSeqStack:SeqStack（intsz）elements=newintsz;assert(elements!=NULL);top=-1;maxSize=sz;断言（assert）机制是C+提供的一种功能，若参数表中给定的条件满足，则继续执行后续的语句；否则出错处理终止程序的执行。,6,顺序栈的溢出处理,voidSeqStack:overflowProcess()/私有函数：当栈满则执行扩充栈存储空间处理int*newArray=newint2*maxSize;/创建更大的存储数组for(inti=0;ilink;while(top!=NULL)/逐个结点释放p=top;top=top-link;deletep;,top,13,入栈操作voidLinkedStack:Push(int,StackNode(intd=0,StackNode*next=NULL):data(d),link(next),x,top,14,出栈操作intLinkedStack:Pop(int,15,取栈顶元素intLinkedStack:getTop(int,top,算法基于原理：N=(Ndivd)d+Nmodd,3.1.4栈的应用-数制转换,例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202,计算顺序,输出顺序,思路：,初始化栈输入要转换的数据N当N不为0,把N%8取余入栈当栈不为空，栈顶元素出栈，输出。,voidconversion()LinkedStackS;intN;cinN;while(N)S.Push(N%8);N=N/8;coutnewOperand;/读取操作数AddOperand(newOperand);/加入到操作数栈S.Pop(newoperand);coutnewoperand;/输出计算结果;,取两个操作数，根据操作符op计算,voidCalculator:DoOperator(charop)doubleleft,right,value;if(get2Operands(left,right)switch(op)case+:value=left+right;S.Push(value);break;case-:value=left-right;S.Push(value);break;case*:value=left*right;S.Push(value);break;case/:if(right=0.0)cerr“Divideby0!”xOPND.Push(x);cin.get(ch);else/是操作符,比较优先级OPTR.GetTop(op);/读一个操作符,42,if(icp(ch)isp(op)/栈顶优先级低OPTR.Push(ch);cin.get(ch);elseif(icp(ch)link=NULL)coutdatalink);,3.问题的解法是递归的,47,在链表中寻找等于给定值的结点并打印其数值voidPrint(ListNode*f,intvalue)if(f!=NULL)if(f-data=value)coutdatalink,value);,48,构成递归的条件,不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。Procedure()if()/递归结束条件return(initialvalue);else/递归return(parameterexchange);,49,递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用n!(n-1)!(n-2)!1!0!=1返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。,3.2.2递归过程与递归工作栈,50,longFactorial(longn)inttemp;if(n=0)return1;elsetemp=n*Factorial(n-1);returntemp;,voidmain()intresult;result=Factorial(4);coutresultendl;,外部调用,内部调用,51,1.递归工作栈,每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。栈顶的工作记录是当前正在执行的这一层的工作记录。称之为活动记录。,返回地址局部变量参数,活动记录框架,递归工作记录,52,2.递归过程改为非递归过程,递归过程简洁、易编、易懂，但是效率低，重复计算多。单向递归和尾递归可直接用迭代实现其非递归过程，其他情形必须借助栈实现非递归过程；改为非递归过程的目的是提高效率。1.迭代法：尾递归：递归语句只有一个，而且在程序最后，因为是尾部,所以根本没有必要去保存任何局部变量。单向递归：虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法。2.其他的递归：用栈实现。,53,调用次数NumCall(k)=,斐波那契数列的递归调用树,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),时间复杂度：,2n,如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,2*Fib(k+1)-1,54,斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法longFib(longn)if(n=1)returnn;elsereturnFib(n-1)+Fib(n-2);,如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,55,尾递归用迭代法实现,对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：longfact(intn)ints=0;for(inti=1;ilink;returnk;输出队列中元素的重载操作ostream,75,3.3.4队列的应用：打印杨辉三角形,逐行打印二项展开式(a+b)i的系数：杨辉三角形(Pascalstriangle),分析第i行元素与第i+1行元素的关系,从前一行的数据可以计算下一行的数据,i=2,i=3,i=4,013310,14641,01210,0110,s,t,s+t,从第i行数据计算并存放第i+1行数据,110121013310,ints=0,t;,利用队列打印二项展开式系数的算法,#include#include#includequeue.hvoidYANGHUI(intn)SeqQueueq(n+2);/队列初始化p121q.EnQueue(1);q.EnQueue(1);ints=0,t;,for(inti=1;i=n;i+)/逐行计算coutendl;q.EnQueue(0);for(intj=1;j=i+2;j+)/下一行q.DeQueue(t);q.EnQueue(s+t);s=t;if(j!=i+2)couts=0;j-)if(pqelementsj=temp)break;elsepqelementsj+1=pqelementsj;pqelementsj+1=temp;,j,86,具有最小优先级的元素出队intPQueue:RemoveMin(int,87,取队头元素intPQueue:GetFront(int,1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2.熟练掌握栈类型的两种实现方法，特别应注意栈