文档详情

队列的基本操作.pptx

发布:2022-04-08约8.45千字共55页下载文档
文本预览下载声明
1;队列的基本操作: (1)初始化队列 Qini (Q) (2)入队 QADD(Q,X) (3)出队 QDel(Q,X) (4)判断队列是否为空 qempty(Q) (5)判断队列是否为满qfull(Q) ;二、队列的存储结构 ;二、队列的存储结构 ;三、队列的基本运算;2、判队列空:若队列Q为空,则返回值true,否则返回值false。;function qfull(Q:queue):Boolean; begin Qfull:=(=m); end;;4、元素进队:若队列Q不满时,把元素X插入到队列Q的队尾,否则返回信息“Overflow”:;5、元素出队:若队列Q不空,则把队头元素删除并返回值给X,否则输出信息“Underflow”???;例1假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序,模拟上述舞伴配对问题。 输入:第一行两队的人数 第二行舞曲的数目;分析:设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=3 n=2 k=6;const max=10000; var a,b:array[1..max] of integer; m,n,k1,k,i,f1,r1,f2,r2:integer; begin readln(m,n); for i:=1 to m do a[i]:=i; for i:=1 to n do b[i]:=i; readln(k); k1:=1; f1:=1;r1:=m;f2:=1;r2:=n;;repeat writeln(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; until k1k end.;例2.集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下: (1)数1属于M; (2)如果X属于M,则Y=2*X+1和Z=3*x+1也属于M; (3)此外再没有别的数属于M。 ;分析:可以用两个队列a和b来存放新产生的数,然后通过比较大小决定是否输出,具体方法如下: (1)令fa和fb分别为队列a和队列b的头指针,它们的尾指针为r。初始时,X=1,fa=fb=r=1; (2)将2*x+1和3*x+1分别放入队列a和队列b的队尾,尾指针加1。即: r←r+1; a[r]←2*x+1,b[r]←3*x+1 ;(3)将队列a和队列b的头结点进行比较,可能有三种情况: (A)a[ha]b[hb] (B)a[ha]=b[hb] (C)a[ha]b[hb] 将比较的小者取出送入X,取出数的队列的头指针相应加1。 (4)重复(2),(3)直至取出第N项为止。;算法二:;m:=1;i:=1; while m=n do begin if a[i]0 then begin write(i, ); m:=m+1; end; i:=i+1; end; end.; 编一个程序,找出一条通过迷宫的路径。这里有兰色方块的单元表示走不通,将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。  ;分析(1)怎样来存储迷宫?将它变成0,1二维数组。这样上述迷宫可转化为:;(2)老鼠在迷宫中怎样探索路径?有几个方向可以探索呢? *只有三个探索方向的位置。如mg[1,1] *有五个探索方向的位置。如mg[3,1] *有八个探索方向的位置。如mg[3,2] 思考:能否都转化为八个方向的探索呢? ;这样存储的迷宫数组就转化成:;因此,数组定义为: Mg:array[0..m+1,0..n+1] of integer;;(3)如何才能记录踪迹,并把探索的踪迹记忆下来呢?;例如:从(1,1
显示全部
相似文档