队列的基本操作学习教案.pptx
上传人:王子****青蛙 上传时间:2024-09-13 格式:PPTX 页数:55 大小:333KB 金币:10 举报 版权申诉
预览加载中,请您耐心等待几秒...

队列的基本操作学习教案.pptx

队列的基本操作学习教案.pptx

预览

免费试读已结束,剩余 45 页请下载文档后查看

10 金币

下载此文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

会计学队列的基本操作:(1)初始化队列Qini(Q)(2)入队(rùduì)QADD(Q,X)(3)出队QDel(Q,X)(4)判断队列是否为空qempty(Q)(5)判断队列是否为满qfull(Q)二、队列(duìliè)的存储结构二、队列的存储(cúnchǔ)结构三、队列的基本(jīběn)运算2、判队列(duìliè)空:若队列(duìliè)Q为空,则返回值true,否则返回值false。functionqfull(Q:queue):Boolean;beginQfull:=(Q.r=m);end;4、元素(yuánsù)进队:若队列Q不满时,把元素(yuánsù)X插入到队列Q的队尾,否则返回信息“Overflow”:5、元素出队:若队列Q不空,则把队头元素删除并返回值给X,否则(fǒuzé)输出信息“Underflow”:例1假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲(wǔqǔ)能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲(wǔqǔ)。现要求写一个程序,模拟上述舞伴配对问题。输入:第一行两队的人数第二行舞曲(wǔqǔ)的数目分析:设计两个队列分别存放男士和女士。每对跳舞的人一旦(yīdàn)跳完后就回到队尾等待下次被选。如m=3n=2k=6constmax=10000;vara,b:array[1..max]ofinteger;m,n,k1,k,i,f1,r1,f2,r2:integer;beginreadln(m,n);fori:=1tomdoa[i]:=i;fori:=1tondob[i]:=i;readln(k);k1:=1;f1:=1;r1:=m;f2:=1;r2:=n;repeatwriteln(a[f1]:3,'',b[f1]:3);r1:=r1+1;a[r1]:=a[f1];f1:=f1+1;r2:=r2+1;b[r2]:=b[f2];f2:=f2+1;k1:=k1+1;untilk1>kend.例2.集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下:(1)数1属于M;(2)如果(rúguǒ)X属于M,则Y=2*X+1和Z=3*x+1也属于M;(3)此外再没有别的数属于M。分析:可以用两个队列(duìliè)a和b来存放新产生的数,然后通过比较大小决定是否输出,具体方法如下:(1)令fa和fb分别为队列(duìliè)a和队列(duìliè)b的头指针,它们的尾指针为r。初始时,X=1,fa=fb=r=1;(2)将2*x+1和3*x+1分别放入队列(duìliè)a和队列(duìliè)b的队尾,尾指针加1。即:r←r+1;a[r]←2*x+1,b[r]←3*x+1(3)将队列(duìliè)a和队列(duìliè)b的头结点进行比较,可能有三种情况:(A)a[ha]>b[hb](B)a[ha]=b[hb](C)a[ha]<b[hb]将比较的小者取出送入X,取出数的队列(duìliè)的头指针相应加1。(4)重复(2),(3)直至取出第N项为止。算法(suànfǎ)二:m:=1;i:=1;whilem<=ndobeginifa[i]<>0thenbeginwrite(i,'');m:=m+1;end;i:=i+1;end;end.编一个程序,找出一条通过迷宫的路径。这里(zhèlǐ)有兰色方块的单元表示走不通,将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。分析(1)怎样(zěnyàng)来存储迷宫?将它变成0,1二维数组。这样上述迷宫可转化为:(2)老鼠在迷宫(mígōng)中怎样探索路径?有几个方向可以探索呢?*只有三个探索方向的位置。如mg[1,1]*有五个探索方向的位置。如mg[3,1]*有八个探索方向的位置。如mg[3,2]思考:能否都转化为八个方向的探索呢?这样(zhèyàng)存储的迷宫数组就转化成:因此(yīncǐ),数组定义为:Mg:array[0..m+1,0..n+1]ofinteger;(3)如何(rúhé)才能记录踪迹,并把探索的踪迹记忆下来呢?例如:从(1,1)入口(rùkǒu)到达(6,8),往下探索时队列的情况(4)如何防止重复探索:将迷宫(mígōng)中的0替换为-1Proceduremglj(varsq:sqtype);BeginSqini;Whilef<=rdoBeginx:=sq[f].x;y:=sq[f].y;forv:=1to8dobegini:=x+zl[v,1];j:=y+zl[v,2];ifmg