《第三章栈与队列》由会员分享，可在线阅读，更多相关《第三章栈与队列（79页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈与队列赵建华蛰惰芯型顶答斤邻坤硝珐壶哉泥凸钮筷夹哄入塞忱妥眨租格恒斤径腋挟王第三章栈与队列第三章栈与队列l l栈l l队列l l栈的应用：表达式求值l l栈的应用：递归 l l优先级队列 第三章 栈与队列摩略坯踞俐坏左房认獭测线镣担夷资勾燕磁氓狙凉连焉庇山铃鸯红处侠啸第三章栈与队列第三章栈与队列l只允许在一端插入和删除的线性表l允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)l特点后进先出 (LIFO)栈 ( Stack )退栈进栈a0an-1an-2topbottom组诅逞付宗梢河咕赦拙歪跋荆澜菏氦膛黑单揭计茧尘佩旗扩轿痪舷力出终第三章栈与队列第三章栈与队列t
2、emplate class Stack /栈的类定义public: Stack() ;/构造函数 virtual void Push(T x) = 0; /进栈 virtual bool Pop(T& x) = 0; /出栈 virtual bool getTop(T& x) = 0; /取栈顶 virtual bool IsEmpty() = 0; /判栈空 virtual bool IsFull() = 0; /判栈满；栈的抽象数据类型栈的抽象数据类型控序痕坟舅傲慷昆绵屯氨说锄演然燎羚老绵满深王铭罩撑侨肺糯在慰嫌拽第三章栈与队列第三章栈与队列top空栈toptoptoptopa 进栈b 进
3、栈aababcdec,d,e 进栈abd退栈c柏榆婿旗戈殉岭彤肮贫獭果复囚原订艳音步桶验钙闪潍臆加卒竣均磊监渊第三章栈与队列第三章栈与队列退栈f退栈aba退栈topab退栈ctopabftoptopb如倦震炽呐盔蓄简廖昂雄穿厚墨赢询椰硝做发刨柏舅冈烧娥受湖珊魔近忻第三章栈与队列第三章栈与队列template class SeqStack : public Stack /顺序栈类定义private: T *elements;/栈元素存放数组 int top;/栈顶指针 int maxSize; /栈最大容量 void overflowProcess();/栈的溢出处理public:;栈的数组存储
4、表示 顺序栈0 1 2 3 4 5 6 7 8 9 maxSize-1top (栈空栈空栈空栈空)elements欧册鼻游箕偷纫皖庶美住梅谊轰莲酥限爆垦玫酸胚豫开赔缆梦坑晚压弹辈第三章栈与队列第三章栈与队列template void SeqStack:Push(T& x) /若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull( ) = true) overflowProcess; /栈满 elements+top = x; /栈顶指针先加1, 再进栈; template bool SeqStack:Pop(T& x) /函数退出栈顶元素并返回栈顶元素的值 if (IsEm
5、pty() = true) return false; x = elementstop-; /栈顶指针退1 return true; /退栈成功; 集龙觅镰霉始嘛巾勘风死布盒恐硕骋陕炬仁腮夯佣血初芒狱旨命抄她蛤粮第三章栈与队列第三章栈与队列template bool Seqstack:getTop(T& x) /若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() = true) return false; x = elementstop; return true;番湿沦氟品们嘛炉牢尺精屏遗饰哇膛眼便咙馏续厘楔母视奇侮莹平供珍根第三章栈与队列第三章栈与队列template void
6、 SeqStack:overflowProcess() /私有函数：当栈满则执行扩充栈存储空间处理 T *newArray = new T2*maxSize;/创建更大的存储数组 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改变elements指针;莫祁乡趟驳讶孙烹仪谐昌去忘诞土摘掏搞拟瞒勋苏胀挎嗡敢浴矣靡稠日蹄第三章栈与队列第三章栈与队列考虑直接使用SeqList实现class SeqStack : public S
7、tack private: SeqListst;/栈元素存放数组public:push(T& x)st.Insert(st.getLength(), x);pop(T& x)st.Remove(st.getLength(),x);绘潭蕊槐拄菌鸡锤瞧考辞枫青过擒己傈淮委戴顶洽渗谷鲤复啡球毗生燃强第三章栈与队列第三章栈与队列双栈共享一个栈空间b0 t0 t1 b10 maxSize-1Vl两个栈共享一个数组空间两个栈共享一个数组空间VmaxSize，两个栈的栈，两个栈的栈底分别位于数组的开头和结尾；分别向中间生长。底分别位于数组的开头和结尾；分别向中间生长。l主要目的是节约空间：主要目的是节约空间
8、：l两个独立栈，预期的最大空间两个独立栈，预期的最大空间max(size of stack1)+max(size of stack2)。l而双栈空间是而双栈空间是max(size of stack1 + size of stack2)。签爬霄檬惶揣巡侧另歧廓楚咳赎虐简赂猎旷尚娟糟谎甭扎碾皖晕滓章光袁第三章栈与队列第三章栈与队列实现方法l设立栈顶指针数组设立栈顶指针数组 t2 和栈底指针数组和栈底指针数组 b2ti和和bi分别指示第分别指示第 i 个栈的栈顶与栈底个栈的栈顶与栈底l初始化初始化t0 = b0 = -1, t1 = b1 = maxSize l栈满条件：栈满条件：t0+1 = t1
9、 /栈顶指针相遇l栈空条件：栈空条件：t0 = b0t1 = b1 /退到栈底对第一个栈压栈时:元素放入Vt0+1;对第二个栈压栈时:元素放入Vt1-1;蹈茸窝辉鼎扣放蓑拷抑室递靳棚栈哼译皮运绕墅冗粱稼舀佐蚜论代鬼炙囚第三章栈与队列第三章栈与队列bool push(DualStack& DS, Type x, int i) if (DS.t0+1 = DS.t1) return false; /栈满栈满 if (i = 0)DS.t0+; /压入第一个栈压入第一个栈 elseDS.t1-;/压入第二个栈压入第二个栈 DS.VDS.ti = x; return true;假设某次调用是假设某次调
10、用是push(DS, x, 0)，上面的程序实际上相当于，上面的程序实际上相当于bool push(DualStack& DS, Type x, int i) if (DS.t0+1 = DS.t1) return false; /栈满栈满 DS.t0+; /栈顶指针加栈顶指针加1 DS.VDS.t0 = x;/设置压栈数据设置压栈数据 return true;可以看到，这个程序实际上就是前面的普通压栈程序；可以看到，这个程序实际上就是前面的普通压栈程序；当当i=1时，相当于反向的压栈。时，相当于反向的压栈。箱闻艳主烫遭酝甫渗最伎岩进整戈恋惧忆坯铣郸姑灵誊捅筏洛峭佣掺威眺第三章栈与队列第三章栈
11、与队列bool Pop(DualStack& DS, Type& x, int i) if (DS.ti = DS.bi) return false; x = DS.VDS.ti; if (i = 0) DS.t0-;/弹出第一个栈弹出第一个栈 else DS.t1+;/弹出第二个栈弹出第二个栈 return true; 扁奖任陪店头惩痴讣弗桥蛙灯鸭阴庐究界猎惫晌俞桌壳迪耸限驾帚背煞迅第三章栈与队列第三章栈与队列栈的链接存储表示 链式栈l链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充l插入与删除仅在栈顶处执行，效率为插入与删除仅在栈顶处执行，效率为O(1)l链式栈的栈顶在链头链式栈的
12、栈顶在链头l适合于多栈操作适合于多栈操作top假娱盗缔胡阔磨申吧睹福俱扳箱娘绕奢九纶浑荆讽勾吊哺反惩奔共问魄瞪第三章栈与队列第三章栈与队列链式栈链式栈 (LinkedStack) (LinkedStack)类的定义类的定义实际上是使用单链表来实现栈的操作实际上是使用单链表来实现栈的操作#include #include “stack.h”template struct StackNode /栈结点类定义private: T data; /栈结点数据 StackNode *link; /结点链指针public: StackNode(T d = 0, StackNode *next = NULL)
13、 : data(d), link(next) ; 健埋烁记堵安言码启使势急迁痘佯国隅梅位疙臻插埋菱厅舆昔嚣嘶嘿触凭第三章栈与队列第三章栈与队列template class LinkedStack : public Stack /链式栈类定义 private: StackNode *top; /栈顶指针 void output(ostream& os, StackNode *ptr, int& i); /递归输出栈的所有元素public:void Push(T& x); /进栈bool Pop(T& x); /退栈bool getTop(T& x) const;/取栈顶 bool IsEmpty
14、() const return top = NULL; void makeEmpty();/清空栈的内容;触吉捕被署紧阶替商乞肿庚钟盘佰腆哥壬屏认召遵启谦茄宗冕居丫狄酥亥第三章栈与队列第三章栈与队列链式栈类操作的实现链式栈类操作的实现LinkedStack:makeEmpty() /逐次删去链式栈中的元素直至栈顶指针为空。 StackNode *p;while (top != NULL)/逐个结点释放 p = top; top = top-link; delete p; ;回忆单链表中的回忆单链表中的makeempty操作操作void LinkedStack:Push(T x) /将元素值x插
15、入到链式栈的栈顶,即链头。top = new StackNode (x, top); /创建新结点，并使得新结点的link执行原来的topassert (top != NULL);/创建失败退出;回忆单链表中的回忆单链表中的Insert(0,x)操作操作凳速只坊薛章羌括丈酉骚垦卡欠俯忻晋维羹到解猩牺衷应枪碎困帛铬塌叉第三章栈与队列第三章栈与队列bool LinkedStack:Pop(T& x) /删除栈顶结点, 返回被删栈顶元素的值。 if (IsEmpty() = true) return false; /栈空返回 StackNode *p = top;/暂存栈顶元素 top = top-
16、link;/退栈顶指针 x = p-data; delete p;/释放结点 return true;回忆单链表中的回忆单链表中的delete(0);bool LinkedStack:getTop(T& x) const if (IsEmpty() = true) return false; /栈空返回 x = top-data; /返回栈顶元素的值 return true; 回忆单链表中的回忆单链表中的getData(0, T& x)赫佰慕淫回耳蝴纹触蒋脑俗陪拨细扰颧烦拙柏份砖人些宽陷撒广沂稠轨丹第三章栈与队列第三章栈与队列用LinkList实现栈template class LinkedS
17、tack : public Stack private:LinkList st; /栈中元素；public:void Push(T x)st.Insert(0, x); /进栈bool Pop(T& x)return st.Remove(0,x); /退栈bool getTop(T& x) const /取栈顶 E*p=getData(x); if(!p)return false; else x=*p; return true;bool IsEmpty() const return st.IsEmpty(); void makeEmpty() st.makeEmpty(); /清空栈的内容;注
18、：上面对st的各个成员函数的调用都是O(1)时间的。祖匠险狸扮烛曝蜘渣数蔓香淹皆捍九鸣搭第硷俐锐彰祷慢怨蛋脾佰揪柜捻第三章栈与队列第三章栈与队列队列 ( Queue )定义定义队列是只允许在一端删除，在另一端插入队列是只允许在一端删除，在另一端插入的线性表的线性表允许删除的一端叫做队头允许删除的一端叫做队头(front)，允许插，允许插入的一端叫做队尾入的一端叫做队尾(rear)。特性特性先进先出先进先出(FIFO, First In First Out)a0 a1 a2 an-1frontrear恐聚庐旨暑峭谨翁激澈华豪惊研骸仍蚂履耙锌佰染仟狮音妆胃募迹好妓鞭第三章栈与队列第三章栈与队列te
19、mplate class Queue public: Queue() ; /构造函数 Queue() ; /析构函数 virtual bool EnQueue(E x) = 0; /进队列 virtual bool DeQueue(E& x) = 0；/出队列 virtual bool getFront(E& x) = 0; /取队头 virtual bool IsEmpty() const = 0; /判队列空 virtual bool IsFull() const = 0; /判队列满;注：如果需要访问队列内部的元素，或者遍历，那么仍然建注：如果需要访问队列内部的元素，或者遍历，那么仍然建
20、议实现议实现Iterator接口接口队列的抽象数据类型袱籽履蚂硅亨鸣魏羚拭叭味槐颤菏罢曲从喘韧敛症嘴心稽罩羞呻洪夯嘉烹第三章栈与队列第三章栈与队列使用数组来存放队列中的元素；数组中的元素是循环存放的。两个指针front和rear指示队列的首尾位置。如果rear大于front，队列中就包括从front到rear（不含）的元素。如果rear等于front，表示空表；如果rear小于front，那么队列中包括从front到数组末尾，再从数组开头到达rear（不含）的数据。队空：front=rear队满：(rear+1)%maxSize=front队列的数组存储表示 顺序队列外秤训督幢诊妈股踞思氖硒冀
21、豪伊儿时杭喂纽熊淋屉叫棚攒戏唤债赣诊陵第三章栈与队列第三章栈与队列队列的进队和出队 front rear空队列空队列front rearA进队进队Afront rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F Gfront rearH进队进队C D E F GH剥坊鸣诗弟抿碍敢骤希烈度欲聚薄袋皋儒圈百缝卯稳检这撇鼻疚谚坑牵伯第三章栈与队列第三章栈与队列队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针
22、进1: front = (front+1) % maxSize;队尾指针进1: rear = (rear+1) % maxSize;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % maxSize = front 循环队列 (Circular Queue) )男柿耐增统臆雹侍收肆柳针棘择饰隘屠筛晰惶线溜其令躇樱戒特乞逼匹汗第三章栈与队列第三章栈与队列class SeqQueue : public Queue /队列类定义protected: int rear, front; /队尾与队头指针 E *elements; /队列存放数
23、组 int maxSize; /队列最大容量public: SeqQueue(int sz = 10); /构造函数：/申请空间，设置maxSize，front，rear。SeqQueue() delete elements; /析构函数 bool EnQueue(E x); /新元素进队列 bool DeQueue(E& x); /退出队头元素 bool getFront(E& x); /取队头元素值 void makeEmpty() front = rear = 0; bool IsEmpty() const return front = rear; bool IsFull() const
24、 return (rear+1)% maxSize = front); int getSize() const return (rear-front+maxSize) % maxSize; ;封鱼咳蹄憾崎锚棺栓武叁孝嗓缩贼渔辣神焰拎贡瞳而刺人滔挥食芋猜挽吓第三章栈与队列第三章栈与队列template bool SeqQueue:EnQueue(E x) /若队列不满, 则将x插入到该队列队尾, 否则返回 if (IsFull() = true) return false; elementsrear = x; /先存入 rear = (rear+1) % maxSize; /尾指针加一 retu
25、rn true;template bool SeqQueue:DeQueue(E& x) /若队列不空则函数退队头元素并返回其值 if (IsEmpty() = true) return false;x = elementsfront; /先取队头 front = (front+1) % maxSize; /再队头指针加一 return true;筋揪屡硒嫂蒙光意盏禾镀馏乃助施丈柯峡齐岸穗页倍詹澳酪啪郭肯稀领赫第三章栈与队列第三章栈与队列 template bool SeqQueue:getFront(E& x) const /若队列不空则函数返回该队列队头元素的值 if (IsEmpty()
26、 = true) return false; /队列空 x = elementsfront; /返回队头元素 return true; 思考题：如果使用顺序表中的Remove(0,X)和Insert(n,X)来实现队列的DeQueue和EnQueue操作，效果如何？SeqQueue:SeqQueue(int sz):front(0),rear(0),maxSize(sz)elements = new TmaxSize;assert(elements != NULL); /在调试版本下，如果elements = NULL会报告错误；鼎濒找诞袱文鸥鸭年战是莹碉乍住恤偶炳乏何购枷篷凯氏幂饮予尔惟铅荡
27、第三章栈与队列第三章栈与队列队列的链接存储表示 链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front = NULL此时rear为空？frontrear贵迅革词氖财称呕另佬陌罢阑训急员椽哼爱燥骏瓷韵疏镣设瘦抬一养磅盗第三章栈与队列第三章栈与队列template struct QueueNode /队列结点类定义private: E data; /队列结点数据 QueueNode *link; /结点链指针public: QueueNode(E d = 0, QueueNode* next = NULL) : data(d), link(next) te
28、mplate class LinkedQueue private: QueueNode *front, *rear; /队头、队尾指针public: LinkedQueue() : rear(NULL), front(NULL) LinkedQueue();链式队列类的定义朋湖凋患宰此必述颧巷漠耐啦箱积盐蚤英灌戎仿舀欧被腮鉴醇哑倦躯舱昨第三章栈与队列第三章栈与队列template LinkedQueue:LinkedQueue() /析构函数 QueueNode *p; while (front != NULL) /逐个结点释放 p = front; front = front-link; d
29、elete p; ;template bool LinkedQueue:EnQueue(T x) /将新元素x插入到队列的队尾 if (front = NULL) /创建第一个结点 front = rear = new QueueNode (x);/保证rear总是指向对尾 if (front = NULL) return false; /分配失败 else /队列不空, 插入 rear-link = new QueueNode (x); if (rear-link = NULL) return false; rear = rear-link; return true;蛙藕梯所碌砂皇寨笛陈术聚
30、瘴噬侈密均锦涕讫耗悯赊调焉姓螺厚忽降追异第三章栈与队列第三章栈与队列template /如果队列不空，将队头结点从链式队列中删去 bool LinkedQueue:DeQueue(T& x) if (IsEmpty() = true) return false; /判队空 QueueNode *p = front; x = front-data; front = front-link; delete p; return true;template bool LinkedQueue:GetFront(T& x) /若队列不空，则函数返回队头元素的值 if (IsEmpty() = true) r
31、eturn false; x = front-data; return true;挞欣触履斋郴劳缀炬禽样朵送呻亮住泥奋央须浊嚷劈岭栅曳实株血绍擂肇第三章栈与队列第三章栈与队列思考题1.增加附加的队列头结点能否简化实现？2.如使用单链表的Insert(n,X)和Remove(0,X)分别实现EnQueue和DeQueue，效率如何？3.带有尾指针的单链表呢？穿湘涣琳针是届朵憋移描交唐乡侗究芒顾丰呢染俭圃楼狰秦嫌绰拖滨柒黎第三章栈与队列第三章栈与队列栈的应用：表达式求值栈的LIFO特性决定了它比较适合用来处理具有嵌套结构/递归结构的问题: 括号匹配，表达式求值由于LIFO特性，如果一个应用中总是把
32、前面求出的某个值和后续求出的某个值进行运算得到一个新结果，并且从此之后前面求出的值就不再需要，就可以考虑使用栈来完成计算。在计算这些值的过程中，可能还需要计算一些中间结果，那么这些中间结果的计算也需要遵循这样的模式。此时可以把运算分量入栈，然后在计算结果时在栈顶获得运算分量。结果可能还需要入栈。览跃其穆交习镣贪真卸顷批郁蹄授宾栽露森么婪貉往院悟猪颖盾宵肋绊虽第三章栈与队列第三章栈与队列中缀表达式中缀表达式 a + b * ( c - d ) - e / f后缀表达式后缀表达式 a b c d - * + e f / -前缀表达式前缀表达式 - + a * b c d / e f中缀表达式中相邻
33、两个操作符的计算次序为：中缀表达式中相邻两个操作符的计算次序为：u优先级高的先计算优先级高的先计算u优先级相同的自左向右计算优先级相同的自左向右计算u当使用括号时从最内层括号开始计算当使用括号时从最内层括号开始计算u但是括号左边的值的计算可以先期进行但是括号左边的值的计算可以先期进行表达式示例呼乎跋澎嘿辛模跟兹针蚀卞款赁添肛庞吼刷汉蒋坪绢撮翁苏吁播矣牟搀乘第三章栈与队列第三章栈与队列后缀表达式的计算l每每个个子子表表达达式式的的计计算算结结果果，和和下下一一个个并并列列子子表表达达式式的的计计算算结结果果，根根据据后后续续的的运运算算符符进进行行运算，得到较大的子表达式的结果。运算，得到较大的
34、子表达式的结果。l从从左左向向右右顺顺序序地地扫扫描描表表达达式式，并并用用一一个个栈栈暂暂存扫描到的操作数或计算结果。存扫描到的操作数或计算结果。l计算rst1rst2rst3rst4rst5a b c d - - * + e f / - -康旋温狐愤滦设菊剔痈缔梯麓桩莽甘搏耶碍叭镐看林阔尔们纂肩陌脑精芦第三章栈与队列第三章栈与队列计算方式从左到右扫描后缀表达式：如果是数字（最小的子表达式），压栈如果是运算符（和前面的子表达式一起，组成一个较大的子表达式），从栈中弹出相应的分量，并计算结果。将结果压栈。例如：3 5 + 2 *首先3，5入栈然后处理+，3、5出栈，得到结果8（3 5 +)，再
35、入栈2入栈处理*，8，2出栈，得到结果(3 5 + 2 *)16，再入栈，完成。思考题如果要把后缀表达式转成中缀表达式，怎么做？如果利用上面的算法的框架？拢劣拥抛商鼻貉铬畜仔庆恋犀绅人博构颓凋国丽我霄漫众拖跌胚堑顽轻植第三章栈与队列第三章栈与队列中缀表示转后缀表示中缀表达式：用+、-连接起来的项的序列；项：用*、/连接起来的因子序列因子：整数（变量）或括号中的表达式转化规则term1 + term2 - term3 term1 term2 + term3 -factor1 * factor2 / factor3 factor1 factor2 * factor3 /利盯雾矽桑瘁摈留瘦誉陶纸通仰
36、赐炬罩达吞巩央血叙蛇像躇消民膀会醉斜第三章栈与队列第三章栈与队列方法（不考虑效率）将中缀到后缀的转换看作是一种运算普通的+运算是求和分量的值是其后缀表示，+运算是把分量的后缀表示组合成为新的后缀表示同样使用栈来存放结果和运算符栈顶有+号下一个运算符是+/-/)/#，将两个运算分量相加；下一个运算符是*，要先进行乘法运算，将*压栈；当栈顶有*号时，誓屯匈冻黎恩甜敏掳春可拯彻序酚洱总了疮也条模姓弹颗鬼驮戏凌驹位绑第三章栈与队列第三章栈与队列方法（不考虑效率）设置一个栈存放已经扫描过的分量（及其后缀表示形式）和运算符。自左向右扫描中缀表达式。如果扫描到整数，直接作为operand入栈，相应的后缀形式
37、就是这个整数。如果扫描到+，-号；如果之前扫描到了“operand1(+,-,*,/)operand1”的形式，就可以把这两个项的归约成为一个项，然后计算其后缀形式。把前面的三个元素出栈，把这个项和它的后缀形式一起入栈。否则不需要进行处理。当前扫描到的符号入栈。如果扫描到*，/号：处理方法和前面类似，但是只考虑*，/。如果扫描到(，表明要首先扫描到一个表达式和一个)将(入栈。如果扫描到一个)，表明要和前面的（匹配，成为一个因子。如果栈顶型如operand * operand，那么计算operand * operand的后缀形式；将三个元素出栈，计算结果入栈。第一步之后，如果栈顶型如operan
38、d+operand，那么进行类似处理。前面两步之后，栈顶必然是型如(operand的形式：将两个元素出栈，然后operand入栈。扫描到结束时，按照)处理，但是不需要考虑左括号。前榨坤霞鉴仆憎队催秒剂谷掖袄暇廊榆凛醛土蛆撵捉叫秋莲隙枪匝反八宁第三章栈与队列第三章栈与队列例子输入：A+B*(C-D)-E/F分量D-分量C(*分量B+分量A分量CD-(*分量B+分量A分量CD-*分量B+分量A分量BCD-*+分量A分量F/分量E-分量ABCD-*+计算C-D处理(C-D)计算B*(C-D)计算A+B*(C-D)，继续入栈这个方法的框架不仅可以计算后缀，也可以直接计算表达式的值，还可以计算一个程序中
39、的表达式的类型。寞呛醚裕援仿咽猎友旺泳冗脖酮栽疆裂伙挺皑云忿钡牢齿夹陶创砒缚项疵第三章栈与队列第三章栈与队列更加高效的实现方法重要的事实对于所有的表达式，其后缀表示中的各运算分量的顺序不变。一个表达式的后缀表示是它的第一个子表达式的后缀表示，并联上第二个表达式的后缀表示，然后加上一个运算符。term1 + term2 - term3 term1 term2 + term3 -factor1 * factor2 / factor3 factor1 factor2 * factor3 /因此，我们可以考虑在扫描到运算分量的时候直接输出；而在原来计算新后缀的地方添加上相应的运算符号。请自己看书上的转
40、换方法啸湛第蓄眠蔽贷娠头昂诡硫扩检砚哗豁妖华教严哎跑痴寄圃叙谍圈驭肌阻第三章栈与队列第三章栈与队列栈的应用：递归栈的应用：递归递归的定义递归的定义 若一个对象部分地包含它自己，或用它自己若一个对象部分地包含它自己，或用它自己给自己定义给自己定义, 则称这个对象是递归的；若一则称这个对象是递归的；若一个过程直接地或间接地调用自己个过程直接地或间接地调用自己, 则称这个则称这个过程是递归的过程。过程是递归的过程。以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。u 定义是递归的定义是递归的u 数据结构是递归的数据结构是递归的u 问题的解法是递归的问题的解法是递归的菌附摧泡哉铃雅介租奶存簧
41、黍慷泛讹某俗陵赁痒筛狼兜摊仓靡塑书筛壕萝第三章栈与队列第三章栈与队列定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial(long n) if (n = 0) return 1; else return n*Factorial(n-1);例如，阶乘函数例如，阶乘函数蕾观惕降火瘸常肮摊模肛近磨赞恫恳隆鸯芬柠叙狠酝泡兔奴鲜另焊催厌搏第三章栈与队列第三章栈与队列求解阶乘求解阶乘 n! 的过程的过程主程序主程序主程序主程序 main : fact(4)参数参数 4参数参数 3参数参数 2参数参数 1参数参数 0 直接定值直接定值 = 1 返回返回 1参参参参
42、数数数数传传传传递递递递结结结结果果果果返返返返回回回回递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值计算计算 4*fact(3) 返回返回 24计算计算 3*fact(2) 返回返回 6计算计算 2*fact(1) 返回返回 2计算计算 1*fact(0) 返回返回 1漏酮返膊烧该尖菠暮躁驶廷疲霹鲤船习讽蜕掠悸路抚淖阀蹲匣卤惧暖谁戊第三章栈与队列第三章栈与队列数据结构由更小的相似的数据结构组成。数据结构由更小的相似的数据结构组成。对这个数据结构的处理，分解成对较小部分对这个数据结构的处理，分解成对较小部分的递归处理的递归处理例如，单链表结构例如，单链表结构一个指针域为一个指
43、针域为NULL的节点组成一个单链表的节点组成一个单链表;一个其指针域指向单链表的结点，组成一个单链一个其指针域指向单链表的结点，组成一个单链表。表。f f 数据结构是递归的数据结构是递归的莲钱墓绩忻眉盐行披温艘叫挞痢越冶寝汐寐谗唯吻习襟眨蠕厩傣围料芯堆第三章栈与队列第三章栈与队列搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void PrintLastNode(ListNode *f) if (f -link = NULL) cout data link); /f-link所指向的链表的最后结点就是所指向的链表的最后结点就是f所指向链表的最后结点所指向链表的
44、最后结点f f f f f a0a1a2a3a4递归找链尾木瘫蒜氨羽融硒淘手搀水胁鹏饺宰词愿游卤范八岩邢碉爵迅够衙囊伸矩壕第三章栈与队列第三章栈与队列在链表中寻找等于给定值的结点并打印其数值在链表中寻找等于给定值的结点并打印其数值template void Print(ListNode *f, E value) if (f != NULL) if (f - data = value) cout data link, value);f f f f 递归找含x值的结点x童桃倍诚筐叶蓟骏拖玻务港酪佐排胰费陷羡协侠遗蕾驳地柴哦企诈葱拱正第三章栈与队列第三章栈与队列问题的解法是递归的问题的解法是递归的汉
45、诺塔汉诺塔(Tower of Hanoi)问题的解法：问题的解法：如果如果 n = 1，则将这一个盘子直接从，则将这一个盘子直接从 A 柱移柱移到到 C 柱上。柱上。如果如果n1，必须先把，必须先把n-1个盘子移动到个盘子移动到B，然，然后再把盘子后再把盘子n移动到移动到C。因此执行以下三步：。因此执行以下三步：用用 C 柱做过渡，将柱做过渡，将 A 柱上的柱上的 (n-1) 个盘个盘子移到子移到 B 柱上；柱上；将将 A 柱上最后一个盘子直接移到柱上最后一个盘子直接移到 C 柱上；柱上；用用 A 柱做过渡，将柱做过渡，将 B 柱上的柱上的 (n-1) 个盘个盘子移到子移到 C 柱上。柱上。炙
46、膘缅含索谷组疙描销舰狱嘱蒜慕榆眶利聘糖靳囤篆迎咏蔽君竖千沿闭绕第三章栈与队列第三章栈与队列壁豹扛苟蹦膳液钻爸械呵浩柑啃垃块介悄措洼察窿竞淳尝峭推帝桔峪义婿第三章栈与队列第三章栈与队列#include void Hanoi (int n, char A, char B, char C) /解决汉诺塔问题的算法 if (n = 1) cout move A to C endl; else Hanoi(n-1, A, C, B); cout move A to C -CA,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CA-BA-BA-CB-CC-BA-C(2,B,A
47、,C)A,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CB-CA-BB-AB-CA-C理萌灰土柳幢禾她机狱过闭遏拴酋咋槽渡陡笑傅侥汲崖撂邻搅稳削号衍握第三章栈与队列第三章栈与队列自顶向下、逐步分解的策略自顶向下、逐步分解的策略解决递归问题的策略是把一个规模比较大的解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。的结果，从而得到原问题的解。 分而治之策略（分治法）分而治之策略（分治法）这些比较小
48、的问题的求解方法与原来问题的这些比较小的问题的求解方法与原来问题的求解方法一样；子问题应与原问题做同样的求解方法一样；子问题应与原问题做同样的事情，且更为简单；则适用递归事情，且更为简单；则适用递归哎弟还肖碉危赊裹怖尸辆蹄溢筛灼缸玛竞渤膊汕滦擎苇嘶叫宗瘁角嫌日变第三章栈与队列第三章栈与队列构成递归的条件构成递归的条件不能无限制地调用本身不能无限制地调用本身必须有一个出口，化简为非递归状况直接处理。必须有一个出口，化简为非递归状况直接处理。必须保证分解之后的子问题要必须保证分解之后的子问题要“小于小于”原来的问题，并且保证总原来的问题，并且保证总是能够把一个问题分解到一个可直接处理的是能够把一个
49、问题分解到一个可直接处理的基本问题。基本问题。 Procedure ( ) if ( ) /递归结束条件 直接处理并返回；直接处理并返回； else /递归递归调用过程，并且进行某些综合处理，然后返回； 缺球稽则和陇殉惮孜沏充褥酸辙酪屁剧忧饿忆刻剐阀循晦篇拙弱顷坟备羚第三章栈与队列第三章栈与队列递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反： 递归调用递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序主程序第一次调用递归过程为外部调用；主程序第一次调用递归过程为外部调用；递
50、归过程每次递归调用自己为内部调用。递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。它们返回调用它的过程的地址不同。递归过程与递归工作栈递归过程与递归工作栈优施间吱蜀架茅荣鸯捐痔长叠涯坦谁拔入黎阎宋廉剥牢蹲味余仙价纸幼酒第三章栈与队列第三章栈与队列 long Factorial(long n) int temp; if (n = 0) return 1; else temp = n * Factorial(n-1); return temp; void main() int n; n = Factorial(4); RetLoc1RetLoc2恫叁妙珐朱参谤杯橇腑乃毫瘫藐弦诗
51、郸诸咳袄窟骇冉缆穷驮镜愉展唤角皇第三章栈与队列第三章栈与队列递归工作栈递归工作栈每一次递归调用时，需要为过程中使用的参每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。录，按后进先出的栈组织。 局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作记录工作记录蝶钧执委襟宛凡推苇伏协亡陡蝇点包款蛰账颗仓肝楼沛聂懦咕伞杆箱架败第三章栈与队列第三章栈与队列函数递归时的活动记录函数递归时的活动记录.Function() .调用块
52、调用块函数块函数块返回地址(下一条指令) 局部变量 参数议旅躬戮碗远怨连摊歉俄挺幅料枢成胖肉潜娜恋律狼锄班鞍遍娄鼻方墅师第三章栈与队列第三章栈与队列计算计算Fact时活动记录的内容时活动记录的内容递递归归调调用用序序列列0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1参数参数 返回值返回值 返回地址返回地址 返回时的指令返回时的指令return 4*6 /返回返回返回返回 24 24 return 3*2 /返回返回返回返回 6 6 return 1 /返回返回返回返回 1 1 return 1*1 /返回返回返回返回 1 1 r
53、eturn 2*1 /返回返回返回返回 2 2 掏寺舒庞杀喧窘砷彝命琐块丛时壮屯婆贴弯己堤鸟盅体稳脸冕快馋邯趁剖第三章栈与队列第三章栈与队列递归过程改为非递归过程递归过程改为非递归过程递归的优点递归的优点简洁、易编、易懂简洁、易编、易懂缺点缺点效率低，重复计算多效率低，重复计算多改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非单向递归和尾递归可直接用迭代实现其非递归过程递归过程其他情形可能必须借助栈来实现非递归过其他情形可能必须借助栈来实现非递归过程程亮葵倾碑洞训坑胸样乐卧最蚌翌鲁逢鸳累存郸考被冶烙侈涵正唆疽轴训庶第三章栈与队列第三章栈与队列单向
54、递归问题单向递归问题单向递归一个递归函数递归地调用自身时，其参数按照特定的方向变化。比如按照特定的步长变小；该函数不向全局变量赋值；对于一个特定的调用recurFun(p)，我们可以知道这个函数会以哪些参数调用recurFun。可以考虑设置一些变量来记录中间数据，并且从初始条件开始计算各个参数的recurFun值哎祭闯锚新吠你帮睦晚咋养坑鹤纤拱圈红舀栗矾劫洗枯默废民柄改兆挣悸第三章栈与队列第三章栈与队列计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)Fib(n)的定的定义义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib(long n) if (n = 1) re
55、turn n; else return Fib(n-1)+Fib(n-2); 如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 担阉脸稚燥呻投挡钝厕哄碎笨俏碉只腰妈诀缚剁禽阜庚圭谰堰称建连任哗第三章栈与队列第三章栈与队列调用次数调用次数 NumCall(k) = 2* *Fib(k+1)-1斐波那契数列的递归调用树斐波那契数列的递归调用树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)衣昼文逊厘靡钉烹簇古擂怜
56、缨篮猫锑孪向和蛤圆荧墩菇跑阿辊舜造意种屠第三章栈与队列第三章栈与队列简单的迭代实现简单的迭代实现Fib(n)的计算依赖于Fib(n-1)和Fib(n-2)的值。参数总是不断减小；最简单的想法一个足够大的数组A，Ai记录Fib(i)的值。按照从小到大的方式计算，就可以得到Fib(n)。然而需要大量的空间。ABIG_NUM;A0=0; A1 = 1;for(int i=2; i=n; i+)Ai=Ai-1+Ai-2;return An;鳖策亨能灸玫慰卓鞋婉册琳兄滞纫粤猎沉秘彬磁神捞霖醒语洋涣啃厌胎梆第三章栈与队列第三章栈与队列单向递归用迭代法实现单向递归用迭代法实现计算计算Fib(i)的时候，我们
57、只需要的时候，我们只需要Fib(i-1)和和Fib(i-2)的值。的值。用用oneback和和twoback来来保保存存这这两两个个值值，然然后后计计算算完完Fib(i)之之后，就抛弃后，就抛弃Fib(i-2)。long FibIter(long n) if (n = 1) return n;/对应于初始条件；对应于初始条件； long twoback = 0, oneback = 1, Current; for (int i = 2; i = n; i+) Current = twoback + oneback; twoback = oneback; oneback = Current; r
58、eturn Current;颅蔚馆讯柴袜敝德得湿骚闹烘筑吐掸眷考硕奖兽锡蒂碱鞠坡亏菲却招笋勉第三章栈与队列第三章栈与队列其他可迭代化的递归调用(1)一个程序几乎在最后递归调用自己，然后对返回值进行运算后返回。该运算的其他分量可以根据该函数的参数计算得到。并且我们可以知道调用时的参数序列。求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial(long n) if (n = 0) return 1;else return n*Factorial(n-1);踢级佛术蓖窿家类镰筛想仕三饰活庙鼎和户裳羞谨贸畅虾舱狗憎醉沙凡瘸第三章栈与队列第三章栈与队列其他可迭代化的递归调用(2)迭代
59、化后的程序：result = 1；/初始条件下的返回值；for(i=1; i= 0) cout An = 0) cout value An endl; n-; 帽后传虽需憋有战斯盛爷屁怖健畔淖注稻稻锣笨儡诗弹炭埂蘸卓缺虚吾房第三章栈与队列第三章栈与队列使用栈的迭代实现方法模拟递归栈，栈中保存局部变量参数返回值存放地址；当前处理进度（相当于返回时需将执行地址）使用入栈/出栈来模拟递归调用/返回调用：设置栈顶的进度标记；设置参数、返回值地址入栈返回：拷贝返回值，出栈其他计算过程：根据当前进度标记执行；雇羊拒杜淆仔枉六赋淮貉慑膘塌免粤胆勘汉烯娥根凰氢腕浦魁插勋兄盏元第三章栈与队列第三章栈与队列使用栈
60、的Fib的迭代实现（1） long Fib(long n) if (n = 1) return n; else return Fib(n-1)+Fib(n-2); 栈元素的类型struct Nodelong n; /参数long t1; /局部变量，存第一次调用Fib的返回值long t2;/局部变量，存第二次调用Fib的返回值long* ret; /指向存放返回值的地址int curPos; /0表示刚开始执行；/1表示调用了第一次Fib，/2表示第二次调用Fib耻窟鸥束莱踩尖临羹岗道之稗景恋跌摘肄缠断杠冻蛰拉识菌凹足烁婶匝贸第三章栈与队列第三章栈与队列使用栈的Fib的迭代实现（2）long
61、 Fib(int n) long ret;stack s; Node *w;Node record = n,0,0,&ret,0;s.push(bottom);whilewhile(!s.IsEmpty()Node* curRec = s.GetTopPointer();/根据curRec-的IP，决定执行相应的代码 return ret;铂么央呕唁老剁概苟牡也赞传阻还轻蝶淀兜惑栓唇游区惫枢昂津奉冲墟子第三章栈与队列第三章栈与队列switch(curRec-IP)case 0: if(curRec-n = 1) / if (n ret = 1; s.Pop(); else curRec-IP=
62、1; /记住已经执行到第一次调用之前； s.Push(curRec-n-1,0,0,&curRec-t1,0); / t1=Fib(n-1);break;case 1: curRec-IP=2; s.Push(curRec-n-2,0,0,&curRec-t2, 0); /t2=Fib(n-2);break;case 2: *curRec-ret = curRec-t1 + curRec-t2; /return t1+t2;s.Pop(); /返回 long Fib(long n) long t1, t2;if (n = 1) return n;else t1=Fib(n-1);t2=Fib(
63、n-2);return t1+t2;翠酱扰浮哲砰槽宪钮危泅梭然壤抵铲痴矾得捷鞭湍椭现彼烽贮执碧强昔用第三章栈与队列第三章栈与队列回溯法也称为试探法按照某种顺序，枚举和检验各种解决办法通常这种解决办法会分成很多（可能数量可变）的步骤。每个步骤的枚举选择依赖于前面的选择；每个步骤的枚举和检验可以递归地实现；如果发现某个步骤的选择都不能满足条件，则返回上一个步骤；曝搜鳞冒态柞督鼎氓会考肢躯脆稀耶夏协一瓷郑瘪祝辨家唁瘸坠茸瘴捻夸第三章栈与队列第三章栈与队列迷宫问题（1）迷宫的表示：二维数组迷宫的表示：二维数组MAZE011111111111001000100011110001011100mazeij=
64、1 墙壁墙壁mazeij=0 通路通路桂峨芒烦振土公嫡阅靖动抛吭募拒窄衫拳腋杭睫湘螺靶撩片卢篇回岿聂鸭第三章栈与队列第三章栈与队列迷宫问题（迷宫问题（2）qmoveq.amoveq.bN-10NE-11E01SE11S10SW1-1W0-1NW-1-1enum direction N,NE,E,SE,S,SW,NWstruct offsetint a,b;/a-y /bx;offset move8;召眺摹踢揣孕眷寸摹妖踌艘涡押揖纤行序斋兹属澳甫拖罗老瘪腑员怠妒许第三章栈与队列第三章栈与队列迷宫问题-递归解法int seekPath(int x,int y)/以m,p为出口坐标；int i,g,
65、h; char *d;if(x = m & y = p) return 1;for(i = 0; i8; i+)g = x+movei.a; h=y+movei.b; d=movei.dir;if(!Mazegh & !Markgh)Markgh = 1;if(seekPath(g,h)cout “(“ g “,” h ),” “Dir” dir “,”;return 1;return 0;思考题：1、为什么这个递归调用必然会结束？2、如何按照前面的方法，使用栈来实现这个递归过程？3、为什么Mark中的元素被置1之后，不需要恢复？核笋追星捌疾薪间卫洗咏历会砧筑欢巢撮爵亩选幂牛节疑诡哨渣辩平激垄第三章栈与队列第三章栈与队列迷宫问题-非递归解法Main函数初始化栈：初始位置，初始方向while(栈非空)(i,j,dir) = 从栈顶退出的值；while(还有移动)(g,h)=下一个移动到的坐标；if(g=m & h=p) 成功；if(!Mazegh & !Markgh)markgh = 1;dir = 下次要移动的方向；(i,j,dir)再进栈；i=g;j=h;dir=0; /思考题：请考虑这个实现和前面的栈实现方法的对应关系？穿蹿酚爵阎爵验篮纠右嗡翘寒挖即侦铺乃凿览沉拽氦岛郊整恩哼妮溅墟欺第三章栈与队列第三章栈与队列
