名师推荐数据结构与算法第三章课件

1、第3章 栈和队列3.1 栈3.2 队列3.3 栈与队列的应用嘶箩碗恰彝击穿起愿淬佃虏迅只尤讳庚诌图潍帧裙迫铸乍量穆主泻椅薪此数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈ADT栈栈（Stack）只允许在表的一端进行插入和删除的线性表允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）不含元素的栈称为空栈 插入：进栈，入栈 删除：出栈，退栈特点后进先出（LIFO）先进后出（FILO）望江非险凌醚资殷澈滥犹田许屁氨骗以瓣岸绰漓踊土漾棠斋峭垂合寄雁鸥数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈

2、ADT栈问题有三个元素按 a1, a2, a3 的次序依次进栈，其出栈次序有几种可能？出栈次序： a1，a2，a3 a1，a3，a2 a2，a1，a3 a2，a3，a1 a3，a2，a1注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。妨适篓因顶知侨程鬃巨固颇羚乓枣匿痕撑伺密抹钟蘑曙礼糠紧颁霞扳评秩数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈ADT栈栈的抽象数据类型ADT Stack Data 数据项列表 top：栈顶位置 Operations Constructor Process：创建一个空栈 IsEmpty

3、Process：判断栈是否为空 Output：如果栈为空，则返回true，否则返回false GetTop Process：取栈顶元素 Output：返回栈顶元素欧邀笺县村诞蘑仪翅处胶灸饶桥侩巢涤缀枫拟察蹿误搁临闰铬埠姨均磁妇数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈ADT栈 Length Process：求栈中元素个数 Output：返回栈中元素的个数 Push Input：要添加的数据元素 Process：向栈中添加元素x，即进栈 Pop Process：删除栈顶元素，即出栈 Output：返回栈顶元素 Clear Process：删除栈中所

4、有元素并置新的栈顶 /Stack竖褒敝改啡籽佃儒奉株反侄落冷街轻庆朱业腕糠穗砸氮衍位辽邓祖慕缎壁数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现顺序栈顺序栈的定义如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6附设指针top指示栈顶元素在数组中的位置。 top确定用数组的哪一端表示栈底。a1a2a3屑绽许寅敞砾谋鉴蔷鱼暇喊市穴淌腆辅舟请唬雾嘎安侦仑甜壤行标式祖管数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现顺序栈的基本操作出栈：先出栈 top再减1进栈：top先加1 再进栈栈空：to

5、p= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：top=MaxStackSize-1toptop蚌赠销萄稻街镁宽廉婚期塞掉察里枕容选哲弄蛾槛售趣弛刚田科机霄遇醇数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现const int MaxStackSize=50; /栈中能容纳最大元素个数class SeqStack DataType StackListMaxStackSize; int top; public: Stack (); /构造函数，初始化top bool IsEmpty (); /判断栈的状态是否为空

6、 bool IsFull (); DataType GetTop (); /取栈顶元素 void Push (const DataType x); /入栈 DataType Pop (); /出栈 void Clear (); /栈清空;/ SeqStack堆为时竟惜昔魂君节职惜都耍铝蜀柴掷灼侯幂写秋则强斌际埂藩就擂獭萨数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现顺序栈的操作的实现构造函数，初始化一个空栈 Stack ( ) StackList = new DataTypeMaxStackSize; top=-1; / Stack疽褪封届梆

7、拯歹滴脾全腕候禾琼叠炳浦滋料乳滚验里慨杀望董晕或峰从刷数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现判断栈是否为空 bool IsEmpty ( ) if (top=-1) return true; else return false; / IsEmpty轩涝愚报鲤翌参氯采儿酣焉恃缸俭抒轨痔榴糊缔凭憨岭犁枢惧武袋幽了我数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现判断栈是否已满 bool IsFull( ) if (top=MaxStackSize-1) return true; else

