大赛精美PPT课件.ppt

《大赛精美PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、READY?NowLoading…院系:信息工程学院班级：信息管理与信息系统姓名：xxx数据结构ppt课件LOGO第一节队列队列是限定只能在表的一端插入元素，在表的另一端删除元素的线性数据结构。允许插入元素的一端称队尾（rear），允许删除元素的另一端称队头（front）。若队列中无元素，则称为空队列。若给定队列Q=(a0,a1,…,an－1)，则称a0是队头元素，an－1是队尾元素。若元素a0,…,an－1依次入队列，则元素出队列的次序与入队列一致，a0出队列后，a1才能出队列，见图3-4。由于队列的这种先进先出的特点，因此队列是先进先出（

2、FirstInFirstOut－FIFO）的线性数据结构。<1>.队列ADT<2>·队列的顺序表示图3—4队列示意图—————————————————————————a(1)a(2)a(3)........a(n-1)—————————————————————————Append(入队列)Serve（出队列）Front（队头）Rear（队尾）队列的基本运算包括构造一个空队列，判定一个队列是否为空队列，判定一个队列是否已满，在一个未满的队列中插入一个新元素，从一个非空的队列中删除队头元素等。当然我们还可以根据应用需要增加其它必要的队列运算，如求队列的长度，

3、清除一个队列，以及遍历一个队列等。队列的抽象数据类型定义见ADT3－2。ADT3－2Queue{数据：零个或多个元素的线性序列（a0,a1,...,an－1)，其最大允许长度为ＭaxQueue。运算：voidCreateQueue(Queue*q,intmaxsize);已构造一个空队列。BOOLIsEmpty（Queueq）若队列为空，则返回TRUE，否则返回FALSE。BOOLIsFull（Queueq）若队列已满，则返回TRUE，否则返回FALSE。voidAppend（Queue*q,Tx）若队列已满，则指示Overflow，否则值为x的新元素进

4、队列。voidServe（Queue*q）若队列为空，则指示Underflow，否则从队列中删除队头元素。voidQueueFront（Queueq,T*x）若队列为空，则指示Underflow，否则在参数x中返回队头元素值。}<1>.队列ADT<2>·队列的顺序表示与堆栈一样，队列可以采用顺序存储，也可以采用链接存储。当我们用一维数组存储队列时，被称为顺序队列（sequentialqueue），图3－5是队列的顺序表示示意图。队列的链接表示在下一小节讨论。队列的顺序实现可以用下面的C语言结构定义：typedefstructqueue{intFront，

5、Rear,MaxQueue;TElements[MaxSize];}Queue乐子吴吞制作队列运算需要两个指针，Front指向队头元素，Rear指向队尾元素。MaxQueue为队列的最大允许长度，它应不大于整型常量MaxSize。一维数组Elments用以存放队列中的元素，实现队列的顺序存储。初始状态下，我们将Front和Rear两个指针均置成－1，代表空队列，见图3－6（a）。图中，f和r分别代表Front和Rear。图3－6入队列和出队列运算的简单实现空队列；(b)元素20、30、40、50依次进队列；(c)元素20、30、40依次出队列；(d)元素

6、60入队列初始状态下，我们将Front和Rear两指针均置成0。为了循环使用数组，可以利用取余运算符%计算新元素的插入位置(即新队尾元素的位置)和删除队头元素后的新队头元素的位置。队头指针进一操作：Front=(Front+1)%MaxQueue；队尾指针进一操作：Rear=(Rear+1)%MaxQueue；我们看到，指针Front和Rear始终以顺时针方向移动。初始状态下，我们将Front和Rear两指针均置成0。为了循环使用数组，可以利用取余运算符%计算新元素的插入位置(即新队尾元素的位置)和删除队头元素后的新队头元素的位置。队头指针进一操作：Fr

7、ont=(Front+1)%MaxQueue；队尾指针进一操作：Rear=(Rear+1)%MaxQueue；我们看到，指针Front和Rear始终以顺时针方向移动。［程序3－3］循环队列实现voidCreateQueue(Queue*q,intmaxsize){q->Front=q->Rear=0;q->MaxQueue=maxsize;}BOOLIsEmpty(Queueq){returnq.Front==q.Rear;}BOOLIsFull(Queueq)return(q.Rear+1)%q.MaxQueue==q.Front;}voidAppen

8、d(Queue*q,Tx){if(IsFull(*q))printf("Over