队列及其应用_fan.ppt

1、队列及其应用,安庆四中 范江文,队列,队列是一种先进先出(FIFO)的线性表 队列的顺序存储结构和链式存储结构 队列必须构造成循环队列的形式,否则会出现“假溢出”,队列基本操作： （1）初始化 init() （2）是否为空 empty() （3）是否满 full() （4）入队 inqueue() （5）出队 delqueue() （6）取队头元素 gethead() （7）队列长度 lenqueue(),一般队列存储方式,（1）顺序存储：用数组表示，front和rear分别表示队头元素和队尾元素； 约定：front指向队头元素在队列中的前一个位置，rear指向队尾元素在队列中的当前位置。,c

2、onst qmaxsize=.; type qelement=数据类型； queue=record data:array1.qmaxsizeof qelement; front,rear:0.qmaxsize; end; var q:queue;,顺序存储,rear=0 front=0 空队列,front=0 rear=3 a1,a2,a3入队,front=1 rear=3 a1出队,front=3 rear=3 a2,a3出队,front=3 rear=5 a4,a5入队,顺序存储队列的基本操作,(1)初始化 init() procedure init(var q:queue); begin

3、 q.front:=0;q.rear:=0; end; (2)是否为空 empty() function empty(var q:queue); begin empty:=(q.front=q.rear); end; (3)是否满 full() function full(var q:queue); begin full:=(q.rear=qmaxsize); end;,顺序存储队列的基本操作,(4)入队 inqueue(); procedure inqueue(var q:queue;x:qelement); begin if full(q) then writeln(FULL) else

4、begin inc(q.rear);q.datarear:=x; end; (5)出队 delqueue() procedure delqueue(var q:queue;x:qelement); begin if empty(q) then writeln(EMPTY) else begin inc(q.front); x:=q.dataq.front; end; (6)队头元素:m:=q.front+1;gethead:=q.datam (7)队列长度：lenqueue:=q.rear-q.front,一般队列存储方式,(2)链接存储：用一个单链表来实现。为了便于表示空队列，使用一个表头单

5、元，将队头指针指向表头单元。,type queueptr=queuenode; queuenode=record data:elemtp; next:queueptr; end; linkedquetp=record front,rear:queueptr; end;,q.front,q.front,.,链接存储队列的基本操作,(1)入队 inqueue(var q:linkedquetp;x:elemtp); procedure inqueue(var q:linkedquetp;x:elemtp); begin new(q.rear.next); q.rear:=q.rear.next;

6、q.rear.data:=x; q.rear.next:=nil; end; (2)出队 delqueue(var q:linkedquetp;x:elemtp); procedure delqueue(var q:linkedquetp;x:elemtp); begin if empty(q) then writeln(EMPTY) else begin p:=q.front; q.front:=q.front.next; dispose(p); end,链接存储队列的基本操作,(3)置空队列 clear(q) procedure clear(var q:linkedquetp); begi

7、n q.rear:=q.front; while q.frontnil do begin q.front:=q.front.next; dispose(q.rear); q.rear:=q.front; end; new(q.front); q.front.next:=nil; q.rear:=q.front; end;,循环队列存储方式,解决“假溢出”现象，q1接在qm之后，形成循环表，当删除a1之后插入am+1时，不移动队列中现有元素，直接把它加到q1位置上去。实际上就形成了一个环，这种队列称为循环队列。 约定：损失一个元素空间。当front=rear时定义为空；当rear从后面追上fro

8、nt时，作为队满标志：rear+1=front,0,3,2,4,1,5,0,3,2,4,1,5,0,3,2,4,1,5,0,3,2,4,1,5,front=rear=0 空队列,a1,a2,a3,a4,a5,front=0 rear=5 a1.a5入队,队满,front=3 rear=5 a1.a3出队,a4,a5,a4,a5,a6,a7,a8,rear=2 front=3 a6.a8入队，队满,入队:rear:=(rear+1) mod max 出队:front:=(front+1) mod max,循环队列存储,const maxsize=.; type qelement=数据类型; qu

9、eue=record data=array0.maxsize-1of qelement; front，rear:0.maxsize-1; end; var q:queue;,循环队列基本操作,(1)初始化 init() procedure init(var q:queue); begin q.front:=0; q.rear:=0; end; (2)是否为空 empty() function empty(var q:queue):boolean; begin empty:=(q.front=q.rear); end; (3)是否溢出 full() function full(var q:que

10、ue):boolean; begin full:=(q.(rear+1) mod maxsize=q.front); end;,循环队列基本操作,(4)入队 inqueue(var q:queue; x:qelement); procedure inqueue(var q:queue;x:qelement); begin if full(q) then writeln(FULL) else begin q.rear:=(q.rear+1)mod maxsize; q.dataq.rear:=x; end; (5)出队 delqueue(var q:queue; x:qelement); pro

