数据结构队列.ppt

《数据结构队列.ppt》由会员分享，可在线阅读，更多相关《数据结构队列.ppt（40页珍藏版）》请在课桌文档上搜索。

1、3.2 队列,3.2.1 队列的定义,返回,3.2.2 队列的顺序存储结构及其基本运算的实现,3.2.3 队列的链式存储结构及其基本运算的实现,3.2.4 队列的应用例子,队列简称队,它也是一种运算受限的线性表,其限制仅允许在表的一端进行插入,而在表的另一端进行删除。我们把进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。,3.2.1 队列的定义,队列的入队和出队操作示意图,3.2.2 队列的顺序存储结构及其基本运算的实现,假设队列的元

2、素个数最大不超过整数MaxSize,所有的元素都具有同一数据类型ElemType,则顺序队列类型SqQueue定义如下:typedef struct ElemType dataMaxSize；int front,rear；/*队首和队尾指针*/SqQueue,从前图中看到,图(a)为队列的初始状态,有front=rear成立,该条件可以作为队列空的条件。那么能不能用rear=MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。为了能够充分地使用数组

3、中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。,循环队列首尾相连,当队首front指针满足 front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算()来实现:队首指针进1:front=(front+1)MaxSize 队尾指针进1:rear=(rear+1)MaxSize 循环队列的除头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按逆时针方向进1。,怎样区分这两者之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件

4、为:(q-rear+1)%MaxSize=q-front队空条件仍为:q-rear=q-front,循环队的入队和出队操作示意图,在循环队列中,实现队列的基本运算算法如下:(1)初始化队列InitQueue(,(2)销毁队列ClearQueue(,(3)判断队列是否为空QueueEmpty(q)若队列q满足q-front=q-rear条件,则返回1；否则返回0。对应算法如下:int QueueEmpty(SqQueue*q)return(q-front=q-rear);,(4)入队列enQueue(q,e)在队列不满的条件下,先将队尾指针rear循环增1,然后将元素添加到该位置。对应算法如下:

5、int enQueue(SqQueue*,(5)出队列deQueue(q,e)在队列q不为空的条件下,将队首指针front循环增1,并将该位置的元素值赋给e。对应算法如下:int deQueue(SqQueue*,例3.6 什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？,答:在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若 rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由

6、于队列的操作方法所致。,解决队列上溢的方法有以下几种:(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。(2)当出现假溢出时可采用以下几种方法:采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；,每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置；采用循环队列方式:把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循“先进先出”的原则。,例3.7 对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,可以用队

7、列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。,解:当已知队首元素的位置front和队列中元素个数count后:队空的条件为:count=0队满的条件为:count=MaxSize计算队尾位置rear:rear=(front+count)%MaxSize 对应的算法如下:typedef struct ElemType dataMaxSize;int front;/*队首指针*/int count;/*队列中元素个数*/QuType;/*队列类型*/,void InitQu(QuType*,int EnQu(QuType*,int DeQu(QuType*,in

8、t QuEmpty(QuType*q)/*判空*/return(q-count=0);,链队组成:(1)存储队列元素的单链表(2)指向队头和队尾指针的链队头结点,3.2.3 队列的链式存储结构及其基本运算的实现,链列的入队和出队操作示意图,单链表中数据结点类型QNode定义如下:typedef struct qnode ElemType data;/*数据元素*/struct qnode*next;QNode;链队中头结点类型LiQueue定义如下:typedef struct QNode*front;/*指向单链表队头结点*/QNode*rear;/*指向单链表队尾结点*/LiQueue;,

9、在链队存储中,队列的基本运算算法如下:(1)初始化队列InitQueue(q)构造一个空队列,即只创建一个链队头结点,其front和rear域均置为NULL,不创建数据元素结点。对应算法如下:void InitQueue(LiQueue*,(2)销毁队列ClearQueue(q)释放队列占用的存储空间,包括链队头结点和所有数据结点的存储空间。对应算法如下:void ClearQueue(LiQueue*/*释放链队结点占用空间*/,(3)判断队列是否为空QueueEmpty(q)若链队结点的rear域值为NULL,表示队列为空,返回1；否则返回0。对应算法如下:int QueueEmpty(L

10、iQueue*q)if(q-rear=NULL)return 1;else return 0;,(4)入队列enQueue(q,e)创建data域为e的数据结点*s。若原队列为空,则将链队结点的两个域均指向*s结点,否则,将*s链到单链表的末尾,并让链队结点的rear域指向它。对应算法如下:,void enQueue(LiQueue*,(5)出队列deQueue(q,e)若原队列不为空,则将第一个数据结点的data域值赋给e,并删除之。若出队之前队列中只有一个结点,则需将链队结点的两个域均置为NULL,表示队列已为空。对应的算法如下:,int deQueue(LiQueue*,3.2.4 队列

11、的应用例子采用队列求解迷宫问题 使用一个队列Qu记录走过的方块,该队列的结构如下:struct int i,j;/*方块的位置*/int pre;/*本路径中上一方块在Qu中的下标*/QuMaxSize;int front=-1,rear=-1;/*队首指针和队尾指针*/这里使用的队列Qu不是循环队列(因为要利用出队的元素找路径),因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径。,(1)首先将(1,1)入队;(2)在队列Qu不为空时循环:出队一次(由于不是循环队列,该出队元素仍在队列中),称该出队的方块为当前方块,front为该方块在Qu中的下标。如果当前方块是出口,则输出

12、路径并结束。否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块(对应的mg数组值为0),将这些可走的相邻方块均插入到队列Qu中,其pre设置为本搜索路径中上一方块在Qu中的下标值,也就是当前方块的front值,并将相邻方块对应的mg数组值置为-1,以避免回过来重复搜索。(3)若队列为空仍未找到出口,即不存在路径。,搜索从(1,1)到(M-2,N-2)路径,实际上,本算法的思想是从(1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是将在第8章介绍的图的广度优先搜索方法。,void mgpath()/*搜索路径为:(1,1)-(M-2,N-2)*/int

13、i,j,find=0,di;rear+;Qurear.i=1;Qurear.j=1;Qurear.pre=-1;/*(1,1)入队*/mg11=-1;/*将其赋值-1,以避免回过来重复搜索*/while(front=rear/*调用print函数输出路径*/,for(di=0;di3;di+)/*把每个可走的方块插入队列中*/switch(di)case 0:i=Qufront.i-1;j=Qufront.j;break;case 1:i=Qufront.i;j=Qufront.j+1;break;case 2:i=Qufront.i+1;j=Qufront.j;break;case 3:i=

14、Qufront.i,j=Qufront.j-1;break;if(mgij=0)rear+;/*将该相邻方块插入到队列中*/Qurear.i=i;Qurear.j=j;Qurear.pre=front;/*指向路径中上一方块下标*/mgij=-1;/*将其赋值-1,以避免重复搜索*/if(!find)printf(不存在路径!n);,本章小结本章基本学习要点如下:(1)理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。,(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件。(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。,练习题 教材中p77的习题2、4和6。上机实验题 教材中p79题5和7。,