数据结构第3章栈和队列4.ppt

第三章 栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 第三章 栈和队列 3.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 栈的存储结构 顺序栈 栈的存储结构 顺序栈 实现：一维数组s[M] 栈的存储结构 顺序栈 实现：一维数组s[M],为了C语言处理方便，设一个base指针 顺序栈的模块说明：p46-47 栈的存储结构 链栈 2 括号匹配的检查 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。 在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 3 行编辑程序 接受用户从终端输入的程序或数据，并存入用户的数据区。 建立一个数据缓冲区，接受用户输入一行字符，然后逐行存入用户数据区。 退格符“#”，退行符“@” 5 表达式求值 算符优先法 （1）先乘除，后加减 （2）从左到右 （3）先括号内，后括号外 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 使用2个工作栈: 一个称作OPTR，寄存运算符； 另一个OPND，寄存操作数或运算结果。 （2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR的栈顶元素和当前读入的字符均为#） 对表达式3*（7-2）求值过程如下 Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上 3.4 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 链队列 定义 循环队列－队列的顺序存储结构 实现：用一维数组实现sq[M] Operandtype evaluateexpression() { initstack(optr); push(optr,‘#’); initstack(opnd); c=getchar(); While (c!=‘#’ || gettop(optr)!=‘#’) { if (!in(c,OP)) {push(opnd,c);w=getchar();}//不是运算符则进栈 else switch precede(gettop(optr),c) { //比较优先权 case ‘’: push(optr,c);　c=getchar(); break; //栈顶优先权低 　　　　 case ‘=’: pop(optr,x);　 c=getchar();break;//脱括号 　　　　 case ‘’: pop(optr, theta); //退栈并将运算结果进栈 　　　　　　　　 pop(opnd, b); pop(opnd, a); 　　　　　　　　　push(opnd,operate(a,theta,b)); break;} }　 Return gettop(opnd) } 算法的实现p53 optr-寄存运算符opnd-寄存操作数 7. - 〉） =〉 operate 3.3 栈与递归 过程的嵌套调用 r 主程序 s r r r s 子过程1 r s t 子过程2 r s t 子过程3 例 递归的执行情况分析 递归过程及其实现 递归：函数直接或间接的调用自身叫~ 实现：建立递归工作栈 void print(int w) { int i; if ( w!=0)