进栈溢出.ppt
《进栈溢出.ppt》由会员分享,可在线阅读,更多相关《进栈溢出.ppt(76页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop双栈共享一个栈空间双栈共享一个栈空间b0 t0 t1 b10 maxSize-1V栈的应用栈的应用栈在日常生活中和计算机程序设计中有着许多应用,下面仅介绍栈在计算机中的应用。1.算术表达式的求值算术表达式的求值算术表达式中包含了算术运算符和算术量(常量、变量、函数),而运算符之间又存在着优先级,不能简单地进行从左到右运算,编译程序在求值时,不能简单从左到右运算,必须先算运算级别高的,再算运
2、算级别低的,同一级运算才从左到右(C+中有些从右到左)。因此,要实现表达式求值,必须设置两个栈,一个栈存放运算符,另一个栈存放操作数(算术量),在进行表达式求值时,编译程序从左到右扫描,遇到操作数,一律进入操作数栈,遇到运算符,则应与运算符栈的栈顶比较,若运算符优先级高于栈顶则进栈,否则退栈,退栈后,在操作数栈中退出两个元素(先退出在运算符右,后退出在运算符左),然后用运算符栈中退出的栈顶元素进行运算,运算的结果存入操作数栈中,直到扫描完毕。这时运算符栈为空,操作数栈中只有一个元素,即为运算的结果。例求表达式1+2*3-4/2的值,栈的变化如下。步骤操作数栈运算符栈说明开始两栈均为空111进入
3、操作数栈+进入运算符栈2进入操作数栈*进入运算符栈3进入操作数栈退栈2*3进入操作数栈退栈1+6进入操作数栈234567891+12+12+1117+*236+*+步骤操作数栈运算符栈说明107-进入运算符栈4进入操作数栈/进入运算符栈2进入操作数栈退栈4/2进入操作数栈退栈7-2进入操作数栈1112131415161774-74-/742-/772-5当然,算术表达式除了简单求值外,还会涉及到算术表达式的两种表示方法,即中缀表示法和后缀表示法。刚才的例3-3中的表达式就是中缀表达式,中缀表达式求值较麻烦(须考虑运算符的优先级,甚至还要考虑圆括号),而后缀表达式求值较方便(无须考虑运算符的优先
4、级及圆括号)。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律,例如,对于下列各中缀表达式:(1)3/5+8(2)18-9*(4+3)(3)(25+x)*(a*(a+b)+b)对应的后缀表达式为:(1)35/8+(2)18943+*-(3)25x+aab+*b+*2中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式,表达式中操作数次序不变,运算符次序发生变化,同时去掉了圆括号。转换规则是:设立一个栈,存放运算符,首先栈为空,编译程序从左到右扫描中缀表达式,若遇到操作数,直接输出,并输出一个空格作为两个操作数的分隔符;若遇到运算符,则必须与栈顶比
5、较,运算符级别比栈顶级别高则进栈,否则退出栈顶元素并输出,然后输出一个空格作分隔符;若遇到左括号,进栈;若遇到右括号,则一直退栈输出,直到退到左括号止。当栈变成空时,输出的结果即为后缀表达式。将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算,栈的变化及输出结果如下步骤栈中元素输出结果说明1((进栈2(1输出13(+1+进栈4(+12输出2512+退栈输出,退栈到(止6*12+*进栈7*(12+(进栈8*(12+(进栈9*(12+8输出810*(-12+8-进栈11*(-12+82输出212*(12+82-退栈输出,退栈到(止13*(/12+82-/进栈1
6、4*(/(12+82-(进栈15*(/(12+82-7输出716*(/(-12+82-7-进栈17*(/(-12+82-74输出418*(/12+82-74-退栈输出,退栈到(止19*12+82-74-/退栈输出,退栈到(止2012+82-74-/*退栈并输出步骤栈中元素输出结果说明3后缀表达式的求值后缀表达式的求值将中缀表达式转换成等价的后缀表达式后,求值时,不需要再考虑运算符的优先级,只需从左到右扫描一遍后缀表达式即可。具体求值步骤为:设置一个栈,开始时,栈为空,然后从左到右扫描后缀表达式,若遇操作数,则进栈;若遇运算符,则从栈中退出两个元素,先退出的放到运算符的右边,后退出的放到运算符左
7、边,运算后的结果再进栈,直到后缀表达式扫描完毕。此时,栈中仅有一个元素,即为运算的结果。例,求后缀表达式:12+82-74-/*的值,栈的变化情如下:步骤栈中元素说明111进栈2122进栈3遇+号退栈2和1431+2=3的结果3进栈5388进栈63822进栈73遇-号退栈2和88368-2=6的结果6进栈93677进栈1036744进栈步骤栈中元素说明1136遇-号退栈4和7123637-4=3的结果3进栈133遇/号退栈3和614326/3=2的结果2进栈15遇*号退栈2和31663*2=6进栈176扫描完毕,运算结束从上可知,最后求得的后缀表达式之值为6,与用中缀表达式求得的结果一致,但后
8、缀式求值要简单得多。4函数的嵌套调用函数的嵌套调用在函数嵌套调用中,一个函数的执行没有结束,又开始另一个函数的执行,因此必须用栈来保存函数中中断的地址,以便调用返回时能从断点继续往下执行。例设有一个主程序,它调用函数a,函数a又调用函数b,函数b又调用函数c,(见下页),其中r,s,t分别表示中断地址,我们可以用一个栈来描述调用情况(见下页)。主程序调用函数a,留下一个断点地址r进栈,然后主函数处于挂起状态,进入函数a中执行,函数a中再调用函数b,留下一个断点地址s进栈,然后函数a处于挂起状态,进入函数b中执行,函数b中调用函数c,留下一个断点地址t进栈,然后函数b处于挂起状态,进入函数c中执
9、行,函数c执行完后,要返回断点处继续执行,但返回到那一个断点呢?根据栈顶元素来决定。返回时,执行退栈操作,先退出t,故返回t断点继续执行,接着退栈退出s,故返回s断点继续执行,接着退栈退出r,返回r断点继续执行,最后栈为空,算法结束。迷宫问题小型迷宫小型迷宫路口路口 动作动作结果结果1 1(入口入口)正向走 进到 2 22 2左拐弯 进到 3 33 3右拐弯 进到 4 44 4(堵死)回溯 退到 3 33 3(堵死)回溯 退到 2 22 2正向走 进到 5 55 5(堵死)回溯 退到 2 22 2右拐弯 进到 6 66 6左拐弯 进到7 7(出口出口)43521766左左 0 直直 2 右右
10、0行行 3 行行 5 行行 6 0 0 4 0 0 0 0 0 0 7 0 0 7小小型型迷迷宫宫的的数数据据迷宫的类定义迷宫的类定义#include#include#includeclass Maze private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intCurrentPos);Maze:Maze(char*filename)/构造函数:从文件filename 中读取各路口/和出口的数据ifstreamfin;fin.open(filename,ios:in|
11、ios:nocreate);/为输入打开文件,文件不存在则打开失败 if(!fin)cout“迷宫数据文件”filename “打不开”MazeSize;/输入迷宫路口数 intsec=new IntersectionMazeSize+1;/创建迷宫路口数组创建迷宫路口数组for(inti=1;iintseci.left intseci.forward intseci.right;fin EXIT;/输入迷宫出口输入迷宫出口fin.close();迷宫漫游与求解算法迷宫漫游与求解算法intMaze:TraverseMaze(intCurrentPos)if(CurrentPos 0)/路口从路
12、口从 1 开始开始 if(CurrentPos=EXIT)/出口处理出口处理 cout CurrentPos ;return1;else /递归递归向左向左搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.left)cout CurrentPos “”;return1;else /递归递归向前向前搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.forward)cout CurrentPos “”;return1;else /递归递归向右向右搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.r
13、ight)cout CurrentPos ;return1;return 0;递归与回溯递归与回溯 常用于搜索过程常用于搜索过程n皇后问题皇后问题 在在 n 行行 n 列的列的国际象棋棋盘上,国际象棋棋盘上,若两个皇后位于同一行、同一列、若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相同一对角线上,则称为它们为互相攻击。攻击。n皇后问题是指皇后问题是指找到这找到这 n 个个皇后的互不攻击的布局皇后的互不攻击的布局。1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角
14、线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k=i+jk=n+i-j-1解题思路解题思路n n安放第安放第 i 行行皇后时,需要在列的方向从皇后时,需要在列的方向从 0 到到 n-1 试探试探(j=0,n-1)n n在第在第 j 列安放一个皇后:列安放一个皇后:uu如果在列、主对角线、次对角线方向如果在列、主对角线、次对角线方向有其它皇后,则出现攻击,撤消在第有其它皇后,则出现攻击,撤消在第 j 列安放的皇后。列安放的皇后。uu如果没有出现攻击,在第如果没有出现攻击,在第 j 列安放的列安放的皇后不动,递
15、归安放第皇后不动,递归安放第 i+1行皇后。行皇后。n n设置设置 4 个数组个数组u col n:coli 标识第标识第 i 列是否安放列是否安放了皇后了皇后u md2n-1:mdk 标识第标识第 k 条主对条主对角线是否安放了皇后角线是否安放了皇后u sd2n-1:sdk 标识第标识第 k 条次对角条次对角线是否安放了皇后线是否安放了皇后u qn:qi 记录第记录第 i 行皇后在第几列行皇后在第几列void Queen(int i)for(int j=0;jn;j+)if(第第 i 行第行第 j 列没有攻击列没有攻击)在在第第 i 行第行第 j 列安放皇后列安放皇后;if(i=n-1)输出
16、一个布局输出一个布局;else Queen(i+1);撤消撤消第第 i 行第行第 j 列的皇后列的皇后;算法求精算法求精void Queen(int i)for(int j=0;jn;j+)if(!colj&!mdn+i-j-1&!sdi+j)/*第第 i 行第行第 j 列没有攻击列没有攻击*/colj=mdn+i-j-1=sdi+j=1;qi=j;/*在在第第 i 行第行第 j 列安放皇后列安放皇后*/if(i=n-1)/*输出一个布局输出一个布局*/for(intk=0;kn;k+)cout qk ,;cout endl;else Queen(i+1);colj=mdn+i-j-1=sdi
17、+j=0;qi=0;/*撤消撤消第第 i 行第行第 j 列的皇后列的皇后*/地图四染色问题地图四染色问题使使地地图图中中相相邻邻的的国国家家或或行行政政区区域域不不重重色色,最最少少可可用用四四种种颜色对地图着色。颜色对地图着色。说明此结论,利用栈采用回溯法对地图着色。说明此结论,利用栈采用回溯法对地图着色。思想:对每个行政区编号:思想:对每个行政区编号:1-71-7 对颜色编号;对颜色编号;a a、b b、c c、d d;从从第第一一号号行行政政区区开开始始逐逐一一染染色色,每每一一个个区区域域逐逐次次用用四四种种颜颜色色进进行行试试探探,若若所所取取颜颜色色与与周周围围不不重重,则则用用栈
18、栈记记下下来来该该区区域域的的色色数数,否否则则依依次次用用下下一一色色数数进进行行试试探探。若若出出现现a-da-d均均与与周周围围发发生生重重色色,则则需需退退栈栈回回溯溯,修修改改当当前前栈栈顶顶的色数。的色数。0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0R 1:7,1:7 1 2 3 4 5 6 71 2 3 4 5 6 7 Void mapcolor(int R,int n,int s)s1=1;/1号区域染号区域染1色色I=2;J=1
19、;/I为区域号,为区域号,J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(KI)&(sK RI,K!=J)K=K+1;/若不相邻,或若相邻且不重色,对下一个区域判断。若不相邻,或若相邻且不重色,对下一个区域判断。IF(K4)THEN I=I-1;J=sI+1 (1)(2)(4)(5)(6)(7)(3)1#粉色粉色2#黄色黄色3#红色红色4#绿色绿色 1 2 3 2 1 2 3 1 2 2 4 3 1 2 3 2 4 3 1 2 3 2 4 1 2 3 2 4 3 1 1 2 2 3 41 2 3 4 5 6
20、7 S 1:7 Void mapcolor(int R,int n,int s)I=6;J=1;/I为区域号,为区域号,J为染色号为染色号 while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号 while(kI)&(sk RI,k!=J)k=k+1;=4/若不相邻,或若相邻且不重色,对下一个区域判断。若不相邻,或若相邻且不重色,对下一个区域判断。IF(K4)THEN I=I-1;J=sI+1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0
21、0 0 0 1 0 1 1 1 1 1 01 2 3 4 5 6 71 2 3 4 5 6 7 3 4 2 2 11 2 3 4 5 6 7 I=6,J=5I=6,J=5k=4k=4 a b c b a b c a b b d c a b cb d c a b cb d a b c b d caa b b c dS1:71 2 3 4 5 6 7 a 粉色粉色 b 黄色黄色c 红色红色 d 绿色绿色(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)
22、(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)队列的进队和出队队列的进队和出队 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 GC D E F Gfront rearH进进队,溢出01234567front01234567front01234567frontrearAABCrearrear空队列空队列A进进队队B,C进进队队0123456701
23、234567A退退队队B退退队队01234567D,E,F,G,H进进队队frontBCrearAfrontBCrearfrontCrearDEF GH优先级队列(PriorityQueue)F优先级队列优先级队列 是不同于先进先出队是不同于先进先出队列的另一种队列。每次从队列中取列的另一种队列。每次从队列中取出的是具有最高优先权的元素出的是具有最高优先权的元素F例如下表:任务的优先权及执行顺例如下表:任务的优先权及执行顺序的关系序的关系数字越小,优先权越高数字越小,优先权越高 优先队列的类定义优先队列的类定义#include#include$include const intmaxPQSiz
24、e=50;/缺省元素个数缺省元素个数template classPQueuepublic:PQueue();PQueue()deletepqelements;void PQInsert(const Type&item);TypePQRemove();void makeEmpty()count=-1;intIsEmpty()const return count=-1;int IsFull()const return count=maxPQSize;intLength()const return count;private:Type*pqelements;/存放数组存放数组intcount;/队列
25、元素计数队列元素计数 优先队列部分成员函数的实现优先队列部分成员函数的实现 template PQueue:PQueue():count(-1)pqelements=new TypemaxPQSize;assert(pqelements!=0);/分配断言分配断言template voidPQueue:PQInsert(const Type&item)assert(!IsFull();/判队满断言判队满断言count+;pqelementscount=item;template Type PQueue:PQRemove()assert(!IsEmpty();/判队空断言判队空断言Typemin
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 溢出
限制150内