数据结构严蔚敏ppt课件第3章.ppt
《数据结构严蔚敏ppt课件第3章.ppt》由会员分享,可在线阅读,更多相关《数据结构严蔚敏ppt课件第3章.ppt(109页珍藏版)》请在三一办公上搜索。
1、第三章栈和队列,【课前思考】,简单地说,线性结构是一个数据元素的序列。,必然是依从上往下的次序,即n,2,1。它们遵循的是后进先出的规律,这正是本章要讨论的栈的结构特点。,是排队。在计算机程序中,模拟排队的数据结构是队列。,【学习目标】,1. 掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法。 4. 理解递归算法执行过程中栈的状态变化过程。,栈和队列是在程序设计中被广泛使用的两种线性数据结构,因此本章的学习重点在于掌握这两种结构的特点,以便能在应用问题中正确使用。,【知识点】,顺序
2、栈、链栈、循环队列、链队列,【重点和难点】,【学习指南】,在这一章中,主要是学习如何在求解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难,但应该对它们了如指掌,特别要注意它们的基本操作实现时的一些特殊情况,如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为:3.15,3.17,3.19,3.22, 3.27 ,3.28,3.30,3.31,3.32。其中前4个主要是练习栈的应用,后4个主要是有关队列的实现方法的练习。,通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列Insert(L, i, x) Insert(
3、S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3.1 栈,3.2 栈的应用举例,3.4 队列,目 录,3.3 栈与递归的实现,3.1 栈,一、栈的定义,栈(stack)作为一种限定性线性表,是将线性表的插入和删除运算限制为仅在表的一端进行。 通常将表中允许进行插入、删除操作的一端称为栈顶(Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端,被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入
4、操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。 插入:最先放入栈中元素在栈底,最后放入的元素在栈顶; 删除:最后放入的元素最先删除,最先放入的元素最后删除。 栈是一种后进先出(Last In First Out)的线性表,简称为LIFO表。,图3.1 栈,例:设一个栈的输入序列为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均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,
5、B,A。所以本题答案为D。,二、栈的主要操作,1.初始化栈:InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈:PUSH(&S,X)将元素X插入到栈S中,也称为 “入栈”、 “插入”、 “压入”。3.出栈: POP(&S,&e) 删除栈S中的栈顶元素,也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素: GETTOP(S,&e)取栈S中栈顶元素。5.判栈空: EMPTY(S)判断栈S是否为空,若为空,返回值为1,否则返回值为0。,三、栈的抽象数据类型描述,ADT Stack 数据对象: D=ai| ai ElemSet,i=1,2,n,n 0 数据关系: R1= | a
6、i-1 , ai D, i=1,2,n 基本操作: InitStack(&S) 操作前提: S为未初始化的栈。 操作结果: 将S初始化为空栈。 ClearStack(&S) 操作前提: 栈S已经存在。 操作结果: 将栈S置成空栈。 StackEmpty(S) 操作前提: 栈S已经存在。 操作结果: 若栈S为空,则返回TRUE,否则FALSE。,StackLength(S) 操作前提:栈S已经存在。 操作结果:返回S的元素个数即栈的长度。 IsFull(S) 操作前提: 栈S已经存在。 操作结果: 判栈满函数,若S栈已满,则函数值为TRUE, 否则为FALSE。 StackTraverse(S,
7、visit() 操作前提:栈S已经存在且非空。 操作结果:从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败,则操作失效。,Push(&S,e) 操作前提:栈S已经存在。 操作结果:在S的顶部插入(亦称压入)元素e;若S栈未满,将e插入栈顶位置,若栈已满,则返回FALSE,表示操作失败,否则返回TRUE。 Pop(&S,&e) 操作前提:栈S已经存在。 操作结果:删除(亦称弹出)栈S的顶部元素,并用e带回该值;若栈为空,返回值为FALSE,表示操作失败,否则返回TRUE。 GetTop(S, &e) 操作前提: 栈S已经存在。 操作结果:取栈S的顶部元素。与Pop(&
8、S, &e)不同之处在于GetTop(S,&e)不改变栈顶的位置。ADT Stack,1. 顺序栈 顺序栈是用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时由于栈的操作的特殊性, 还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top=0或 top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。 栈的顺序存储结构定义如下:,四、 栈的表示和实现,#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef
9、 struct SElemType *base; /在栈构造前和销毁后base值为NULL SElemType *top; /栈顶指针 int stacksize; SqStack; /当前已分配存储空间或简单定义如下: #define M 100 int sM; int top;,图3.2 顺序栈中的进栈和出栈,Top指向栈顶元素初态:top=-1; 空栈,栈中无元素,进栈:top=top+1; stop=x;退栈:取stop; top=top-1;栈满:top=M-1;栈溢出(上溢),不能再进栈(错误状态)top=-1时不能退栈,下溢(正常状态,常作控制条件),(1)构造空顺序栈算法:初始
10、化栈Status InitStack ( SqStack / InitStack,2.顺序栈基本操作的实现如下:,程序描述:/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; typedef struct /define structure SqStack() SElemType *base;
11、 SElemType *top; int stacksize; SqStack;,int InitStack(SqStack ,(2) 取顺序栈的栈顶元素 Status GetTop ( SqStack S, SElemType / GetTop,(3)将元素压入顺序栈算法(进栈)Status Push ( SqStack / Push,(4)将元素弹出顺序栈算法(退栈)Status Pop ( SqStack / Pop,(5) 判栈空否 Int Empty ( SqStack S) / 如果栈 S 空,返回 1 ;如果栈 S 不空,返回 0 。if ( S.top = = S.base )
12、 return 1; / 如果栈 S 为空,则返回 1else return 0; / 如果栈 S 为空,则返回 0 / Empty end,3栈的共享有时,一个程序设计中,需要使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补。,栈空:top1=0,top2=M-1;栈满:top1+1=top2,两个栈共享存储单元可用如下C语句描述:#define MAXSIZE 100 #define DUSTA
13、CKSIZE 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 100Struct duseqstack elemtype datamaxsize; int top2 ; /两个栈的栈顶指针 int flag; ,(1)两个栈共享存储单元的进栈算法Status DuSqS
14、tackPush ( DuSqStack / 如果 flag 不为 1,2,则返回 ERROR else / 如果 flag 为 1 或 2,则入栈 switch ( S.flag ) case 1 : / 标志位 flag 为 1,S.dataS.top1 = x; / 元素 x 入栈 S1 S.top1+; / 修改栈 S1 的栈顶指针 break; case 2 : / 标志位 flag 为 2 S.dataS.top2 = x; / 元素 x 入栈 S2 S.top2- -; / 修改栈 S2 的栈顶指针 break; / switch 结束 return OK; / else 结束
15、/ else 结束 / DuSqStackPush,(2)两个栈共享存储单元的退栈算法Status DuSqStackPop ( DuSqStack / 元素 x 出栈 / if 结束,else return ERROR; / 如果栈 S1 为空,则返回 ERROR break; case 2 : / 标志位 flag 为 1 if ( S.top2MAXSIZE-1 ) /若栈 S2 不空,对 S2 进行操作 S.top2+; / 修改栈 S2 的栈顶指针 x = S.dataS.top2; / 元素 x 出栈 / if 结束 else return ERROR; / 如果栈 S2 为空,则
16、返回 ERROR break; / switch结束 return OK; / else结束 / DuSqStackPop,4.链栈(1)链栈结构及数据类型栈的链式存贮结构,也称为链栈,它是一种限制运算的链表,即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图3-4。,typedef struct SNode /define structure LinkStack SElemType data; struct SNode *next; SNode,*LinkStack,(2)链栈的五种栈运算,(a)栈初始化void inistack(LinkStack top) top = ( Li
17、nkStack ) malloc ( sizeof ( SNode ) ); top-next=NULL;(b)进栈运算Status Push_L ( LinkStack / Push_L,(c)退栈运算Status Pop_L ( LinkStack / Pop_L,(d)取栈顶元素Status GetTop_L ( LinkStack top, SElemType / else 结束 / GetTop_L,(5)判栈空int empty(LinkStack *top) if(top-next=NULL) return(1); else return(0);,课 前 复 习,设n 个元素的进
18、栈序列是P1,P2,P3, Pn,其输出序列是1,2,3,n,若P1=3,则P2的值 ()。 A、可能是2B、一定是2C、不可能是1D、一定是1,一、 数制转换 假设要将十进制数N转换为d进制数,一个简单的转换算法是重复下述两步, 直到N等于零: X = N mod d (其中mod为求余运算)N = N div d (其中div为整除运算) 计算过程从低位到高位,打印输出从高位到低位,3.2 栈的应用举例 栈在日常生活中和计算机程序设计中有着许多应用,下面仅介绍栈在计算机中的应用。,void Conversion(int N)/*对于任意的一个非负十进制数N, 打印出与其等值的8进制数*/
19、Stack S; int x; /* S为顺序栈或链栈 */ InitStack( 算法3.1,二、括号匹配问题 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。 解:设置一个括号栈,扫描表达式:遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (in ,if (expi=) /*遇到,若栈顶是,
20、则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若栈顶是 ,则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; i+; /*表达式扫描完毕*/ if (top-1) tag=0; /*若栈不空,则不配对*/ return(tag); ,三、行编辑程序功能:接收用户从终端输入的数据或程序,并存入用户的数据区。算法思想:设输入缓冲区为一个栈结构,每当从终端接收一个字符后先作如下判别:若它既不是退格符(#)也不是退行符(),则将该字符入栈;若是退格符(#),则从栈顶删去一个字符
21、;若是退行符(),则将栈清空。算法描述如下:,void LineEdit()InitStack(s);ch=getchar();While(ch!=EOF) /EOF为全文结束符 while(ch!=EOF,五、 表达式求值,表达式求值是高级语言编译中的一个基本问题, 是栈的典型应用实例。 任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数, 也可以是被说明为变量或常量的标识符;运算符可以分为算术运算符、 关系运算符和逻辑运算符三类;基本界限符有左右括号和表达式结束符等。,1.无括号算术表达式求值,表达式计算 程序
22、设计语言中都有计算表达式的问题, 这是语言编译中的典型问题。 (1) 表达式形式: 由运算对象、 运算符及必要的表达式括号组成; (2) 表达式运算: 运算时要有一个正确的运算形式顺序。由于某些运算符可能具有比别的运算符更高的优先级,因此表达式不可能严格的从左到右, 见图3.5。,图3.5 表达式运算及运算符优先级,图3.6 无括号算术表达式的处理过程,2. 算术表达式处理规则 (1) 规定优先级表。 (2) 设置两个栈: OVS(运算数栈)和OPTR(运算符栈)。 (3) 自左向右扫描,遇操作数进OVS,遇操作符则与OPTR栈顶优先数比较:当前操作符OPTR栈顶, 当前操作符进OPTR栈;当
23、前操作符OPTR栈顶,OVS栈顶、次顶和OPTR栈顶,退栈形成运算T(i),T(i)进OVS栈。 例: 实现A/BC+D*E的运算过程时栈区变化情况如图3.7所示。,图3.7 A/BC+D*E运算过程的栈区变化情况示意图,+,*,3. 带括号算术表达式 假设操作数是整型常数,运算符只含加、减、乘、除等四种运算符, 界限符有左右括号和表达式起始、结束符“”,如: (7+15)*(23-28/4)。 引入表达式起始、 结束符是为了方便。 要对一个简单的算术表达式求值, 首先要了解算术四则运算的规则, 即: (1) 从左算到右;(2) 先乘除, 后加减;(3) 先括号内, 后括号外。,运算符和界限符
24、可统称为算符,它们构成的集合命名为OPTR。根据上述三条运算规则,在运算过程中,任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一: 12, 1的优先权高于2。,表 3-1 算符之间的优先关系,实现算符优先算法时需要使用两个工作栈: 一个称作optr, 用以存放运算符;另一个称作opnd,用以存放操作数或运算的中间结果。 算法的基本过程如下: 首先初始化操作数栈opnd和运算符栈optr, 并将表达式起始符“”压入运算符栈; 依次读入表达式中的每个字符,若是操作数则直接进入操作数栈opnd, 若是运算符,则与运算符栈optr的栈顶运算符进行优先权比较,并做如下处理: ,(1)
25、若栈顶运算符的优先级低于刚读入的运算符, 则让刚读入的运算符进optr栈; (2) 若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入,同时将操作数栈opnd退栈两次,得到两个操作数a、b,对a、 b进行运算后, 将运算结果作为中间结果推入opnd栈; (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符(左括号)退栈即可。,算法具体描述如下:,int ExpEvaluation()/*读入一个简单算术表达式并计算其值。 operator和operand分别为运算符栈和运算数栈, OPS为运算符集合*/ InitStack( while(c
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 严蔚敏 ppt 课件

链接地址:https://www.31ppt.com/p-1924687.html