2007第5讲队列的基本操作[xinn].ppt

队列的基本操作 ;一、队列的定义 队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。;结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。 ;队列的基本操作： （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:=（Q.r＝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二维数