栈和队列 .ppt
《栈和队列 .ppt》由会员分享,可在线阅读,更多相关《栈和队列 .ppt(93页珍藏版)》请在三一文库上搜索。
1、第3章 栈和队列,主要内容,栈 栈的应用举例 栈与递归的实现 队列 离散事件模拟(选讲),重点与难点,本章的重点 掌握栈和队列的基本运算在两种存储结构下的实现 本章的难点 栈的应用算法、循环队列中对边界条件的处理,主要内容,从数据结构角度:操作受限的线性表限定性的数据结构,其基本操作是线性表操作的子集: 只能在线性表的表尾进行插入和删除先进后出 只能在线性表的表尾进行插入,在表头进行删除先进先出 从数据类型角度:与线性表不同的抽象数据类型(多型),3.1 栈,栈的定义 限定仅在表尾进行插入或删除操作的线性表,栈的表尾称为栈顶,表头称为栈底。不含元素的空表称为空栈。 栈称为后进先出的线性表(La
2、st In First Out,LIFO)。,3.1 栈,抽象数据类型栈的定义 ADT Stack 数据对象: D=ai| ai(-ElemSet,i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D,i=2,.,n 基本操作: InitStack(&S) 操作结果:构造一个空的栈S。 DestroyStack(&S) 初始条件:栈S已经存在。 操作结果:销毁栈S。,ClearStack(&S) 初始条件:栈S已经存在。 操作结果:将栈S重置为空栈。 StackEmpty(S) 初始条件:栈S已经存在。 操作结果:若S为空栈,则返回TRUE,否则返回FALSE。 Stack
3、Length(S) 初始条件:栈S已经存在。 操作结果:返回S的元素个数,即栈的长度。,3.1 栈,GetTop(S,&e) 初始条件:栈S已经存在。 操作结果:栈S存在且非空则返回S的栈顶元素。 Push(&S,e) 初始条件:栈S已经存在。 操作结果:插入元素e为新的栈顶元素入栈 Pop(&S,&e) 栈S存在 初始条件:栈S已经且非空。 操作结果:删除S的栈顶元素并用e返回其值出栈 StackTraverse(S,visit() 初始条件:栈S已经且非空。 操作结果:则从栈底到栈顶依次对S的每个数据元素调用函数visit(),一旦visit()失败,则操作失败 ADT Stack,3.1
4、 栈,3.2 栈的表示和实现,顺序栈 栈的常用存储结构(为什么?) 链栈,由于栈的插入和删除操作具有它的特殊性,所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量难以扩充的弱点仍就没有摆脱。,3.2 栈的表示和实现,顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。 栈所需最大空间很难估计,一般来说,在初始化设空栈时不应限定栈的最大容量。设定两个常量: 存储空间初始分配量MAX_STACK 存储空间分配增量STACKINCREMENT,3.2 栈的表示和实现,C语言中,顺序栈也可以采用 静态分配 type
5、def struct SElemType baseMAX_STACK; int top; /指示栈顶位置 SqStack; 动态分配 typedef struct SElemType *base; SElemType *top; / 设两指针便于判断栈是否为空 int StackSize; / 栈的当前可使用的最大容量. SqStack;,3.2 栈的表示和实现,C语言中,顺序栈也可以采用 静态分配 typedef struct SElemType baseSTACK_INIT_SIZE; int top; /指示栈顶位置 SqStack; 动态分配 typedef struct SElemT
6、ype *base; SElemType *top; / 设两指针便于判断栈是否为空 int StackSize; / 栈的当前可使用的最大容量. SqStack;,建议!,3.2 栈的表示和实现,顺序栈 InitStack( ,3.2 栈的表示和实现,顺序栈 Push( ,3.2 栈的表示和实现,顺序栈 Pop( ,3.2 栈的表示和实现,顺序栈 GetTop(S, ,3.2 栈的表示和实现,链栈 若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。 链栈通常用一个无头结点的单链表表示。 由于栈的插入删除操作只能在一端进行,而对于单链表来说,在首端插入删除结点要比
7、尾端相对地容易一些,所以,将单链表的首端作为栈顶端,即将单链表的头指针作为栈顶指针。,3.2 栈的表示和实现,链栈,3.2 栈的表示和实现,链栈的类型说明 动态分配 typedef struct stacknode SElemType data; struct stacknode *next; stacknode, *LinkStack;,3.3 栈的应用,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用字符逆置,将从键盘输入的字符序列逆置输出。 比如,从键盘上输入:tset a si sihT; 算法将输出:This is a test typed
8、ef char SElemType;,3.3 栈的应用字符逆置,void ReverseRead() InitStack( ,3.3 栈的应用,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用数制转换,十进制数值转换成二进制。 使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2,并保留其余数;重复此操作,直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。,3.3 栈的应用数制转换,数制转换 (692)10 = (1010110100)2,3.3 栈的应用数制转换,void Decimal _ Binary
9、( ) InitStack( ,3.3 栈的应用括号匹配的检验,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用括号匹配的检验,检验表达式中的括号匹配情况 假设在一个算术表达式中,可以包含三种括号: “(”和“)”、“”和“”、 “”和“”,并且这三种括号可以按任意的次序嵌套使用。 比如,.(.)。 现在需要设计一个算法,用来检验在输入的算术表达式中所使用括号的合法性。,3.3 栈的应用括号匹配的检验,算术表达式中各种括号的使用规则 出现左括号,必有相应的右括号与之匹配,并且每对括号之间可以嵌套,但不能出现交叉情况。可以利用一个栈结构保存每个出现的左
10、括号,当遇到右括号时,从栈中弹出左括号,检验匹配情况。,3.3 栈的应用括号匹配的检验,在检验过程中,若遇到以下几种情况之一,就可以得出括号不匹配的结论: 当遇到某一个右括号时,栈已空,说明到目前为止,右括号多于左括号; 从栈中弹出的左括号与当前检验的右括号类型不同,说明出现了括号交叉情况; 算术表达式输入完毕,但栈中还有没有匹配的左括号,说明左括号多于右括号。,3.3 栈的应用括号匹配的检验,int Check( ) InitStack(,3.3 栈的应用括号匹配的检验,case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop( ,3.3 栈
11、的应用,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用行编辑程序,一个简单的行编辑程序的功能 接受用户从终端输入的程序或数据,并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为退格符,以表示前一个字符无效,为退行符,表示当前行所有字符均无效。,3.3 栈的应用行编辑程序,示例 在终端上用户输入为: whli#ilr#e(s#*s) 应为: while(*s) 在终端上用户输入为: Outchaputchar(*s=#+) 应为: putchar(*s+),3.3 栈的应用行编辑程序,可以将输入缓冲区设为一个栈结构,每当从终端接受了一个字
12、符之后先作如下判别: 如是它既不是退格符也不是退行符,则将该字符压入栈顶; 如果是一个退格符,则从栈顶删去一个字符; 如果它是一个退行符,则将字符栈清空。,3.3 栈的应用行编辑程序,void LineEdit ( ) / 利用字符栈s,从终端接收一行并传送至调用过程的数据区 InitStack(S); / 构造空栈S ch = getchar ( ); / 从终端接收第一个字符 while(ch!=EOF) / EOF为全文结束符 while(ch!=EOFch!=n) switch(ch) case#:Pop (S,c); break; / 仅当栈非空时退栈 case:ClearStack
13、(S); break; / 重置S为空栈 default: Push (S,ch); break;/ 有效字符进栈,未考虑栈满情形 ch=getchar( ); / 从终端接收下一个字符 / 将从栈底到栈顶的栈内字符传送至调用过程的数据区 ClearStack(S); / 重置S为空栈 if (ch!=EOF) ch = getchar( ); DestoryStack(S); ,3.3 栈的应用,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用,表达式求值 无括号算术表达式求值 带括号算术表达式求值,3.3 栈的应用,表达式求值 无括号算术表达式求
14、值 带括号算术表达式求值,3.3 栈的应用带括号算术表达式求值,直接对带括号的算术表达式求值 可分解为二步求值(重点掌握) 第一步 将该算术表达式转化为后缀表达式 第二步 对后缀表达式求值,3.3 栈的应用带括号算术表达式求值,实现算符优先算法时需要使用两个工作栈:一个称作运算符栈operator;另一个称作操作数栈operand。 算法的基本过程如下: 初始化操作数栈operand和运算符栈operator,并将表达式起始符“#”压入运算符栈; 读入表达式中的每个字符,若是操作数则直接进入操作数栈operand,若是运算符,则与运算符栈operator的栈顶运算符进行优先权比较,并做如下处理
15、:,3.3 栈的应用带括号算术表达式求值,1 若栈顶运算符的优先级低于刚读入的运算符,则让刚读入的运算符进operator栈; 2 若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入,同时将操作数栈operand退栈两次,得到两个操作数a、b,对a、b进行运算后,将运算结果作为中间结果推入operand栈; 3 若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符(左括号)退栈即可。 当operator栈的栈顶元素和当前读入的字符均为“#”时,说明表达式起始符“#”与表达式结束符“#”相遇,整个表达式求值完毕。,3.3 栈的应用带括号算术表达式求值
16、,表3.1 算符间的优先关系,3.3 栈的应用带括号算术表达式求值,求3*(7-2)的值,3.3 栈的应用带括号算术表达式求值,char EvaluateExpression() SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack( else switch (Precede(GetTop(*OPTR),c),3.3 栈的应用带括号算术表达式求值, case : Pop(OPTR, ,3.3 栈的应用,字符逆置 数制转换 括号匹配的检验 行编辑程序 表达式求值 栈与递归的实现,3.3 栈的应用栈与递归的实现,递归的定义及分类 递归的应
17、用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用 递归设计,3.3 栈的应用栈与递归的实现,递归的定义及分类 递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用 递归设计,3.3 栈的应用栈与递归的实现,递归(recursive)的定义 若在一个函数、过程或者数据结构定义的内部,直接或间接出现定义本身的应用。 递归的分类 直接递归(direct recursive):函数F的代码中直接包含了调用F的语句; 间接递归(indircet recursive):间接递归是指函数F调用了函数G,G又调用了H,如此进行下去,直到F又被调用。,3.3 栈的应用栈与
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 栈和队列 队列
链接地址:https://www.31doc.com/p-4155526.html