《《队列及其实现》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《队列及其实现》PPT课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、Houfeng Wang,ICL of PKU,1,队列及其实现,排队上车,排队上车,Bus Stop Queue,Houfeng Wang,ICL of PKU,5,队列的特点,队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的这一端叫队列的头，允许进行插入的这一 端叫队列的尾。当队列中没有任何元素时，称为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。,Houfeng Wang,ICL of PKU,6,队列也称作先进先出表(First In First Out表，简称FIFO表）图4.7是队列的
2、示意图,Houfeng Wang,ICL of PKU,7,队列的基本运算,1.Queue createEmptyQueue(void)创建一个空队列2.int isEmptyQueue(Queue qu)判队列qu是否为空队列，当qu为空队列时取真值，否则取假值 3.void enQueue(Queue qu,DataType x)往队列qu中插入一个值为x的元素4.void deQueue(Queue qu)从队列qu中删除一个元素 5.DataType frontQueue(Queue qu)求队列qu头部元素的值,Houfeng Wang,ICL of PKU,8,队列的实现,Houf
3、eng Wang,ICL of PKU,9,顺序表示,队列的顺序表示，约定：队头指针指出实际队头元素所在的位置，而队尾指针指出实际队尾元素所在位置的下一个位置。结构定义：#define MAXNUM/队列中最大元素个数struct SeqQueue/顺序队列类型定义 DataType qMAXNUM;int f,r;/f 指向队列头，r 指向队列尾;typedef struct SeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/,Houfeng Wang,ICL of PKU,10,设paqu是PSeqQueue类型的变量，则头变量paqu-f存放即将要被删除的元素的下标，尾
4、变量paqu-r存放即将要被插入的元素（当前还不是队列中的元素）的下标。初始时paqu-f=paqu-r=0。队列中元素的个数可以用paqu-r-paqu-f计算得到，当paqu-r=paqu-f时，元素的个数为0，即为空队列。例子：观察变化过程,约定,Houfeng Wang,ICL of PKU,11,Houfeng Wang,ICL of PKU,12,基本运算,PSeqQueue createEmptyQueue_seq(void)创建一个空队列，返回指向空队列的指针。2.int isEmptyQueue_seq(PSeqQueue paqu)判断paqu所指的队列是否为空队列，当pa
5、qu所指的队列为空队列时，则返回1，否则返回0。,Houfeng Wang,ICL of PKU,13,PSeqQueue createEmptyQueue_seq(void)/创建一个空队列，返回指向空队列的指针 PseqQueue psqu;psqu=(PseqQueue)malloc(sizeof(struct SeqQueue);if(psqu!=NULL)psqu-r=0;psqu-f=psqu-r;return(psqu);,Houfeng Wang,ICL of PKU,14,int isEmptyQueue_seq(PSeqQueue paqu)/判断paqu所指的队列是否为空
6、队列，当paqu所指的队/列为空队列时，则返回1，否则返回0 return(paqu-r=0);,Houfeng Wang,ICL of PKU,15,void enQueue_seq(PSeqQueue paqu,DataType x)进队列运算，表示往paqu所指的队列中插入一个值为的元素。void deQueue_seq(PSeqQueue paqu)出队列运算，表示从paqu所指的队列中删除一个元素。DataType frontQueue_seq(PSeqQueue paqu)当paqu所指的队列不空时，求队列头部元素的值，队列保持不变。自己实现上述三个算法（！）,Houfeng Wa
7、ng,ICL of PKU,16,当队列满时，再作进队操作，这种现象称为上溢；当队空时，作删除操作，这种现象称为下溢。溢出现象在运算中都要考虑。当paqu-r=MAXNUM时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）位置，这种现象称为假溢出。,队列的溢出,Houfeng Wang,ICL of PKU,17,解决假溢出通常采用的方法是：把数组paqu-qMAXNUM从逻辑上看成一个环，即规定paqu-q0是paqu-qMAXNUM-1的下一个元素。当paqu-qMAXNUM-1已经插入元素以后，就把paqu-r置成0，再有元素要插入时，就插到paqu-q0的位置上，这
8、种队列也称为环形队列环形队列空与满的区别：牺牲队列中的一个结点，当队列中已有MAXNUM-1个结点时就称满，再要插入就发生溢出（见图4.9）,Houfeng Wang,ICL of PKU,18,Houfeng Wang,ICL of PKU,19,环形队列中队列基本运算的算法,1.PSeqQueue createEmptyQueue_seq(void)为队列结构申请空间，创建一个空队列。,Houfeng Wang,ICL of PKU,20,*创建一个空队列（同前）,PSeqQueue createEmptyQueue_seq(void)PSeqQueue paqu;paqu=(PSeqQu
9、eue)malloc(sizeof(struct SeqQueue);if(paqu=NULL)printf(Out of space!n);else paqu-f=0;paqu-r=0;return(paqu);,Houfeng Wang,ICL of PKU,21,int isEmptyQueue_seq(PSeqQueue paqu)判断paqu所指的队列是否为空队列。（请与前面非循环队列区别）int isEmptyQueue_seq(PSeqQueue paqu)return(paqu-f=paqu-r);,Houfeng Wang,ICL of PKU,22,3.void enQue
10、ue_seq(PSeqQueue paqu,DataType x)当队列不满时，将元素x插入paqu所指的队列中。void enQueue_seq(PSeqQueue paqu,DataType x)/*在队列中插入一元素x*/if(paqu-r+1)%MAXNUM=paqu-f)printf(Full queue.n);else paqu-qpaqu-r=x;paqu-r=(paqu-r+1)%MAXNUM;,Houfeng Wang,ICL of PKU,23,4.void deQueue_seq(PSeqQueue paqu)出队列运算，当队列不空时，从paqu所指的队列中删除一个元素v
11、oid deQueue_seq(PSeqQueue paqu)/*删除队列头部元素*/if(paqu-f=paqu-r)printf(Empty Queue.n);elsepaqu-f=(paqu-f+1)%MAXNUM;,Houfeng Wang,ICL of PKU,24,5.DataType frontQueue_seq(PSeqQueue paqu)当paqu所指的队列不空时，取队列头部元素，队列本身保持不变。DataType frontQueue_seq(PSeqQueue paqu)/*对非空队列,求队列头部元素*/return(paqu-qpaqu-f);,Houfeng Wan
12、g,ICL of PKU,25,链接表示,lastNode,Houfeng Wang,ICL of PKU,26,队列的链接表示,链接结点的结构定义：struct Node;typedef struct Node*PNode;struct Node/结点结构 DataType info;PNode link;,Houfeng Wang,ICL of PKU,27,队列的链接结构封装,struct LinkQueue/链接队列类型定义 PNode f;/头指针 PNode r;/尾指针;实际应用中，经常使用的是链接队列类型的指针类型，因此常有如下定义：typedef struct LinkQue
13、ue*PLinkQueue;,Houfeng Wang,ICL of PKU,28,Houfeng Wang,ICL of PKU,29,链接队列中基本运算的实现,1.PLinkQueue createEmptyQueue_link()申请队列结构空间，创建一个空队列。PLinkQueue createEmptyQueue_link()PLinkQueue plqu;plqu=(PLinkQueue)malloc(sizeof(struct LinkQueue);if(plqu!=NULL)plqu-f=NULL;plqu-r=NULL;else printf(Out of space!n);
14、return(plqu);,Houfeng Wang,ICL of PKU,30,2.int isEmptyQueue_link(PLinkQueue plqu)判断plqu所指的队列是否为空队列，当plqu所指的队列为空队列时，则返回1，否则返回0。判断链接表示队列是否为空队列 int isEmptyQueue_link(PLinkQueue plqu)return(plqu-f=NULL);,Houfeng Wang,ICL of PKU,31,3.void enQueue_link(PLinkQueue plqu,Datatype x)进队列运算，往plqu所指的队列中插入一个值为x的元
15、素。void enQueue_link(PLinkQueue plqu,Datatype x)PNode p;p=(PNode)malloc(sizeof(struct Node);if(p=NULL)printf(Out of space!);else p-info=x;p-link=NULL;if(plqu-f=NULL)plqu-f=p;plqu-r=p;else plqu-r-link=p;plqu-r=p;,Houfeng Wang,ICL of PKU,32,4.void deQueue_link(PLinkQueue plqu)出队列运算，表示从plqu所指的队列中删除队列头部元
16、素。void deQueue_link(PLinkQueue plqu)PNode p;if(plqu-f=NULL)printf(Empty queue.n);else p=plqu-f;plqu-f=plqu-f-link;free(p);,Houfeng Wang,ICL of PKU,33,5.Datatype frontQueue_link(PLinkQueue plqu)当plqu所指的队列不为空时，取队列头部元素的值，队列保持不变。Datatype frontQueue_link(PLinkQueue plqu)/*在非空队列中求队头元素*/return(plqu-f-info);,Houfeng Wang,ICL of PKU,34,应用：农夫过河,Houfeng Wang,ICL of PKU,35,作业与上机,假设以数组Qm存放循环队列中的元素,同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(EnQueue)和删除(DlQueue)元素的操作 若使用循环链表来表示队列，p是链表中的一个指针(视为队尾指针)。试基于此结构给出队列的插入(EnQueue)和删除(DlQueue)算法，并给出队列空的判断条件。上机：P102T3,
