最新where、when、-why定语从句课件PPT.ppt 30页

'where、when、-why定语从句 1.引导定语从句。2.代替先行词。3.在定语从句中担当一个成分。关系词的三个作用:确定关系代词的步骤1.先找先行词，2.看先行词指的是人还是物。3.看关系词在从句中充当的成分。 where、when、why引导的定语从句 Iwillneverforgetthetime.Weworkedonthefarmduringthattime.Iwillneverforgetthetimewhenweworkedonthefarm.duringwhich关系词when代替时间，相当于“介词+which”，在从句中充当时间状语。 Oct.1,1949isthedaywhen∕onwhichthePRCwasfounded.Oct.1,1949istheday.ThePRCwasfoundedontheday. 对比：1、Doyourememberthedayswespenttogether?Doyourememberthedays?Wespentthedaystogether.（作宾语）2、Doyourememberthedaysweworkedtogether?Doyourememberthedays?Weworkedduringthedaystogether?（作状语）解题关键：看引导词在从句中充当的成分：作主语或宾语用that/which；作状语用when。(that∕which)when Thisisthereason.Hewaslateforthereason.Thisisthereasonwhyhewaslate.forwhich关系词why代替reason(原因），相当于“for+which”，在从句中充当原因状语。 对比：1、Iknowthereasonhegaveyou.Iknowthereason.Hegaveyouthereason.（作宾语）2、Iknowthereasonyoufailed.Iknowthereason.Youfailedforthereason.（作状语）解题关键：看引导词在从句中充当的成分：作主语或宾语用that/which；作状语用why。(that∕which)why 关系副词的用法关系副词指代先行词是在从句中充当的成分when(=at/in/on/duringwhich)where(=in/atwhich)why(=forwhich)时间时间状语地点地点状语原因原因状语关系副词引导定语从句时，既引导定语从句，又在定语从句中充当状语。 3.Icanstillrememberthesitting-room___mymotherandIusedtositintheevening.A.whatB.whichC.thatD.where 4.Ishallneverforgetthoseyears___Ilivedinthecountrywiththefarmers,____hasagreateffectonmylife.A.that,whichB.when,whichC.which,thatD.when,who 栈和队列 栈栈的基本概念1栈的概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。 设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop) 栈的顺序存储结构简称为顺序栈，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。◆静态顺序栈实现简单，但不能根据需要增大栈的存储空间；◆动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。栈的顺序存储表示 采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。◆用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。◆用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。◆结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;栈的动态顺序存储表示 ◆结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。图3-2是一个动态栈的变化示意图。图3-2(动态)堆栈变化示意图空栈bottomtop元素a进栈bottomtopa元素b，c进栈bottomtopabc元素c退栈bottomtopabbottomtopabdef元素d，e，f进栈 采用静态一维数组来存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，◆栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。◆用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。◆结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。栈的静态顺序存储表示 ◆结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。图3-3静态堆栈变化示意图空栈bottomtopTop=11个元素进栈bottomtopaTop=33个元素进栈bottomtopabcTop=4栈满bottomtopabedTop=2元素c进栈bottomtopab 1队列的基本概念队列(Queue)：也是运算受限的线性表。是一种先进先出(FirstInFirstOut，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首(front)：允许进行删除的一端称为队首。队尾(rear)：允许进行插入的一端称为队尾。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。队列队列及其基本概念 队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…,an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…,an，即队列的修改是依先进先出的原则进行的，如图3-5所示。a1,a2,…,an出队入队队尾队首图3-5队列示意图 队列的顺序存储结构利用一组连续的存储单元(一维数组)依次存放从队首到队尾的各个元素，称为顺序队列。设立一个队首指针front，一个队尾指针rear，分别指向队首和队尾元素。◆初始化：front=rear=0。◆入队：将新元素插入rear所指的位置，然后rear加1。◆出队：删去front所指的元素，然后加1并返回被删元素。◆队列为空：front=rear。◆队满：rear=MAX_QUEUE_SIZE-1或front=rear。 在非空队列里，队首指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。如图3-6所示是数组大小为5的顺序队列中队首、队尾指针和队列中元素的变化情况。(a)空队列Q.frontQ.rear入队3个元素a3a2a1Q.frontQ.rear(c)出队3个元素Q.frontQ.rear(d)入队2个元素a5a4Q.frontQ.rear图3-6队列示意图 循环队列为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(CircularQueue)。i=(i+1)%MAX_QUEUE_SIZE;例：设有循环队列QU[0，5]，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图3-7所示。 123450(a)空队列frontrear123450(b)d,e,b,g入队frontdebgrear123450(c)d,e出队bgfrontrear123450(d)i,j,k入队bgfrontijkrear123450(e)b,g出队ijkrearfront123450(f)r,p,s,t入队ijkfrontrprear图3-7循环队列操作及指针变化情况 方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即：◆rear所指的单元始终为空。◆循环队列为空：front=rear。◆循环队列满：(rear+1)%MAX_QUEUE_SIZE=front。 习题6、设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈，出栈顺序为b,d,c,f,e,a那么栈容量至少应该是()。--栈的容量(深度)A.6B.5C.4D.3E.216.对于入栈顺序为a,b,c,d,e,f,g的序列，下列()不可能是合法的出栈序列。A.a,b,c,d,e,f,gB.a,d,c,b,e,g,fC.a,d,b,c,g,f,eD.g,f,e,d,C,b,a'