数据结构(严蔚敏)课件第3章资料.ppt

《数据结构(严蔚敏)课件第3章资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列【课前思考】1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。它们遵循的是"后进先出"的规律，这正是本章要讨论的"栈"的结构特点。3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是"排队"。在计算机程序中，模拟排队的数据结构是"队列"。【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。　2.熟练掌握栈类型的两种实现方法

2、。　3.熟练掌握循环队列和链队列的基本操作实现算法。　4.理解递归算法执行过程中栈的状态变化过程。栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。【知识点】顺序栈、链栈、循环队列、链队列【重点和难点】【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，

3、3.17，3.19，3.22，3.27,3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈3.2栈的应用举例3.4队列目录3.3栈与递归的实现3.1栈一、栈的定义栈(stack)作为一种限定性线性表，是将线

4、性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。插入：最先放入栈中元素在栈底，最后放入的元素在栈顶；删除：最后放入的元素最先删除，最先放入的元素最后删除。栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。图3.1栈例：设一个栈的输入序列为A,B,C,D,则借助

5、一个栈所得到的输出序列不可能是。(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。二、栈的主要操作1.初始化栈：InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：POP(&S，&e)删除栈S中的栈顶元素，也称为”退栈”、

6、“删除”、“弹出”。4.取栈顶元素：GETTOP(S，&e)取栈S中栈顶元素。5.判栈空：EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。三、栈的抽象数据类型描述ADTStack{数据对象：D={ai

7、ai∈ElemSet，i=1,2,…,n,n≥0}数据关系：R1={

8、ai-1,ai∈D,i=1,2,…,n}基本操作：InitStack(&S)操作前提：S为未初始化的栈。操作结果：将S初始化为空栈。ClearStack(&S)操作前提：栈S已经存在。操作结果：将栈S置成空栈。StackEmp

9、ty(S)操作前提：栈S已经存在。操作结果：若栈S为空，则返回TRUE,否则FALSE。StackLength(S)操作前提：栈S已经存在。操作结果：返回S的元素个数即栈的长度。IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE，否则为FALSE。StackTraverse(S,visit())操作前提：栈S已经存在且非空。操作结果：从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败，则操作失效。Push(&S,e)操作前提：栈S已经存在。操作结果：在S的顶部

10、插入(亦称压入)元素e；若S栈未满，将e插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。Pop(&S,&e)