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

第三章栈和队列,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in,栈和队列是两种常用的数据类型,3.1栈的类型定义,3.2栈类型的实现,3.3栈的应用举例,3.4队列的类型定义,3.5队列类型的实现,3.1栈的类型定义,ADTStack数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。,基本操作：,ADTStack,栈的特点,栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，.,ai，.，an），其中a1是栈底元素，an是栈顶元素。,设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=0,栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。,栈空,10进栈,30出栈,栈满,栈的定义（顺序表）,#defineSTACK_INI_SIZE100/存储空间初始分配量#defineSTACKINCREMENT10/存储空间分配增量typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;,InitStack(SElemType*top;intstacksize;SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,StatusInitStack(SqStack,StatusPush(SqStack,StatusPop(SqStack注意：判定栈空的条件S.top=S.base,StatusGetTop(SqStack,StatusStackEmpty(SqStackS)if(S.top=S.base)return1;elsereturn0;,栈顶指针,链栈,a1,an,注意:链栈中指针的方向,an-1,3.3栈的应用举例,例一、数制转换,例二、括号匹配的检验,例三、行编辑程序问题,例四、迷宫求解,例五、表达式求值,例六、实现递归,例一、数制转换算法基于原理：N=(Ndivd)d+Nmodd,例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202,计算顺序,输出顺序,voidconversion()InitStack(S);scanf(%d,/conversion,例二、括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列：()12345678,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,Statusmatching(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=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+,结论:,1）操作数之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息，致使运算的次序不确定;,4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。,如何从后缀式求值？,先找运算符，再找操作数,例如：abcde/f+,ab,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f,从原表达式求得后缀式的规律为：,1)设立操作数栈；,2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；,3)若当前字符是操作数，则直接发送给后缀式。,4)若当前运算符的优先数高于栈顶运算符，则进栈；,5)否则，退出栈顶运算符发送给后缀式；,6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,voidtransform(charsuffix,charexp)InitStack(S);Push(S,#);Scanf(EXP,ch);/p=exp;ch=*p;while(!StackEmpty(S)if(!IN(ch,OP)Pass(Suffix,ch);elseif(ch!=#)p+;ch=*p;elsePop(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中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。,例六、实现递归,将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回！,例如：voidmain()voida()voidb()a();b();/main/a/b,Main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,voidhanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。12if(n=1)3move(x,1,z);/将编号为的圆盘从x移到z4else5hanoi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔6move(x,n,z);/将编号为n的圆盘从x移到z7hanoi(n-1,y,x,z);/将y上编号为至n-1的8/圆盘移到z,x作辅助塔9,3.4队列的类型定义,a1,a2,a3,a4,an-1,an,队列示意图,队头,队尾,队列是一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。,队列的抽象数据类型定义,ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an端为队列尾,基本操作：,ADTQueue,队列的基本操作：,InitQueue(structQNode*next;QNode,*QueuePtr;,typedefstruct/链队列类型QueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,StatusInitQueue(LinkQueue,StatusEnQueue(LinkQueue,StatusDeQueue(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,循环队列的实现,#defineMAXQSIZE100/最大队列长度typedefstructElemType*base;/动态分配存储空间intfront;/头指针，若队列不空，/指向队列头元素intrear;/尾指针，若队列不空，指向/队列尾元素的下一个位置SqQueue;,StatusInitQueue(SqQueue,StatusEnQueue(SqQueue,StatusDeQueue(SqQueue,例1：舞伴问题：舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。舞伴问题的类型描述：typedefstructcharname20;charsex;/性别，F表示女性，M表示男性Person;typedefPersondatatype;/队列中元素的数据类型为Person,3.5.3队列的应用例子,舞伴问题的算法：voidDancePartner(Persondancer,intnum)/结构数组dancer中存放跳舞的男女，num是跳舞的人数。inti;Personp;SqQueue*Mdancers,*Fdancers;InitQueue(Mdancers);/男士队列初始化InitQueue(Fdancers);/女士队列初始化for(i=0;i(8,8)*/inti,j,find=0,di,k;SqQueueQ;InitQueue(Q,200);ElemTypee,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)case0:i=e.i;j=e.j+1;break;/向东case1:i=e.i+1;j=e.j;break;/向南case2:i=e.i;j=e.j-1;break;/向西case3:i=e.i-1;j=e.j;break;/向北if(mgij=)/*将该相邻方块插入到队列中*/d.i=i;d.j=j;d.pre=k;EnQue