数据结构课件第3章.ppt

3.4　队　列 3.4.1 抽象数据类型“队列”的定义 　　队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。在队列中可以插入的一端称为队尾(rear)，可以删除的一端称为队头或队首(front)。 　　将一个元素插到队列中的操作叫做入队列或进队，从队列中删除一个元素的操作叫做出队列或出队。队列是一种先进先出(First In First Out,FIFO)的线性表，或简称队列是一种FIFO结构。 ● 队列的定义 a1 a2 a3 ??? an 出队列 入队列 队头 队尾 图3.6　队列示意图 　　　　　　　 返回目录 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中元素个数 } 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列：用链表表示的队列。 　　链队列应包含两个指针：队头指针、队尾指针。 　　为了操作方便，给链队列附加一个头节点。 ^ ··· ^ q.front q.rear 队头指针q.front 队尾指针q.front 附加头结点 队头 队尾 空链队列： 图3.7　链队列示意图 3.4　队　列 3.4.2 链队列——队列的链式表示和实现 ● 链队列的表示 struct queuenode { elemtp data; queuenode *next; }; ^ ··· 队头指针q.front 队尾指针q.front 附加头结点 队头 队尾 图3.8　链队列示意图 struct linkedqueue { queuenode *front; queuenode *rear; }; 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 * 第3章　栈和队列 　　　　　　　 返回总目录 目　录 　3.1　栈 　3.2　栈的应用举例 　3.3　栈与递归的实现 　3.4　队列 ●基本要求： 　１）理解栈和队列的概念，存储表示，进栈、退栈和进队、出队操作的算法； 　２）对栈和队列的存储方式及基本操作有较深刻的理解； 　３）初步了解栈的基本应用。如表达式的求值、递归的设计实现等。 ●学习重点： 　１）栈和队列的基本操作； 　２）栈在实现递归中的应用；　 ●　两种重要的受限线性结构：栈和队列 　 　　从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集。它们是操作受限的线性表，即可称为限定性的数据结构。但从数据类型角度看，它们又是和线性表大不相同的两类重要的抽象数据类型。 　　　引　言 　　　引　言 ●　栈、队列和线性表三者的操作规则比较 　 　　　　　　　 返回目录 　　线性表：可以在表的任何位置上插入、删除元素。 　　栈：　　 对栈仅限定在表的一端（表尾）进行插入　　　　　　 或删除操作。可以在表的任何位置上插入、 　　　　　　 删除元素。 　　队列：　限定在表的一端进行插入，而在另一端删　　　　　　 除元素。 　　因此，从ADT的角度看，栈、队列和线性表是不相同的。 3.1　栈 3.1.1　 抽象数据类型”栈”的定义 　 ● 定义 ：栈是限定仅在表的一端进行插入或删除操作的线性表。 图3.1　栈