《第3章栈和队列ppt课件》由会员分享，可在线阅读，更多相关《第3章栈和队列ppt课件（51页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 栈和队列栈和队列北京师范大学北京师范大学 教育技术学院教育技术学院 杨开城杨开城秽轿收邮肚催遭护出软偷瘫按挤沼咀拈纫吠氦骑店髓鱼柬吃祁围直盟馆能第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈栈的定义栈的定义如果一个线性表的插入和删除操作只能在线性表的一端进行，而不能如果一个线性表的插入和删除操作只能在线性表的一端进行，而不能在其他位置上进行，那么这个线性表被称为在其他位置上进行，那么这个线性表被称为栈栈(Stack)。后进先出后进先出(Last In First Out)栈的操作包括：栈的操作包括： 初始化空栈初始化空栈 销毁栈销毁栈 判断栈的空和满判断栈的空和满 入
2、栈入栈 出栈出栈币弹崇眼勺乎橱梅假宅马扳霸啤组削叫桶如烧痔札岂抓谭递棠范乃涤佛深第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈顺序栈顺序栈(1)顺序栈的数据类型定义如下：顺序栈的数据类型定义如下：typedef struct stack_tag elemtype *elem; /*指向存放数据元素的内存块*/ int top; /*栈顶标识，elemtop是栈顶元素*/ int size; /*栈的容量*/ SQSTACK;峡浦肪戎琢洱鹰窗蒲兼石跟叫时醛楷雪贩磺遗茸柿覆教键诌鹏盾篡灌仕蒸第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈顺序栈顺序栈(2)1初始化栈初始化
3、栈int InitSqstack(SQSTACK *S, int n)/*初始化顺序栈，栈的容量是n。成功则返回1，否则返回0*/ S-elem=(elemtype *)malloc(n*sizeof(elemtype); /*为数据元素分配内存*/ if(S-elem=NULL)return 0; /*初始化失败*/ S-size=n; /*设置栈的容量*/ S-top=-1; /*设置栈为空栈*/ return 1; 2销毁栈销毁栈void DestroySqstack(SQSTACK *S)/*释放栈所占有的内存*/ free(S-elem); /*释放内存，并设置为NULL*/ S-e
4、lem=NULL; S-top=-1;/*将其他成员设置成安全值*/ S-size=0;驻鹅洋盈树穿抿彤恫演翠蛆照颠冻捅申静庇仁稠摆围陡营耐染魏链壹蔚咨第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈顺序栈顺序栈(3)3入栈入栈int Push(SQSTACK *S,elemtype e)/*在栈顶一端插入数据元素e，操作成功，则返回1，否则返回0*/ if(IsSqstackFull(*S)return 0; /*栈满，操作失败*/ S-top+;/*top增1*/ S-elemS-top=e; /*将e赋值成新的栈顶*/ return 1;4出栈出栈int Pop(SQSTAC
5、K *S,elemtype *e)/*获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回0*/ if(IsSqstackEmpty(*S) return 0; /*如果栈空，操作失败*/ *e=S-elemS-top; /*获取栈顶元素*/ S-top-; /*删除栈顶*/ return 1;氟裸脑窜魄沤它扼荔围斯瓶皑皖士梭颜李仁吐醉映嗡铺饼芋脉硒凯松匣指第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈顺序栈顺序栈(4)5判断栈空、栈满判断栈空、栈满int IsSqstackEmpty(SQSTACK S)/*如果栈空，则返回1，否则返回0*/ return S.top=-
6、1; /*top是栈顶标识，是-1时表示空栈*/int IsSqstackFull(SQSTACK S)/*如果栈满，则返回1，否则返回0*/ return S.top=S.size-1; /*top作为elem的下标，其最大值是size-1 */踢卯屏蝴登愁灸浦幕相另流舷镣尉沏虞陋浊遭眺亭样掐乾砸募婿拐睛与革第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈链式栈链式栈(1)链式栈的数据类型定义：链式栈的数据类型定义：typedef struct node_tag elemtype data; struct node_tag *next; NODE, *NODEPTR, *LINK
7、STACK;链式栈的操作：链式栈的操作：1入栈入栈int Push(LINKSTACK L,elemtype e)/*将数据元素e入栈*/ NODEPTR p; p=(NODEPTR)malloc(sizeof(NODE); if(p=NULL)return 0; p-data=e;/*形成数据元素e的结点p*/ p-next=L-next;/*将p插到头结点后面*/ L-next=p; return 1; 夷珍运迁鲸忠撑仇运攒浚纲颜胰拆续条诽梆超硼度交佯醚凳又溜犊恿潜把第3章栈和队列ppt课件第3章栈和队列ppt课件一、栈一、栈链式栈链式栈(2)2出栈出栈int Pop(LINKSTACK
8、L, elemtype *e)/*获取栈顶数据，删除栈顶*/ NODEPTR p; p=L-next; /*p指向栈顶*/ if(p=NULL) return 0; L-next=p-next; /*摘除栈顶*/ *e=p-data; /*获取原栈顶数据*/ free(p); /*释放原栈顶结点*/ return 1; 海斜港穴娟吃谊涸停照堂碑铝会昼琶演毒眠神甩倡悯峙怖日故絮总舔疆促第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用括号匹配检查括号匹配检查while(stri!=0) ch=stri; if(ch=() Push(&s,ch); else if(ch=)
9、if(!Pop(&s,&ch) /*缺少左括号与当前右括号配对*/ DestroySqstack(&s); return 0; i+; if(IsSqstackEmpty(s) i=1; else i=0; /*说明有左括号没有配对*/ DestroySqstack(&s);/*销毁栈*/ return i; 【任务描述】【任务描述】 要求设计算法，对于给定的表达式字符串，检查其中括号是否匹配。要求设计算法，对于给定的表达式字符串，检查其中括号是否匹配。typedef char elemtype;int CheckBracket(char *str)/*如果字符串str中括号配对，则返回1，否
10、则返回0*/ int i,len; SQSTACK s; /*定义一个栈*/ elemtype ch; len=strlen(str); /*将栈s的最大容量设置为字符串的长度*/InitSqstack(&s,len); /*初始化栈*/ i=0; /*从左向右扫描字符串，遇到括号进行入栈和出栈处理*/瑰潭甥钵咯愚圾收况邵迭灯迅届臻挠瘴溢峰为涸懂漂去隘律南潞蔷磕晒篡第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用算术表达式求值算术表达式求值(1)与表达式求值有关的知识：与表达式求值有关的知识：表达式中运算符具有优先级和结合性特征表达式中运算符具有优先级和结合性特征中缀表
11、达式中，双目运算符需要两个操作数，一个操作数在左边，另中缀表达式中，双目运算符需要两个操作数，一个操作数在左边，另一个在右边。一个在右边。表达式求值算法的基本思想：表达式求值算法的基本思想：从左向右扫描表达式，获取单词。从左向右扫描表达式，获取单词。如果单词是操作数，则入操作数栈；如果单词是操作数，则入操作数栈；如果单词是常规运算符或者左括号如果单词是常规运算符或者左括号: :如果单词的栈外优先级数高，则如果单词的栈外优先级数高，则将运算符入栈；否则反复出栈处理，直到单词栈外优先级数高为止。将运算符入栈；否则反复出栈处理，直到单词栈外优先级数高为止。如果单词是右括号，则反复出栈处理，直到运算符
12、栈顶是左括号为止。如果单词是右括号，则反复出栈处理，直到运算符栈顶是左括号为止。将左括号出栈。将左括号出栈。如果单词是如果单词是= =，反复出栈处理，直到运算符栈空。这时操作数栈，反复出栈处理，直到运算符栈空。这时操作数栈的栈顶就是表达式的值。的栈顶就是表达式的值。【任务描述】【任务描述】已知已知str是某算术表达式字符串，编写算法求得这个算术表达式的值。比如，是某算术表达式字符串，编写算法求得这个算术表达式的值。比如，str的内容是的内容是”22*5+6*(10-5)”，那么算法求得的值应该是，那么算法求得的值应该是140。这个算法不。这个算法不考虑单目运算符。为了简便起见，只允许使用加考虑
13、单目运算符。为了简便起见，只允许使用加(+)、减、减(-)、乘、乘(*)、除、除(/)、乘方乘方()这这5个运算符，这个运算符，这5个运算符都是双目运算符。个运算符都是双目运算符。运算符运算符运算符运算符优先级数优先级数优先级数优先级数栈内优栈内优栈内优栈内优先级先级先级先级栈外优栈外优栈外优栈外优先级先级先级先级 5 56 6* /* /4 43 3+ -+ -2 21 1 ( (0 07 7屏天谗窟涤矩晓厌苫想哗八柏凋侥隆涝频令砖戊积凋泌勉温吕嘉焦衔窝介第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用算术表达式求值算术表达式求值(2)单词的数据类型：单词的数据类型：
14、typedef structint type; /*标识word成员是运算符还是操作数*/ union float X; char op; word; WORD;typedef WORD elemtype;#define ERROR 0#define OPERAND 1 /*标识操作数*/#define OPERATOR 2 /*标识运算符*/算法算法int Evaluate(char *exp, float *result)/*计算表达式exp的值，*result存放计算结果。如果操作成功，返回1，否则返回0*/ int k=0; WORD w,W1,W2,W3; SQSTACK s1,s2
15、;/*s1是操作数栈，s2是运算符栈*/ *result=0; InitSqstack(&s1,50);/*初始化两个栈*/ InitSqstack(&s2,50);w.word.op=(; Push(&s2,w);/*事先在运算符栈放置一个左括号*/猜陡累轨汇跋校集从扣全农俯硬毕脊滦躁硕否满茶硷式折径典碟楔崩艇戊第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用算术表达式求值算术表达式求值(3)while(1) w=GetWord(exp,&k);/*获取一个单词，k指向下一个单词*/ if(w.type=ERROR) return 0;/*表达式有错*/ else i
16、f(w.type=OPERAND) Push(&s1,w);/*是操作数,入栈*/ else if(w.type=OPERATOR) /*是运算符*/ switch(w.word.op) case ): while(s2.elems2.top.word.op!=() /*反复出栈处理，直到栈顶是左括号*/ if(!Pop(&s1,&W2)|!Pop(&s1,&W1)|!Pop(&s2,&W3) /*表达式有错*/ DestroySqstack(&s1); DestroySqstack(&s2); return 0; if(!(W2.word.X=0&W3.word.op=/) W1.word.
17、X=comput(W1.word.X,W3.word.op,W2.word.X); Push(&s1,W1);/*计算结果入栈*/ else DestroySqstack(&s1);DestroySqstack(&s2); return 0; /*表达式计算出现了除以0的情况*/ Pop(&s2,&W3);/*栈顶的左括号出栈*/ break;胯苯从卖疽哆碴吓雷谷椽电钧舟否雌犯空心菲段于仆樱卉辕牙嘶珊债骑讼第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用算术表达式求值算术表达式求值(4) case =: while(s2.elems2.top.word.op!=() /
18、*反复出栈处理，直到遇到最开始放在栈里的左括号为止*/ if(!Pop(&s1,&W2)|!Pop(&s1,&W1)|!Pop(&s2,&W3) /*表达式有错*/DestroySqstack(&s1); DestroySqstack(&s2); return 0; if(!(W2.word.X=0&W3.word.op=/) W1.word.X=comput(W1.word.X,W3.word.op,W2.word.X); Push(&s1,W1);/*计算结果入栈*/ else DestroySqstack(&s1);DestroySqstack(&s2); return 0; /*表达式
19、计算出现了除以0的情况*/ *result=s1.elems1.top.word.X;/*操作数栈顶的值就是最终的表达式的值*/ if(s1.top!=0) DestroySqstack(&s1); DestroySqstack(&s2); return 0; else DestroySqstack(&s1); DestroySqstack(&s2); return 1;黎蚂蓝扦匡很敢敷铲颊拯乞签杂沥牙夏鸽癌颧搀牺长搏肠耻沫粕焚咕讥嚷第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用算术表达式求值算术表达式求值(5) default: while(InPri(s2.ele
20、ms2.top.word.op)OutPri(w.word.op) /*只要栈顶运算符的优先级数大于栈外运算符的优先级数，则反复出栈处理*/ if(!Pop(&s1,&W2)|!Pop(&s1,&W1)|!Pop(&s2,&W3) DestroySqstack(&s1); DestroySqstack(&s2); return 0; if(!(W2.word.X=0&W3.word.op=/) W1.word.X=comput(W1.word.X,W3.word.op,W2.word.X);Push(&s1,W1); else DestroySqstack(&s1); DestroySqsta
21、ck(&s2); return 0; Push(&s2,w);/*此时栈外运算符优先级数高，入栈*/ break; /*属于switch语句*/ /*属于while(1)语句*/ 蚌扬计育几魔缸嫌表屡殖堰验瞧医巍浩装范相珐几任岗锈晃堑快潮坝型耽第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用迷宫路径求解迷宫路径求解(1)【任务描述】【任务描述】给定某个迷宫的布局及其入口和出口的坐标（如图给定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，所示，注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空
22、白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有路径。路径。需要解决需要解决2个问题：个问题：迷宫在计算机中如何表示。迷宫在计算机中如何表示。 int maze 12= 1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,1,0,0,1,1,1, 1,0,1,0,1,0,1,0,1,1,1,1, 1,0,1,0,0,0,1,0,1,1,1,1, 1,0,1,1,1,1,1,0,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1
23、,1,1 ;如何探索从入口到达出口的所有路径。如何探索从入口到达出口的所有路径。深度优先探索回溯：从当前位置出发，向四个方向探索，如果发现某方向的深度优先探索回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位置）。走过的地方要打上置）。走过的地方要打上“已走标记已走标记”，回退时要将，回退时要将“已走已走”标记清除。标记清
24、除。眯享勤届伴蛤幼绷讫前盎捆氨常父鱼纸潍饲按鞠骂耙招催组欲按存腥啪情第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用迷宫路径求解迷宫路径求解(2)typedef struct int x,y;/*位置坐标*/ int v; /*探索方向*/ elemtype;int movex5=0,0,1,0,-1;int movey5=0,-1,0,1,0;#define M 27#define N 25#define MAXSIZE 200算法：算法：void go(int mazeMN ,int x0,int y0 ,int xx ,int yy)/*找出maze中从入口(x,
25、y)到出口(xx,yy)的所有路径*/ int x,y,x1,y1,v; SQSTACK s; /*存放探索路径的栈*/ elemtype e; InitSqstack(&s,MAXSIZE);/*初始化栈*/ 有宰轩十置醒兄蓖鹤栽害玄恢苞琴衰遭招攘滩帮岩段恳肆耳坤娘琐环浙泼第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用迷宫路径求解迷宫路径求解(3) e.x=x0; e.y=y0; e.v=0; Push(&s,e);/*将入口入栈，探索方向是0，准备探索*/ mazey0x0=2;/*打上已走标记*/ while(!IsSqstackEmpty(s) /*如果栈未空
26、，探索没有结束*/ Pop(&s,&e); x=e.x; y=e.y; /*弹出栈顶，作为当前位置*/ v=e.v+1; /*探索新的方向*/ if(e.v0)/*说明这次出栈是回退操作，清除原探索位置的已走标记*/ mazey+moveye.vx+movexe.v=0;髓全捎仰忆湃讣秧锻焊铃审藩袖蔡航煌哑踊赢霉翅猫惹餐菜两整存杂铜仪第3章栈和队列ppt课件第3章栈和队列ppt课件二、栈的应用二、栈的应用迷宫路径求解迷宫路径求解(4) while(v0&x10&y1=4*/ else return Ackerman(n-1,Ackerman(n,x,y-1),x); /*递归调用*/ 押病焊主
27、踌摇妆乳片茵甄庙奶浓亨槐碱郁弹暴壮铸形袍卒浩砷阀戏碾挑善第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法Ackerman函数函数(2)非递归算法非递归算法(I)【算法思想】【算法思想】Ackerman函数的非递归算法包含函数的非递归算法包含两种基本操作：两种基本操作：递归分解，这是一个循递归分解，这是一个循环操作。即如果当前问题不环操作。即如果当前问题不是递归终点，就将当前问题是递归终点，就将当前问题不断递归分解，将产生的第不断递归分解，将产生的第二个子问题入栈，将产生的二个子问题入栈，将产生的第一个问题作为当前问题，第一个问题作为当前问题，直到
28、遇到递归终点为止；遇直到遇到递归终点为止；遇到递归终点时即可求值。到递归终点时即可求值。弹出栈顶问题，转去递弹出栈顶问题，转去递归分解。归分解。这两个操作构成一个循环。当这两个操作构成一个循环。当栈为空时，循环结束，算法终止。栈为空时，循环结束，算法终止。入栈信息是入栈信息是(n,x)拟瘫间善酬忆舷注曾逞吏庞身傣筛开浦矛下蓟凋简蕴患刮议协棕栋畔蠕物第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法Ackerman函数函数(3)typedef structint n,x; elemtype; #define MAXSIZE 500int Ackerm
29、an1(int n,int x,int y) SQSTACK s; elemtype e; int val; /*用来存放函数值*/ InitSqstack(&s,MAXSIZE);while(1) /*递归分解和出栈处理*/ while(n0&y0) e.n=n-1;e.x=x; Push(&s,e);/*将问题(n-1,x)入栈*/ y-;/*递归分解,y参数规模减1*/ /*此刻当前问题是A(n,x,0)或A(0,x,y) */val=AkmValue(n,x); if(IsSqstackEmpty(s) /*求值完毕*/ DestroySqstack(&s); return val;
30、else /*否则，弹出栈顶问题信息(n,x)，作为当前问题转去递归*/ Pop(&s,&e); n=e.n;x=val;y=e.x; /*当前问题变为(n,val,x)*/ /while(1) int AkmValue(int n,int x) if(n=0)return x+1; else /*属于y=0的情况*/ switch(n) case 1:return x; case 2:return 0; case 3:return 1; default:return 2;/*n=4*/ 胯兜绑拐入坑沁砂澎拾口皇邱舟蓄是赐庐鸡幻航盯嗡毕拍朱藏玛勉砂在碗第3章栈和队列ppt课件第3章栈和队列pp
31、t课件三、递归问题的非递归算法三、递归问题的非递归算法Ackerman函数函数(4)非递归算法非递归算法(II)【算法思想】【算法思想】首先将初始问题入栈，然后进入首先将初始问题入栈，然后进入递归分解和出栈处理的循环。递归分解和出栈处理的循环。先执行对栈顶问题的递归分解，先执行对栈顶问题的递归分解，一直分解到递归终点。求得递归一直分解到递归终点。求得递归终点的函数值终点的函数值valval，并弹出栈顶。，并弹出栈顶。如果栈为空，则算法终止，返回如果栈为空，则算法终止，返回valval；否则出栈问题信息；否则出栈问题信息(n,x,y)(n,x,y)，形成新的问题信息，形成新的问题信息(n-1,v
32、al,x)(n-1,val,x)后入栈。后入栈。这时栈顶问题可能不是递归终点，这时栈顶问题可能不是递归终点，是需要继续递归分解的问题。这是需要继续递归分解的问题。这时转到前面进行栈顶问题的递归时转到前面进行栈顶问题的递归分解操作。分解操作。入栈信息是入栈信息是(n,x,y)入栈的问题信息不同，算法细节也会不同入栈的问题信息不同，算法细节也会不同蝶联肝烟沤渊潞谁兴成因狙班寿阔凛泼雨谤互畔荤四酱把教趴展撒骋蟹踩第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法Ackerman函数函数(5)#define MAXSIZE 500typedef struc
33、tint n,x,y; elemtype;int Ackerman2(int n,int x,int y) SQSTACK s; elemtype e; int val; InitSqstack(&s,MAXSIZE) e.n=n;e.x=x;e.y=y; Push(&s,e); /*初始问题(n,x,y)入栈*/ while(1) e=s.elems.top; /*取栈顶问题，开始递归分解*/ n=e.n;x=e.x;y=e.y; while(n0&y0) y-; e.n=n;e.x=x;e.y=y; Push(&s,e); /*遇到递归终点，求值*/val=AkmValue(n,x);/*
34、弹出栈顶，因为是递归终点*/ Pop(&s,&e); if(IsSqstackEmpty(s) DestroySqstack(&s); return val; else/*将栈顶问题转换为(n-1,val,x)*/ Pop(&s,&e); e.n-; e.y=e.x; e.x=val; Push(&s,e); /while 1 夜末况打叮勇勤演教酋吸捶鳞帆议辜榴由腋蝎牢枷雷塔彩仿石属导疏威芭第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法汉诺塔问题汉诺塔问题(1)【任务描述】【任务描述】假设有假设有3 3根柱子，第根柱子，第1 1根根柱子上套着柱
35、子上套着n n个半径大小不同的盘子个半径大小不同的盘子（盘子中央有小孔），并且大盘子在（盘子中央有小孔），并且大盘子在下面，小盘子在上面，见图下面，小盘子在上面，见图3_143_14。要。要求将第求将第1 1根柱子上的盘子搬到第根柱子上的盘子搬到第3 3根柱根柱子上。在搬动过程中，可以使用第子上。在搬动过程中，可以使用第2 2根柱子暂时存放盘子，但无论何时都根柱子暂时存放盘子，但无论何时都必须保证大盘子在下面，小盘子在上必须保证大盘子在下面，小盘子在上面，并且一次只能搬动一个盘子。面，并且一次只能搬动一个盘子。递归算法递归算法void hanoi(int n,int A,int B,int C
36、)/*汉诺塔的递归算法汉诺塔的递归算法*/ if(n=1)move(A,C);/*递归出口递归出口*/ else hanoi(n-1,A,C,B); move(A,C); hanoi(n-1,B,A,C); 馅藻推烯赏没售旭毡比求杉庚徽千咳脉添竖哼施滩拭敢渺性重绪鬃逆炊米第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法汉诺塔问题汉诺塔问题(1)非递归算法：非递归算法：typedef structtypedef structint n,x,y,z;int n,x,y,z; elemtype; elemtype;void hanoi1(int n,i
37、nt A,int B,int C) void hanoi1(int n,int A,int B,int C) /*汉诺塔的非递归算法*/ SQSTACK s; elemtype e; int t; SQSTACK s; elemtype e; int t; InitSqstack(&s,200); InitSqstack(&s,200); e.n=n; e.x=A; e.y=B; e.z=C; e.n=n; e.x=A; e.y=B; e.z=C; Push(&s,e); Push(&s,e);/*将初始问题(n,A,B,C)入栈*/厂需轧贰悦涡妒娠舞畴猴卖措薛酪粕钱簇铺任褥勺薪陀邹桌点几萨虱
38、冬悄第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法汉诺塔问题汉诺塔问题(2) while(1) while(1) /*进入递归分解和出栈处理的循环*/ e=s.elems.top; e=s.elems.top; /*取栈顶问题*/ while(e.n1) while(e.n1) /*递归分解的循环*/ e.n-; t=e.y; e.y=e.z; e.z=t; e.n-; t=e.y; e.y=e.z; e.z=t; Push(&s,e); Push(&s,e); Pop(&s,&e); Pop(&s,&e);/*栈顶是递归终点，出栈*/ mov
39、e(e.x,e.z); move(e.x,e.z);/*完成递归终点的操作*/ if(IsSqstackEmpty(s) if(IsSqstackEmpty(s) /*如果栈空，操作结束，算法终止*/ DestroySqstack(&s); DestroySqstack(&s); return; return; Pop(&s,&e); Pop(&s,&e);/*弹出栈顶问题，准备转化为第二个子问题*/ move(e.x,e.z); move(e.x,e.z);/*Move(A,C)，这一步做完了，才能转化第二个子问题*/ e.n-; t=e.x; e.x=e.y; e.y=t; e.n-; t
40、=e.x; e.x=e.y; e.y=t; /*形成第二个子问题(n-1,B,A,C)*/ Push(&s,e); Push(&s,e);/*(n-1,B,A,C)入栈，转到前面，进行栈顶问题的递归分解*/ 欣裕渐航顿端敷察苯虫瞥惑旭踪形较构挝垮给类赣膨叉荫仇别眼保肝草绵第3章栈和队列ppt课件第3章栈和队列ppt课件三、递归问题的非递归算法三、递归问题的非递归算法设计思路设计思路亨给粗谰疮俭足晋戏晰课屡廉撩匿议芬候虱燃麻汪您杉烁祟以浑割命单吓第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列队列的定义队列的定义队列队列(Queue)也是一种操作受限的线性表。与栈不也是一种操作受
41、限的线性表。与栈不同的是，队列只能在一端插入数据元素，在另一端同的是，队列只能在一端插入数据元素，在另一端删除数据元素。删除数据元素。 先进先出先进先出(First In First Out) 队列的基本操作包括：队列的基本操作包括：初始化空队销毁队列判断队空或队满初始化空队销毁队列判断队空或队满入队入队出队出队获得队列长度获得队列长度辉送猛嫁韧泌驼彝寞屎挨暂刮深奢肚桌赛函写榨钙编策郑曼疽靖丧哈淹包第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列顺序顺序(循环循环)队列队列(1)数据类型定义：数据类型定义：typedef struct elemtype *elem; /*指向存
42、放队列数据元素的数组*/ int front,rear; /*分别是队首和队尾下标，也称为队首指针和队尾指针*/ int size; /*数组elem的容量*/ SQQUEUE;基本操作基本操作1初始化空队初始化空队int InitSqqueue(SQQUEUE *q,int n)/*初始化队列，将队列容量设为n。成功则返回1，否则返回0*/ /*容量为n的顺序队列，需要容量是n+1数组*/q-elem=(elemtype *)malloc(n+1)*sizeof(elemtype); if(q-elem=NULL)return 0; /*操作失败*/ q-front=q-rear=0; /*
43、队首指针、队尾指针都归零*/ q-size=n+1; /*设置容量*/ return 1; 缉赡瞩嘎教键研侵笼亿烦彼桌酱枕客倍锄编抬歇甚概拉罗起惹汐脖控掐酪第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列顺序顺序(循环循环)队列队列(2)2销毁队列销毁队列void DestroySqqueue(SQQUEUE *q)/*销毁队列*/ free(q-elem); /*释放队列所占内存*/ q-elem=NULL; /*将其他成员设置成安全值*/ q-front=q-rear=0; q-size=0; 3判断队空判断队空int IsSqqueueEmpty(SQQUEUE q)/*
44、如果队空，则返回1，否则返回0*/ return q.front=q.rear; 仇仲垒喷浑熄骗嘿粘位挂役咙则猾念双新另添错祁肉砌躁擅巩赫拙端瓦掳第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列顺序顺序(循环循环)队列队列(3)4入队入队int EnSqqueue(SQQUEUE *q, elemtype e)/*将数据元素e入队，操作成功返回1，否则返回0*/ if(IsSqqueueFull(*q)return 0; q-elemq-rear=e; /*将e放置在队列中*/ q-rear=(q-rear+1)%q-size; /*队尾指针向后移动*/ return 1; 5
45、判断队满判断队满int IsSqqueueFull(SQQUEUE q)/*如果队满，则返回1，否则返回0*/ return q.front=(q.rear+1)%q.size; 畸朗剪董鸣妒证扮例招颅怯压精使乘角呸猾牵妊咏纂塞记辩铁税框铅纽玫第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列顺序顺序(循环循环)队列队列(4)6出队出队int DeSqqueue(SQQUEUE *q, elemtype *e)/*将队首元素复制给*e,操作成功返回1，否则返回0*/ if(IsSqqueueEmpty(*q)return 0; /*如果队空，操作失败*/ *e=q-elemq-f
46、ront; /*复制队首元素*/ q-front=(q-front+1)%q-size; /*队首指针向后移动*/ return 1; 7获得队列长度获得队列长度int SqqueueLen(SQQUEUE q)/*返回队列长度*/ return (q.size+q.rear-q.front)%q.size; 意秤穆两亏御够啤汕戏箍团搪荷囊谜编粱艇曼宙眷茬元钾垃憾仔帚旬尝向第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列链式队列链式队列(1)数据类型定义：数据类型定义：typedef struct node_tag elemtype data; struct node_tag
47、*next; NODE, *NODEPTR; /*定义单链表结点和指针类型*/typedef struct NODEPTR front,rear;/*队首队尾指针*/LKQUEUE;基本操作：基本操作：1初始化空队初始化空队void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL; 览灾押鹤猪幌著禁帘跌茨豁琐激菇愈窒挎崖氦硷端治疲框迢玉亭暴峪侄睫第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列链式队列链式队列(2)2销毁队列销毁队列void DestroyLkqueue(LKQUEUE *Q) NODEPTR p; while(Q-fro
48、nt!=NULL) p=Q-front; Q-front=p-next; /*摘除队首结点*/ free(p); Q-rear=NULL; 岳盼咆穿冤然革掖郊誓驱勃土绥驴畅醚袍炸藐哇诅雇殉灌沁汽铲菏统用蓉第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列链式队列链式队列(3)3入队入队int EnLkqueue(LKQUEUE *Q,elemtype e) NODEPTR p; p=(NODEPTR)malloc(sizeof(NODE); if(p=NULL)return 0; p-data=e; p-next=NULL; if(Q-front=NULL) /*如果队空，则将队
49、首队尾指针都指向结点p*/ Q-front=Q-rear=p;else /*否则将结点p插入到队尾结点后面*/ Q-rear-next=p; Q-rear=p; return 1; 把厢挤汗畜牲肮液南碾颓挠仑较交幽芭襄水誉揽意缉闸翘似秧屹锥逛娱砸第3章栈和队列ppt课件第3章栈和队列ppt课件四、队列四、队列链式队列链式队列(4)4出队出队int DeLkqueue(LKQUEUE *Q,elemtype *e) NODEPTR p; if(Q-front=NULL)return 0; p=Q-front; Q-front=p-next; if(Q-front=NULL)Q-rear=NULL
50、;/*如果队空，则将队尾指针置NULL*/ *e=p-data; free(p); return 1; 追众铆敲妊咳骑该士泽窍懦挪褪员齿览抬悼盘涌侠辽卑彬仓窑障惕不慨律第3章栈和队列ppt课件第3章栈和队列ppt课件五、队列的应用五、队列的应用迷宫最短路径迷宫最短路径(1)【任务描述】【任务描述】给定某个迷宫的布局及其入口和出口的坐标，给定某个迷宫的布局及其入口和出口的坐标，设计算法找出从入口到出口的最短路径。设计算法找出从入口到出口的最短路径。思考方式：从入口出发，走思考方式：从入口出发，走1步可以到达哪里？走步可以到达哪里？走2步可以步可以到达哪里？走到达哪里？走3步可以到达哪里？步可以到
51、达哪里？算法需要一个辅助队列算法需要一个辅助队列梨暗串箍纤昂顺为抵坤匆厦看矫焊叉颐葬理斌涉锨边弦做碉腿减洲仰畜灿第3章栈和队列ppt课件第3章栈和队列ppt课件五、队列的应用五、队列的应用迷宫最短路径迷宫最短路径(2)typedef struct int x,y,pre;/*(x,y)是坐标，pre是前驱位置在队列数组中的下标*/ elemtype;int movex5=0,0,1,0,-1,movey5=0,-1,0,1,0;void go1(int mazeMN ,int x,int y ,int xx ,int yy) /*求最短路径求最短路径*/ elemtype e; SQQUEUE
52、 q; int x1,y1,i,k; if(!InitSqqueue(&q,M*N) return;/*初始化队列失败*/ /*入口的前驱设成-1，表示空*/e.x=x; e.y=y; e.pre=-1; EnSqqueue(&q,e);/*入口入队*/mazeyx=2;/*打上已走标记*/while(!IsSqqueueEmpty(q) /*只要队不空，就循环*/ DeSqqueue(&q,&e);/*出队一个位置*/ x1=e.x; y1=e.y;/*设置相邻位置信息入队时的前驱下标*/ e.pre=(q.front-1)%q.size; 亢揽花丝庞滥湍煎李窘炊笆并丸赚崇史伴和棍喉疾傍底姜
53、谬蔫涟狐夯进狡第3章栈和队列ppt课件第3章栈和队列ppt课件五、队列的应用五、队列的应用迷宫最短路径迷宫最短路径(3)for(i=1;i=4;i+) /*从四个方向探索相邻位置是否可走*/ e.x=x1+movexi; e.y=y1+moveyi; if(mazee.ye.x=0) /*某个相邻位置可走*/ EnSqqueue(&q,e);/*将其入队*/mazee.ye.x=2;/*打上“已走”标记*/if(e.x=xx&e.y=yy) /*遇到出口，输出最短路径，并返回*/ k=(q.rear-1)%q.size; while(k!=-1) /*从出口开始,沿着pre,逆序遍历队列中的数
54、据单元,直到入口*/ e=q.elemk; 输出坐标输出坐标(e.x,e.y)/*这条指令不是C语句*/ k=q.elemk.pre; DestroySqqueue(&q); return; /*属于for语句*/ /*属于while语句*/逻绦菊蛮鞘敖疹连爷刘瑟滚旭幕跟屏脉屠馆搁日咖同故女莱檬温领诵辈洼第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(1)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数
55、函数汉诺塔问题汉诺塔问题亦癣唱佣辙骇瘫夺颧桅拍窑得陨浙褪戌乏嫉旧翰猴垛筛伞狱玲聪须愉诽欢第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(2)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题诊蝴转壳叹辛储沂踢嚣需爱摄剐杰宏裕岳玲灰任韩予卷账紫柿腊勋胶殷敞第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(3)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算
56、法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题并联囱驻抗剂敏后缴企慑粗孺睦尽舒辣柴己倘满登唉戍宜帐汲晾泽寐稗四第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(4)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题茸湛哑僻摊泪倾耪仓闽捕链弯炙狭
57、漓鸿惺戳此芋摊翔纬谨皇蛾寄跺痊陋好第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(5)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题挖李元铃陇安暮咙昼大颤上辽慌妄诅攘腊谨级谜汁苇殷架躲啄奸左客啸姿第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(6)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径
58、迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题钡前液嗓留啃孜途魄倡鸭写避啡棚郎葡吃赔挨矮邯办贤阀悠煮设滥捣炒泌第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(7)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题蔓招辣误昆翠扁付毅竿闸骡依当崎侦容嗓液并饥蚌西啼鄂磕祝耸梅嫂必架第3章栈和队列ppt
59、课件第3章栈和队列ppt课件导航图导航图(8)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题唇磁舶咀蚀饿罢曾惹稗空胸殖袍塞帚堂型欣漱澎烷议六戒密寝乖醚榴孺轴第3章栈和队列ppt课件第3章栈和队列ppt课件导航图导航图(9)栈和队列栈和队列栈栈栈的应用栈的应用递归问题的递归问题的非递归算法非递归算法队列队列队列的应用队列的应用(迷宫最短路径迷宫最短路径)括号匹配检查括号匹配检查表达式求值表达式求值迷宫路径迷宫路径斐波那契斐波那契Ackerman函数函数汉诺塔问题汉诺塔问题固篙问春巍簇靴筒乌货美触倒谆屿侩绚排脐敷却幼呸淌细场力个桨南蚂窥第3章栈和队列ppt课件第3章栈和队列ppt课件
