数据结构与算法。第3章栈 和队 列3.ppt

《数据结构与算法。第3章栈 和队 列3.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2021年7月25日数据结构讲义1从上图所示的循环队可以看出：可见在队满和队空情况下都有：front==rear，这显然是必须要解决的一个问题。方法之一是：附设一个存储队中元素个数的变量如num，当num==0时队空，当num==MAXSIZE时为队满。另一种方法是：少用一个元素空间，把图(d)所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1)%MAXSIZE==front，也能和空队区别开。我们采用第一种方法。2021年7月25日数据结构讲义

2、2循环队列的类型定义如下：typedefstruct{datatypedata[MAXSIZE];/*数据的存储区*/intfront,rear;/*队头队尾指针*/intnum;/*队中元素的个数*/}CSeQueue;/*循环队*/2021年7月25日数据结构讲义3⑴置空队【算法3-14】构建一个空的循环队算法CSeQueue*Init_SeQueue(){CSeQueue*q;q=(CSeQueue*)malloc(sizeof(CSeQueue));q>front=q>rear=MAXSIZ

3、E-1;q>num=0;returnq;}2021年7月25日数据结构讲义4⑵入队【算法3-15】循环队入队算法intIn_SeQueue(CSeQueue*q,datatypex){if(q>num==MAXSIZE){printf("队满");return-1;/*队满不能入队*/}else{q->rear=(q>rear+1)%MAXSIZE;q>data[q>rear]=x;q>num++;return1;/*入队完成*/}}2021年7月25日数据结构讲义5⑶出队【算法3-16】循

4、环队出队算法intOut_SeQueue(CSeQueue*q,datatype*x){if(q>num==0){printf("队空")；return-1;/*队空不能出队*/}else{q>front=(q>front+1)%MAXSIZE;*x=q>data[q>front];/*读出队头元素*/q>num--;return1;/*出队完成*/}}2021年7月25日数据结构讲义6⑷判队空【算法3-17】判循环队空队算法intEmpty_SeQueue(CSeQueue*q){if(q

5、>num==0)return1;elsereturn0;}2021年7月25日数据结构讲义7⒉链队链式存储的队称为链队。和链栈类似，用单链表来实现链队，根据队的FIFO原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如图所示。图中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。2021年7月25日数据结构讲义8链队的描述如下：typedefstructnode{datatypedata;structnode*next;}QNode;/*链队结点

6、的类型*/typedefstruct{QNnode*front,*rear;}LQueue;/*将头尾指针封装在一起的链队*/定义一个指向链队的指针：LQueue*q;2021年7月25日数据结构讲义9带头结点的链队如图所示：2021年7月25日数据结构讲义10(1)创建一个带头结点的空队【算法3-18】置一个空链队算法LQueue*Init_LQueue(){LQueue*q;Qnode*p;q=(LQueue*)malloc(sizeof(LQueue));/*申请头尾指针结点*/p=(QNode*

7、)malloc(sizeof(QNode));/*申请链队头结点*/p>next=NULL;q>front=p;q>rear=p;returnq;}2021年7月25日数据结构讲义11(2)入队【算法3-19】链队入队算法voidIn_LQueue(LQueue*q,datatypex){QNode*p;p=(QNode*)malloc(sizeof(QNode));p>data=x;p>next=NULL;q>rear>next=p;q>rear=p;}2021年7月25日数据结构讲义

8、12(3)判队空【算法3-20】判链队空算法intEmpty_LQueue(LQueue*q){if(q>front==q>rear)return1;elsereturn0;}2021年7月25日数据结构讲义13(4)出队【算法3-21】链队出队算法intOut_LQueue(LQueue*q,datatype*x){QNode*p;if(Empty_LQueue(q)){printf("队空");return0;/*队空，出队失败*/