《数据结构(严蔚敏)第3章（课堂PPT）》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)第3章（课堂PPT）（109页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 栈和队列,2,【课前思考】,简单地说，线性结构是一个数据元素的序列。,必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。,是排队。在计算机程序中，模拟排队的数据结构是队列。,3,【学习目标】,1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法。 4. 理解递归算法执行过程中栈的状态变化过程。,4,栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。
2、,【知识点】,顺序栈、链栈、循环队列、链队列,【重点和难点】,5,【学习指南】,在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。,6,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L,
3、 i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,7,3.1 栈,3.2 栈的应用举例,3.4 队列,目 录,3.3 栈与递归的实现,8,3.1 栈,一、栈的定义,栈(stack)作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。 通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底(Bottom)
4、。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 插入：最先放入栈中元素在栈底，最后放入的元素在栈顶； 删除：最后放入的元素最先删除，最先放入的元素最后删除。 栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。,9,图3.1 栈,10,例：设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。 (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均在栈中,按照入栈顺序,在栈中
5、顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,11,二、栈的主要操作,1.初始化栈：InitStack( /在栈构造前和销毁后base值为NULL SElemType *top; /栈顶指针 int stacksize; SqStack; /当前已分配存储空间 或简单定义如下： #define M 100 int sM; int top;,17,图3.2 顺序栈中的进栈和出栈,Top指向栈顶元素 初态：top=-1; 空栈，栈中无元素， 进栈：top=top+1; stop=x; 退栈：取stop; top=top-1; 栈满：top=M-1;栈溢出（上溢），不能
6、再进栈（错误状态） top=-1时不能退栈，下溢（正常状态，常作控制条件）,18,（1）构造空顺序栈算法:初始化栈 Status InitStack ( SqStack / InitStack,2.顺序栈基本操作的实现如下:,19,程序描述： /This program is to initialize a stack # include # include # include # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType;
7、 typedef struct /define structure SqStack() SElemType *base; SElemType *top; int stacksize; SqStack;,20,int InitStack(SqStack ,21,（2） 取顺序栈的栈顶元素 Status GetTop ( SqStack S, SElemType / GetTop,22,（3）将元素压入顺序栈算法（进栈） Status Push ( SqStack / Push,23,（4）将元素弹出顺序栈算法（退栈） Status Pop ( SqStack / Pop,24,（5） 判栈空否
8、Int Empty ( SqStack S) / 如果栈 S 空，返回 1 ；如果栈 S 不空，返回 0 。 if ( S.top = = S.base ) return 1; / 如果栈 S 为空，则返回 1 else return 0; / 如果栈 S 为空，则返回 0 / Empty end,25,3栈的共享 有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。,栈空：
9、top1=0,top2=M-1; 栈满：top1+1=top2,26,两个栈共享存储单元可用如下C语句描述： #define MAXSIZE 100 #define DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE; int top1; /top1 is the pointer of DuSqStack S1 int top2; /top2 is the pointer of DuSqStack S2 int flag;DuSqStack; / 或： #define MAXSIZE 100 Struct dus
10、eqstack elemtype datamaxsize; int top2 ; /两个栈的栈顶指针 int flag; ,27,（1）两个栈共享存储单元的进栈算法 Status DuSqStackPush ( DuSqStack / 如果 flag 不为 1,2，则返回 ERROR else / 如果 flag 为 1 或 2，则入栈 switch ( S.flag ) case 1 : / 标志位 flag 为 1,28,S.dataS.top1 = x; / 元素 x 入栈 S1 S.top1+; / 修改栈 S1 的栈顶指针 break; case 2 : / 标志位 flag 为 2
11、 S.dataS.top2 = x; / 元素 x 入栈 S2 S.top2- -; / 修改栈 S2 的栈顶指针 break; / switch 结束 return OK; / else 结束 / else 结束 / DuSqStackPush,29,（2）两个栈共享存储单元的退栈算法 Status DuSqStackPop ( DuSqStack / 元素 x 出栈 / if 结束,30,else return ERROR; / 如果栈 S1 为空，则返回 ERROR break; case 2 : / 标志位 flag 为 1 if ( S.top2MAXSIZE-1 ) /若栈 S2
12、不空，对 S2 进行操作 S.top2+; / 修改栈 S2 的栈顶指针 x = S.dataS.top2; / 元素 x 出栈 / if 结束 else return ERROR; / 如果栈 S2 为空，则返回 ERROR break; / switch结束 return OK; / else结束 / DuSqStackPop,31,4.链栈 （1）链栈结构及数据类型 栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图3-4。,typedef struct SNode /define structure LinkStack S
13、ElemType data; struct SNode *next; SNode,*LinkStack,32,（2）链栈的五种栈运算,（a）栈初始化 void inistack(LinkStack top) top = ( LinkStack ) malloc ( sizeof ( SNode ) ); top-next=NULL; （b）进栈运算 Status Push_L ( LinkStack / Push_L,33,（c）退栈运算 Status Pop_L ( LinkStack / Pop_L,34,（d）取栈顶元素 Status GetTop_L ( LinkStack top,
14、SElemType / else 结束 / GetTop_L,35,（5）判栈空 int empty(LinkStack *top) if(top-next=NULL) return(1); else return(0); ,36,课 前 复 习,设n 个元素的进栈序列是P1，P2，P3， Pn，其输出序列是1,2，3，n，若P1=3，则P2的值 ()。 A、可能是2B、一定是2 C、不可能是1D、一定是1,37,一、 数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步， 直到N等于零： X = N mod d (其中mod为求余运算) N = N div d (其中
15、div为整除运算) 计算过程从低位到高位，打印输出从高位到低位,3.2 栈的应用举例 栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。,38,void Conversion(int N) /*对于任意的一个非负十进制数N， 打印出与其等值的8进制数*/ Stack S; int x; /* S为顺序栈或链栈 */ InitStack( 算法3.1,39,二、括号匹配问题 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。 解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,40,int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (in ,41,if (expi=) /*遇到,若栈顶是, 则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若栈顶是 ,则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; i+
