《数据结构(严蔚敏)第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+