8、return false; / IsFull钒歉摹状烦馅叛吨橙吨过较备舅煮裴樱氮貌黄问冒债坟芯虎怀汲些泛捎航数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现取栈顶元素 DataType GetTop( ) if (IsEmpty( ) cout”栈空！”endl; return nulldata; return StackListtop; 色拖卡出甸嘘帽砌茶赊怯棱网黄住蔚凡念棱稿鼓倚垦誊偶隔淤太踏嗡相窄数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现向栈顶压入元素 void Push (Data

9、Type x) if (IsFull( ) cout”栈满！”endl; else StackList+top = x; / Push柏燃舒寐坯来术嫉篙逾向截氯磁砧罩洛渺匀诅旭近费领驮巩隙蒋孩逊泉陵数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现删除栈顶元素 DataType Pop( ) if (IsEmpty( ) cout”栈空！”next=NULL; /创建头结点 void Push (DataType data);戳腻届侮罗乙吻嚼短八甫机层尘蓝鲸俊辅桂亏续剁颈喇堂京吭芝仓受淌痉数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三

10、章清华大学出版社赵玉兰3.1 栈栈的实现 DataType Pop ( ); DataType GetTop ( ); void Clear ( ) top-next=NULL; bool IsEmpty ( ) return top -next= = NULL; ;/ LinkStack魂惰饭蠢畅式釉囚践圈液祟北边疯该砌磷败质孩敖赃敌株介呀荆忱獭顾犊数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现类中操作算法的描述入栈操作 void Push (DataType item ) p=new StackNode ( item); p-next=t

11、op-next; top-next=p; /Push踊妄尝亦装旭浩阅币似潦殴湃冕扎胳裔磊瞻历赞线难吴览奏舞邮瓮拎挪危数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈的实现出栈操作 DataType pop ( ) if ( top-next!=NULL ) p=top-next; retvalue=p-data; /暂存栈顶数据 top -next=p-next; /修改栈顶指针 delete p; /释放，返回数据 return retvalue; else /栈空的情况 cout”the stack is empty!”next!=NULL) r

12、eturn top-next-data; else /栈空的情况 cout”the stack is empty!”1时，先把塔 A 上的 n-1 个圆盘移到塔 B，然后将 n 号盘从塔 A 移到塔 C，再将 n-1 个圆盘从塔 B移到塔C。即把求解 n 个圆盘的Hanoi问题转化为求解 n-1 个圆盘的 Hanoi 问题，依次类推，直至转化成只有一个圆盘的 Hanoi 问题。斯缕钉瞳撼齿沟拽蜒豁惕使躇毒嫌良辐昔淆聋碌驻庇参路秽去调谴淮由芥数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归碗陆陋获尘较羡刚舆矣龟谁巷蛔说长痈脊崇懊质羌溯蝶租即请名淳

13、嫩秀恶数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归解决汉诺塔问题的算法 main( ) int n; coutn; hanoi( n ,A,B,C ); void hanoi (int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 咕扔晋卯饰请放廉汤蛆域陋屠佃蛊聘哄才辟嗓翰譬搞箱幽酝炊致研晓袖愿数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1

14、栈栈与递归递归过程和运行时栈递归函数的运行轨迹描述方法1）写出函数当前调用层执行的各语句，并用箭头表示语句的执行次序；2）对函数的每个递归调用，写出相应的函数调用，从调用处画一条箭头指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条箭头指向调用语句的下面，表示返回路线；3）在返回路线上标出本层调用所得的函数值。 笋诞顿妮局滓锌饵滋捶衍捶钟主越鹊秘娱陨泞愿雏汐喳栋填铺璃亡份韶庭数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归n=3 时汉诺塔递归算法的运行轨迹Hanoi ( 3, A, B, C）Move ( A, 3, C )Hanoi

15、( 2, A, C, B）Hanoi ( 2, A, C, B）Hanoi ( 3, A, B, C）Hanoi ( 1, A, B, C）递归第三层递归第二层递归第一层Move ( A, 1, C )Hanoi ( 1, C, A, B）Move ( C, 1, B )Hanoi ( 1, B, C, A）Move ( B, 1, A )Hanoi ( 1, A, B, C）Move ( A, 1, C )Hanoi ( 1, A, B, C）Move ( A, 2, B )Hanoi ( 1, C, A, B）Hanoi ( 2, B, A, C）Hanoi ( 1, B, C, A）Mo

16、ve ( B, 2, C )Hanoi ( 1, A, B, C）Hanoi ( 2, B, A, C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)珠捕疗仓斋劫瓢吗三捂顷嗓俄薄滚揪膜住贬蔫钞犹碉闹亮稗选虏担曹睛饯数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归递归函数的内部执行过程当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需要将实参和返回值地址等数据传递给被调函数，当函数调用时，这些数据与局部变量一起构成一条“工作记录”，被压入系统提供的栈（运行时栈）。当被调函数返回时，按

17、照返回地址执行调用函数中下一条指令，同时释放栈中相应的工作记录。廷逞短削漫墒圆岳煌契鱼孟琼尧婶坤叙太汀例弄凤尽葫靛紧蒙丹咆章顷蛔数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归主程序Call proc1rproc1proc2proc3sCall proc2tCall proc3rst系统运行时栈局部变量返回地址实际参数工作记录琴骚码羌沧倦妮底砒吁蒲排肃钱播块汹硅敬吕丹婿猜鹏侣羞悠皑哺倦甘耿数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归递归调用的内部执行过程运行开始时，首先为递归调用建立一个系统

18、运行时栈；每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址等组成的工作记录压入栈中；每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。坟尊烂咐抡我塑剂碘虽规悠劝态燕粹徐涛拒茅滴缚晌咳眨室涡纤套环施藐数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归n=3 时汉诺塔递归算法的部分执行过程 main() hanoi ( 3,A,B,C ); void hanoi(int n,char x,char y,char z) if (n=1) move (1,x,z);

19、 else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 0123456789ABC321返回地址zyxn 3ABC 01CAB82ACB61ABC612力腆灶孜纲歧旁维渭讽必战昂侮椒力浊迂窝墨碑集栅寨斜旅葬务慈逸渤饵数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.1 栈栈与递归递归总结递归是重要的设计和编程工具，使许多算法变得简单，易于设计和实现。 优点递归使算法的时间复杂度和空间复杂度同时增大，有时会导致效率急剧恶化，或者溢出系统栈。 缺点使用递归时应该权衡效率和设计的关系。在有足够的空间并且时间

20、要求不高的情况下可以使用递归。钥乃讥唱擞虽寄婴粕玉茅单镶庞修乖唤扼房款豁献欧餐如聊靴巷竿僳闹护数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列ADT定义定义队列（Queue）是只允许在表的一端进行删除，而在另一端进行插入的线性表。允许删除的一端叫做队头（front）允许插入的一端叫做队尾（rear）特点先进先出（FIFO，First In First Out）a1 a2 a3. an 入队出队frontrear抬裹帝淌醇爷催拱悍玄彩套隧蕊完凹少杏褥陇烷踢驴点腮须也饭巨豢膀塘数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉

21、兰3.2 队列ADT定义ADT队列的定义ADT Queue Data 数据项列表 front：队列中第一个元素的位置 rear：队列中最后一个元素的位置 Operations Constructor Process：初始化队首和队尾 IsEmpty Process：判断是否为空队列 Output：若队列空，返回true，否则返回false恢难意潘伍夯庭得琐鸽值潦勒符漠彬材眶汹吟棵癌挣沤坯瑟树喀胆醇淖哲数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列ADT定义 Length Process：求队列中元素个数 Output：返回队列的元素个数 Front

22、 Process：取出队头元素 Output：返回队头元素 Enter Input：要进入队列的元素 Process：在队尾插入新的元素 Leave Process：删除队头元素 Output：返回队头元素 ClearQueue Process：删除队列中所有元素并设置初始状态/Queue推孤史屁苯抠妨囊绑临镍府袄五恼理僚疽时杉局甭拈谊谱惠独奠珐究蔑莆数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现顺序队列顺序队列的定义const int MaxQSize=50;class SeqQueue int front, rear; DataTyp

23、e QueueListMaxQSize; public: SeqQueue();/构造函数,初始化数据成员 void Enter(DataType item); DataType Leave(); void Clear(); DataType Front(); int Length(); bool IsEmpty(); bool IsFull(); ;/ SeqQueue迂鹅坐茵巩锅玉榷命而昏湿涸阶丫幸罢蛮去现淌馈吵钥铆研受腑乍攀苫蚌数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现顺序队列的进队和出队 设两个指针 front 和 rear（

24、初始 frontrear0）front 指向队头元素，出队时先取出，再 front+1rear 指向队尾元素的下一个位置，进队时先将新元素加入，再 rear+1队空条件：front=rear，此时不能出队队满条件：rear=MaxQSize，此时不能进队戒湛类壬焚葛捷哀桑粹陆颐究霸牧帐佬四贺造娜鸡缆匣餐汹肪立艺专失燥数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现存在问题 rear=MaxQSize时，再有元素进队发生溢出当front= 0真溢出当front 0假溢出解决假溢出的方案固定队头，出队时，剩余元素均向前移动固定队尾，入队时，剩余

25、元素均向前移动循环队列：把队列设想成环形，让 0 接在 MaxQSize-1 后更好书鲤周啸唇伐阻筑佩茫啪邯策拟蕊凳奈枯争既疏捏灯饱三气囚宦目辖椽凉数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现循环队列也是队列的顺序存储结构实现利用“模”运算入队QueueListrear=item; rear=(rear+1)%MaxQSize; 出队item=QueueListfront; front=(front+1)% MaxQSize; 01frontrear.MaxQSize-1舵判澜藏困鹃信诌赏耻怀亿罚第丁恢礁膛岩山整难叛偏将溯办作御计妒廊数

26、据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现仍然存在问题如何判断队列是“空”还是“满”？队空：front=rear队满：front=rear侮琳俗歇殃炭肆侧拢亥睫埔烘啮阜滴弄顽场凌蛔卸崔挥臆债睹超滚机出淤数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现三种处理方法给队列设一个标志位以区别队列是空还是满给队列增加一个统计元素个数的变量 count，当count=MaxQSize 时队满；count=0 时队空少用一个变量，约定 rear+1 等于 front（从后面赶上队头指针）为队满的

27、情况队满条件：( rear+1 ) % MaxQSize=front队空条件： front = rear实县染忍切午芽邻蔓必箭急佰陌涛四檀囚俞赵碧七壤忽绵毛一贿在驱鲜潍数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现循环队列类的操作算法描述构造函数，初始化一个空队列 SeqQueue () front=rear=0; / SeqQueue入队操作 void Enter (DataType item) if ( (rear+1)%MaxQSize=front ) /判断是否队满 cout”队列已满，不能入队！”endl; else Queue

28、Listrear=item; rear=(rear+1)%MaxQSize; / Enter心草驮烷毕起凛凄沮摔子娜憎赘代呜淌逊慧儿斟衬趟构滨刹武蹈臆皖仆狮数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现出队操作 DataType Leave() if ( front=rear ) /判断是否队空 cout”队列已空，不能出队”next = NULLfront图 3.13 链队列a1a2a3a4 rear万抵邯唾锌盯您腿校拖象埠燥渍桥轰权壁助框滥煽察仗楼步俩买象墒淡叭数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社

29、赵玉兰3.2 队列队列的实现链队列描述 class QNode /链队结点的类 DataType data; QNode *next; public: QNode(DataType item=nulldata) data= item; next=NULL; friend class LinkQueue; ; / QNode菜郎窄埋神橙圭脯匝狄贱谎劝些鉴突镜黑肯趴堑首挨趣室炮跋椽鄂需济配数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现class LinkQueue QNnode *front, *rear; public: LinkQueue

30、() rear =front=new QNode(); void Enter (DataType item ); DataType Leave(); DataType Front(); void Clear () front-next = rear-next = NULL; bool IsEmpty () return front next= NULL; ; / LinkQueue 挫玻秘颓朱诈汇米抨狸凯厚窗廖碎岸所碌仲屁檄纱脾刑婪褂砧件诺钥蹈统数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现链队列基本操作的算法描述入队操作 void En

31、ter ( DataType item ) rear-next = new QNode ( item); rear=rear-next; /Enter香缆夯腮沽赘忙哗峻呈磐击忍绥硕赵渴莉仁腑杉假桅锰灶织都示老完邱骸数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.2 队列队列的实现出队操作 DataType Leave( ) if (!IsEmpty ( ) ) /判队不空 p = front-next; DataType retvalue = p-data;/保存队头的值 front-next = p-next; delete p; if ( front-n

32、ext=NULL ) /删除队列中唯一结点后，重新设置rear rear=front; return retvalue; else cout” 队列空!”next-data; else cout”队列空，无队头元素！”0 时重复（1），（2） （1）若N0，则将 N % r 压入栈 s 中，执行（2）； 若N0，将栈 s 的内容依次出栈，算法结束。（2）用 N/r 代替 N紧郎肥衷峡茹漏讽若虚蹄讹冀佛暑鹰悔枝闭猜氦撩玛触怖蛋畜萝椭呆公愈数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用算法描述 void conversion ( int N，

33、int r ) SeqStack s; int x; while ( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( ) ; coutx ; /while /conversion林里惮悉阉尼弘居樊暇虽骨犊继卤疮迪挣净赠篇铰娟窥分酞阶恒健遂峡沁数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用应用2：表达式求值表达式表达式由操作数（operand）、运算符（operator）和分界符（delimiter）组成操作数：变量或常数运算符：算术运算符、关系运算符、逻辑运算

34、符分界符：括号表达式的表示方法前缀表达式中缀表达式后缀表达式铰盆彝鄂革巫矿蹦帜后隆颜傅泼痊刀泥阿冠充快酉锈妓纸讶层防凝跑造华数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用后缀表达式（逆波兰式）求值后缀表达式不含括号运算符放在两个操作数后面例中缀表达式 2 + ( 3 * 8 4 ) / 5后缀表达式 2 3 8 * 4 - 5 / +所有的求值计算皆按运算符出现的顺序，严格从左向右进行比中缀表达式的计算简单缆铁揣缸肚弯尝搐绎拍盖疫蔬暴瓦氟趟勾背切贸哼妹渔浙慕笋庚忙皇爆盐数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出

35、版社赵玉兰3.3 栈与队列的应用算法思想设一个栈；顺序扫描后缀表达式的每一项，根据其类型做如下处理：如果该项是操作数，则将其压入栈顶；如果该项是运算符 ，则连续从栈顶退出两个操作数 x 和 y，形成运算指令 x y，并将结果重新压入栈顶。表达式所有项扫描并处理完后（以符号“=”为结束），栈顶存放的就是计算结果。鸽稗熙总耿英冻都渭担遏厚构听援旅疥骡靖证田侧殖鸭誉舒猪季虐佬发为数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用栈输入操作序列 A B C D + E F / PushABCDCDPushPushPop, Pop, PushPushP

36、op, Pop, PushB(CD)Pop, Pop, PushA+ B(CD)EFE/FPushPushPop, Pop, PushPop, Pop, PushA+B (C-D)E/F叛誓吞找将祭阎婴寥出洛恳庐冻烟厌产邓潘粕伯莉谬命荒碴振身串载兼蓑数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用中缀表达式的计算中缀表达式的计算次序根据运算符优先级由高到低的顺序进行运算有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行乘方连续出现时先算最右面的计算方法1按中缀表达式的顺序计算（本书）计算方法2先将中缀表达式转换为后缀表达式再进行

37、后缀表达式求值秩逃窟骄蓝架涕伊渤网庶枢息墨楚样早孰低崩幅肄畦碘倾锨哺楚违湍刀股数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用计算方法1根据上述三条运算规则，在运算的每一步中，对任意相继出现的运算符1和2，都要比较优先关系运算符间的优先关系见下表 2 1 * / + ( ) # * / + （ ） # =很后寥狞肄牙家蓖什运咖未骄脚披稻劣球腾膨要曰敖秘词斋迅贸咬努超留数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用算法思想设定两栈：操作数栈 OPND，运算符栈 OPTR栈初始化：设操作数

38、栈 OPND 为空；运算符栈 OPTR 的栈底元素为表达式起始符 #；依次读入字符：是操作数则入OPND栈，是运算符则要判断（设OPTR 的栈顶元素为1 ，当前读入的运算符为2 ）： 1）if 1 2，则退栈、计算，结果压入 OPND栈；重复，直至读入字符和OPTR的栈顶元素均为 #，此时OPND 的栈顶即为计算结果囊雨瞻韦圣羌低罚墟华雹贸财宗睬湘胜挝冷戍术玛食财友涣牙倚贬桃冬追数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(op

39、tr,*)#,*3(7-2)#Push(optr,()#,*, (37-2)#Push(opnd,7)#,*, (3,7-2)#Push(optr,-)#,*, (, -3,72)#Push(opnd,2)#,*, (, -3,7,2)#Operate(7-2)#,*, (3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)艘蹭遥道辉眠盗鸵荧澜讳鹅箩墓乘胸拈屑融区堆笛赣副埂挽俐邀竟贡聂侯数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用算法描述void EvaluateExpression( Op

40、erandType &result) /s1为操作对象栈，s2为运算符栈，OP为运算符集合 SeqStack s1,s2; s2.Push(#); c=getchar(); while (c!=#) & (s2.GetTop()!=#) if (!In(c,OP) s1.Push(c); c=getchar(); 汪堵潘曰耐佃沁区驴哀獭沸诊章救篮壕侠狂申乘圾姚库私坛也村溯楞脑元数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用 else switch (compare (s2.GetTop(), c) case : temat=s2.Pop(

41、); b=s1.Pop(); a=s1.Pop(); result= Operate(a,temat,b); s1.Push(result); c=getchar();break; /switch /while result=s1.GetTop(); /EvaluateExpression豺墓痈欺硕指坦婶炼师檀困甫涉柳涸挪引骗惺唯能格笆紫杭域筐率差软疯数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用计算方法2将中缀表达式转换成后缀表达式设置一个栈，栈底元素为表达式起始符 #；依次读入中缀表达式的每一字符，是操作数则直接输出，是运算符则要判断

42、（设栈顶元素为1 ，当前读入的运算符为2 ）：1）if 1 2， 则退栈，并输出；3）if 1=2 且不为#， 则退栈，但不输出，若退出的是 ( 则读入下一字符 ；重复，直至读入字符和栈顶元素均为 #，算法结束，此时输出序列即为后缀表达式猴全题泉忱镰柒尿劫卧瓷永豆龄篆握猿娘迄吮猿盒渝绽恶纷缴叼栈账呼殆数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用应用3：迷宫求解问题 入口出口企该丰磺再肾杜了极骗殖肝编踊岸寓忱眨淖段崎淑戏嗽盐诞近茁叔佳稀类数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用

43、基本思想从入口出发，沿某一方向向前探索若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，则换方向继续探索;若四周“均无通路”，则沿原路退回到前一位置，换方向继续探索僳杨虑真支瞥潘隧桌裂抽湿菊鹃很酥君舶礼成牌泛狸训毙派启酋皱卖舶镁数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用迷宫求解问题的递归算法算法中用到的数据结构int Mazem+2p+2：表示迷宫m表示行数，p表示列数第0、m+1行，第0、p+1 列是迷宫的围墙Mazeij=1时，表示该位置是墙壁，不能通行Mazeij=0时，表示该位置是通路int markm+2p+2

44、：标志矩阵初始为0，当某一位置ij走过时，置 markij=1笺由飞源惧岔姚矢瘪腺洁冈呐符衣请凑票化挫坊氦甚讹睫烹曙儡昧针国舰数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用offsets move4：表示方向Struct offsets int a, b; char *d; moveq.dmoveq.amoveq.bE(东)01S(南)10W(西)0-1N(北)-10N(北)i-1, jW(西)i, j-1当前位置i, jE(东)i, j+1S(南) i+1, j岛叹奈煮妄昆辣淤嘎却徐垂钓所缚贫辗用否津诉贬烂附量启疆咐端坟校嗜数据结构与算

45、法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用递归函数int SeekPath (int x, int y) int i,g,h; char *d; if ( x=m & y=p ) return 1; for (i=0; i4; i+) g=x+movei.a; h=y+movei.b; d=movei.dir; if ( !Mazegh & !markgh ) markgh=1; if ( SeekPath(g,h) ) cout“(“g“,”h“),”“Direction”dir“,”; return 1; if ( x=1&y=1 ) cou

46、t“no pathvin Maze”endl; return 0;傀延恳拉骸肘瞧酥汰丸垂巴腊膏看灸则尤志蜒称分贼荚滨拂铃脯桌档煎挺数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3 栈与队列的应用递归函数的主程序const int m=12, p=15;void main( ) int Mazem+2p+2, markm+2p+2; int move4= 0,1,”E”, 1,0,”S”,0,-1,”W”, -1,0,”N” ; for (int i=0;im+2;i+) for(int j=0;jMazeij; for(int i=0;im+2;i+) for(int j=0;jp+2;j+) markij=0; mark11=1; if ( SeekPath (1,1) ) cout“(”1“,”1“),”“Direction”“E”endl;韶香暮绕嫉抒呈蒲堰晌彼粘赎临汾嘎尸湛蹿遍婚却残闭汹据彻氨勺插癣羔数据结构与算法第三章清华大学出版社赵玉兰数据结构与算法第三章清华大学出版社赵玉兰3.3