数据结构6.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,3.4 队列,3.4.1 抽象数据类型队列的定义,队列(,Queue),也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为,队头(,front),，,允许插入的一端称为,队尾(,rear),。,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(,First In First Out),的线性表，简称,FIFO,表。,当队列中没有元素时称为,空队列,。在空队列中依次加入元素,a,1,a,2,a,n,之后，,a,1,是,队头元素,，,a,n,是,队尾元素,。显然退出队列的次序也只能是,a,1,a,2,a,n,，,也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：,队列的抽象数据定义见书,59,3.4.2 非循环队列和循环队列,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为。入队时将新元素插入所指的位置，然后加。出队时，删去所指的元素，然后加并返回被删元素。由此可见，当头尾指针相等时队列为空。,在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。,0 1 2 3,Front,rear,a,b,c,Front rear,(,a),队列初始为空（,b）A,B,C,入队,b,c,front rear front,rear,（c)a,出队,(,d)b,c,出队，队为空,队空：,Q.front=Q.rear,队满：,Q.rear-Q.front=,maxsize,（,求队长）,入队：新元素按,rear,指示位置加入，再将队尾指针加一，即,rear=rear,+1,出队：将,front,指示的元素取出，再将队头指针加一，即,front=front,+1，。,非,循环队列,和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在,“,假上溢,”,现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。,为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为,循环队列（,Circular Queue),。,在,循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（,QueueSize,-1）,时，其加1操作的结果是指向向量的下界0。,显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。,打开,P64,如图3.14所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过,Q.front=Q.rear,来判断队列“空”还是“满”。,解决此问题的方法至少有两种：,其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：,rear,所指的单元始终为空）,0,1,2,3,4,5,rear,front,J4,J5,J6,0,1,2,3,4,5,rear,front,J9,J8,J7,J4,J5,J6,0,1,2,3,4,5,rear,front,初始状态,J4,J5,J6,出队,J7,J8,J9,入队,队空：,front=rear,队满：,front=rear,解决方案：,1.另外,设一个标志,以区别队空、队满,2,.少用一个元素空间,：,队空：,front=rear,队满：(,rear+1)%M=front,队空：,Q.front=Q.rear,队满：,Q.front=(Q.rear+1)%,maxSize,入队:,Q.rear=(Q.rear+1)%,maxSize,出队:,Q.front=(front+1)%,maxSize,;,求队长:(,Q.rear-Q.front+,maxSize,)%,maxSize,循环队列,3.4.3 链队列,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。,null,*q,q.front,q.rear,非空队列,q.front,q.rear,null,空队列,*q,链队列示意图,和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型,LinkQueue,定义为一个结构类型：,typedef struct queuenode,datatype,data;,struct queuenode,*next;,queuenode,;,typedef struct,queuenode,*front;,queuenode,*rear;,linkqueue,;,下面给出链队列上实现的基本运算：,构造一个空队列：,void,initqueue,(,linkqueue,*q),q.front-next=q.rear-next=null;,q.front,q.rear,null,置队空,*q,队列的判空：,int queueempty,(,linkqueue,*q),return(q.front-next=null&,q.rear-next=null);,void,enqueue,(,linkqueue,*q,datatype,x),queuenode,*p,p=(,queuenode,*),malloc,(,sizeof,(,queuenode,);,pdata=x;,pnext=null;,if(,queueempty,(q),q.front-next=q.rear=p;,else,q.rearnext=p;,q.rear=p;,入队操作,null,*q,q.front,q.rear,入队,x,null,p,出队操作：,Datatype dequeue,(,linkqueue,*q),datatype,x;,queuenode,*p,if(,queueempty,(q),error(“queue underflow”);,p=q.front-next;,x=pdata;,q.front-next=pnext;,if(q.rear=p),q.rear=q.front;,free(p);,return x;,null,*q,q.rear,x,null,q.front,p,存储池,出队,队列应用举例,划分子集问题,问题描述：已知集合,A=a1,a2,an，,及集合上的关系,R=(,ai,aj,)|,ai,aj,A,ij，,其中(,ai,aj,),表示,ai,与,aj,间存在冲突关系。要求将,A,划分成,互不相交,的子集,A1,A2,Ak,(kn)，,使任何子集中的元素均无冲突关系，同时要求,分子集个数尽可能少,例,A=1,2,3,4,5,6,7,8,9,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),可行的子集划分为：,A1=1,3,4,8,A2=2,7,A3=5,A4=6,9,