资源描述：
《队列的特点及其表示实现ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、队列的特点及其表示实现教学目的：1.掌握队列的有关概念和特点。 2.熟练掌握循环队列的基本操作（队列初始化、入队列和出队列）实现算法，特别注意队满和队空的描述方法。*3.会在相应的应用问题中正确选用队列，注意理解操作受限的含义。重点难点：队列的操作特点。3.4队列*3.4.1抽象数据类型队列的定义*3.4.2链队列-队列的链式表示和实现3.4.3循环队列-队列的顺序表示和实现教学内容内容回顾栈的特点及其表示实现3.4队列线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q
2、,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n导入队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。概念：队尾rear：插入端，线性表的表尾。队头front：删除端，线性表的表头。3.4.1抽象数据类型队列的定义队列(Queue)图示操作特点：先进先出(FIFO：FirstInFirstout)a1a2a3an-1出队列入队列队头队尾……ADTQueue{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥
4、0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾基本操作：}ADTQueue队列的抽象数据类型定义队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())用链表表示的队列简称为链队列。一个链队列显然需要分别指示
6、队头和队尾的两个指针。为了方便操作，添加一个头结点，并令头指针指向头结点。…a2rearfronta1an∧3.4.2链队列-队列的链式表示和实现(a)非空队Q.frontQ.reara1an∧…a2(b)空队Q.front==Q.rearQ.rearQ.front∧(c)链队中只有一个元素结点Q.frontQ.reara1∧1.基本形态typedefstructQNode{//结点类型QElemTypedata;structQNode*next;}QNode,*QueuePtr;2.链队列——链式映象
7、typedefstruct{//链队列类型QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列StatusInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;returnO
8、K;}StatusEnQueue(LinkQueue&Q,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(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回E
9、RRORif(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;}3.4.3循环队列-队列的顺序表示和实现1、顺序存储：用一组地址连续的存储单元依次存放从队头到队尾的元素，另外还需附设两个指针front和rear分别指示队列头元
10、素和队列尾元素的位置。简单说，“数组+头、尾位置”为了在C语言中描述方便，约定：初始化建空队列时令：front=rear=0，每当插入新的队列尾元素时，rear+1，每当删除队列头元素时，front+1，因此，在非空队列中，头指针始终指向队头元素，尾指针始终指向队尾元素的下一个位置。例如：空队列J7J6J56543210Q.front=4Q.rear=7J1J2J3J4相继入队6543210Q.front=Q.rear=06543210Q.
