数据结构与算法教学课件ppt作者王曙燕chapter3栈和队列.ppt

数据结构与算法教学课件ppt作者王曙燕chapter3栈和队列.ppt

《数据结构与算法教学课件ppt作者王曙燕chapter3栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法教学课件ppt作者王曙燕chapter3栈和队列.ppt（43页珍藏版）》请在冰点文库上搜索。

1,第3章栈和队列,3.2栈,3.3队列,3.1应用实例,3.4实例分析与实现,3.5算法总结,2,第3章栈和队列,3.1应用实例,实例一：

迷宫求解问题这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。

迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。

实例二：

马踏棋盘问题将马随机地放在国际象棋88棋盘Board88的某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线将数字1,2，64依次填入一个88的方阵并输出。

实例三：

舞伴问题假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一首舞曲。

3,第3章栈和队列,3.2栈,定义：

作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。

通常将表中允许进行插入、删除操作的一端称为栈顶（Top），表的另一端被称为栈底（Bottom）。

当栈中没有元素时称为空栈。

栈的插入操作被形象地称为进栈或入栈。

栈的删除操作称为出栈或退栈。

特点：

后进先出（LIFO）,进栈,出栈,4,第3章栈和队列,3.2栈,顺序栈,链栈,5,第3章栈和队列,3.1栈,顺序栈,用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。

通常以top=-1表示空栈。

6,第3章栈和队列,3.2栈,顺序栈,的C语言描述,#defineStack_Size50typedefstructStackElementTypeelemStack_Size;inttop;SeqStack;,A,B,C,top,top,top,top,D,top,E,top,7,第3章栈和队列,3.2栈,顺序栈的基本操作：

初始化,判栈空,判栈满,进栈,出栈,取栈顶元素,数据结构与算法,8,第3章栈和队列,3.2栈,顺序栈的基本操作：

初始化,voidInitStack（SeqStack*S）S-top=-1;,9,第3章栈和队列,3.1栈,顺序栈的基本操作：

判栈空,intIsEmpty（SeqStack*S）return（S-top=-1?

TRUE:

FALSE）;,10,第3章栈和队列,3.2栈,顺序栈的基本操作：

判栈满,intIsFull（SeqStack*S）return（S-top=Stack_Size?

TRUE:

FALSE）;,11,第3章栈和队列,3.2栈,顺序栈的基本操作：

进栈,intPush（SeqStack*S,StackElementTypex）if（S-top=Stack_Size）return（FALSE）;S-top+;S-elemS-top=x;return（TRUE）;,12,第3章栈和队列,3.2栈,顺序栈的基本操作：

出栈,intPop（SeqStack*S,StackElementType*x）if（S-top=-1）return（FALSE）;else*x=S-elemS-top;S-top-;return（TRUE）;,13,第3章栈和队列,3.2栈,顺序栈的基本操作：

取栈顶元素,intGetTop（SeqStackS,StackElementType*x）if（S-top=-1）return（FALSE）;else*x=S-elemS-top;return（TRUE）;,14,第3章栈和队列,3.2栈,两栈共享技术,双端栈,主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。

首先为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。

top0,top1,数据结构与算法,15,第3章栈和队列,3.2栈,两栈共享,数据结构定义：

#defineM100typedefstructStackElementTypeStackM;StackElementTypetop2;DqStack;,16,第3章栈和队列,3.2栈,两栈共享,初始化,voidInitStack（DqStack*S）S-top0=-1;S-top1=M;,17,第3章栈和队列,3.2栈,两栈共享,进栈,intPush（DqStack*S,StackElementTypex,inti）if（S-top0+1=S-top1）return（FALSE）;switch（i）case0:

S-top0+;S-StackS-top0=x;break;case1:

S-top1-;S-StackS-top1=x;break;default:

return（FALSE）;return（TRUE）;,18,第3章栈和队列,3.2栈,两栈共享,出栈,intPop（DqStack*S,StackElementType*x,inti）switch（i）case0:

if（S-top0=-1）return（FALSE）;*x=S-StackS-top0;S-top0-;break;case1:

if（S-top1=M）return（FALSE）;*x=S-StackS-top1;S-top1+;break;default:

return（FALSE）;return（TRUE）;,19,第3章栈和队列,3.2栈,链栈,采用链表作为存储结构实现的栈。

为便于操作，采用带头结点的单链表实现栈。

因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。

若top-next=NULL，则代表空栈。

注意：

链栈在使用完毕时，应该释放其空间。

20,第3章栈和队列,3.2栈,链栈,数据结构定义：

typedefstructnodeStackElementTypedata;structnode*next;LinkStackNode,*LinkStack;,21,第3章栈和队列,3.2栈,链栈,进栈,temp,a1,temp,a2,temp-next=top-next;,top-next=temp;,intPush（LinkStacktop,StackElementTypex）LinkStackNode*temp;temp=（LinkStackNode*）malloc（sizeof（LinkStackNode）;if（temp=NULL）return（FALSE）;temp-data=x;temp-next=top-next;top-next=temp;return（TRUE）;,22,第3章栈和队列,3.2栈,链栈,出栈,intPop（LinkStacktop,StackElementType*x）LinkStackNode*temp;temp=top-next;if（temp=NULL）return（FALSE）;top-next=temp-next;*x=temp-data;free（temp）;return（TRUE）;,23,第3章栈和队列,3.2栈,链栈,多栈运算,采用多个单链表来实现多个链栈,数据结构与算法,24,第3章栈和队列,3.2栈,链栈,多栈运算,数据结构描述,#defineM10typedefstructnodeStackElementTypedata;structnode*next;LinkStackNode,*LinkStack;LinkStacktopM;,数据结构与算法,25,第3章栈和队列,3.2栈,链栈,多栈运算,:

