3数据结构与算法北京大学 张铭 栈和队列

数据结构与算法数据结构与算法数据结构与算法数据结构与算法 第第第第3 3 3 3章章章章 栈与栈与栈与栈与 队列队列队列队列本章由赵海燕主写本章由赵海燕主写本章由赵海燕主写本章由赵海燕主写北京大学北京大学北京大学北京大学张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，2012.62012.62012.62012.62012.62012.6。“十一五十一五十一五十一五十一五十一五”国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6操作受限的线性表操作受限的线性表o栈（Stack）n运算只在表的一端进行o队列（Queue）n运算只在表的两端进行“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1 栈栈o后进先出（LastInFirstOut）n一种限制访问端口的线性表n栈存储和删除元素的顺序与元素到达的顺序相反n也称为“下推表”o栈的主要元素n栈顶（top）元素：栈的唯一可访问元素元素插入栈称为“入栈”或“压栈”（push）删除元素称为“出栈”或“弹出”（pop）n栈底：另一端“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6 栈栈的示意的示意图图 o每次取出（并被删除）的总是刚压进的元素，而最先压入的元素则被放在栈的底部 o当栈中没有元素时称为“空栈”k0k1.kn-1栈顶栈底出栈进栈“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6栈的主要操作栈的主要操作o入栈（push）o出栈（pop）o取栈顶元素（top）o判断栈是否为空（isEmpty）“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1.1 栈的抽象数据类型栈的抽象数据类型 template /栈的元素类型为 Tclass Stack public:/栈的运算集void clear();/变为空栈 bool push(const T item);/item入栈，成功则返回真，否则返回假 bool pop(T&item);/返回栈顶内容并弹出，成功返回真，否则返回假 bool top(T&item);/返回栈顶内容但不弹出，成功返回真，否则返回假bool isEmpty(;/若栈已空返回真 bool isFull();/若栈已满返回真;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6栈的实现栈的实现方式方式o顺序栈（Array-based Stack）n使用向量实现，本质上是顺序表的简化版栈的大小n关键是确定哪一端作为栈顶o链式栈（Linked Stack）n用单链表方式存储，其中指针的方向是从栈顶向下链接“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1.2 顺序栈顺序栈 template class arrStack:public Stack private:/栈的顺序存储int mSize;/栈中最多可存放的元素个数inttop;/栈顶位置，应小于mSizeT*st;/存放栈元素的数组public:/栈的运算的顺序实现arrStack(int size)/创建一个给定长度的顺序栈实例mSize=size;top=-1;st=new TmSize;arrStack()/创建一个顺序栈的实例 top=-1;arrStack()/析构函数delete st;void clear()/清空栈内容top=-1;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈顺序栈 o按压入先后次序，最后压入的元素编号为4，然后依次为3,2,1 123top栈底4“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈示意顺序栈示意012345s.top=-1s.top=0A0B1C2D3E4F5s.top=5A012345A0B1C2D345s.top=3“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈的溢出顺序栈的溢出o上溢（Overflow）n当栈中已经有maxsize个元素时，如果再做进栈运算，所产生的现象o下溢（Underflow）n对空栈进行出栈运算时所产生的现象“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈顺序栈 o若入栈的顺序为1,2,3,4的话，则出栈的顺序可以有哪些?n1234n1243n1324n1342n1423n1432n2134n2143“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6压入栈顶压入栈顶 bool arrStack:push(const T item)if(top=mSize-1)/栈已满 cout 栈满溢出 endl;return false;else/新元素入栈并修改栈顶指针st+top=item;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6从栈顶弹出从栈顶弹出 bool arrStack:pop(T&item)/出栈的顺序实现if(top=-1)/栈为空cout 栈为空，不能执行出栈操作 endl;return false;else item=sttop-;/返回栈顶元素并修改栈顶指针return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6从栈顶读取，但不弹出从栈顶读取，但不弹出 bool arrStack:top(T&item)/返回栈顶内容，但不弹出if(top=-1)/栈空cout 栈为空，不能读取栈顶元素 endl;return false;else item=sttop;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6其他算法其他算法 o把栈清空void arrStack:clear()top=-1;o栈满时，返回非零值（真值true）bool arrStack:isFull()return (top=maxsize-1);“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6栈的变种栈的变种o两个独立的栈n底部相连：双栈n迎面增长哪一种更好些？迎面增长的栈top1top2“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1.3 链式栈链式栈 ki+2 ki+1 ki k0 topdatanexto用单链表方式存储o指针的方向从栈顶向下链接“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6链式栈的创建链式栈的创建 template class lnkStack:public Stack private:/栈的链式存储Link*top;/指向栈顶的指针int size;/存放元素的个数public:/栈运算的链式实现lnkStack(int defSize)/构造函数top=NULL;size=0;lnkStack()/析构函数clear();“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6压入栈顶压入栈顶 /入栈操作的链式实现bool lnksStack:push(const T item)Link*tmp=new Link(item,top);top=tmp;size+;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6自单链栈弹出自单链栈弹出 /出栈操作的链式实现bool lnkStack:pop(T&item)Link *tmp;if(size=0)cout 栈为空，不能执行出栈操作data;tmp=top-next;delete top;top=tmp;size-;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈和链式栈的比较顺序栈和链式栈的比较o时间效率n所有操作都只需常数时间n顺序栈和链式栈在时间效率上难分伯仲o空间效率n顺序栈须说明一个固定的长度n链式栈的长度可变，但增加结构性开销“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序栈和链式栈的比较顺序栈和链式栈的比较o实际应用中，顺序栈比链式栈用得更广泛些 n顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素 n顺序栈读取内部元素的时间为O(1)，而链式栈则需要沿着指针链游走，显然慢些，读取第k个元素需要时间为O(k)一般来说，栈不允许“读取内部元素”，只能在栈顶操作“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1.4 栈的应用栈的应用o栈的特点：后进先出n体现了元素之间的透明性o常用来处理具有递归结构的数据n深度优先搜索n表达式求值n子程序函数调用的管理n消除递归“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算表达式的值计算表达式的值o表达式的递归定义n基本符号集：0，1，9，+，-，*，/，（，）n语法成分集：,n语法公式集 o中缀表达式 23+(34*45)/(5+6+7)o后缀表达式 23 34 45*5 6+7+/+o后缀表达式求值“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6中中缀缀表达法的表达法的语法公式语法公式 =+|=*|/|=|（）=|=0|1|2|3|4|5|6|7|8|9“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6中缀表达的算术表达式的中缀表达的算术表达式的计计算次序算次序 1.先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须配对2.在无括号或同层括号时，先乘(*)、除()，后加(+)、减(-)3.在同一个层次，若有多个乘除（*、）或加减(+，-)的运算，那就按自左至右顺序执行 23+(34*45)/(5+6+7)=?计算特点？“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀表达式后缀表达式 =+|-|=*|/|=|=0|1|2|3|4|5|6|7|8|9 “十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀表达式的计算后缀表达式的计算o 23 34 45*5 6+7+/+=？计算特点？中缀和后缀表达式的主要异同？23+34*45/(5+6+7)=?23 34 45*5 6+7+/+=？“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6o从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号：(1)当输入的是操作数时，直接输出到后缀表达式序列；(2)当遇到开括号时，把它压入栈；(3)当输入遇到闭括号时，先判断栈是否为空，若为空（括号不匹配），应该作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中），若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。中缀表达式中缀表达式后缀表达式后缀表达式“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6中缀表达式中缀表达式后缀表达式后缀表达式o从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号：（4）当输入为运算符op（四则运算+-*/之一）时（a）循环 当（栈非空 and 栈顶不是开括号 and 栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中；（b）将输入的运算符压入栈内；（5）最后，当中缀表达式的符号全部读入时，若栈内仍有元素，把它们全部依次弹出，放在后缀表达式序列的尾部。若弹出的元素遇到开括号，则说明括号不匹配，做异常处理，清栈退出。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6中缀表达式中缀表达式后缀表达式后缀表达式待处理中缀表达式：输出后缀表达式：栈的状态23/45567*()()34“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀表达式求值后缀表达式求值 o循环：依次顺序读入表达式的符号序列（假设以作为输入序列的结束），并根据读入的元素符号逐一分析：1.当遇到的是一个操作数，则压入栈顶；2.当遇到的是一个运算符,就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶o如此继续，直到遇到符号,这时栈顶的值就是输入表达式的值“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀表达式求值后缀表达式求值待处理后缀表达式：23/45567*34栈状态的变化1530111885108“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀表达式求值后缀表达式求值o中缀表达式：n运算符在中间n需要括号改变优先级n 4*x*(2*x+a)co后缀表达式n运算符在后面n完全不需要括号n4 x *2 x *a+*c“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6后缀计算器的类定义后缀计算器的类定义/Class Declaration 类的说明 (参见算法3.5)class Calculator private:Stack s;/这个栈用于压入保存操作数 /从栈顶弹出两个操作数opd1和opd2bool GetTwoOperands(double&opd1,double&opd2);/取两个操作数，并按op对两个操作数进行计算void Compute(char op);public:Calculator(void);/创建计算器实例，开辟一个空栈 void Run(void);/读入后缀表达式，遇到符号=时，求值计算结束 void Clear(void);/清除计算器，为下一次计算做准备 ;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.1.5 栈与递归栈与递归o函数的递归定义 o主程序和子程序的参数传递 o栈在实现函数递归调用中所发挥的作用“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归递归o作为数学和计算机科学的基本概念，递归是解决复杂问题的一个有力手段n符合人类解决问题的思维方式，递归能够描述和解决很多问题，为此许多程序设计语言都提供了递归的机制n而计算机则只能按照指令集来顺序地执行。o计算机内（编译程序）是如何将程序设计中的便于人类理解的递归程序转换为计算机可处理的非递归程序的?“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归定义阶乘递归定义阶乘n！函数函数 o阶乘n！的递归定义如下：o递归定义由两部分组成：n递归基础/出口n递归规则“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算阶乘计算阶乘n n！的循环迭代程序！的循环迭代程序 /使用循环迭代方法，计算阶乘n!的程序long factorial(long n)int m=1;int i;if(n0)for(i=1;i =n;i+)m =m*i;return m;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算阶乘计算阶乘n！的递归程序的递归程序/递归定义的计算阶乘n!的函数long factorial(long n)if(n=0)return 1;elsereturn n*factorial(n-1);/递归调用“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归问题求解过程示例：阶乘递归问题求解过程示例：阶乘回推：递推：4！=4*3！4！=4*3!=24 3！=3*2！3！=3*2！=6 2！=2*1！2！=2*1！=2 1！=1*0！1！=1*0！=1 0！=1已知“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归函数的实现递归函数的实现o栈的一个最为广泛的应用也许是用户所看不到，此即大多数程序设计语言运行环境都提供的函数调用机制。n运行时环境指的是目标计算机上用来管理存储器并保存指导执行过程所需的信息的寄存器及存储器的结构。o函数调用n在非递归情况下，数据区的分配可以在程序运行前进行，一直到整个程序运行结束才释放，这种分配称为静态分配。采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据区n在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而必须每调用一次就分配一份，以存放当前所使用的数据，当返回时随即释放。故其存储分配只能在执行调用时才能进行，即所谓的动态分配：在内存中开辟一个称为运行栈（runtime stack）的足够大的动态区“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6函数运行时的动态存储分配函数运行时的动态存储分配o用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（stack）区域和堆（heap）区域n栈区域用于分配发生在后进先出LIFO风格中的数据（诸如函数的调用）n堆区域则用于不符合LIFO（诸如指针的分配）的动态分配“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6运行栈中的活动记录运行栈中的活动记录o函数活动记录（activation record）是动态存储分配中一个重要的单元n当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6运行栈中的活动记录运行栈中的活动记录o运行栈随着程序执行时发生的调用链或生长或缩小n每次调用时，执行进栈操作，把被调函数的活动信息压入栈中，即当进行一个新的函数调用时，每个新的活动记录都分配在栈的顶部n而在每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中n被调函数中变量地址全部采用相对于栈顶的相对地址来表示o一个函数在运行栈上可以有若干不同的活动记录，每个都代表了一个不同的调用n对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目。n当函数递归调用时，函数体的同一个局部变量，在不同的递归层次被分配给不同的存储空间，放在内部栈的不同位置“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6函数调用与返回处理函数调用与返回处理o调用可以分解成以下三步来实现：n调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等。n分配被调方需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息。n调用方暂停，把计算控制转到被调方，亦即自动转移到被调用的函数的程入口。o当被调方结束运行，返回到调用方时，其返回处理一般也分解为三步进行：n传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等。n释放分配给被调方的数据区。n按返回地址把控制转回调用方。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归时运行栈的变化示例递归时运行栈的变化示例以阶乘为例：#include main()int x;scanf(“%d”,&x)；printf(“%dn”,factorial(4);“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算阶乘时的运行栈计算阶乘时的运行栈n:4控制链返回地址第1次调用factorial时的活动记录x:4主程序main的活动记录栈生长方向栈生长方向n:4控制链返回地址第1次调用factorial时的活动记录x:4主程序main的活动记录n:3控制链返回地址第2次调用factorial时的活动记录“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算阶乘时的运行栈计算阶乘时的运行栈“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归算法的非递归实现递归算法的非递归实现o以阶乘为例，非递归方式n建立迭代n递归转换为非递归o以Hanoi塔为例呢？“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6计算阶乘计算阶乘n n！的循环迭代程序！的循环迭代程序 /使用循环迭代方法，计算阶乘n!的程序long factorial(long n)int m=1;int i;if(n0)for(i=1;i 0)/?s.push(n-);while(!isEmpty(s)/?m*=s.pop(s);return m;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归转换为非递归的方法递归转换为非递归的方法o机械方法1.设置一工作栈当前工作记录2.设置 t+2个语句标号3.增加非递归入口4.替换第 i(i=1,t)个递归规则5.所有递归出口处增加语句：goto label t+1;6.标号为t+1的语句的格式7.改写循环和嵌套中的递归8.优化处理“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.61.1.设置一工作栈记录当前工作记录设置一工作栈记录当前工作记录o在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员代替n返回语句标号域(t+2个数值)n函数参数(值参、引用型)n局部变量 typedef struct elem /栈数据元素类型int rd;/返回语句的标号Datatypeofp1 p1;/函数参数 Datatypeofpm pm;Datatypeofq1 q1;/局部变量 Datatypeofqn qn;ELEM;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.62.2.设置设置t+2t+2个语句标号个语句标号olabel 0：第一个可执行语句olabel t+1：设在函数体结束处olabel i (1=i=t)：第i个递归返回处“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.3.增加非递归入口增加非递归入口/入栈S.push(t+1，p1,，pm，q1，qn);“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.64.4.替换第替换第i(i=1,i(i=1,t),t)个递归规则个递归规则o假设函数体中第i(i=1,t)个递归调用语句为：recf(a1,a2,am)；则用以下语句替换：S.push(i,a1,am)；/实参进栈goto label 0；.label i：x=S.pop()；/*退栈，然后根据需要，将x中某些值赋给栈顶的工作记录S.top()相当于把引用型参数的值回传给局部变量*/“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.65.5.所有递归出口处增加语句所有递归出口处增加语句o goto label t+1;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.66.6.标号为标号为t+1t+1的语句的语句switch(x=S.top().rd)case 0:goto label 0;break;case 1:goto label 1;break;.case t+1:item=S.pop()/返回处理break;default:break;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.67.7.改写循环和嵌套中的递归改写循环和嵌套中的递归o对于循环中的递归，改写成等价的goto型循环o对于嵌套递归调用譬如，recf(recf()改为：exmp1=recf();exmp2=recf(exmp1);exmpk=recf(exmpk-1)然后应用规则 4 解决“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.68.8.优化处理优化处理o经过上述变换所得到的是一个带goto语句的非递归程序。可以进一步优化n 去掉冗余进栈/出栈n 根据流程图找出相应的循环结构，从而消去goto语句“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6递归的非递归实现递归的非递归实现o请大家思考，用机械的转换方法n阶乘函数n2阶斐波那契函数f0=0,f1=1,fn=fn-1+fn-2nHanoi塔“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.2 队列队列o先进先出（FirstInFirstOut）n限制访问点的线性表 按照到达的顺序来释放元素所有的插入在表的一端进行，所有的删除都在表的另一端进行o主要元素n队头（front）n队尾（rear）“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列示意图队列示意图队头队尾进队出队k0 k1 k2 .kn-1“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的主要操作队列的主要操作o入队列（enQueue）o出队列（deQueue）o取队首元素（getFront）o判断队列是否为空（isEmpty）“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.2.1 队列的抽象数据类型队列的抽象数据类型template class Queue public:/队列的运算集void clear();/变为空队列bool enQueue(const T item);/将item插入队尾，成功则返回真，否则返回假bool deQueue(T&item);/返回队头元素并将其从队列中删除，成功则返回真bool getFront(T&item);/返回队头元素，但不删除，成功则返回真bool isEmpty();/返回真，若队列已空bool isFull();/返回真，若队列已满;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的实现队列的实现方式方式o顺序队列n关键是如何防止假溢出o链式队列n用单链表方式存储，队列中每个元素对于链表中的一个结点“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.2.2 顺序队列顺序队列 o使用顺序表来实现队列o用向量存储队列元素，并用两个变量分别指向队列的前端和尾端“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.676543210Q.frontQ.reark0k1k2Q.frontQ.rearQ.rearQ.frontk5队列空再进队一个元素如何？队列示意：普通队列示意：普通k4“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的溢出队列的溢出o上溢n当队列满时，再做进队操作，所出现的现象o下溢n当队列空时，再做删除操作，所出现的现象o假溢出n当 rear=MAXNUM时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）位置，这种现象称为假溢出“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6k4k5k6Q.frontQ.rearQ.rearQ.frontk6k5队列满队列示意：环形队列示意：环形k0k1k2k3Q.rearQ.front队列空k4“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6Q.rearQ.frontk1k2k7k6k5k4k3Q.frontQ.rear空队列队列满，判断(Q.rear+1)=Q.front队列示意：环形队列示意：环形“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序队列的类定义顺序队列的类定义 class arrQueue:public Queue private:int mSize;/存放队列的数组的大小int front;/表示队头所在位置的下标int rear;/表示队尾所在位置的下标T*qu;/存放类型为T的队列元素的数组public:/队列的运算集 arrQueue(int size)/创建队列的实例mSize=size+1;/浪费一个存储空间，以区别队列空和队列满qu=new T mSize;front=rear=0;arrQueue()/消除该实例，并释放其空间delete qu;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6新元素插入队列尾端新元素插入队列尾端1234frontrear1234frontrear5插入5到队列中“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的插入队列的插入bool arrQueue:enQueue(const T item)/item入队，插入队尾if(rear+1)%mSize)=front)cout 队列已满，溢出 endl;return false;qurear=item;rear=(rear+1)%mSize;/循环后继return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6从队列前端取出从队列前端取出/删除删除bool arrQueue:deQueue(T&item)/返回队头元素并从队列中删除if(front=rear)cout 队列为空 endl;return false;item=qufront;front=(front+1)%mSize;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的运行示意图队列的运行示意图frontrearfrontrear1234frontrearfrontrear1“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的运行示意图队列的运行示意图frontrearfrontrear5frontrear56789“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.63.2.3 链式队列链式队列o单链表队列 o链接指针的方向是从队列的前端向尾端链接 k0 k1 k2 kn-1.fr“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6链式队列的类定义链式队列的类定义template class lnkQueue:public Queue private:int size;/队列中当前元素的个数Link*front;/表示队头的指针Link*rear;/表示队尾的指针public:/队列的运算集 lnkQueue(int size)/创建队列的实例size=0;front=rear=NULL;lnkQueue()/消除该实例，并释放其空间clear();“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6链式队列的插入链式队列的插入/item入队，插入队尾bool lnkQueue :enQueue(const T item)if(rear=NULL)/空队列front=rear=new Link(item,NULL);else /添加新的元素rear-next=new Link(item,NULL);rear=rear-next;size+;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6链式队列的删除链式队列的删除/返回队头元素并从队列中删除bool lnkQueue :deQueue(T&item)Link*tmp;if(size=0)/队列为空，没有元素可出队cout 队列为空 data;tmp=front;front=front-next;delete tmp;if(front=NULL)rear=NULL;size-;return true;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6顺序队列与链式队列的比较顺序队列与链式队列的比较 o顺序队列 n固定的存储空间n方便访问队列内部元素o链式队列n可以满足浪涌大小无法估计的情况 n访问队列内部元素不方便“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6队列的应用队列的应用 o只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构。o调度或缓冲n消息缓冲器 n邮件缓冲器 n计算机的硬设备之间的通信也需要队列作为数据缓冲 n操作系统的资源管理 o宽度优先搜索“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6变种的栈或队列结构变种的栈或队列结构 o双端队列 o双栈 o超队列 o超栈“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6小结小结 o栈n栈的特点n栈的实现n栈的应用o队列n队列的特点n队列的实现n队列的应用“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.62008.6The EndThe EndThe EndThe EndThank You!Thank You!http:/ 张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，2008.62008.62008.62008.62008.62008.6。“十一五十一五十一五十一五十一五十一五”国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材