11、cedure delqueue(var q:queue; x:qelement); begin if empty(q) then writeln(EMPTY) else begin q.front:=(q.front+1）mod maxsize; x:=q.dataq.front; end;,循环队列基本操作,(6)队头元素 gethead(var q:queue):qelement; m:=(q.front+1)mod maxsize; gethead:=q.datam; (7)队列长度lenqueue(var q:queue):integer; lenqueue:=(q.rear-q.fr

12、ont+maxsize) mdo maxsize;,用队列实现图的宽度优先搜索算法,我们要对图进行分层次遍历,遍历的序列为1，2，7，,宽度有先搜索算法遍历序列图,分析,要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下： 第一步：将初始点放入队列，并将该点设置为已标号的点。 第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。 第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。,Procedure bfs(v); 从v开始宽度有先遍历图 begin init(var q:queue); 初始化队列q

13、q.inqueue(v); vistedv:=true; 初始点v放入队列，并标号 repeat while v的邻接顶点存在 do begin q.inqueue（var q:queue; v的邻接顶点）; vistedv的邻接顶点:=true; end; q.delqueue(var q:queue;v:qelement); until q.empty(var q:queue) ; 直到队列为空 end ;,队列应用,舞伴问题,假设在周末舞会上，男士们和女士们进入舞厅时，各排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数各不相同，则较长的那一队中未配对者等待下

14、一轮舞曲。,分析：先入队的男士或女士是先出队配成舞伴。典型FIFO可用队列 1、构造两个队列男队a,女队b 2、依次将a,b的队头元素取出配成舞伴，直至队列为空 3、若某队仍有等待配对者，继续配对；直到所有人都配对成功。,参考代码：,program wuban; type at=array1.100of integer; var n,m,aa,i:integer; a,b:at; function max(mm,nn:integer):integer; var s,i,j,min:integer; begin if mmnn then begin s:=mm;mm:=nn;nn:=s;end;

15、 for i:=mm downto 1 do if (mm mod i =0)and(nn mod i=0)then begin max:=mm*nn div i; exit; end; end;,procedure add(var aa:at;x,r:integer); begin aar:=x; inc(r); end; begin readln(m,n); for i:=1 to max(m,n) do begin if i mod m0 then add(a,i mod m,i) else add(a,m,i); if i mod n0 then add(b,i mod n,i) el

16、se add(b,n,i); end; for i:=1 to max(m,n) do writeln(ai, ,bi); readln; end.,面积,编程计算有“*”围成的下列图形的面积。面积的计算方法是统计“*”所围成的闭合曲线中水平线和垂直线交点的数目。,算法分析,gr存储这张表 图形面积=总的个数-外围0的个数-*的个数 外围0的找法：从左上角0开始，找所有与它相邻的0，存入队列。一个0的相邻点找完，再找队列的下个相邻点；直到所有的0找到为止。,上、右、下、左增量,参考程序,const n=10; gr:array1.n,1.nof 0.2=( (0,0,0,0,0,0,0,0,0

17、,0), (0,0,0,0,1,1,1,0,0,0), (0,0,0,0,1,0,0,1,0,0), (0,0,0,0,0,1,0,0,1,0), (0,0,1,0,0,0,1,0,1,0), (0,1,0,1,0,1,0,0,1,0), (0,1,0,0,1,1,0,1,1,0), (0,0,1,0,0,0,0,1,0,0), (0,0,0,1,1,1,1,1,0,0), (0,0,0,0,0,0,0,0,0,0) ); d:array0.1,1.4of integer=(0,1,0,-1),(-1,0,1,0); var que:array1.n*n,0.1of byte; i,j,f,x

18、,y,start,tail,sum:integer; begin sum:=0; for i:=1 to n do for j:=1 to n do if gri,j0 then inc(sum);,x:=1;y:=1;start:=1;tail:=1; que1,0:=x; que1,1:=y; gr1,1:=2; repeat for f:=1 to 4 do begin x:=questart,0+d0,f; y:=questart,1+d1,f; if(x0)and(x0)and(ytail; writeln(area=,n*n-sum-tail); readln;,练习,1.迷宫问题：编程找出一条通过迷宫的路径，即输出从入口处（左上角）到