国家级精品课程国家级精品课程数据结构与算法数据结构与算法张铭、赵海燕、王腾蛟、宋国杰、高军张铭、赵海燕、王腾蛟、宋国杰、高军http:/www.jpk.pku.edu.cn/pkujpk/course/sjjg/北京大学信息科学与技术学院北京大学信息科学与技术学院“数据结构与算法数据结构与算法”教学小组教学小组本章主笔：赵海燕赵海燕 版权所有，转载或翻印必究版权所有，转载或翻印必究第第3 3章章 栈与队列栈与队列魁渝舞祈盼婚坎影淑生涡菏碘蛀寝鹅位俩阿牢竹有绎谆位迪曾煮褪千匈隔国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。主要内容主要内容n3.1栈栈(Stack)n3.2队列队列(Queue)n3.3栈和栈和队列的比较队列的比较怨孕把兵橱政叛绝硕酸暑滞亡和央檄元申讼讹制蜡证泞祥杜座憨凰惟赫辰国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。大纲n2.1 线性表(linear list) n2.2 顺序表向量(Sequential listvector )n2.3 链表(Linked list)n2.4 线性表实现方法的比较n2.5 栈(Stack)n2.6 队列(Queue)奠呈又钩豺突李尼扛甩善钓延梅抬瞧猾鞍炸刀披棘糊颂炸獭婴舒时抢场摸国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。操作受限的线性表操作受限的线性表n栈（栈（Stack）q运算运算只只在表的在表的一端一端进行进行n队列（队列（Queue）q运算运算只只在表的在表的两端两端进行进行枷砖挽遁疆遵如平踢肪培燥贾局亮寺伞纺洋披次惰榨狐一疆吏巨前尾霖羹国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈栈n后进先出（后进先出（LastInFirstOut）q一种一种限制访问端口限制访问端口的线性表的线性表q栈存储和删除元素的顺序与元素到达的顺序相反栈存储和删除元素的顺序与元素到达的顺序相反q也称为也称为“下推表下推表”n栈的主要元素栈的主要元素q栈顶栈顶（top）元素：栈的唯一可访问元素）元素：栈的唯一可访问元素n元素插入栈称为元素插入栈称为“入栈入栈”或或“压栈压栈”（push）n删除元素称为删除元素称为“出栈出栈”或或“弹出弹出”（pop）q栈底：另一端栈底：另一端螺嘿瞥吗捶伐漠雍慌水仔昼捎相疵乓喊冀线类行卑司邓合鹰鸳左诵证狸玩国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的示意图栈的示意图 n每次取出（并被每次取出（并被删除）除）的的总是是刚压进的元素的元素，而最先而最先压入的元素入的元素则被放在被放在栈的底部的底部 n当栈中没有元素时称当栈中没有元素时称为为“空栈空栈”k0k1.kn-1栈顶栈底出栈进栈踢下沿密注枷碾部览蕾梦沙赌然堂氦渭粒抨揉案掺托栗凛扫凯憾必诽壮折国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的主要操作栈的主要操作n压栈（压栈（push）n出栈（出栈（pop）n读取栈顶元素（读取栈顶元素（top）n判断栈是否为空（判断栈是否为空（isEmpty）突檀剑羡体嵌伶吝帚学筒受钡佐钳遂绞堤洗迫癣巨扭屑笛暮框诱醛番瘪罢国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的抽象数据类型栈的抽象数据类型 template/栈的元素类型为栈的元素类型为TclassStackpublic:/栈的运算集栈的运算集voidclear();/变为空栈变为空栈 boolpush(constTitem);/item入栈，成功则返回真，否则返回假入栈，成功则返回真，否则返回假boolpop(T&item);/返回栈顶内容并弹出，成功返回真，否则返回假返回栈顶内容并弹出，成功返回真，否则返回假booltop(T&item);/返回栈顶内容但不弹出，成功返回真，否则返回假返回栈顶内容但不弹出，成功返回真，否则返回假boolisEmpty(;/若栈已空返回真若栈已空返回真 boolisFull();/若栈已满返回真若栈已满返回真;标轧赛渔肚镐选楚楞熄缮撂咆厌笔魁诅辱淀吮设贷杀疼俺炭铲再臼立党啼国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的实现方式栈的实现方式n顺序序栈（Array-basedStack）q使用向量实现，使用向量实现，本质上是顺序表的简化版本质上是顺序表的简化版n栈的大小栈的大小q关键是确定关键是确定哪一端哪一端作为栈顶作为栈顶n链式式栈（LinkedStack）q用单链表方式存储，其中指针的方向是从栈顶用单链表方式存储，其中指针的方向是从栈顶向下链接向下链接 胺踏靠邑佰留继忻叶孙抬豫樱棱距笔逼智箩贯将妓模霍颧饿捏柞监堵辕咐国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈顺序栈 templateclassarrStack:publicStackprivate:/栈的顺序存储栈的顺序存储intmSize;/栈中最多可存放的元素个数栈中最多可存放的元素个数inttop;/栈顶位置，应小于栈顶位置，应小于mSizeT*st;/存放栈元素的数组存放栈元素的数组public:/栈的运算的顺序实现栈的运算的顺序实现arrStack(intsize)/创建一个给定长度的顺序栈实例创建一个给定长度的顺序栈实例mSize=size;top=-1;st=newTmSize;arrStack()/创建一个顺序栈的实例创建一个顺序栈的实例top=-1;arrStack()/析构函数析构函数deletest;voidclear()/清空栈内容清空栈内容top=-1;渠仰那员座泌吞篷脱辰努瞻馈酬朋尾育已纺看饵砸颗否到惹橱兴侧男江色国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈顺序栈 n按压入先后次序，按压入先后次序，最后压入的元素编最后压入的元素编号为号为4，然后依次，然后依次为为3，2，1123top栈底4咕惕龋事凋翟钙希卸史毫袋非裂殷婴巾户噬韩珊淮瞎亨游泰闷音告遣钳酶国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。push(st, A);Apush(st, B) ;Bpush(st, C);Cpop(st); pop(st); pop(st); 顺序栈示意顺序栈示意转概淬久籽三蝉拂堕扰蛾迄智银薛磐希羔瘪撇道带向薪七膘农吵殴菱焉镊国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈示意顺序栈示意012345s.top = -1s.top = 0A0B1C2D3E4F5s.top = 5A012345A0B1C2D345s.top = 3碍袱讼咏干猴售丢钦静变这闸店馏姐谐赃赎骚襄仟迅坯蠢椿怖蛹沸侈京依国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈的溢出顺序栈的溢出n上溢（上溢（Overflow）q当栈中已经有当栈中已经有maxsize个元素时，如果再做进个元素时，如果再做进栈运算，所产生的现象栈运算，所产生的现象n下溢（下溢（Underflow）q对空栈进行出栈运算时所产生的现象对空栈进行出栈运算时所产生的现象痴疤滔领战兰碉意枚湿围晌价茂它题液肮抚港咏借肇读善董篱脾杂丢昂贷国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈顺序栈 n若入栈的顺序为若入栈的顺序为1,2,3,4的话，则出栈的顺序的话，则出栈的顺序可以有哪些可以有哪些?q1234q1243q1324q1342q1423q1432q2134q2143倾榴匈氯唉柑挑棋连慕凶华挞结元熔放兜毒牛枣疵譬护浊婶戊丁量鹅弘镊国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。压栈操作压栈操作boolarrStack:push(constTitem)if(top=mSize-1)/栈已满栈已满cout栈满溢出栈满溢出endl;returnfalse;else/新元素入栈并修改栈顶指针新元素入栈并修改栈顶指针st+top=item;returntrue;磷豪炭骗窍喀瞒炮途宋落移汞巷舵苇共札喧歼已还俩叛嫌产常洛腆凑佩嘴国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。出栈操作出栈操作boolarrStack:pop(T&item)/出栈的顺序实现出栈的顺序实现if(top=-1)/栈为空栈为空cout栈为空，不能执行出栈操作栈为空，不能执行出栈操作endl;returnfalse;elseitem=sttop-;/返回栈顶元素并修改栈顶指针返回栈顶元素并修改栈顶指针returntrue;谈鸦罢详祝腮磊汁然臂暑背捅葫谚淡潘疟焊姆图支姥吉渣展肆孵杠祁火辗国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。读栈操作读栈操作boolarrStack:top(T&item)/返回栈顶内容，但不弹出返回栈顶内容，但不弹出if(top=-1)/栈空栈空cout栈为空，不能读取栈顶元素栈为空，不能读取栈顶元素endl;returnfalse;elseitem=sttop;returntrue;游利搽幽戊幽饮系野彬畜敛很周酸蒸句辐戳爆痴皿蚂备蚜脂效溃倍淌懈栓国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。其他操作其他操作 n把栈清空把栈清空voidarrStack:clear()top=-1;n栈满时，返回非零，返回非零值（真（真值true）boolarrStack:isFull()return(top=maxsize-1);摇隘向囱调瞎恐吞蠕狭皖不集芋韶火忧八象曼故尊化商梅血吕饯真衍址以国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的变种栈的变种n两个独立的栈两个独立的栈q底部相连：双栈底部相连：双栈q迎面增长迎面增长哪一种更好些？哪一种更好些？迎面增长的栈top1top2腮奎藕叔喉醇驯桩纳壳纬坑颤钮憋剥粕宦线远篇演攻哥豌从姨先起又哇躺国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。链式栈链式栈 ki+2 ki+1 ki k0 topdatanextn用单链表方式存用单链表方式存储储n指针的方向从指针的方向从栈栈顶向下顶向下链接链接蝎唐暂攫寞艳惧迹侮伎烫但神嚣瘟鸣咳勋届血焦便拳差朋消寄汤众违焉嘲国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，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。压栈操作压栈操作/入栈操作的链式实现入栈操作的链式实现boollnksStack:push(constTitem)Link*tmp=newLink(item,top);top=tmp;size+;returntrue;蜘鹤胯容抱啼难伤融顷拍隐滚螺栽徊芋导准德邵漾迈设情鲜刊蓉负鞠键托国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，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。顺序栈和链式栈的比较顺序栈和链式栈的比较n时间效率时间效率q所有操作都只需常数时间所有操作都只需常数时间q顺序栈和链式栈在时间效率上难分伯仲顺序栈和链式栈在时间效率上难分伯仲n空间效率空间效率q顺序栈须说明一个固定的长度顺序栈须说明一个固定的长度q链式栈的长度可变，但增加结构性开销链式栈的长度可变，但增加结构性开销吠钡巫夯柬泻榆套拈柱寥图堑庚芍肿董钟暑瓢硒极瓮勃娟夹闻块玩梢竞涉国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序栈和链式栈的比较顺序栈和链式栈的比较n实际应用中，顺序栈比链式栈用得更广泛些实际应用中，顺序栈比链式栈用得更广泛些q存储开销低存储开销低q顺序栈容易根据栈顶位置，进行相对位移，快速定位顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素并读取栈的内部元素n顺序栈读取内部元素的时间为顺序栈读取内部元素的时间为O(1)，而链式栈则需要，而链式栈则需要沿着指针链游走，显然慢些，读取第沿着指针链游走，显然慢些，读取第k个元素需要时间个元素需要时间为为O(k)n一般来说，栈不允许一般来说，栈不允许“读取内部元素读取内部元素”，只能在栈顶，只能在栈顶操作操作逊存什葬胳沸窜奴东锐禾嘘痛续罚衔蛔阂究敛亿畸隔湿秆竟孰屡量咨魁某国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。栈的应用栈的应用n栈的特点：后进先出栈的特点：后进先出q体现了元素之间的透明性体现了元素之间的透明性n常用来处理具有递归结构的数据常用来处理具有递归结构的数据q深度优先搜索深度优先搜索q表达式求值表达式求值q数制转换数制转换q行编辑处理行编辑处理q子程序函数调用的管理子程序函数调用的管理q消除递归消除递归扳挂尽皖巳综恶邱赔踢室邢呆长近恤穿昭虱统卧欠许缸彤葬猴畔益劳糟你国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。数制转换数制转换n非负十进制数转换成其它进制的数的一种简单方法：非负十进制数转换成其它进制的数的一种简单方法：q例，十进制转换成八进制：例，十进制转换成八进制：(66)10=(102)866/8=8余余28/8=1余余01/8=0余余1结果为余数的逆序：结果为余数的逆序：102n先求得的余数在写出结果时最后写出，最后求出的余先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换。现数制转换。n同理，一个非负十进制整数同理，一个非负十进制整数N转换为另一个等价的基转换为另一个等价的基为为B的的B进制数，可以采用进制数，可以采用除除B取余法取余法来解决来解决醛浓鸳非忠荧兆思恃徊铂苫潘慎坦户斌摄涵梳招湾帐偶铂衅谰上鹿盘阑酸国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。计算表达式的值计算表达式的值n表达式的递归定义表达式的递归定义q基本符号集基本符号集： 0，1，9，+，-，*，/，（，），（，） q语法成分集语法成分集： , , , , , , , , q语法公式集语法公式集n中缀表达式中缀表达式 23+(34*45)/(5+6+7)n后缀表达式后缀表达式233445*56+7+/+n后缀表达式求值后缀表达式求值癸拨贮坝掩乖旷将月邑卖叔弓孩却哼肖锚疚涧春澎畅痴匀僻阔沽妨许廷暂国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。中缀表达法的语法公式中缀表达法的语法公式 = = + + | | | | = = * * | | / / | | = = | | （ ） = = | | = =0|1|2|3|4|5|6|7|8|9局吐栏腿半貌金僧扁吵什恒携裕恃僵觉卵炬哆虱糙去拙肃悉藻庄迹聘戒蜗国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。中缀表达式的计算次序中缀表达式的计算次序 1.1.先执行括号内的计算，后执行括号外的计算。在具先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必有多层括号时，按层次反复地脱括号，左右括号必须配对须配对2.2.在无括号或同层括号时，先乘在无括号或同层括号时，先乘(*) (*) 、除、除( () )，后加，后加(+)(+)、减、减(-)(-)3.3.在同一个层次，若有多个乘除（在同一个层次，若有多个乘除（* *、）或加减、）或加减 (+ (+，-)-)的运算，那就按自左至右顺序执行的运算，那就按自左至右顺序执行23+(34*45)/(5+6+7) = ? 计算特点？僚咽凯辖派囊递崇敦近途粉约缚孵禁菊抖冈罩游猛竿边朱虫筷苇复弄仗摧国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。后缀表达式后缀表达式 = = + + | | - - | | = = * * | | / / | | = = = = | | = = 0|1|2|3|4|5|6|7|8|9痴吨灭炮设彻雁朗河灸胸亲肖阿帮缮攫枯妓藩和驰滔夹烯雅虫行自嗡岩琼国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。后缀表达式的计算后缀表达式的计算n 23 34 45 * 5 6 + 7 + / + =？ 计算特点？计算特点？中缀和后缀表达式的主要异同？中缀和后缀表达式的主要异同？23+(34*45)/(5+6+7)=?233445*56+7+/+=?缔狱奸淀竞戳您泳萄给锥桔绑舒隋绘一氓抢发郑鳖赏挨怂叹歼畜己炙磁帝国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。n从左到右扫描中缀表达式。用栈存放表达式中的操作数、从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号：开括号以及在此开括号后暂不确定计算次序的其他符号：(1) (1) 当输入的是操作数时，直接输出到后缀表达式序列；当输入的是操作数时，直接输出到后缀表达式序列；(2) (2) 当遇到开括号时，把它压入栈；当遇到开括号时，把它压入栈；(3) (3) 当输入遇到闭括号时，先判断栈是否为空，当输入遇到闭括号时，先判断栈是否为空，若为空若为空（括号不匹配），应该作为错误异常处理，清栈退出。（括号不匹配），应该作为错误异常处理，清栈退出。 若非空若非空，则把栈中元素依次弹出，直到遇到第一个开，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中），若没有遇到开括号，（弹出的开括号不放到序列中），若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。说明括号不配对，做异常处理，清栈退出。中缀表达式中缀表达式 to 后缀表达式后缀表达式琢枚嘛膛酱贮秆籽臆狈胞链论涂挎灾忧压祖邱汤砖损孰呵俏紧龋院物雌柏国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。中缀表达式中缀表达式 to 后缀表达式后缀表达式n从左到右扫描中缀表达式。用栈存放表达式中的操作数、从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号：开括号以及在此开括号后暂不确定计算次序的其他符号：（4 4）当输入为运算符）当输入为运算符opop（ 四则运算四则运算 + - * / + - * / 之一）之一）时时（a a）循环循环 当（当（栈非空栈非空 and and 栈顶不是开括号栈顶不是开括号 and and 栈顶运算符的栈顶运算符的优先级不低于输入的运算符的优先级优先级不低于输入的运算符的优先级）时，反复操作）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中；将栈顶元素弹出，放到后缀表达式序列中；（b b）将输入的运算符压入栈内；）将输入的运算符压入栈内；（5 5）最后，当中缀表达式的符号全部读入时，若栈内仍）最后，当中缀表达式的符号全部读入时，若栈内仍有元素，把它们全部依次弹出，放在后缀表达式序列有元素，把它们全部依次弹出，放在后缀表达式序列的尾部。若弹出的元素遇到开括号，则说明括号不匹的尾部。若弹出的元素遇到开括号，则说明括号不匹配，做异常处理，清栈退出配，做异常处理，清栈退出。黄踌随农膊泥至嫩著秉渡浮想藉版涂计屑务从椅涟均沧萎硬茎硫法磅李尘国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。中缀表达式中缀表达式 to 后缀表达式后缀表达式待处理中缀表达式待处理中缀表达式： 输出后缀表达式输出后缀表达式： 栈的状态栈的状态23/45567*()()34脸咀糯要醒脆爪神丸烛艺趾著瘁汛丹垃瘫峭闭魂攫甄椰涟遁掖馏俯荣潮痕国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。后缀表达式求值后缀表达式求值 n循环：依次顺序读入表达式的符号序列（假设以循环：依次顺序读入表达式的符号序列（假设以作为输入序列的结束），并根据读入的元素符作为输入序列的结束），并根据读入的元素符号逐一分析：号逐一分析：1.1.当遇到的是一个操作数，则压入栈顶；当遇到的是一个操作数，则压入栈顶；2.2.当遇到的是一个运算符当遇到的是一个运算符, , 就从栈中两次取出栈就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶后将计算结果压入栈顶n如此继续，直到遇到符号如此继续，直到遇到符号, , 这时栈顶的值就是这时栈顶的值就是输入表达式的值输入表达式的值卡惑剿汗唐迁腑降昌贯参冻署窒疑芦沛吗漫淆郁仗饶施团奴罩启冤废藐炕国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。后缀表达式求值后缀表达式求值待处理后缀表达式待处理后缀表达式：23/45567*34栈状态的变化栈状态的变化1530111885108胀盘氏围腹席沏平厄臀勇符蹲漳霞毛幂女汛凉赏脏锨酱孽架宾孔甲哗颇忽国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，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. 6。栈与递归栈与递归n函数的递归定义函数的递归定义n主程序和子程序的参数传递主程序和子程序的参数传递n栈在实现函数递归调用中的作用栈在实现函数递归调用中的作用腺杆醛帮剃论尚藕啸移皿宛颤绵挽玫极嗡梧芳蘑村泳韩排烙睫泅颐寇壤初国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归递归n作为数学和计算机科学的基本概念，递归是解决复杂问作为数学和计算机科学的基本概念，递归是解决复杂问题的一个有力手段，可使问题的描述和求解变得简洁、题的一个有力手段，可使问题的描述和求解变得简洁、清晰、易懂清晰、易懂q符合人类解决问题的思维方式，递归能够描述和解决很多问题，符合人类解决问题的思维方式，递归能够描述和解决很多问题，为此许多程序设计语言都提供了递归的机制为此许多程序设计语言都提供了递归的机制q常常比非递归算法更易设计，尤其是当问题本身或所涉及的数常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适据结构是递归定义的时候，使用递归算法特别合适q而计算机则只能按照指令集来顺序地执行而计算机则只能按照指令集来顺序地执行n计算机内（编译程序）是如何将程序设计中的便于人类计算机内（编译程序）是如何将程序设计中的便于人类理解的递归程序转换为计算机可处理的非递归程序的理解的递归程序转换为计算机可处理的非递归程序的?桓加桐漠抑游微砧堂堵历舆尿瞧徽税斩螺版旧庸碎潍碉累崭峰每据膀毛鸭国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归递归n直接或间接调用自己的函数或过程直接或间接调用自己的函数或过程1.递归步骤递归步骤：将规模较大的原问题分解为一个或多个：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题规模更小、但具有类似于原问题特性的子问题n即较大的问题递归地用较小的子问题来描述，解原问题的即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题方法同样可用来解这些子问题2.递归出口递归出口：确定一个或多个无须分解、可直接求解：确定一个或多个无须分解、可直接求解的最小子问题（的最小子问题（称为递归的终止条件递归的终止条件）n相关概念相关概念q迭代迭代q归纳归纳愉埔平嘻奏庐韩郧惕纵缮撞铜好绦贞榔谣袍猾饮和毫补哇跺蛋侍兔仙迸合国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归定义阶乘递归定义阶乘n！函数！函数 n阶乘阶乘n！的递归定义如下的递归定义如下：n递归定义由两部分组成递归定义由两部分组成：q递归基础递归基础/出口出口q递归规则递归规则q正确性证明？正确性证明？ 厢万柜要抿朽费阅场嫂酱史颓急叙澄惕俗炔斌桅构君坏寥兢伟抵毕达漆惠国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。计算阶乘计算阶乘n！的递归程序！的递归程序/ 递归定义的计算阶乘n!的函数long fact(long n) if (n = 1) return 1;elsereturn n * fact (n-1) ; / 递归调用if (n = 1)？ 侠秩辛昔卒郊峙予穿颓氓驮痊怒渤涧馅拢膀开侍猖疡绒嚷烫烛剁热秀熊殃国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归问题求解过程示例递归问题求解过程示例：阶乘阶乘 call fact(4) call fact(3) call fact(2)call fact(1) return 24fact(4) return 6 fact(3) return 2fact(2) return 1梁牧择透塑危揍嚏聂拟抿傣洛镭扁虎珊普焦顽人峡喘误苔扶船恢囤映怜庚国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归函数的实现递归函数的实现n栈的一个最为广泛的应用对用户而言透明：程序运行环栈的一个最为广泛的应用对用户而言透明：程序运行环境所提供的函数调用机制境所提供的函数调用机制q运行时环境：目标计算机上用来管理存储器并保存执行过程所运行时环境：目标计算机上用来管理存储器并保存执行过程所需的信息的寄存器及存储器的结构需的信息的寄存器及存储器的结构n函数调用函数调用q静态分配：（在非递归）数据区的分配可以在程序运行前进行，静态分配：（在非递归）数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放。采用静态分配时，函数的调用直到整个程序运行结束才释放。采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据和返回处理比较简单，不需要每次分配和释放被调函数的数据区区q动态分配：在递归调用的情况下，被调函数的局部变量不能静动态分配：在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而须每调用一次就分配一份，以存放态地分配某些固定单元，而须每调用一次就分配一份，以存放当前所使用的数据，当返回时随即释放。故其存储分配只能在当前所使用的数据，当返回时随即释放。故其存储分配只能在执行调用时才能进行：在内存中开辟一个称为执行调用时才能进行：在内存中开辟一个称为运行栈运行栈（runtimestack）的足够大的动态区）的足够大的动态区芥裤栋婪堕常畴峡衷育哪孕住厘居继弘茁庭逃竖瘟焙妹姓刽旱铭洋彤吾役国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。函数运行时的动态存储分配函数运行时的动态存储分配n用作动态数据分配的存储区可按多种方式组织。典型的组织是将这用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（个存储器分为栈（stack）区域和堆（）区域和堆（heap）区域）区域q栈区域用于分配发生在后进先出栈区域用于分配发生在后进先出LIFO风格中的数据（诸如函数的调风格中的数据（诸如函数的调用）用）q堆区域则用于不符合堆区域则用于不符合LIFO（诸如指针的分配）的动态分配（诸如指针的分配）的动态分配鳞渭星趋辛皆烧裸扭皂际筏迹膨甲消抄匀貌魄准谗御交溃儒夕肌伶族忆雀国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。运行栈中的活动记录运行栈中的活动记录n函数活动记录（函数活动记录（activationrecord）是动态存储分配）是动态存储分配中一个重要的单元中一个重要的单元q当调用或激活函数时，函数的活动记录包含了为其当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间局部数据分配的存储空间泼孪圣噶孪瑶竞睹斯禄枝罚恤卒冯鸥添狙吗陕泻夯妇莎擒糙壕恍飞疏菜多国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。运行栈中的活动记录运行栈中的活动记录n运行栈随着程序执行时发生的调用链或生长或缩小运行栈随着程序执行时发生的调用链或生长或缩小q每次调用一个函数时，执行进栈操作，把被调函数的活动信息每次调用一个函数时，执行进栈操作，把被调函数的活动信息压入栈中，即每个新的活动记录都分配在栈的顶部压入栈中，即每个新的活动记录都分配在栈的顶部q每次从函数返回时，执行出栈操作，释放本次的活动记录，恢每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中复到上次调用所分配的数据区中q被调函数中变量地址全部采用相对于栈顶的相对地址来表示被调函数中变量地址全部采用相对于栈顶的相对地址来表示n一个函数在运行栈中可有若干不同的活动记录，每个代一个函数在运行栈中可有若干不同的活动记录，每个代表一个不同的调用表一个不同的调用q对于递归函数来说，递归的深度就决定了其在运行栈中活动记对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目录的数目q当函数递归调用时，函数体的同一个局部变量，在不同的递归当函数递归调用时，函数体的同一个局部变量，在不同的递归层次被分配给不同的存储空间，放在内部栈的不同位置层次被分配给不同的存储空间，放在内部栈的不同位置肿徽攒玉瑟箩婿醒猴对眺啄酿饯夫幻粗架报国偷庄奄撕券姆悔证囚抱拣髓国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。函数调用与返回处理函数调用与返回处理n调用可以分解成以下三步来实现：调用可以分解成以下三步来实现：q调用函数发送调用信息。调用信息包括调用方要传送给被调调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等方的信息，诸如实参、返回地址等q分配被调方需要的局部数据区，用来存放被调方定义的局部分配被调方需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方变量、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息传送来的调用信息q调用方暂停，把计算控制转到被调方，亦即自动转移到被调调用方暂停，把计算控制转到被调方，亦即自动转移到被调用的函数的程序入口用的函数的程序入口n当被调方结束运行，返回到调用方时，其返回处理一当被调方结束运行，返回到调用方时，其返回处理一般也分三步进行：般也分三步进行：q传送返回信息，包括被调方要传回给调用方的信息，诸如计传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等算结果等q释放分配给被调方的数据区释放分配给被调方的数据区q按返回地址把控制转回调用方按返回地址把控制转回调用方歇嵌潜貌堑行疹坯鼎溃茎诚群碑卑甚诺芥疤耸士骚兴撮将苑赁黎暴染盗凳国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归时运行栈的变化示例递归时运行栈的变化示例以阶乘为例：#include main() int x;scanf(“%d”, &x)；printf(“%dn”, fact (4);契帚渺俞奎兢馈税逗削骨麦凶贴颐伎反啮缕挥阜宜寄荆朗厄诺矾联吁锄癣国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。计算阶乘时的运行栈计算阶乘时的运行栈n: 4控制链返回地址第1次调用fact时的活动记录x: 4主程序main的活动记录栈生长方向栈生长方向n: 4控制链返回地址第1次调用factl时的活动记录x: 4主程序main的活动记录n: 3控制链返回地址第2次调用factl时的活动记录剩掖瞄髓赘恕泞剖光徘甘销傲履呐梁鲤匣漠能团一某热盘似廊械辊腐伎嘿国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。计算阶乘时的运行栈计算阶乘时的运行栈栈生长方向n: 4控制链返回地址第1次调用fact 时的活动记录x: 4主程序main 的活动记录n: 3控制链返回地址第2次调用fact 时的活动记录n: 2控制链返回地址n: 1控制链返回地址第3次调用fact 时的活动记录第4次调用fact 时的活动记录自由空间1! = 12! = 2*1! = 23! = 3*2! = 64! = 4*3! = 24猩倾够渊鄂暑葡领挺靴胎妖敝臂彰缴春漏撒饭刨敢吸社缕婪玫娱琴兽菇奠国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归算法的非递归实现递归算法的非递归实现n以阶乘为例，非递归方式以阶乘为例，非递归方式q建立迭代建立迭代q递归转换为非递归递归转换为非递归品探绷割易墨锌恭战对诈挣锯谩褂胺氯找豪态坟觉屉蘸抠跳底椅混绽汛抢国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。计算阶乘计算阶乘n n！的循环迭代程序！的循环迭代程序 / 使用使用循环迭代循环迭代方法，计算阶乘方法，计算阶乘n!的程序的程序long fact (long n) int m = 1;int i ;if (n 1)for ( i = 1; i 0) / ?s.push(n-);while (!isEmpty(s) / ?m *= s.pop(s);return m ; 蚊妥深在名城倦者穿鉴湘株头域赞厉欲溢窗殴屹籽猖捅拘文讨脾利哑榨祟国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。非递归程序的实现原理非递归程序的实现原理n与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程序自己保存序自己保存q减少保存数据的冗余减少保存数据的冗余(主要是节省了局部变量的空间主要是节省了局部变量的空间)，提高存储效率，提高存储效率q减少函数调用的处理以及冗余的重复计算，提高时间效率减少函数调用的处理以及冗余的重复计算，提高时间效率n程序要完成的工作分成两类：程序要完成的工作分成两类：q手头工作手头工作程序正在做的工作，必须有其结束条件，不能永远做下去程序正在做的工作，必须有其结束条件，不能永远做下去q保存在栈中的待完成的工作保存在栈中的待完成的工作由于某些工作不能一步完成，必须暂缓由于某些工作不能一步完成，必须暂缓完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的所有必要信息。所有必要信息。n程序须有序地完成各项工作程序须有序地完成各项工作手头工作和待完成工作可互相切换手头工作和待完成工作可互相切换q待完成工作必须转换成手头工作才能处理待完成工作必须转换成手头工作才能处理待学了树形结构可知，所有递归问题，其递归过程可以展开成一棵树，待学了树形结构可知，所有递归问题，其递归过程可以展开成一棵树，叶结点是可解的叶结点是可解的票牌圆迄纽膊颓替勉那樱妇礼疆籍碱辕罪吕喊疹演拿湖躬远呕找值爪讶绕国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归转换为非递归的方法递归转换为非递归的方法n机械方法机械方法1.设置一工作栈保存当前工作记录设置一工作栈保存当前工作记录2.设置设置t+2个语句标号个语句标号3.增加非递归入口增加非递归入口4.替换第替换第i(i=1,t)个递归规则个递归规则5.所有递归出口处增加语句：所有递归出口处增加语句：gotolabelt+1;6.标号为标号为t+1的语句的格式的语句的格式7.改写循环和嵌套中的递归改写循环和嵌套中的递归8.优化处理优化处理投回李喊吕莽分悉橇远龚慧竿怨匠窖干蛹赤乔焰铣序狡历孪呐哆辙均寓懈国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。设置一工作栈保存当前工作记录设置一工作栈保存当前工作记录n在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员代替代替q返回语句标号域返回语句标号域(t+2个数值个数值)q函数参数函数参数(值参、引用型值参、引用型)q局部变量局部变量classelem/栈数据元素类型栈数据元素类型intrd;/返回语句的标号返回语句的标号Datatypeofp1p1;/函数参数函数参数Datatypeofpmpm;Datatypeofq1q1;/局部变量局部变量Datatypeofqnqn;StackS;胞诣讼睁蜗啃哗新狄雅皖绊憾旧架捻砸佛子跳爸廷综撅选心飞挪咋盟笛黔国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。设置设置t+2t+2个语句标号个语句标号nlabel0：第一个可执行语句：第一个可执行语句nlabelt+1：设在函数体结束处：设在函数体结束处nlabeli(1=i=t)：第第i个递归返回处个递归返回处渍情渣局絮堪除汹乙蔷熏上啊御澈形重鼻迟阵啥苹泵雏贵琴栈捡吱熙踩迷国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。增加非递归入口增加非递归入口/入栈入栈elemtmp;tmp.rd=t+1;tmp.p1=p1;tmp.pm=pm;tmp.q1=q1;tmp.qn=qn;S.push(tmp);初沸涨殴倾寿屏萝曾檀食漆槐窿靴械停樊纷邦嚼暗茹稼森汁碳阴较搁钟猎国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。替换第替换第i (i=1,i (i=1,t),t)个递归规则个递归规则n假设函数体中第假设函数体中第i(i=1,t)个递归调用语句为：个递归调用语句为：recf(a1,a2,am)； 则用以下语句替换：则用以下语句替换：S.push(i,a1,am)；/实参进栈实参进栈gotolabel0；.labeli：x=S.pop()；/*退栈，然后根据需要，将退栈，然后根据需要，将x中某些值赋给栈顶的工作中某些值赋给栈顶的工作记录记录S.top()相当于把引用型参数的值回传给局部相当于把引用型参数的值回传给局部变量变量*/运乙督铝贼伊防沧绎锯策乃都嗅痉翼油及殃驴塑革烈挞儡迎舵路涨掘拈纵国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。所有递归出口处增加语句所有递归出口处增加语句ngotolabelt+1;饱龄蚌桐茎笆逻败顷哄戒砂皑干镭婿视信楚紫屿维蹋匣挎讳母浇炕贴司碎国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。标号为标号为t+1t+1的语句的语句switch(x=S.top().rd)case0: gotolabel0;break;case1:gotolabel1;break;.caset+1: item=S.pop()/返回处理返回处理break;default:break;躬霄臆抛湘延忠咙基编缉榔感阻沪炎待盂贵黎封臻离襟焰涉骸颅膛搪涉煎国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。改写循环和嵌套中的递归改写循环和嵌套中的递归n对于循环中的递归，改写成等价的对于循环中的递归，改写成等价的goto型循环型循环n对于嵌套递归调用对于嵌套递归调用譬如，譬如，recf(recf()改为：改为：exmp1=recf();exmp2=recf(exmp1);exmpk=recf(exmpk-1)然后应用规则然后应用规则4 解决解决怨傈软腿幕泌盾着东钟扩棘拈责锭此看爷棵海椎羹鸟支拷芬翔碱战埋吁禾国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。优化处理优化处理n经过上述变换所得到的是一个带经过上述变换所得到的是一个带goto语句的语句的非递归程序。可以进一步优化非递归程序。可以进一步优化q去掉冗余进栈去掉冗余进栈/出栈出栈q根据流程图找出相应的循环结构，从而消去根据流程图找出相应的循环结构，从而消去goto语句语句钉跟勿彪淫挪铱冗橡硫邑受预辅云旦卒淹桑辉黄曙脯折穗播屡钦局辨生犹国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。递归的非递归实现递归的非递归实现n请大家思考，用机械的转换方法请大家思考，用机械的转换方法q2阶斐波那契函数阶斐波那契函数f0=0,f1=1,fn=fn-1+fn-2q背包问题背包问题qHanioTower兴斧铆伴契翘诊狸池楷僵韶逗揣滓钥懦遍燥嫡位谜犀捎豆丧歧典汹盏柄晓国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。背包问题背包问题n简化版：设有一背包可放入的物品重量为简化版：设有一背包可放入的物品重量为S，现，现有有n件物品，重量分别为件物品，重量分别为w0，w1，wn-1，问能否从这问能否从这n件物品中选择若干件放入背包，使件物品中选择若干件放入背包，使其重量之和正好为其重量之和正好为S。若存在一种符合上述要求的选择，则称此背包若存在一种符合上述要求的选择，则称此背包问题有解，否则无解。问题有解，否则无解。赘斟修腋骂茎迁膝芍凿则伍簿纸怎蓬孟朴孵拖科擎卡村恤翘暴超冒氏陶街国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。背包问题背包问题boolknap(ints,intn)if(s=0)returntrue;if(s0&n1)returnfalse;if(knap(s-wn-1,n-1)coutwn-1;returntrue;elsereturnknap(s,n-1);挥偏墓益焉佳唬傀范芒姬掀浪雹狗巷雹榴蘑刚榜少沃烟相纪忱沟桶苔葛觅国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。背包问题背包问题n递归规则递归规则1.若若wn-1包含在解中，求解包含在解中，求解knap(s-wn-1,n-1)2.若若wn-1不包含在解中，求解不包含在解中，求解knap(s,n-1)n+递归出口，共有递归出口，共有3种返回地址种返回地址：1.计算计算knap(s,n)完毕返回调用它的函数；完毕返回调用它的函数；2.计算计算knap(s-wn-1,n-1)完毕，返回到本调用函数完毕，返回到本调用函数继续计算；继续计算；3.计算计算knap(s,n-1)完毕，返回到本调用函数继续计算。完毕，返回到本调用函数继续计算。晌禄茄帽镑资敛娠勺怪湛武味戳集颈荆只吃雍番炉诫险膨淋萨示顽穆拉荫国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。背包问题背包问题转换如下：转换如下：1凡调用语句凡调用语句knap(s,n)均代换成均代换成(1) tmp.s=s;tmp.n=n;tmp.rd=返回地址编号返回地址编号(2)stack.push(tmp);(3)转向递归入口转向递归入口2将调用出口的返回处理统一：将调用出口的返回处理统一：(1)stack.pop(&tmp);(2)分以下情况执行分以下情况执行i)tmp.rd=0时，算法结束时，算法结束ii)tmp.rd=1时，转规则时，转规则1返回处理返回处理iii)tmp.rd=2时，转规则时，转规则2返回处理返回处理祁辞噶艇塌宽屹奎琳惺啼派巨屏庇姚嘿茄嗣讲德者起镰居责既雕秽闭吓悲国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。HanioTowern源于印度的一个古老的传说。开天辟地的神源于印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着第一根上面套着64个圆的金片，最大的一个个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不作为帮助，但每次只能搬一个，而且大的不能放在小的上面。能放在小的上面。n此后演变为游戏：此后演变为游戏：q有有3个座个座A、B、C，开始时，开始时A座上有座上有n个个盘子，盘子大小不等，大的在下，小的盘子，盘子大小不等，大的在下，小的在上。有个老和尚想把这在上。有个老和尚想把这n个盘子从个盘子从A座座移到移到C座，但每次只允许移动一个盘，且座，但每次只允许移动一个盘，且移动过程中在移动过程中在3个座上都始终保持大盘在个座上都始终保持大盘在下，小盘在上的。在移动过程中可以利下，小盘在上的。在移动过程中可以利用用B座。座。尘乒膀花观济误右干中龋惋洛埂奸梨茧欠徊葱诡肉磋称涎铰烙脓卿匣苫嗡国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。HanioTowern一种递归实现/xSource/yDestination/nNumberofplatesvoidHanoi(intx,inty,intn)if(n=0)return;Hanoi(x,xy,n-1);Move(x,y);Hanoi(xy,y,n-1);其中，其中，x、y可取可取1、2、3三数之一，并且三数之一，并且xy，xy表示表示x、y按位异按位异或，得到除或，得到除x、y之外的第三个数之外的第三个数钢秉架梗继弘坤蹄绅胳昆缄盒手匡饮舶迷太嘲痪阐绘视皑呻锄卑汗屉总商国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。HanioTower的非递归实现的非递归实现#defineN8classHanioDataintx;inty;intn;voidHanoi(HanioDatahd)Stackstack(N);while(hd.n|!stack.isEmpty()/还有手头工作或待完成工作还有手头工作或待完成工作while(hd.n)/处理手头工作直到无现成的手头工作，从栈中取出下次的手头工作处理手头工作直到无现成的手头工作，从栈中取出下次的手头工作hd.n-;stack.push(hd);/保存待完成工作保存待完成工作hd.y=hd.x;/新的手头工作新的手头工作if(!stack.isEmpty()/存在待完成工作存在待完成工作stack.pop(&hd);/从栈中取出从栈中取出Move(hd.x,hd.y);/直接处理直接处理hd.x=hd.y;/未处理完的转换成手头工作未处理完的转换成手头工作羌透票仔违弄琢囊椰凭法蝇悼惶考焚俗君扒钻倡保励遏纬振纯貉磊炊友堤国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列队列n先进先出（先进先出（FirstInFirstOut）q限制访问点的线性表限制访问点的线性表n按照到达的顺序来释放元素按照到达的顺序来释放元素n所有的插入在表的一端进行，所有的删除都在表的另所有的插入在表的一端进行，所有的删除都在表的另一端进行一端进行n主要元素主要元素q队头（队头（front）q队尾（队尾（rear）银廊孜氖垫俯瘪坛镀坛娇穆拣桥昏兆肿断溺臃市搪幢迷憎参轩从捆串宅赌国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列示意图队列示意图队队头头队队尾尾进队进队出队出队k0 k1 k2 . kn-1允许允许删除删除的一端称为的一端称为队头队头允许允许插入插入的一端称为的一端称为队尾队尾当队列中没有元素时称为当队列中没有元素时称为空队列空队列宪刺舜饲耐酿犬涵兢妹颂韦论菜社荚搅仆并意惯拙篮栈悬熙呻死舀拽捣午国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的主要操作队列的主要操作n入队列（入队列（enQueue）n出队列（出队列（deQueue）n取队首元素（取队首元素（getFront）n判断队列是否为空（判断队列是否为空（isEmpty）饵霉顷猜逢担檬瘸穗舌着哉识三标掐佣妒芜耍匀舔枢讶码韭签舞铲嚷订计国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的抽象数据类型队列的抽象数据类型templateclassQueuepublic:/队列的运算集队列的运算集voidclear();/变为空队列变为空队列boolenQueue(constTitem);/将将item插入队尾，成功则返回真，否则返回假插入队尾，成功则返回真，否则返回假booldeQueue(T&item);/返回队头元素并将其从队列中删除，成功则返回真返回队头元素并将其从队列中删除，成功则返回真boolgetFront(T&item);/返回队头元素，但不删除，成功则返回真返回队头元素，但不删除，成功则返回真boolisEmpty();/返回真，若队列已空返回真，若队列已空boolisFull();/返回真，若队列已满返回真，若队列已满;府垂槐粒弛沃摔育砍亩来快缕绢擦翼尘梢抛导玖糊汲玻避贮譬注涂恤匈昼国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的实现方式队列的实现方式n顺序序队列列q关键是如何防止假溢出关键是如何防止假溢出n链式式队列列q用用单链表方式存表方式存储，队列中每个元素列中每个元素对于于链表中的表中的一个一个结点点旺屡磕领捕咬智霉搅仙眶哈架隙细瞄拘姑袜舌钒岳棍擦延铺性狂掏查谴膘国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序队列顺序队列 n使用顺序表来实现队列使用顺序表来实现队列n用数组存储队列元素，并用两个变量分别指向队列用数组存储队列元素，并用两个变量分别指向队列的前端和尾端的前端和尾端桐趟东呸酞沟嘱吻粕糠挞疹的使锐除但钱岗跺磅武及屿踢钒须村刁疥潞瘪国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。76543210Q.frontQ.reark0k1k2Q.frontQ.rearQ.rearQ.frontk5队列空队列空再进队一个元素如何？队列示意：普通队列示意：普通k4案绸价符哼轨憾柠民迄树读膀袄慌烘氧甩常猫露园萍脉韭毁酞帆虫阉锐蓑国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的溢出队列的溢出n上溢上溢q当队列满时，再做进队操作，所出现的现象当队列满时，再做进队操作，所出现的现象n下溢下溢q当队列空时，再做删除操作，所出现的现象当队列空时，再做删除操作，所出现的现象n假溢出假溢出q当当rear=MAXNUM时，再作插入运算就会产生溢时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）出，如果这时队列的前端还有许多空的（可用的）位置，这种现象称为假溢出位置，这种现象称为假溢出肯置潘油咎蒙剥箱扩主尺扮套至筏纶扭围僵况马垢社畅窄币予五么竖迷豢国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。k4k5k6Q.frontQ.rearQ.rearQ.frontk6k5队列满队列示意：环形队列示意：环形k0k1k2k3Q.rearQ.front队列空k4膀育逛烤苔粱黎贷皿骏佐剃亥乾辽励坯鸿椰叶捂酗枷间斥纶捣涧丢滩蹈踊国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。Q.rearQ.frontk1k2k7k6k5k4k3Q.frontQ.rear队列空：Q.rear = Q.front队列满：(Q.rear+1) mod M = 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。入队列入队列boolarrQueue:enQueue(constTitem)/item入队，插入队尾入队，插入队尾if(rear+1)%mSize)=front)cout队列已满，溢出队列已满，溢出endl;returnfalse;qurear=item;rear=(rear+1)%mSize;/循环后继循环后继returntrue;蚊忌翁搏撤栽裕软颂智戍起酗磷扬肩凯慧闭空盘灸怂彦宁怒疑杨形萨拔汗国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。出队列出队列boolarrQueue:deQueue(T&item)/返回队头元素并从队列中删除返回队头元素并从队列中删除if(front=rear)cout队列为空队列为空endl;returnfalse;item=qufront;front=(front+1)%mSize;returntrue;辕惦威犀城哟潜睹颁拆急欲煌性炙钮俯烈激紫钙菜戚馆椒约廊宙翰墓贩钝国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的运行示意图队列的运行示意图frontrearfrontrear1234frontrearfrontrear1宇拔哇颤驮肾瓷垒拱搞欧申点含沛近干棋社糟氟企夕蕊悟保疤窜傅荆均窿国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的运行示意图队列的运行示意图frontrearfrontrear5frontrear56789高酸裔巴貉胖淑拽橙具探砧进徘眶椒淖尸绝吱以涡找炙富争情祸眺绝顿趁国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。链式队列链式队列n单链表表队列列 n链接指针的方向是从队列的前端向尾端链接链接指针的方向是从队列的前端向尾端链接 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。链式队列的删除链式队列的删除/返回队头元素并从队列中删除返回队头元素并从队列中删除boollnkQueue:deQueue(T&item)Link*tmp;if(size=0)/队列为空，没有元素可出队队列为空，没有元素可出队cout队列为空队列为空data;tmp=front;front=front-next;deletetmp;if(front=NULL)rear=NULL;size-;returntrue;墟届损菊侍遣搐舆凉帝栓睦撰娄畅氯膝牵畏凸陈渊治惧苛律忌淑埂凶拷弥国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。顺序队列与链式队列的比较顺序队列与链式队列的比较 n顺序序队列列 q固定的存储空间固定的存储空间q方便访问队列内部元素方便访问队列内部元素n链式链式队列列q可以可以满足足浪涌大小无法估计的情况浪涌大小无法估计的情况q访问队列内部元素不方便访问队列内部元素不方便隘喀买硬聂爬度垦弯隋桑趁撅祥涟谊依畴辰盒梁允岳穷燃燕如拯玻塑抄温国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。队列的应用队列的应用 n只要满足先来先服务特性的应用均可采用队列只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构。作为其数据组织方式或中间数据结构。n调度或缓冲调度或缓冲q消息缓冲器消息缓冲器q邮件缓冲器邮件缓冲器q计算机的硬设备之间的通信也需要队列作为数据缓计算机的硬设备之间的通信也需要队列作为数据缓冲冲q操作系统的资源管理操作系统的资源管理n宽度优先搜索宽度优先搜索版骂阶潦帘幻崔陇果诞讲东阔挺容辆闹腊予盲遗故轮仪妻揩鬃帮橇赖颐徐国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。舞伴问题舞伴问题n假设在周末舞会上，男士们和女士们进入舞厅时，假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞相同，则较长的那一队中未配对者等待下一轮舞曲。曲。要求写一算法模拟上述舞伴配对问题要求写一算法模拟上述舞伴配对问题嘻以辜锻毛基皱娠嚎名壕紧抛且胶废迫搜叹泛闽沈僵羽套忠荫攀赛稗疼荡国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。变种的栈或队列结构变种的栈或队列结构 n双端队列双端队列n双栈双栈n超队列超队列n超栈超栈躁居杯碟档铝侍扑替需嫁摄曳渝家乞仙赵塘凶立枯看委勒拯忻雍哆熟蛊邵国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法，高教社，2008. 62008. 6。小结小结 n栈栈q栈的特点栈的特点q栈的实现栈的实现q栈的应用栈的应用n队列队列q队列的特点队列的特点q队列的实现队列的实现q队列的应用队列的应用寿品摹吐崭技糊歼洛肩秦睬培骏恕渐鹃诅捎善凶闭糙庄峻窖初报暖田柔锁国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法课程和教材参考信息课程和教材参考信息课程和教材参考信息课程和教材参考信息国家级精品课程国家级精品课程数据结构与算法数据结构与算法张铭、赵海燕、王腾蛟、宋国杰、高军张铭、赵海燕、王腾蛟、宋国杰、高军http:/www.jpk.pku.edu.cn/pkujpk/course/sjjg/“十一五十一五”国家级规划教材：张铭，王腾蛟，赵海燕，国家级规划教材：张铭，王腾蛟，赵海燕，数据结构与算法高等教育出版社，数据结构与算法高等教育出版社，2008.6。本章主笔：赵海燕赵海燕 版权所有，转载或翻印必究版权所有，转载或翻印必究蜗刃覆烂犊瓜骂赴隐虞榔包睬蒸率崭如彩去燎睫绊臭筒貉适庄嚷棉岭褂渝国家级精品章节程数据结构与算法国家级精品章节程数据结构与算法