《数据结构教学课件》cha课件.ppt

第三章 栈和队列,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in,栈和队列是两种常用的数据类型,3.1 栈的类型定义,3.2 栈类型的实现,3.3 栈的应用举例,3.4 队列的类型定义,3.5 队列类型的实现,3.1 栈的类型定义,ADT Stack 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：,ADT Stack,栈的特点,栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，.,ai，.，an），其中a1是栈底元素，an是栈顶元素。,设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=0,栈中的运算：1.设置空栈；2.插入一个新的栈顶元素 3.删除栈顶元素；4.读取栈顶元素。,栈空,10进栈,30出栈,栈满,栈的定义（顺序表）,#define STACK_INI_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增量typedef structSElemType*base;SElemType*top;int stacksize;SqStack;,InitStack(&S),DestroyStack(&S),ClearStack(&S),StackEmpty(s),StackLength(S),GetTop(S,&e),Push(&S,e),Pop(&S,&e),StackTravers(S,visit(),InitStack(&S)操作结果：构造一个空栈 S。,DestroyStack(&S),初始条件：栈 S 已存在。操作结果：栈 S 被销毁。,StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。,StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。,GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。,a1,a2,an,ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。,Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。,a1,a2,an,e,Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1,3.2栈类型的实现,顺序栈,链栈,/-栈的顺序存储表示-#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct SElemType*base;SElemType*top;int stacksize;SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,Status InitStack(SqStack,Status Push(SqStack,Status Pop(SqStack 注意：判定栈空的条件S.top=S.base,Status GetTop(SqStack,Status StackEmpty(SqStack S)if(S.top=S.base)return 1;else return 0;,栈顶指针,链栈,a1,an,注意:链栈中指针的方向,an-1,3.3 栈的应用举例,例一、数制转换,例二、括号匹配的检验,例三、行编辑程序问题,例四、迷宫求解,例五、表达式求值,例六、实现递归,例一、数制转换 算法基于原理：N=(N div d)d+N mod d,例如：（1348)10=(2504)8，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,void conversion()InitStack(S);scanf(%d,/conversion,例二、括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列：()1 2 3 4 5 6 7 8,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,Status matching(string.,例三、行编辑程序问题,如何实现？,“每接受一个字符即存入存储器”?,并不恰当！,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。,合理的作法是：,假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);,则实际有效的是下列两行：while(*s)putchar(*s+);,while(ch!=EOF/从终端接收下一个字符,ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();,while(ch!=EOF)/EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,例四、迷宫求解,通常用的是“穷举求解”的方法,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,设定当前位置的初值为入口位置；do 若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为 新的当前位置；否则 while(栈不空）；,求迷宫中一条从入口到出口的路径的算法：,若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；,若栈空，则表明迷宫没有通路。,限于二元运算符的表达式定义:表达式:=(操作数)+(运算符)+(操作数)操作数:=简单变量|表达式 简单变量:=标识符|无符号整数,例五、表达式求值,表达式的三种标识方法：,设 Exp=S1+OP+S2,则称 OP+S1+S2 为前缀表示法,S1+OP+S2 为中缀表示法,S1+S2+OP 为后缀表示法,一个中缀式到其他式子的转换方法这里给出一个中缀表达式a+b*c-(d+e)第一步：按照运算符的优先级对所有的运算单位加括号式子变成：(a+(b*c)-(d+e)第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成拉：-(+(a*(bc)+(de)把括号去掉：-+a*bc+de前缀式子出现后缀：把运算符号移动到对应的括号后面则变成拉：(a(bc)*)+(de)+)-把括号去掉：abc*+de+-后缀式子出现前缀式，后缀式是不需要用括号来进行优先级的确定的。,例如:Exp=a b+(c d/e)f前缀式:+a b c/d e f中缀式:a b+c d/e f后缀式:a b c d e/f+,结论:,1）操作数之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息，致使运算的次序不确定;,4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,5)后缀式的运算规则为:运算符在式中出现的顺序恰为 表达式的运算顺序;每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。,如何从后缀式求值？,先找运算符，再找操作数,例如：a b c d e/f+,ab,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析“原表达式”和“后缀式”中的运算符:原表达式:a+b c d/e f 后缀式:a b c+d e/f,从原表达式求得后缀式的规律为：,1)设立操作数栈；,2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；,3)若当前字符是操作数，则直接发送给后缀式。,4)若当前运算符的优先数高于栈顶运算符，则进栈；,5)否则，退出栈顶运算符发送给后缀式；,6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,void transform(char suffix,char exp)InitStack(S);Push(S,#);Scanf(EXP,ch);/p=exp;ch=*p;while(!StackEmpty(S)if(!IN(ch,OP)Pass(Suffix,ch);else if(ch!=#)p+;ch=*p;else Pop(S,ch);Pass(Suffix,ch);/while/CrtExptree,switch(ch)case(:Push(S,ch);break;case):Pop(S,c);while(c!=()Pass(Suffix,c);Pop(S,c)break;defult:while(Gettop(S,c)/switch,将中缀表达式转换为前缀表达式：(1)初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2)从右至左扫描中缀表达式；(3)遇到操作数时，将其压入S2；(4)遇到运算符时，比较其与S1栈顶运算符的优先级：(4-1)如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；(4-2)否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；(4-3)否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5)遇到括号时：(5-1)如果是右括号“)”，则直接压入S1；(5-2)如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；(6)重复步骤(2)至(5)，直到表达式的最左边；(7)将S1中剩余的运算符依次弹出并压入S2；(8)依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。,将中缀表达式转换为后缀表达式：与转换为前缀表达式相似，遵循以下步骤：(1)初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2)从左至右扫描中缀表达式；(3)遇到操作数时，将其压入S2；(4)遇到运算符时，比较其与S1栈顶运算符的优先级：(4-1)如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；(4-2)否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；(4-3)否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5)遇到括号时：(5-1)如果是左括号“(”，则直接压入S1；(5-2)如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；(6)重复步骤(2)至(5)，直到表达式的最右边；(7)将S1中剩余的运算符依次弹出并压入S2；(8)依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。,例六、实现递归,将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回！,例如：void main()void a()void b()a();b();/main/a/b,Main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 2 if(n=1)3 move(x,1,z);/将编号为的圆盘从x移到z4 else 5 hanoi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔6 move(x,n,z);/将编号为n的圆盘从x移到z7 hanoi(n-1,y,x,z);/将y上编号为至n-1的8/圆盘移到z,x作辅助塔9,3.4 队列的类型定义,a1,a2,a3,a4,an-1,an,队 列 示 意 图,队头,队尾,队列是一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。,队列的抽象数据类型定义,ADT Queue 数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头，an 端为队列尾,基本操作：,ADT Queue,队列的基本操作：,InitQueue(&Q),DestroyQueue(&Q),QueueEmpty(Q),QueueLength(Q),GetHead(Q,&e),ClearQueue(&Q),DeQueue(&Q,&e),EnQueue(&Q,e),QueueTravers(Q,visit(),InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。,QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。,QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。,GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。,a1,a2,an,ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。,EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。,a1,a2,an,e,DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。,a1,a2,an,3.5 队列类型的实现,3.5.1 链队列链式映象,循环队列顺序映象,3.5.1 链队列链式映象,an,a2,Q.front,Q.rear,删 除,一个元素,添加 一个元素,e,Q.front,Q.rear,队头,队尾,Q.rear,链队列的实现,typedef struct QNode/结点类型 QElemType data;struct QNode*next;QNode,*QueuePtr;,typedef struct/链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,Status InitQueue(LinkQueue,Status EnQueue(LinkQueue,Status DeQueue(LinkQueue,3.5.2 循环队列顺序映象,顺序存储结构,(a)线性队列,(b)循环队列,(a)线性队列,e3,(c),e1,e2出队，e3入队 队 满,rear=2,front,e1,e2,(b),rear,front,(b)e1,e2 入队,队空时，令rear=front=0，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。,front,rear=3,(b)循环队列,rear,队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。,将头尾连接成一个环，形成循环队列。,(2)队满,front,e3,e4,0,1,2,3,rear,e2,循环队列的实现,#define MAXQSIZE 100/最大队列长度 typedef struct ElemType*base;/动态分配存储空间 int front;/头指针，若队列不空，/指向队列头元素 int rear;/尾指针，若队列不空，指向/队列尾元素 的下一个位置 SqQueue;,Status InitQueue(SqQueue,Status EnQueue(SqQueue,Status DeQueue(SqQueue,例1：舞伴问题：舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。舞伴问题的类型描述：typedef struct char name20;char sex;/性别，F表示女性，M表示男性 Person;typedef Person datatype;/队列中元素的数据类型为Person,3.5.3 队列的应用例子,舞伴问题的算法：void DancePartner(Person dancer,int num)/结构数组dancer中存放跳舞的男女，num是跳舞的人数。int i;Person p;SqQueue*Mdancers,*Fdancers;InitQueue(Mdancers);/男士队列初始化 InitQueue(Fdancers);/女士队列初始化 for(i=0;inum;i+)/依次将跳舞者依其性别入队 p=danceri;if(p.sex=F)EnQueue(Fdancers.p);/排入女队 else EnQueue(Mdancers.p);/排入男队,printf(The dancing partners are:n n);while(!QueueEmpty(Fdancers)else,if(!QueueEmpty(Mdancers)/输出男队剩余人数及队头者名字 printf(n There are%d men waiting for the next round.n,Mdacers.count);p=GetHead(Mdancers);printf(%s will be the first to get a partner.n,p.name);,例2：采用队列求解迷宫问题 使用一个队列Qu记录走过的方块,该队列的结构如下:typedef struct int i,j;/*方块的位置*/int pre;/*本路径中上一方块在Qu中的下标*/ElemType;这里使用的队列不是循环队列(因为要利用出队的元素找路径),因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径。,char mg1010=/表示迷宫的矩阵/表示可通过!表示不通/0 1 2 3 4 5 6 7 8 9!,!,!,!,!,!,!,!,!,!,/0!,!,!,!,/1!,!,!,!,/2!,!,!,!,/3!,!,!,!,!,/4!,!,!,/5!,!,!,!,/6!,!,!,!,!,!,!,/7!,!,!,/8!,!,!,!,!,!,!,!,!,!;/9,(1)首先将(1,1)入队;(2)在队列不为空时循环:出队一次(由于不是循环队列,该出队元素仍在队列中),称该出队的方块为当前方块,front为该方块在队列中的下标。如果当前方块是出口,则输出路径并结束。否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块(对应的mg数组值为),将这些可走的相邻方块均插入到队列中,其pre设置为本搜索路径中上一方块在队列中的下标值,也就是当前方块的front值,并将相邻方块对应的mg数组值置为*,以避免回过来重复搜索。(3)若队列为空仍未找到出口,即不存在路径。,搜索从(1,1)到(8,8)路径,实际上,本算法的思想是从(1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是将在第7章介绍的图的广度优先搜索方法。,void mgpath()/*搜索路径为:(1,1)-(8,8)*/int i,j,find=0,di,k;SqQueue Q;InitQueue(Q,200);ElemType e,d;e.i=1;e.j=1;e.pre=-1;EnQueue(Q,e);/(1,1)入队 mg11=*;/将其赋值*,以避免回过来重复搜索 while(!QueueEmpty(Q),for(di=0;di=3;di+)/把每个可走的方块插入队列中 switch(di)case 0:i=e.i;j=e.j+1;break;/向东 case 1:i=e.i+1;j=e.j;break;/向南 case 2:i=e.i;j=e.j-1;break;/向西 case 3:i=e.i-1;j=e.j;break;/向北 if(mgij=)/*将该相邻方块插入到队列中*/d.i=i;d.j=j;d.pre=k;EnQueue(Q,d);mgij=*;/将其赋值-1,以避免重复搜索 if(!find)printf(不存在路径!n);,拓展知识：双端队列,双端队列（deque，全名double-ended queue）就是一个两端都可以插入和删除的队列，是一种具有队列和栈的性质的数据结构。队列的每一瑞都可以插入数据项和移除数据项。这些方法可以叫作insertLeft()和insertRight()，以及removeLeft()和removeRight()。如果严格禁止调用insertLeft()和removeLeft()方法（或禁用右段的操作），双端队列功能就和栈一样。禁止调用insertLeft()和removeRight()（或相反的另一对方法），它的功能就和队列一样了。,双端队列举例,双端队列应用的一个例子：教材配套习题集P263.33,下面是在VC+中使用标准模板库STL中的容器deque的例子：,#include#include using namespace std;void main()int i;typedef deque INTDEQUE;INTDEQUE ds;for(i=1;i:iterator iter;for(iter=ds.begin();iter!=ds.end();iter+)cout*iterendl;*/,作业3.1,配套习题集P24 3.17 3.19 3.28 3.30,1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4.理解递归算法执行过程中栈的状态变化过程。,本章学习要点,