济南大学数据结构课件 第三章.pptVIP

S.base = ( SElemType * ) realloc ( S.base ， ( S.stacksize + STACKINCREMENT ) * sizeof(SElemType) )； if ( ! S.base ) exit(OVERFLOW) ； 思想: 使用栈记录走过的路径: 若当前位置不通，标记该位置，退栈，寻找新路经 若当前位置通，进栈，寻找新路经 基本概念 通道: 空白方块。 墙: 带阴影方块。 路径: 从入口到当前位置所走过的通道块。 简单路径: 求得的路径上不能重复出现同一通道块。 当前位置: 有哪些信誉好的足球投注网站过程中某一时刻所在的方块位置。 下一位置: 当前位置四周东南西北四个方向上相邻的方块。 当前位置可通: 当前位置是未曾走过的通道块。首先该方块是通道块，而且当前位置既不在当前路径上，也不是曾经走过但不通的通道块。 算法描述 设入口位置为当前位置； do { } while (栈不空) 若当前位置可通，则将当前位置进栈； 若该位置是出口位置，则成功； 否则置当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置上有其他方向未经探索，则置当前位置的下一相邻方块为新的当前位置。 若栈不空且栈顶位置的四周都不通，则栈顶出栈，标记不通；重新测试新的栈顶位置，直至找到一个可通的相邻块作为新的当前位置。 初始，1.1当前位置，可通，进栈 1.2当前位置，可通，进栈 1.3不通，2.2为当前位置，进栈 北 南 东 西 2.3不通，3.2为当前位置，进栈 3.3可通，进栈 3.4、4.3、3.2、2.3均不通 3.3出栈，3.2为新栈顶元素 × 3.3、4.2不通，3.1为当前位置，进栈 为了方便计算机实现，增加界符# ， #优先级最低。 # 4 ＋ 2 * 3 － 10 / 5 # 操作符和界符统称为运算符 其他为操作数(运算数) 任意两个相继的运算符?1 和?2之间存在优先关系: ?1 ?2 ?1的优先权低于?2 ?1 = ?2 ?1的优先权等于?2 ?1 ?2 ?1的优先权高于?2 3.2.5 表达式求值 算术表达式 4 ＋ 2 * 3 － 10 / 5 求值 4 ＋ 2 * 3 － 10 / 5 = 4 ＋ 6 － 10 / 5 = 10 － 10 / 5 = 10 － 2 = 8 思想: 使用栈存放操作符 栈顶操作符与当前输入操作符比较 优先级低，新操作符进栈 优先级高，栈顶操作符出栈，计算结果 算符优先关系表 ?1 ?2 + - * / ( ) # + - * / ( = ) # = 4 ＋ 2 * 3 － 10 / 5 # OPND OPTR 当前输入符c # 4 4 + # + + 2 2 * + * * 3 3 - * - 6 + - 10 # - - 10 10 / - / / 5 5 # / # 2 - # 8 # = # return 8 初始，# 进OPTR栈 建立两个栈，OPTR用于存放运算符 OPND用来存放操作数 ‘#’作为输入串的左右分界符 开始分析时，‘#’进入OPTR， OPND为空 ?存放当前OPTR栈顶符号(运算符) C存放当前输入符号 算法需要的工具 InitStack ( OPTR ) ；InitStack ( OPND ) ； Push ( OPTR ，’#’ ) ； if ( ! In( c ，OP ) ) { Push ( OPND ，c ) ；c = get