chap3 栈和队列

第三章栈和队列 栈和队列是两种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 3 1栈3 1 1栈的定义栈 限定只能在表的一端进行插入和删除的特殊的线性表设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 3 1栈3 1 1栈的定义栈 限定只能在表的一端进行插入和删除的特殊的线性表设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 栈顶 top 允许插入和删除的一端 约定top始终指向新数据元素将存放的位置 栈底 bottom 不允许插入和删除的一端 栈的习题 入栈出栈的次序判断栈的特性 3 1 2栈的存储结构顺序栈 链栈 顺序栈 用顺序存储结构表示的栈 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素 一般用一维数组表示 设置一个简单变量top指示栈顶位置 称为栈顶指针 它始终指向待插入元素的位置 栈中的运算 1 设置空栈 2 插入一个新的栈顶元素3 删除栈顶元素 4 读取栈顶元素 设数组S是一个顺序栈 栈的最大容量stacksize 4 初始状态top 0 栈空 10进栈 30出栈 栈满 进栈算法 definestatcksize100intpush ints intx int ptop inttop top ptop if top stacksize printf overflow return 0 else s top x ptop top 实际栈顶指针加1 return 1 通过地址传递 用ptop带回实际栈顶指针 a2 a3 a4 9 8 7 6 5 4 3 2 1 a1 0 top 出栈算法 intpop ints int ptop int py inttop top ptop if top 0 printf stackempty return 0 else top py s top 返回出栈元素 ptop top return 1 通过地址传递 用ptop带回实际栈顶指针 通过指针变量py带回出栈元素 栈s top 栈底 2 链栈用指针来实现的栈叫链栈 栈的容量事先不能估计时采用这种存储结构 链栈的类型说明如下 Typedefstructlnode intdata structlnode next lnode Lstack 进栈算法intlpush Lstacks inte p Lstack malloc sizeof lnode p data e p next s s p return 1 base S 栈s 进栈元素e 进栈算法intlpush Lstacks inte p Lstack malloc sizeof lnode p data e p next s s p return 1 base S 进栈算法intlpush Lstacks inte p Lstack malloc sizeof lnode p data e p next s s p return 1 base S e 进栈算法intlpush Lstacks inte p Lstack malloc sizeof lnode p data e p next s s p return 1 base S e 进栈算法intlpush Lstacks inte p Lstack malloc sizeof lnode p data e p next s s p return 1 base S e r 主程序 3 1 3栈的应用 1 过程的嵌套 2 递归算法 1 n 0 1 n n n 1 n 1 函数的递归调用 1 定义 在调用一个函数的过程中直接或间接地调用该函数本身 直接调用intf x intx inty z z f x return 2 z f函数 调用f函数 intf1 x intx inty z z f2 y return 2 z intf2 t intt inta c c f1 a return 3 c 间接调用 特点是无终止的递归调用 因此 应该给定一个限制递归次数的条件 floatfac intn floatf if n 0 printf n 0 dataerror n elseif n 0 n 1 f 1 elsef fac n 1 n returnf 例如 写一函数求n 以求4的阶乘为例 fac 4 4 fac 3 fac 3 3 fac 2 fac 2 2 fac 1 fac 1 1 fac 4 4 3 2 1 fac 2 2 1 fac 3 3 2 1 下推 回代 利用栈实现递归调用 递归的执行情况分析 longFact intn longs if n 1 s 1 elses n Fact n 1 return s 运算符 界限符 以表达式A B C D为例说明利用栈的求值过程 优先级 43322110 3 表达式的计算 操作数变量 ABCD A B C D top2 思想 从左到右扫描表达式 若当前读入的是操作数 则进操作数 NS 栈 若读入的符号是运算符 应进行判断 若是 进运算符栈 若是 当运算符栈顶是 则弹出栈顶元素 继续扫描下一符号 否则当前读入符号暂不处理 从操作数栈弹出两个操作数 从运算符栈弹出一个运算符 生成运算指令 结果送入操作数栈 继续处理当前读入符号 2 若读入的运算符的优先级大于运算符栈顶的优先级 则进运算符栈 继续扫描下一符号 否则从操作数栈顶弹出两个操作数 从运算符栈弹出一个运算符 生成运算指令 把结果送入操作数栈 继续处理刚才读入的符号 3 若读入的是 且运算符栈顶的符号也是 时 则表达式处理结束 从操作数栈弹出表达式结果 输入 表达式符号序列 表达式求值算法 输出 表达式值y 初始化栈NS OS Push OS top2 t 0 表示扫描下一个符号while t2 IFt 0THENreadW IFW为操作数THENPush NS W top1 ELSE p OS top2 读运算符栈栈顶元素 存入p IF W p or W THEN Push OS W top2 t 0 ELSEIF p and W THEN Pop NS y top1 t 2 处理过程结束 ELSEIF p and w THEN ELSE Pop NS x top1 Pop NS z top1 Pop OS p top2 x zx Push NS x top1 t 1 t 1 当前的符号下次重新考虑 输出y return Pop OS p top2 t 0 4 地图四染色问题 四染色 定理是计算机科学中著名的定理之一 使地图中相邻的国家或行政区域不重色 最少可用四种颜色对地图着色 证明此定理的结论 利用栈采用回溯法对地图着色 思想 对每个行政区编号 1 7对颜色编号 a b c d 从第一号行政区开始逐一染色 每一个区域逐次用四种颜色进行试探 若所取颜色与周围不重 则用栈记下来该区域的色数 否则依次用下一色数进行试探 若出现a d均与周围发生重色 则需退栈回溯 修改当前栈顶的色数 1234567 1234567 1 2 4 5 6 7 3 1 粉色2 黄色3 红色4 绿色 1234567 S 1 7 Voidmapcolor intR intn ints s 1 1 1号区域染1色I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 Voidmapcolor intR intn ints s 1 1 1号区域染1色I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 2 J 1 k 1 Voidmapcolor intR intn ints s 1 1 1号区域染1色I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 2 J 2 k 1 Voidmapcolor intR intn ints s 1 1 1号区域染1色I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 2 J 2 k 2 Voidmapcolor intR intn ints s 1 1 1号区域染1色I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 3 J 1 k 2 2 Voidmapcolor intR intn ints I 2 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 1 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 2 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 2 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 5 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 5 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 4 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 4 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 1 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 1 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 2 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 2 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 2 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 5 J 3 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 1 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 1 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 2 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 2 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 3 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 5 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 1 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 2 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 3 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 4 k 4 Voidmapcolor intR intn ints I 6 J 1 I为区域号 J为染色号while I4 THEN I I 1 J s I 1 1234567 1234567 1234567 I 6 J 5 k 4 S 1 7 1234567 a粉色b黄色c红色d绿色 作业 P75第10题 P76第11题第13题 第15题第17题 A B C D E A B C D E 优先级相同时 应先处理栈中数据 错在哪 P76 11假设一个算术表达式中包含圆括弧 方括弧和花括弧三种类型的括弧 编写一个判别表达式中括弧是否正确配对的函数 P76 11假设一个算术表达式中包含圆括弧 方括弧和花括弧三种类型的括弧 编写一个判别表达式中括弧是否正确配对的函数 voidmain intlen tag charexp size dsgdsg wetewt eewtwrwer etewtewt wetwet etwet len strlen exp tag Correct exp len if tag 1 printf right n elseprintf wrong n 输出结果 wrong P76 13若进栈序列为3 5 7 9 进栈过程中可以出栈 则不可能的一个出