第i号栈的进栈操作,intPushi（LinkStacktopM,StackElementTypex）LinkStackNode*temp;temp=（LinkStackNode*）malloc（sizeof（LinkStackNode）;if（temp=NULL）return（FALSE）;temp-data=x;temp-next=topi-next;topi-next=temp;return（TRUE）;,数据结构与算法,26,第3章栈和队列,3.2栈,链栈,多栈运算,:

第i号栈的出栈操作,intPopi（LinkStacktopM,StackElementType*x）LinkStackNode*temp;temp=topi-next;if（temp=NULL）return（FALSE）;topi-next=temp-next;*x=temp-data;free（temp）;return（TRUE）;,数据结构与算法,27,第3章栈和队列,3.2栈,应用：

括号匹配问题,思想：

1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。

3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。

28,第3章栈和队列,3.1栈,应用：

括号匹配问题,算法实现,voidBracketMatch（char*str）StackS;inti;charch;InitStack（,29,第3章栈和队列,3.2栈,应用：

表达式求值,问题分析：

Exp=ab+（cd/e）f,1）确定计算规则，即明确运算符的优先级；,2）确定当前处理字符是运算符还是操作数；,（限于二元运算符的表达式）,表达式:

=（操作数）+（运算符）+（操作数）,操作数:

=简单变量|表达式,简单变量:

=标识符|无符号整数,3）每个运算符的运算次序要由它之后的一个运算符来定。

30,第3章栈和队列,3.2栈,应用：

表达式求值,3）若当前字符是操作数，则直接压入操作数栈；,4）若当前字符是操作符，且运算符的优先级高于栈顶运算符则进栈；,5）否则，从操作数栈中弹出两个操作数并弹出操作符栈的栈顶运算符，经计算后将结果压入操作数栈。

（限于二元运算符的表达式）,算法思路：

1）设立操作数栈与操作符栈；,2）设表达式的结束符为“#”，预设运算符栈的栈底为“#”；,31,第3章栈和队列,3.2栈,应用：

表达式求值,（限于二元运算符的表达式）,例如：

A/BC+D*E,#,A,/,B,C,BC,T

（1）=,T

（1）,A/T

（1）,T

（2）=,T

（2）,+,D,*,E,D*E,T（3）=,T（3）,T（3）+T

（2）,T（4）=,T（4）,操作数的栈底中存着最终的表达式结果。

#,32,第3章栈和队列,3.2队列,定义：

限定所有的插入操作在表的一端进行，而删除操作在表的另一端进行的线性表。

通常将表中允许进行插入操作的一端称为队尾（rear），允许进行删除操作的一端称为队头（front）。

当队列中没有元素时称为空队。

队列的插入操作称为入队。

队列的删除操作称为出队。

特点：

先进先出（FIFO）,入队,出队,33,第3章栈和队列,3.3队列,链队列,链式映象,顺序映象,循环队列,34,第3章栈和队列,3.3队列,循环队列,35,第3章栈和队列,3.3队列,循环队列,约定：

尾指针指示队列中队尾元素的后一个位置。

数据结构定义,typedefstructQueueElementTypeelementmaxsize;intfront;intrear;SeqQueue;SeqQueue*Q;,36,第3章栈和队列,3.3队列,循环队列:

初始化,voidInitQueue（SeqQueue*Q）Q-front=Q-rear=0;,37,第3章栈和队列,3.3队列,循环队列:

入队,intEnterQueue（SeqQueue*Q,QueueElementTypex）if（Q-rear+1）%MAXSIZE=Q-front）return（FALSE）;Q-elementQ-rear=x;Q-rear=（Q-rear+1）%MAXSIZE;return（TRUE）;,38,第3章栈和队列,3.3队列,循环队列:

出队,intDeleteQueue（SeqQueue*Q,QueueElementTypex）if（Q-front=Q-rear）return（FALSE）;*x=Q-elementQ-front;Q-front=（Q-front+1）%MAXSIZE;return（TRUE）;,39,第3章栈和队列,3.3队列,链队列,40,第3章栈和队列,3.3队列,链队列,typedefstructnodeQueueElementTypedata;structnode*next;LinkQueueNode;typedefstructLinkQueueNode*front;LinkQueueNode*rear;LinkQueue;LinkQueue*Q;,数据结构定义,41,第3章栈和队列,3.3队列,链队列,intInitQueue（LinkQueue*Q）Q-front=（LinkQueueNode*）malloc（sizeof（LinkQueueNode）;if（Q-front!

=NULL）Q-rear=Q-front;Q-front-next=NULL;return（TRUE）;elsereturn（FALSE）;,初始化,42,第3章栈和队列,3.3队列,链队列,intEnterQueue（LinkQueue*Q，QueueElementTypex）LinkQueueNode*NewNode；NewNode=（LinkQueueNode*）malloc（sizeof（LinkQueueNode）;if（NewNode!

=NULL）NewNode-data=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;return（TRUE）;elsereturn（FALSE）;,入队,43,第3章栈和队列,3.3队列,链队列,intDeleteQueue（LinkQueue*Q，QueueElementTypex）LinkQueueNode*p；if（Q-front=Q-rear）return（FALSE）;p=Q-front-next;Q-front-next=p-next;*x=p-data;free（p）;return（TRUE）;,出队,