《【精品数据结构】栈和队列4.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】栈和队列4.ppt（93页珍藏版）》请在金锄头文库上搜索。
1、第3章栈和队列 3 1栈 3 2队列 本章小结 3 1 1栈的定义 3 1 2栈的顺序存储结构及其基本运算实现 3 1 3栈的链式存储结构及其基本运算的实现 3 1 4栈的应用例子 3 1栈 栈是一种只能在一端进行插入或删除操作的线性表 表中允许进行插入 删除操作的一端称为栈顶 栈顶的当前位置是动态的 栈顶的当前位置由一个称为栈顶指针的位置指示器指示 表的另一端称为栈底 当栈中没有数据元素时 称为空栈 栈的插入操作通常称为进栈或入栈 栈的删除操作通常称为退栈或出栈 3 1 1栈的定义 栈的几种基本运算如下 1 初始化栈InitStack s 构造一个空栈s 2 销毁栈ClearStack s
2、释放栈s占用的存储空间 3 求栈的长度StackLength s 返回栈s中的元素个数 4 判断栈是否为空StackEmpty s 若栈s为空 则返回真 否则返回假 5 进栈Push S e 将元素e插入到栈s中作为栈顶元素 6 出栈Pop s e 从栈s中退出栈顶元素 并将其值赋给e 7 取栈顶元素GetTop s e 返回当前的栈顶元素 并将其值赋给e 8 显示栈中元素DispStack s 从栈顶到栈底顺序显示栈中所有元素 3 1 2栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数MaxSize 所有的元素都具有同一数据类型ElemType 则可用下列方式来定义栈类型Sq
3、Stack typedefstruct ElemTypeelem MaxSize inttop 栈指针 SqStack 例3 1设有4个元素a b c d进栈 给出它们所有可能的出栈次序 答 所有可能的出栈次序如下 abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba 例3 2设一个栈的输入序列为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均在栈中 按照入栈顺序
4、 在栈中顺序应为D C B A 出栈的顺序只能是D C B A 所以本题答案为D 例3 3已知一个栈的进栈序列是1 2 3 n 其输出序列是p1 p2 pn 若p1 n 则pi的值 A i B n i C n i 1 D 不确定答 当p1 n时 输出序列必是n n 1 3 2 1 则 p2 n 1 p3 n 2 pn 1 推断出pi n i 1 所以本题答案为C 例3 4设n个元素进栈序列是1 2 3 n 其输出序列是p1 p2 pn 若p1 3 则p2的值 A 一定是2 B 一定是1 C 不可能是1 D 以上都不对答 当p1 3时 说明1 2 3先进栈 立即出栈3 然后可能出栈 即为2 也可
5、能4或后面的元素进栈 再出栈 因此 p2可能是2 也可能是4 n 但一定不能是1 所以本题答案为C 在顺序栈中实现栈的基本运算算法 1 初始化栈initStack 2 销毁栈ClearStack 3 求栈的长度StackLength s 返回栈s中的元素个数 即栈指针加1的结果 对应算法如下 intStackLength SqStack s return s top 1 4 判断栈是否为空StackEmpty s 栈S为空的条件是s top 1 对应算法如下 intStackEmpty SqStack s return s top 1 5 进栈Push 6 出栈Pop 7 取栈顶元素GetTo
6、p s 在栈不为空的条件下 将栈顶元素赋给e 对应算法如下 intGetTop SqStack s ElemType 8 显示栈中元素DispStack s 从栈顶到栈底顺序显示栈中所有元素 对应算法如下 voidDispStack SqStack s inti for i s top i 0 i printf c s elem i printf n 3 1 3栈的链式存储结构及其基本运算的实现采用链式存储的栈称为链栈 这里采用单链表实现 链栈的优点是不存在栈满上溢的情况 我们规定栈的所有操作都是在单链表的表头进行的 下图是头结点为 lhead的链栈 第一个数据结点是栈顶结点 最后一个结点是栈
7、底结点 栈中元素自栈顶到栈底依次是a1 a2 an 链栈示意图 链栈中数据结点的类型LiStack定义如下 typedefstructlinknode ElemTypedata 数据域 structlinknode next 指针域 LiStack 在链栈中 栈的基本运算算法如下 1 初始化栈initStack 2 销毁栈ClearStack 3 求栈的长度StackLength s 从第一个数据结点开始扫描单链表 用i记录访问的数据结点个数 最后返回i值 对应算法如下 intStackLength LiStack s inti 0 LiStack p p s next while p NUL
8、L i p p next return i 4 判断栈是否为空StackEmpty s 栈S为空的条件是s next NULL 即单链表中没有数据结点 对应算法如下 intStackEmpty LiStack s return s next NULL 5 进栈Push 6 出栈Pop 7 取栈顶元素GetTop s 在栈不为空的条件下 将头结点后继数据结点的数据域赋给e 对应算法如下 intGetTop LiStack s ElemType 8 显示栈中元素DispStack s 从第一个数据结点开始扫描单链表 并输出当前访问结点的数据域值 对应算法如下 voidDispStack LiSta
9、ck s LiStack p s next while p NULL printf c p data p p next printf n 例3 5假设表达式中允许包含三种括号 圆括号 方括号和大括号 编写一个算法判断表达式中的括号是否正确配对 3 1 4栈的应用例子 解 对应的算法如下 intcorrect charexp intn charst MaxSize inttop 1 i 0 tag 1 while i n if exp i 遇到 若栈顶是 则继续处理 否则以不配对返回 if st top top elsetag 0 if exp i 遇到 若栈顶是 则继续处理 否则以不配对返回
10、if st top top elsetag 0 if exp i 遇到 若栈顶是 则继续处理 否则以不配对返回 if st top top elsetag 0 i if top 1 tag 0 若栈不空 则不配对 return tag 1 表达式求值这里限定的表达式求值问题是 用户输入一个包含 正整数和圆括号的合法数学表达式 计算该表达式的运算结果 在程序语言中 运算符位于两个操作数中间的表达式称为中缀表达式 例如 1 2 3就是一个中缀表达式 中缀表达式是最常用的一种表达式方式 对中缀表达式的运算一般遵循 先乘除 后加减 从左到右计算 先括号内 后括号外 的规则 因此 中缀表达式不仅要依赖运
11、算符优先级 而且还要处理括号 所谓后缀表达式 就是运算符在操作数的后面 如1 2 3的后缀表达式为123 在后缀表达式中已考虑了运算符的优先级 没有括号 只有操作数和运算符 对后缀表达式求值过程是 从左到右读入后缀表达式 若读入的是一个操作数 就将它入数值栈 若读入的是一个运算符op 就从数值栈中连续出栈两个元素 两个操作数 假设为x和y 计算xopy之值 并将计算结果入数值栈 对整个后缀表达式读入结束时 栈顶元素就是计算结果 算术表达式求值过程是 先将算术表达式转换成后缀表达式 然后对该后缀表达式求值 假设算术表达式中的符号以字符形式由键盘输入 并存放在字符型数组str中 其后缀表达式存放在
12、字符型数组exp中 在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈 将算术表达式转换成后缀表示的方法如下 依次从键盘输入表达式中的字符ch 对于每一个ch 1 若ch为数字 将后续的所有数字均依次存入数组exp中 并以字符 标志数值串结束 2 若ch为左括弧 则将此括弧入栈op 3 若ch为右括弧 则将栈op中左括弧 以前的字符依次删除并存入数组exp中 然后将左括弧 删除 4 若ch为 或 则将当前栈op中 以前的所有字符 运算符 依次删除并存入数组exp中 然后将ch入栈op中 5 若ch为 或 则将当前栈op中的栈顶端连续的 或 删除并依次存入数组exp中 然后将ch入
13、栈op中 6 若字符串str扫描完毕 则将栈op中的所有运算符依次删除并存入数组exp中 然后再将ch存入数组exp中 最后可得到表达式的后缀表示在数组exp中 根据上述原理得到的trans 算法如下 voidtrans charstr charexp 将算术表达式str转换成后缀表达式exp struct chardata MaxSize 存放运算符 inttop 栈指针 op 定义运算符栈 charch inti 0 t 0 t作为exp的下标 i作为str的下标 op top 1 ch str i i while ch 0 str表达式未扫描完时循环 switch ch case 判定为
14、左括号 op top op data op top ch break case 判定为右括号 while op data op top exp t op data op top op top t op top break case case 判定为加或减号 while op top 1 case case 判定为 或 号 while op data op top op data op top exp t op data op top op top t op top op data op top ch break case break 过滤掉空格 default while ch 0 while
15、 op top 1 此时str扫描完毕 栈不空时循环 exp t op data op top t op top exp t 0 给exp表达式添加结束标识 下面对后缀表达式求值 在后缀表达式求值算法中要用到一个数值栈st 该算法实现过程如下 后缀表达式存放在字符型数组exp中 从头开始依次扫描这个后缀表达式 当遇到运算数时 就把它插入到数值栈st中 当遇到运算符时 就执行两次退栈 并根据该运算符对退栈的数值进行相应的运算 再把结果入栈st 重复上述过程 直至后缀表达式exp扫描完毕 此时数值栈st中栈顶的数值即为表达式的值 floatcompvalue charexp 计算后缀表达式的值 s
16、truct floatdata MaxSize 存放数值 inttop 栈指针 st 定义数值栈 floatd charch intt 0 t作为exp的下标 st top 1 ch exp t t while ch 0 exp字符串未扫描完时循环 switch ch case st data st top 1 st data st top 1 st data st top st top break case st data st top 1 st data st top 1 st data st top st top break case st data st top 1 st data st top 1 st data st top st top break case if st data st top 0 st data st top 1 st data st top 1 st data st top else printf n t除零错误 n exit 0 异常退出 st top break default d 0 将数字字符转换成数值存放到d中 while ch 0 2 求解
