数据结构课件第3章节.pptVIP

3.4　队　列 3.4.1 抽象数据类型“队列”的定义 　　队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。在队列中可以插入的一端称为队尾(rear)，可以删除的一端称为队头或队首(front)。 　　将一个元素插到队列中的操作叫做入队列或进队，从队列中删除一个元素的操作叫做出队列或出队。队列是一种先进先出(First In First Out,FIFO)的线性表，或简称队列是一种FIFO结构。 ● 队列的定义 a1 a2 a3 ??? an 出队列 入队列 队头 队尾 图3.6　队列示意图 　　　　　　　 返回目录 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.4　队　列 3.4.1 抽象数据类型“队列”的定义 ● 队列的ADT定义 ADT Queue{ 数据对象：D={ai|ai∈ElemSet，i=1,2,…,n, n=1} 数据关系：R={ai,ai+1|ai,ai+1 ∈D, i=1,2,…,n} 基本操作： InitQueue( Q )；初始化构造一个空队列Q DestroyQueue( Q ); 释放队列Q ClearQueue( Q ) ；将Q清为空队列 EnQueue( Q, x )；入队列操作 DeQueue( Q, e )；出队列操作 GetTop( S, e ) ；取栈顶元素函数 QueueEmpty ( S )；判断栈是否为空 　　QueueLength( Q ); 求当前队列Q中元素个数 } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列：用链表表示的队列。 　　链队列应包含两个指针：队头指针、队尾指针。 　　为了操作方便，给链队列附加一个头节点。 ^ ··· ^ q.front q.rear 队头指针q.front 队尾指针q.front 附加头结点 队头 队尾 空链队列： 图3.7　链队列示意图 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列的表示 struct queuenode { elemtp data; queuenode *next; }; ^ ··· 队头指针q.front 队尾指针q.front 附加头结点 队头 队尾 图3.8　链队列示意图 struct linkedqueue { queuenode *front; queuenode *rear; }; Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列的实现 init_linkedque(linkedqueue q ) {　//构造一个空链队列 q.front = new( queuenode ); //建链队列结点 q.rear = q.front; q.front-next = NULL; } //init_linkedque 图3.9　链队列初始化 q.front ^ q.rear Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列的实现 en_linkedque(linkedqueue q, elemtp x ) {　//插入元素X为Q的新的队尾元素 queueptr p;