ImageVerifierCode 换一换
格式:PPT , 页数:51 ,大小:1.07MB ,
资源ID:373594      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
注意:如需开发票,请勿充值!
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-373594.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(第3章 栈和队列.ppt)为本站会员(towelfact221)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

第3章 栈和队列.ppt

1、第3章 栈和队列,北京师范大学 教育技术学院 杨开城,一、栈栈的定义,如果一个线性表的插入和删除操作只能在线性表的一端进行,而不能在其他位置上进行,那么这个线性表被称为栈(Stack)。 后进先出(Last In First Out)栈的操作包括: 初始化空栈 销毁栈 判断栈的空和满 入栈 出栈,一、栈顺序栈(1),顺序栈的数据类型定义如下: typedef struct stack_tag elemtype *elem; /*指向存放数据元素的内存块*/int top; /*栈顶标识,elemtop是栈顶元素*/int size; /*栈的容量*/SQSTACK;,一、栈顺序栈(2),1初始

2、化栈 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-elem=N

3、ULL;S-top=-1;/*将其他成员设置成安全值*/S-size=0; ,一、栈顺序栈(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(SQSTACK *S,elemtype *e) /*获取栈顶数据元素,并删除栈顶。操作成功,则返回1,否则返回0*/if(IsSqstackEmpty(

4、*S) return 0; /*如果栈空,操作失败*/*e=S-elemS-top; /*获取栈顶元素*/S-top-; /*删除栈顶*/return 1; ,一、栈顺序栈(4),5判断栈空、栈满 int IsSqstackEmpty(SQSTACK S) /*如果栈空,则返回1,否则返回0*/return S.top=-1; /*top是栈顶标识,是-1时表示空栈*/ int IsSqstackFull(SQSTACK S) /*如果栈满,则返回1,否则返回0*/return S.top=S.size-1; /*top作为elem的下标,其最大值是size-1 */ ,一、栈链式栈(1),链

5、式栈的数据类型定义: typedef struct node_tag elemtype data;struct node_tag *next;NODE, *NODEPTR, *LINKSTACK;链式栈的操作: 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; ,一、栈链式栈(2),2出栈

6、int Pop(LINKSTACK 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;,二、栈的应用括号匹配检查,while(stri!=0)ch=stri;if(ch=()Push(,【任务描述】要求设计算法,对于给定的表达式字符串,检查其中括号是否匹配。,typedef char elemtype;int CheckBracket(ch

7、ar *str) /*如果字符串str中括号配对,则返回1,否则返回0*/int i,len;SQSTACK s; /*定义一个栈*/elemtype ch;len=strlen(str); /*将栈s的最大容量设置为字符串的长度*/ InitSqstack(/*从左向右扫描字符串,遇到括号进行入栈和出栈处理*/,二、栈的应用算术表达式求值(1),与表达式求值有关的知识: 表达式中运算符具有优先级和结合性特征 中缀表达式中,双目运算符需要两个操作数,一个操作数在左边,另一个在右边。 表达式求值算法的基本思想: 从左向右扫描表达式,获取单词。 如果单词是操作数,则入操作数栈; 如果单词是常规运算

8、符或者左括号:如果单词的栈外优先级数高,则将运算符入栈;否则反复出栈处理,直到单词栈外优先级数高为止。 如果单词是右括号,则反复出栈处理,直到运算符栈顶是左括号为止。将左括号出栈。 如果单词是=,反复出栈处理,直到运算符栈空。这时操作数栈的栈顶就是表达式的值。,【任务描述】 已知str是某算术表达式字符串,编写算法求得这个算术表达式的值。比如,str的内容是”22*5+6*(10-5)”,那么算法求得的值应该是140。这个算法不考虑单目运算符。为了简便起见,只允许使用加(+)、减(-)、乘(*)、除(/)、乘方()这5个运算符,这5个运算符都是双目运算符。,二、栈的应用算术表达式求值(2),单

9、词的数据类型: typedef struct int 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;SQST

10、ACK s1,s2;/*s1是操作数栈,s2是运算符栈*/*result=0;InitSqstack(/*事先在运算符栈放置一个左括号*/,二、栈的应用算术表达式求值(3),while(1) w=GetWord(exp,二、栈的应用算术表达式求值(4),case =:while(s2.elems2.top.word.op!=()/*反复出栈处理,直到遇到最开始放在栈里的左括号为止*/if(!Pop( ,二、栈的应用算术表达式求值(5),default:while(InPri(s2.elems2.top.word.op)OutPri(w.word.op)/*只要栈顶运算符的优先级数大于栈外运算符

11、的优先级数,则反复出栈处理*/if(!Pop(/*属于switch语句*/*属于while(1)语句*/,二、栈的应用迷宫路径求解(1),【任务描述】给定某个迷宫的布局及其入口和出口的坐标(如图3_9所示,注意横坐标是从左向右的,但是纵坐标是从上向下的),迷宫中空白的地方可以走,阴影的部分表示墙壁,走不通。设计算法找出从入口到出口的所有路径。需要解决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,

12、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,1,1; 如何探索从入口到达出口的所有路径。 深度优先探索回溯:从当前位置出发,向四个方向探索,如果发现某方向的相邻位置可走,则走过去,将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通,则退回到出发点(栈顶中的位置)。走过的地方要打上“已走标记”,回退时要将“已走”标记清除。,二、栈的应用迷宫路径求解(2),typedef struct int x,y;/*位置坐标*/int v; /*探索方向*/elemtype;

13、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,y)到出口(xx,yy)的所有路径*/int x,y,x1,y1,v;SQSTACK s; /*存放探索路径的栈*/elemtype e;InitSqstack(/*初始化栈*/,二、栈的应用迷宫路径求解(3),e.x=x0; e.y=y0; e.v=0;Push(,二、栈的应

14、用迷宫路径求解(4),while(v0 /*(x1,y1)不通,换一个方向探索*/*while循环结束时,说明(x,y)的4个方向都探索过了,应该回退一步*/while stack ,三、递归问题的非递归算法斐波那契问题(1),【任务描述】斐波那契序列中第n项的递归定义如下,设计算法求得第n项斐波那契序列项的值。递归算法 int Fibo(int n) /*斐波那契序列项求解的递归算法*/int val;if(n=1|n=2)return 1;/*到达递归终点*/val=Fibo(n-1)+Fibo(n-2);/*递归调用*/return val;,三、递归问题的非递归算法斐波那契问题(2),

15、非递归算法 【算法思想】首先将问题Fibo(n)入栈。接着进入一个循环:弹出栈顶问题,如果是递归终点,则求值累加;否则将Fibo(n)递归分解为Fibo(n-1)和Fibo(n-2),并将它们分别入栈,直到栈空为止。 【适用条件】由P(n)递归分解产生两个问题规模更小的问题P(n1)和P(n2),它们的求解相互独立,相互之间不构成求解条件。,递归问题的非递归算法设计中栈的作用 保存暂时不能求解的问题,等待条件具备时,再将问题出栈进行求解。被保存的问题,通常是递归分解的结果。,三、递归问题的非递归算法斐波那契问题(3),int Fibonacci(int n) /*非递归算法*/SQSTACK

16、s;int val=0,k;InitSqstack( ,三、递归问题的非递归算法Ackerman函数(1),【任务描述】已知Ackerman函数A(n,x,y)的递归定义如下,设计算法求得Ackerman函数的值。递归算法 int Ackerman(int n,int x,int y) /*递归算法*/ if(n=0)return x+1; /*递归终点*/else if(y=0) /*递归终点*/switch(n)case 1:return x;case 2:return 0;case 3:return 1;default:return 2;/*n=4*/ else return Acker

17、man(n-1,Ackerman(n,x,y-1),x); /*递归调用*/,三、递归问题的非递归算法Ackerman函数(2),非递归算法(I) 【算法思想】 Ackerman函数的非递归算法包含两种基本操作: 递归分解,这是一个循环操作。即如果当前问题不是递归终点,就将当前问题不断递归分解,将产生的第二个子问题入栈,将产生的第一个问题作为当前问题,直到遇到递归终点为止;遇到递归终点时即可求值。 弹出栈顶问题,转去递归分解。 这两个操作构成一个循环。当栈为空时,循环结束,算法终止。 入栈信息是(n,x),三、递归问题的非递归算法Ackerman函数(3),typedef struct int

18、 n,x;elemtype;#define MAXSIZE 500 int Ackerman1(int n,int x,int y) SQSTACK s;elemtype e;int val; /*用来存放函数值*/InitSqstack(/*递归分解,y参数规模减1*/,/*此刻当前问题是A(n,x,0)或A(0,x,y) */ val=AkmValue(n,x); if(IsSqstackEmpty(s) /*求值完毕*/DestroySqstack( /*当前问题变为(n,val,x)*/while(1),int AkmValue(int n,int x) if(n=0)return x

19、+1;else /*属于y=0的情况*/switch(n)case 1:return x;case 2:return 0;case 3:return 1;default:return 2;/*n=4*/,三、递归问题的非递归算法Ackerman函数(4),非递归算法(II) 【算法思想】 首先将初始问题入栈,然后进入递归分解和出栈处理的循环。 先执行对栈顶问题的递归分解,一直分解到递归终点。求得递归终点的函数值val,并弹出栈顶。如果栈为空,则算法终止,返回val;否则出栈问题信息(n,x,y),形成新的问题信息(n-1,val,x)后入栈。 这时栈顶问题可能不是递归终点,是需要继续递归分解的

20、问题。这时转到前面进行栈顶问题的递归分解操作。 入栈信息是(n,x,y),入栈的问题信息不同,算法细节也会不同,三、递归问题的非递归算法Ackerman函数(5),#define MAXSIZE 500 typedef struct int n,x,y;elemtype; int Ackerman2(int n,int x,int y) SQSTACK s; elemtype e; int val;InitSqstack( ,/*遇到递归终点,求值*/ val=AkmValue(n,x); /*弹出栈顶,因为是递归终点*/Pop(/while 1,三、递归问题的非递归算法汉诺塔问题(1),【任

21、务描述】假设有3根柱子,第1根柱子上套着n个半径大小不同的盘子(盘子中央有小孔),并且大盘子在下面,小盘子在上面,见图3_14。要求将第1根柱子上的盘子搬到第3根柱子上。在搬动过程中,可以使用第2根柱子暂时存放盘子,但无论何时都必须保证大盘子在下面,小盘子在上面,并且一次只能搬动一个盘子。,递归算法 void hanoi(int n,int A,int B,int C) /*汉诺塔的递归算法*/if(n=1)move(A,C);/*递归出口*/elsehanoi(n-1,A,C,B);move(A,C);hanoi(n-1,B,A,C);,三、递归问题的非递归算法汉诺塔问题(1),非递归算法:

22、 typedef struct int n,x,y,z;elemtype;void hanoi1(int n,int A,int B,int C) /*汉诺塔的非递归算法*/ SQSTACK s; elemtype e; int t;InitSqstack(/*将初始问题(n,A,B,C)入栈*/,三、递归问题的非递归算法汉诺塔问题(2),while(1) /*进入递归分解和出栈处理的循环*/ e=s.elems.top; /*取栈顶问题*/while(e.n1) /*递归分解的循环*/ e.n-; t=e.y; e.y=e.z; e.z=t;Push(/*(n-1,B,A,C)入栈,转到前面

23、,进行栈顶问题的递归分解*/,三、递归问题的非递归算法设计思路,四、队列队列的定义,队列(Queue)也是一种操作受限的线性表。与栈不同的是,队列只能在一端插入数据元素,在另一端删除数据元素。 先进先出(First In First Out) 队列的基本操作包括: 初始化空队销毁队列判断队空或队满 入队 出队 获得队列长度,四、队列顺序(循环)队列(1),数据类型定义: typedef struct elemtype *elem; /*指向存放队列数据元素的数组*/int front,rear; /*分别是队首和队尾下标,也称为队首指针和队尾指针*/int size; /*数组elem的容量*

24、/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; /*队首指针、队尾指针都归零*/q-size=n+1; /*设置容量*/return 1; ,四、队列顺序(循环)队列(2),2销毁队列 void DestroySqqueue(S

25、QQUEUE *q) /*销毁队列*/free(q-elem); /*释放队列所占内存*/q-elem=NULL; /*将其他成员设置成安全值*/q-front=q-rear=0;q-size=0; 3判断队空 int IsSqqueueEmpty(SQQUEUE q) /*如果队空,则返回1,否则返回0*/return q.front=q.rear;,四、队列顺序(循环)队列(3),4入队 int EnSqqueue(SQQUEUE *q, elemtype e) /*将数据元素e入队,操作成功返回1,否则返回0*/if(IsSqqueueFull(*q)return 0;q-elemq-r

26、ear=e; /*将e放置在队列中*/q-rear=(q-rear+1)%q-size; /*队尾指针向后移动*/return 1; 5判断队满 int IsSqqueueFull(SQQUEUE q) /*如果队满,则返回1,否则返回0*/return q.front=(q.rear+1)%q.size;,四、队列顺序(循环)队列(4),6出队 int DeSqqueue(SQQUEUE *q, elemtype *e) /*将队首元素复制给*e,操作成功返回1,否则返回0*/if(IsSqqueueEmpty(*q)return 0; /*如果队空,操作失败*/*e=q-elemq-fro

27、nt; /*复制队首元素*/q-front=(q-front+1)%q-size; /*队首指针向后移动*/return 1; 7获得队列长度 int SqqueueLen(SQQUEUE q) /*返回队列长度*/return (q.size+q.rear-q.front)%q.size; ,四、队列链式队列(1),数据类型定义: typedef struct node_tag elemtype data;struct node_tag *next;NODE, *NODEPTR; /*定义单链表结点和指针类型*/ typedef struct NODEPTR front,rear;/*队首队

28、尾指针*/ LKQUEUE;基本操作: 1初始化空队 void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL;,四、队列链式队列(2),2销毁队列 void DestroyLkqueue(LKQUEUE *Q) NODEPTR p;while(Q-front!=NULL)p=Q-front;Q-front=p-next; /*摘除队首结点*/free(p);Q-rear=NULL;,四、队列链式队列(3),3入队 int EnLkqueue(LKQUEUE *Q,elemtype e) NODEPTR p;p=(NODEPTR)malloc(sizeo

29、f(NODE);if(p=NULL)return 0;p-data=e;p-next=NULL;if(Q-front=NULL) /*如果队空,则将队首队尾指针都指向结点p*/Q-front=Q-rear=p;else/*否则将结点p插入到队尾结点后面*/Q-rear-next=p;Q-rear=p;return 1;,四、队列链式队列(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=NU

30、LL;/*如果队空,则将队尾指针置NULL*/*e=p-data;free(p);return 1;,五、队列的应用迷宫最短路径(1),【任务描述】给定某个迷宫的布局及其入口和出口的坐标,设计算法找出从入口到出口的最短路径。 思考方式:从入口出发,走1步可以到达哪里?走2步可以到达哪里?走3步可以到达哪里? 算法需要一个辅助队列,五、队列的应用迷宫最短路径(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(

31、int mazeMN ,int x,int y ,int xx ,int yy) /*求最短路径*/ elemtype e; SQQUEUE q; int x1,y1,i,k;if(!InitSqqueue(,五、队列的应用迷宫最短路径(3),for(i=1;i=4;i+) /*从四个方向探索相邻位置是否可走*/ e.x=x1+movexi;e.y=y1+moveyi;if(mazee.ye.x=0) /*某个相邻位置可走*/ EnSqqueue( /*属于for语句*/*属于while语句*/ ,导航图(1),导航图(2),导航图(3),导航图(4),导航图(5),导航图(6),导航图(7),导航图(8),导航图(9),

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1