下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 队列的基本操作及应用

队列的基本操作及应用.doc

队列的基本操作及应用

高学德
2017-10-15 0人阅读 举报 0 0 暂无简介

简介:本文档为《队列的基本操作及应用doc》,可适用于初中教育领域

队列的基本操作及应用江苏省青少年信息学奥林匹克冬令营(JSOI)队列的基本操作及应用【教学目的】()掌握队列的定义及队列的存储结构(顺序存储、链式存储)()掌握队列的基本操作运算:建队列、插入、删除、队列空等()掌握循环队列的概念及运算()能够利用队列解决一些实际问题:宽度优先搜索算法【教学重点】综合运用队列结构解决实际问题。【教学过程】一、队列的定义前面所讲的栈是一种后进先出的数据结构而在实际问题中还经常使用一种“先进先出”(FIFO―FirstInFirstOut)的数据结构:即插入在表一端进行而删除在表的另一端进行我们将这种数据结构称为队或队列把允许插入的一端叫队尾(rear)把允许删除的一端叫队头(front)。如图所示是一个有个元素的队列。入队的顺序依次为a、a、a、a、a出队时的顺序将依然是a、a、a、a、a。出队入队aaaaa入队入队图队列示意图显然队列也是一种运算受限制的线性表所以又叫先进先出表。在日常生活中队列的例子很多如排队买东西排头的买完后走掉新来的排在队尾。二、基本术语()队空:当队列中没有元素时称为空队列()队满:当队列中单元全部被占用()进队:向队列中插入新元素()出队:从队列中删除元素()(假)溢出:队尾指针指向最后一个位置但队头前面仍有空闲的单元可被利用。三、队列操作示意图front=rear=,front=,rear=front=rear=front=rear=(a)空队(b)有个元素(c)一般情况(d)假溢出现象第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)四、队列的存储结构与线性表、栈类似队列也有顺序存储和链式存储两种存储方法。(顺序存储顺序存储的队列称为顺序队列。因为队列的队头和队尾都是活动的因此除了队列的数据区外还有队头、队尾两个指针。顺序队列的类型定义如下:typequeue=recorddata:arraymaxsizeofelemtypefront,rear:integerendfront指向队列中第一个元素的前一个单元rear指向队列中最后一个元素的单元。(链式存储链式存储的队列称为链队。和链栈类似用单链表来实现链队根据队的FIFO原则为了操作上的方便我们分别需要一个头指针和尾指针如图所示。frontaan…arear图链队示意图五、队列的基本运算()初始化:设定Q为一空队列:procedureiniqueue(varQ:queue)beginQfront:=Qrear:=end()判队列空:若队列Q为空则返回值true否则返回值false:functionqempty(Q:queue):Booleanbeginqempty:=(Qfront=Qrear)end()判队满:若队列满则返回值true否则返回值false:functionqfull(Q:queue):BooleanbeginQfull:=(Qrear,maxsize)end()元素进队:若队列Q不满时把元素X插入到队列Q的队尾否则返回信息“Overflow”:procedureinqueue(varQ:queueX:elemtype)beginifqfull(Q)第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)thenwriteln(‘Overflow’)elsebeginQrear:=QrearQdataQrear:=Xendend()元素出队:若队列Q不空则把队头元素删除并返回值给X否则输出信息“Underflow”:proceduredelqueue(varQ:queuevarX:elemtype)beginifqempty(Q)thenwriteln(‘Underflow’)elsebeginQfront:=QfrontX:=QdataQfrontendend()取队头元素:若队列不空返回队头元素的值否则返回信息“Underflow”:functiongethead(Q:queue):elemtypebeginifqempty(Q)thenwriteln(‘Underflow’)elsegethead:=QdataQfrontend六、循环队列所谓循环队列就是将队列存储空间的最后一个位置绕到第一个位置形成逻辑上的环状空间供队列循环使用循环队列的定义如队列。当存储空间的最后一个位置已被使用而要进行入队运算时只要存储空间第一个位置空闲便可将元素加入到第一个位置即将存储空间的第一个位置作为队尾。采用首尾相接的循环队列结构后可以有效地解决假溢出的问题避免数据元素的移动。第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)七、循环队列的基本运算()初始化:设定Q为一空队列:procedureiniqueue(varQ:queue)beginQfront:=Qrear:=end()判队列空:若队列Q为空则返回值true否则返回值false:functionqempty(Q:queue):Booleanbeginqempty:=(Qfront=Qrear)end()判队满:若队列满则返回值true否则返回值false:functionqfull(Q:queue):Booleanbeginqfull:=((Qrear)modmaxsize=Qfront)end()元素进队:若队列Q不满时把元素X插入到队列Q的队尾否则返回信息“Overflow”:procedureinqueue(varQ:queueX:elemtype)beginifqfull(Q)thenwriteln(‘Overflow’)elsebeginQrear:=(Qrear)modmaxsizeQdataQrear:=Xendend()元素出队:若队列Q不空则把队头元素删除并返回值给X否则输出信息“Underflow”:proceduredelqueue(varQ:queuevarX:elemtype)beginifqempty(Q)thenwriteln(‘Underflow’)elsebeginQfront:=(Qfront)modmaxsizeX:=QdataQfrontendend第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)()取队头元素:若队列不空返回队头元素的值否则返回信息“Underflow”:functiongethead(Q:queue):elemtypebeginifqempty(Q)thenwriteln(‘Underflow’)elsegethead:=Qdata(Qfront)modmaxsizeend八、队列的应用队列在计算机科学领域中所起的作用:、解决主机与外部设备之间速度不匹配的问题(如:主机与打印机设置一个打印数据缓冲区)、解决由多用户引起的资源竞争问题(如:CPU资源的竞争操作系统按照每个请求的先后顺序排成一个队列)。九、典型例题例题:年高中组基础题第题从入口()到出口()的可行路线图中数字标号表示关卡:现将上面的路线图按记录结构存储如下:请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。【问题分析与答案】该题是一个路径搜索问题根据图示从入口()到出口()可以有多种途径其中最短的路径只有一条那么如何找最短路径是问题的关键根据题意用一维数组存储各关卡号(设NO)用另一个数组存储访问到某关卡号的前趋卡号所在数组单元下标(设PRE)由于本题是一个典型的图的遍历问题此题采用的是图的广度优先遍历算法并利用队列的方式存储顶点之间的联系。即访问一个点将其后继结点入队并存储它的前趋结点所在单元下标直到最后从()点出口从最后出口的关卡号()开始回访它的前趋卡号则回返的搜索路径便是最短路径(跳过许多不必要搜索的关卡)从列表中可以看出出口关卡号()的被访问路径最短的是:()()()()()开始第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)根据题意要求从存储数据中写出从入口到出口的最少关卡路径的算法是:从队列的最后一个关卡号开始依次回访它的前驱顶点所得到的路径即为最短路径。算法如下:i:=whilenoi<>doi:=irepeatwrite(‘(‘,noi,’)’)write(‘<‘)i:=preiuntili=例题:有升油在升的容器中另有两个升和升的空容器现要求用这三个容器倒油使得最后在升和升的容器中各有升油。【算法分析】提示:三个容器可以看作三个变量CCC每次倒油的可能性只有如下六种情况:C向C倒油C向C倒油C向C倒油C向C倒油C向C倒油C向C倒油()从一个容器的状态(三个容器中油的容量)看虽然有可能经过上述六种倒油的方法产生六种容器状态但实际上这六种新产生的容器状态许多是已经出现过的状态。例如初始状态(,,)表示C=C=C=经过上述六种倒油方法只能产生出两种新的容器状态(,,)表示C向C倒油的结果和(,,)表示C向C倒油的结果。如果再增加应该表示新容器状态是由什么状态产生的指示pre那么用这三个容器倒油的过程就可以用队列的方法来实现了。()队列可以理解为一个数组数组元素是如下记录:RECORDC,C,C,pre:integerEND数组下标为容器状态号。下面是倒油过程的队列图示:CCCPre当倒油产生出第个容器状态时已达到了题解的目的。这时只要根据pre中的状态号可以回溯到第个容器状态的pre值为依次可再获得容器状态号从而即可得到本题的倒油过程(共倒次)而且是最少的倒油次数。注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑:)有没有油可倒)究竟倒多少可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了。队列元素说明了个是因为升容器最多有,种状态升容器最多有,种状态升容器最多有,种状态全部可能的状态为**=种但油的总量为因此种可能状态中大部分是不存在的。变量fprp在程序中用作队列的头指针和尾指针flag在程序中标识是否已倒出了需要的容器状态(C=,C=)第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)例题:迷宫问题下图是一个简单的迷宫迷宫图中阴影部分是不通的路径处于迷宫中的每个位置都可以向个方向探索着按可行路径前进。假设出口位置在最右下角()入口在最左上角()试问能否设计出寻找一个从入口到出口的最短路径的算法呢,图中的()()()()()()()()便是所求的一个这种路径。【算法分析】为了设计求走迷宫的路径首先要对迷宫进行描述一种很自然的想法是把迷宫变为值的二维数组对上例而言可化为:探索路径的选择可描述为:(xy)(xy)(xy)(xy)(xy)(xy)(xy)(xy)(xy)这样一来迷宫中每个位置可探索的情况就分为:,只有三个探索方向的位置:如()探索方向只有()()和(),有五个探索方向的位置:如()探索方向有()()()()(),有八个探索方向的位置:如()探索方向有()()()()()()()()第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)能否不分情况统一按八种情况探索前进的路径呢,只要把原始迷宫数据修正如下即可达到目的(外加一圈不通的围墙)Mg:arraym,nofinteger探索方向可用xy的增量组成数组:xyZl:array,of–第二个要解决的问题应当考虑探索前进路径时如何把探索的踪迹记录下来记录的踪迹一般应包括来处和当前位置现设计如下顺序队列来完成探索路径的踪迹:typesqtype=arrayrofrecordx,y:integer,当前坐标,pre:r,前趋位置,end,这里的r一般<=m×n即迷宫的最大空位数目,varsq:sqtype例如:从()入口进入到达()往下探索时队列sq的情况:x„y„pre„frontrear第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)注意前趋采用了仅登记前趋在队列中的序号(前趋是由front指针指示的数据元素)为了防止被探索过的踪迹被重复探索被探索到的可通行路径需在迷宫中做上标记这里采用在迷宫数据中将换成的方法实现这样在走出迷宫时可以再把迷宫数据还原为原来的样子。例如上例探索到位置()的迷宫数据为:最后根据队列sq中的存储信息和指针位置即可链接成从迷宫入口到出口的最短路径。就上例而言sq队列的最后情况为:XYPre出发点无frontrear前趋当rear指针指示的数据元素已到达出口()时根据rear所据元素的前趋序号即可获得所要的走迷宫的最短路径(回溯)。如果变更增量数组中八个数据元素的顺序队列中存储的路径就可能不相同最后可能回溯出不同的最短路径来。例题:产生数(年NOIP普及组第题)给出一个整数n(n<=)和k个变换规则(k)。规则:个数字可以变换成另个数字规则中右边的数字不能为零。例如:n=k=规则为上面的整数经过变换后可能产生出的整数为(包括原数)第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)共种不同的产生数求经过任意次的变换(次或多次)能产生出多少个不同的整数。仅要求输出不同整数个数。输入:键盘输入格式为nkxyxy„„xnyn输出:屏幕输出格式为一个整数(满足条件的整数个数)。输入输出样例输入:输出:【问题分析】本题考察了同学们三方面的能力:数的表示如数如何表示如何处理转换规则如何表示队列的应用包括入队、出队以及队的查找。注意点:数只能以字符串的形式输入为了计算方便经过类型转换存入整型数组中对数的比较也很困难只能逐位比较处理时用一个队列q开始时队列q中只有n。【数据结构】str:string,输入开始的数,y,y:arrayof,工作单元,q:array,of,队列设长度,front,rear:integer,存入和取出指针,p:array,of,存储变换规则即pi,pi,,【算法流程】front:=rear:=whilefront<=reardobeginq出队y第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)根据规则扩展y生成新数xi逐个检查xi如果xi不在队列q中则xi入队否则不入队front:=frontend输出front值即为所求的个数。十、宽度优先搜索宽度优先搜索在树中又叫按层次遍历。对于树而言宽度优先搜索的思路可以描述为:访问根结点依次访问根结点的每一个子结点(第二层结点)再通过这些结点访问第三层结点„„。宽度优先搜索与深度优先搜索相比时间复杂度都是相同的不同的仅仅在于结点访问的顺序不同。它们在完全遍历的问题上应该说差不多但是在有些问题上比如求最优解有时宽度优先搜索较深度优先搜索好如倒酒问题。为了求一个最优解如果使用深度优先搜索并不能保证找到的解最优只有搜索完整棵树找到所有解再比较它们的优劣才能从中求出最优解这显然不如宽度优先搜索简单。一般说来宽度优先搜索可以利用队列实现主要用于解决求一种状态通过几种规定的操作以最少次数变换到另一种状态的问题。下面是利用队列搜索的一般步骤:()初始状态入队()i:=()对队头的状态进行第i种操作存储结果()检查结果是否出现过若未出现过则此结果进队记下此结果及其前趋()若结果即为所求至步骤()()若i=n队列第一个元素出队至步骤()否则i:=i至步骤()()搜索结束回溯输出结果。注意:在搜索过程中“出队”的元素必须一直保留不能删除最后输出过程时要用到。“判重”即指判断一个新搜索到的状态以前是否出现过如出现过就去掉它。判重一般用于用队列进行搜索而且用队列进行搜索的程序几乎全都用到这种方法。虽然判重需要增加时间而且一次最多只能去掉一种状态但这种状态所产生的众多无用状态所浪费的时间与空间将远远大于判重本身所需要的时间并且在问题无解时不去掉重复结点会造成程序死循环。例题:走马问题:在(,)位置的马走到()的最少步走法。(只能向右走),,第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)(数据结构马的位置:行位置H()列位置L()为了记录过程要记录父节点位置:F()对某节点K,K的位置是节H(P)行L(P)列它是由H(F(P))L(F(P))这个节点产生的。(控制策略从(,)出发找一步可走到的节点(插入队)这一个点的子节点找完后它的价值用完就出队。再从这些第一步可以到达的节点出发找所有一步可到的节点(也就是从(,)出发所有二步可到的节点)。如此反复直到节点位置是(,)则这一定是一个最少步数的答案。从一点的父节点位置可以回溯到(,)(产生规则如何产生新节点对本题只有,种走法(RMAX=)从点(H,L)可以起到(H,L),(H,L),(H,L)(H,L)(只能向右走)。所以可以建立节点位置的增量数组行增量HZ()和列增量LZ()。第页共页江苏省青少年信息学奥林匹克冬令营(JSOI)第页共页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/20

队列的基本操作及应用

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利