2007第五讲队列的基本操作(xinn).ppt
《2007第五讲队列的基本操作(xinn).ppt》由会员分享,可在线阅读,更多相关《2007第五讲队列的基本操作(xinn).ppt(56页珍藏版)》请在三一文库上搜索。
1、队列的基本操作,举例1:到医院看病,首先需要到挂号处挂号,然后,按号码顺序救诊。 举例2:乘坐公共汽车,应该在车站排队,车来后,按顺序上车。,一、队列的定义 队列就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个队尾指针r指向队尾元素,即r总是指向最后被插入的元素;允许删除的一端称为队首,通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。,结论:在队列这种数据结构中,最先插入在元素将是最先被删除;反之最后插入的元素将最后被删除,因此队列又称为“先进先出”(FIFOfirst in first out)的线性表。,队列的基本操作: (1)初始化队列 Q
2、ini (Q) (2)入队 QADD(Q,X) (3)出队 QDel(Q,X) (4)判断队列是否为空 qempty(Q) (5)判断队列是否为满qfull(Q),二、队列的存储结构,1、顺序存储,Const m=队列元素的上限; Type queue=record 队列的类型定义 data : array1m of elemtype f, r: integer ; 队尾指针和队首指针 end; Var q:queue; 队列,Const m=队列元素的上限; Type queue=array1m of elemtype Var q:queue; 队列 f, r: integer ; 队尾指针
3、和队首指针,二、队列的存储结构,2、链式存储,type link= celltype ; celltype=record data:elemtype; next:link; end; var f,r:link;,三、队列的基本运算,1、初始化:设定Q为一空队列:,procedure Qini (var Q:queue); begin Q.f:=0; Q.r:=0; end;,2、判队列空:若队列Q为空,则返回值true,否则返回值false。,function qempty(Q:queue):Boolean; begin qempty:=(Q.f=q.r) end;,function qful
4、l(Q:queue):Boolean; begin Qfull:=(Q.rm); end;,3、判队满:若队列满,则返回值true,否则返回值false。,4、元素进队:若队列Q不满时,把元素X插入到队列Q的队尾,否则返回信息“Overflow”:,procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) then writeln (overflow) 上溢 else begin 后移队尾指针并插入元素x Q.R:=Q.r+1; Q.dataQ.r:=x; end;else end;ADD,5、元素出队:若队列Q不空,则把队头元素删除并
5、返回值给X,否则输出信息“Underflow”:,procedure Qdel(var Q:queue;var X:elemtype); begin if qempty(Q) then writeln(Underflow) 下溢 else begin 后移队首指针并取出队首元素 Q.fQ.f+1; XQ.dataQ.f ; end;else end;,例1假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序,模拟上述舞伴配对问题。
6、 输入:第一行两队的人数 第二行舞曲的数目,应用举例,分析:设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=3 n=2 k=6,const max=10000; var a,b:array1max of integer; m,n,k1,k,i,f1,r1,f2,r2:integer; begin readln(m,n); for i:=1 to m do ai:=i; for i:=1 to n do bi:=i; readln(k); k1:=1; f1:=1;r1:=m;f2:=1;r2:=n;,repeat writeln(af1:3, ,bf1:3)
7、; r1:=r1+1;ar1:=af1; f1:=f1+1 ; r2:=r2+1;br2:=bf2; 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
8、分别放入队列a和队列b的队尾,尾指针加1。即: rr+1; ar2*x+1,br3*x+1,(3)将队列a和队列b的头结点进行比较,可能有三种情况: (A)ahabhb (B)aha=bhb (C)ahabhb 将比较的小者取出送入X,取出数的队列的头指针相应加1。 (4)重复(2),(3)直至取出第N项为止。,算法二:,var a:array130000 of 01; f,t,n,m,i:integer; begin readln(n); for i:=1 to 30000 do ai:=0; a1:=1;f:=1;k:=1;t:=0; while t=n do begin af*2+1:=
9、1;af*3+1:=1; f:=f+1; while af=0 do f:=f+1; T:=t+1; end;,m:=1;i:=1; while m0 then begin write(i, ); m:=m+1; end; i:=i+1; end; end.,编一个程序,找出一条通过迷宫的路径。这里有兰色方块的单元表示走不通,将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。,例4迷宫问题,入口,出口,分析(1)怎样来存储迷宫?将它变成0,1二维数组。这样上述迷宫可转化为:,(2)老鼠在迷宫中怎样探索路径?有几个方向可以探索呢? *只有三个探索方向的位置。如mg1,1 *有五个探索方
10、向的位置。如mg3,1 *有八个探索方向的位置。如mg3,2 思考:能否都转化为八个方向的探索呢?,这样存储的迷宫数组就转化成:,因此,数组定义为: Mg:array0m+1,0n+1 of integer;,而探索方向则变成了统一的情况,都探索8个方向:,(x-1,y+1),(x,y),(x-1,y),(x+1,y),(x,y+1),(x+1,y+1),(x-1,y-1),(x,y-1),(x+1,y-1),0 1,1 1,1 0,1 -1,0 -1,-1 -1,-1 0,-1 1,这样可以定义一个二维数组记录探索方向。,(3)如何才能记录踪迹,并把探索的踪迹记忆下来呢?,踪迹一般应包括来处
11、和当前位置,可以需要用记录类型 Node=record X,y:integer; Pre:0r; End;,用一个对队列记忆探索的踪迹: Sqtype=array1r of node;,例如:从(1,1)入口到达(6,8),往下探索时队列的情况,(4)如何防止重复探索:将迷宫中的0替换为-1,procedure Qini(var sQ:sqtype); begin sQ1.x:=1;sq1.y:=1; Sq1.pre:=0 F:=1;r:=1;mg1,1:=-1; end;,Procedure mglj(var sq:sqtype); Begin Sqini; While f=r do Beg
12、in x:=sqf.x;y:=sqf.y; for v:=1 to 8 do begin i:=x+zlv,1; j:=y+zlv,2; if mgi,j=0 then begin r:=r+1; sqr.x:=i;sqr.y:=j;sqr.pre:=f; mgi,j:=-1; end; if (i=m) and (j=n) then print;exit end;,F:=f+1 End; Writeln(迷宫无路径); End;,如何打印路径?,Procedure print(var sq:sqtype,r:integer); Begin i:=r; repeat writeln(,sqi.
13、x,sqi.y,); i:=sqi.pre until i=0 End;,产生问题:由于顺序存储结构的存储空间属于静态分配,所以,在添加数据元素时,可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列,称为“假溢出”现象。,解决方法:将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。采用首尾相接的结构后,形成一个环状,解决假溢出问题,避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。,Am-1,Am,Am+1,F,R,空闲区,1,2,3,m-1,m,am,Am-1,F,R,Am+1,循环队列的操作,procedure iniqueue(var Q:equeu
14、e); begin Q.f:=m;Q.r:=m; end;,1、初始化:设定Q为一空队列,队首指针和队尾指针均指向存储空间的最后一个位置,2、判队列空:若队列Q为空,则返回值true,否则返回值false。,function qempty(Q:equeue):Boolean; begin qempty:=(Q.f=Q.r) end;,3、判队满:若队列满,则返回值true,否则返回值false。为了区分队列空和队列满,改用“队尾指针追上队首指针” 这一特征作为队列满标志。,function qfull(Q:equeue):Boolean; begin qfull:=(Q.r mod m)+1=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2007 第五 队列 基本 操作 xinn
链接地址:https://www.31doc.com/p-3423180.html