顺序栈和链式栈的比较 实际应用中,顺序栈比链式栈用得更广泛些 口存储开销低 口顺序栈容易根据栈顶位置,进行相对位移,快速定位 并读取栈的内部元素 顺序栈读取内部元素的时间为O(1),而链式栈则需要 沿着指针链游走,显然慢些,读取第k个元素需要时间 为O(k) 般来说,栈不允许“读取内部元素”,只能在栈顶 操作 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序栈和链式栈的比较 ◼ 实际应用中，顺序栈比链式栈用得更广泛些 ❑ 存储开销低 ❑ 顺序栈容易根据栈顶位置，进行相对位移，快速定位 并读取栈的内部元素 ◼ 顺序栈读取内部元素的时间为O(1)，而链式栈则需要 沿着指针链游走，显然慢些，读取第k个元素需要时间 为O(k) ◼ 一般来说，栈不允许“读取内部元素”，只能在栈顶 操作
栈的应用 栈的特点:后进先出 口体现了元素之间的透明性 常用来处理具有递归结构的数据 口深度优先搜索 口表达式求值 口数制转换 a行编辑处理 子程序/函数调用的管理 消除递归 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的应用 ◼ 栈的特点：后进先出 ❑ 体现了元素之间的透明性 ◼ 常用来处理具有递归结构的数据 ❑ 深度优先搜索 ❑ 表达式求值 ❑ 数制转换 ❑ 行编辑处理 ❑ 子程序／函数调用的管理 ❑ 消除递归
数制转换 非负十进制数转换成其它进制的数的一种简单方法: 口例,十进制转换成八进制:(66)10=(102) 66/8=8余2 8/8=1余0 1/8=0余1 结果为余数的逆序:102 先求得的余数在写出结果时最后写出,最后求出的余 写出,符合栈的先入后出性质,故可用栈来实 现数制转换。 同理,个非负十进制整数N转换为另二个等价的基 为B的B进制数,可以采用除B取余法来解决 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 数制转换 ◼ 非负十进制数转换成其它进制的数的一种简单方法： ❑ 例，十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1 结果为余数的逆序：102 ◼ 先求得的余数在写出结果时最后写出，最后求出的余 数最先写出，符合栈的先入后出性质，故可用栈来实 现数制转换。 ◼ 同理，一个非负十进制整数N转换为另一个等价的基 为B的B进制数，可以采用"除B取余法"来解决
计算表达式的值 表达式的递归定义 ¤基本符号集:{0,1,…,9,+,-,*,1,(,)} 口语法成分集:〖表达式〉,<项〉,<因子〉,<常数〉,<数 字>} 口语法公式集 中缀表达式 23+(34*45)(5+6+7) 后缀表达式 233445*56+7+/+ 后缀表达式求值 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 计算表达式的值 ◼ 表达式的递归定义 ❑ 基本符号集：{0，1，…，9，+，-， * ，/，（，）} ❑ 语法成分集：{<表达式> , <项> , <因子> , <常数> , <数 字> } ❑ 语法公式集 ◼ 中缀表达式 23+(34*45)/(5+6+7) ◼ 后缀表达式 23 34 45 * 5 6 + 7 + / + ◼ 后缀表达式求值
中缀表达法的语法公式 <表达式>∷=<项〉+<项〉 <项〉一<项 <项 <项>∴=<因子>*<因子〉 <因子>/<因子〉 <因子〉 <因子>∷=<常数〉 (<表达式>) <常数〉∷=<数字 1<数字><常数 数字〉∷=0|1|213|4|5|6|7|89 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 中缀表达法的语法公式 <表达式> ∷= <项> + <项> | <项> － <项> | <项> <项> ∷= <因子> * <因子> | <因子> / <因子> | <因子> <因子> ∷= <常数> | （ <表达式> ） <常数> ∷= <数字> | <数字> <常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9