《队列和数组》PPT课件

《《队列和数组》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2队列3.2.1队列的定义队列是只能在一端插入、另一端删除的线性表。a1a2a3……an出队入队队头（删除元素）队尾（插入元素）队列的特性：先进先出FIFO13.2.2队列的基本运算初始化队列：init_queue(Q)判断队列是否为空：queue_empty(Q)取队头元素：queue_front(Q,x)入队：enqueue(Q,x)出队：outqueue(Q,x)判断队列是否为满：queue_full(Q)23.2.3顺序队列以顺序存储方式存储的队列叫做顺序队列。ana1a2.…..0123maxsize-1dataf

2、rontQrear类型说明：typedefstruct{elementtypedata［maxsize］;//存放元素的数组intfront,rear;//指向队头的前一个位置和队尾}seqqueue；3顺序队列会产生“假溢出”循环队列frontrear210maxsize-1基本操作：入队：rear=(rear+1)%maxsize;data［rear］=x;出队：front=(front+1)%maxsize;4难题：如何区分循环队列的满和空状态？方法一：设置一个标志，以区分最后一次操作是入队还是出队操作。当头尾两个指针相等

3、时，由该标志判断队列为满或空。方法二：保留一个空间不用，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。5循环队列运算的实现初始化队列：voidinit_queue(seqqueue*Q){Q->front=0;Q->rear=0;}判断队列是否为空：BOOLqueue_empty(seqqueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}判断队列是否为满：BOOLqueue_full(seqqueueQ){if((1+Q.rear)%ma

4、xsize==Q.front)returnTRUE;elsereturnFALSE;}尾指针的下一个位置是头指针所指位置时为满头尾指针相同，则肯定为空6入队voidEnqueue(seqqueue*Q,elementtypex){if(queue_full(Q))error(“溢出”);else{Q->rear=(1+Q->rear)%maxsize;Q->data［Q->rear］=x；}}取队头元素：elementtypequeue_front(seqqueueQ,elementtype*x){if(queue_empty

5、(Q))error(“队空”);else*x=Q.data［(Q.front+1)%maxsize］);}队头元素在front指针所指位置的下一个位置往后移动尾指针填进待插入的元素出队voidOutqueue(seqqueue*Q,elementtype*x){if(queue_empty(*Q))error(“队空，不能出队”);else{Q->front=(Q->front+1)%maxsize;*x=Q->data［Q->front］;}}73.2.4链队列a1a2anfrontrearlinkqueue类型说明typed

6、efstruct{node*front,*rear；//仅需要头尾指针即可}linkqueue；8头结点之后的结点中的值为队头元素链队列运算的实现初始化队列：voidinit_queue(linkqueue*Q){Q->front=(node*)malloc(sizeof(node));Q->rear=Q->front;Q->front->next=NULL;}产生由头指针指示的头结点尾指针也指向该头结点尾结点的后继指针设置为空取队头元素：voidqueue_front(linkqueue*Q,elementtype*x);{i

7、f(empty(*Q))error(“队空，不能取元素”);else*x=Q->front->next->data;}判断队为空：BOOLqueue_empty(linkqueueQ){returnQ.front==Q.rear;}队头元素的值由x返回首尾指针相等9入队：voidEnqueue(linkqueue*Q,elementtypex){node*P=(node*)malloc(sizeof(node));P->data=x;P->next=NULL;Q->rear->next=P;Q->rear=P;}出队：voidO

8、utqueue(linkqueue*Q,elementtype*x);{if(empty(*Q))error(“队空，不能出队”);else{*x=Q->front->next->data;node*u=Q->front->next;Q->front->next