《数据结构》课件第三章.ppt

3.4队列队列是只允许在一端进行插入，在另一端进行删除。an…ai+1…a2a1队头队尾出队列（删除）入队列（插入）先进先出队列的存储方式队列的存储方式有两种：用链表示的队列称为链队列。一个链队列需要两个分别指示队头和队尾的指针才能惟一确定。空的链队列的判决条件为头指针和尾指针均指向头结点单链队列的插入和删除的操作只需修改尾指针或头指针。另一种存储方式为顺序存储∧Q.frontQ.rear队头头结点队尾∧Q.frontQ.rear空队列链队列空：Q-front=Q-rearQ.frontQ.rearxy∧删除x（P62）Q.frontQ.rearxy∧插入x(P62)Q.forntQ.rearx∧∧Q.frontQ.rearStatusEnQueue(LinkQueueQ，QElemTypee){//插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode))；//为结点分配空间if(!p)exit(OVERFLOW)；p-data=e；p-next=NULL；Q.rear-next=p；Q.rear=p；returnOK；}进队列StatusDeQueue(LinkQueueQ，QElemTypee){//若队列不空，则删除Q的队头元素，用e返回其值,并返回OK,//否则返回ERROR；if(Q.front==Q.rear)returnERROR；p=Q.front-next；//指向头结点之后的结点e=p-data；Q.front-next=p-next；if(Q.rear==p)Q.rear=Q.front；free(p)；returnOK；}出队列543210Q.rearQ.front543210J1J2J3Q.rearQ.front543210J3Q.frontQ.rear543210J5J6Q.frontQ.rear01 … …其他种类的队列结构循环队列队列元素用数组存储；Q.rear和Q.front均设为整数。根据“队尾进，队头出”的原则，Q.rear走得始终比Q.front快。01 … …Maxsize-1Q.frontQ.rearQ.rearQ.front0J5 …1J6Maxsize-1循环队列为空：Q.rear=Q.front循环队列满：Q.front=(Q.rear+1)%maxsize1Maxsize-10J3 …J1J2Q.rearQ.front0J3 …Q.rear1Q.frontMaxsize-1StatusEnQueue(SqQueueQ，QElemTypee){//插入元素e为Q的新的队尾元素if((Q.rear+1)％MAXQSIZE==Q.front)returnERROR；//队列满Q.base[Q.rear]=e；Q.rear=(Q.rear+1)％MAXQSIZE；returnOK；}StatusDeQueue(SqQueueQ，QElemTypee){//若队列不空，则删除队头元素，用e返回其值，并返回OKif(Q.Front==Q.rear)returnERROR；//否则返回ERRORe=Q.base[Q.front]；Q.front=(Q.front+1)％MAXQSIZE；returnOK；}队列的应用——图形填充问题123410-10010-1dxdy1234u=i+dx(k)v=j+dy(k)种子填充法图形信息AA是一个二维整型数组，标识出哪些点需要填充。同时它也反映了图形的边界。上机操作试写一个算法判断给定字符序列是否为回文（回文就是正读、反读均相同的字