例:N皇后问题 ·国际象棋中的“后”可以吃掉与她同一行、同一列、同 对角线的棋子,如何在N×N的棋盘摆上N个皇后,使得她 们彼此吃不到对方? 典型算法:试探-回溯法 思路 逐行试探,先在第一行摆一个,再在 第二行摆一个, N行全部摆好,说明找到一种解法 ·如果某一行无法摆放,说明之前行的 摆法不可行,退回到上一行重新摆放 数据结构: ·采用栈记录皇后摆放位置,以便回溯 附设列、左下对角线、右下对角线三 个数组防止皇后冲突 2021/1/29 数据结构及其算法第4章栈和队列
•例：N皇后问题 • 国际象棋中的“后”可以吃掉与她同一行、同一列、同一 对角线的棋子，如何在N×N的棋盘摆上N个皇后，使得她 们彼此吃不到对方？ •典型算法：试探-回溯法 2021/1/29 数据结构及其算法 第4章 栈和队列 12 思路： • 逐行试探，先在第一行摆一个，再在 第二行摆一个，…… • N行全部摆好，说明找到一种解法 • 如果某一行无法摆放，说明之前行的 摆法不可行，退回到上一行重新摆放 数据结构： • 采用栈记录皇后摆放位置，以便回溯 • 附设列、左下对角线、右下对角线三 个数组防止皇后冲突
void queen(intN){/使用栈求解皇后问题 bool *A= new bool[N],*B= new bool[2N-1],*C= new bool[2*N-1]; for (int i=0; iN; ++1)alil= false; for(int i=0; i<2N-1; ++1)b[i]= false; for (int i=0; 1<2N-1;++i)cli]= false; Stack s. Tnitstackls. int ci wl bool place(int i, int j, int N, bool *A, bool *B, bool *c)i return!(A[j]‖B[i+j]‖|C[i-j+N-1]) f (place(, j,N,A,B, c)i mark(i,j,N, true, A, B, C); Push(S, j)j void mark(int i, int j, int N, bool flag, bool *A, bool *B, bool *c)i []=b[1+]=C[i-j 1a8 if ( feasible)i int j; if (I Pop(s, j))break; mark(i-1, j, N, false, A, B, C); j=j+1 else思考:如何对程序进行修改以找出所有的解? 2021/1/29 数据结构及其算法第4章栈和队列
2021/1/29 数据结构及其算法 第4章 栈和队列 13 void queen(int N) { // 使用栈求解N皇后问题 bool *A = new bool[N], *B = new bool[2*N-1], *C = new bool[2*N-1]; for (int i=0; i<N; ++i) A[i] = false; for (int i=0; i<2*N-1; ++i) B[i] = false; for (int i=0; i<2*N-1; ++i) C[i] = false; Stack S; InitStack(S); int sj = 0; while (true) { int i = StackLength(S); bool feasible = false; if (i < N) for (int j = sj; j < N; ++j) { if (place(i, j, N, A, B, C)) { mark(i, j, N, true, A, B, C); Push(S, j); if (i == N-1) { print(S); return; } feasible = true; break; } } if (!feasible) { int j; if (!Pop(S, j)) break; mark(i-1, j, N, false, A, B, C); sj = j+1; } else sj = 0; } } bool place(int i, int j, int N, bool *A, bool *B, bool *C) { return !(A[j] || B[i+j] || C[i-j+N-1]); } void mark(int i, int j, int N, bool flag, bool *A, bool *B, bool *C) { A[j] = B[i+j] = C[i-j+N-1] = flag; } 思考：如何对程序进行修改以找出所有的解？
例:表达式求值问题(算符优先法) 般的算术表达式又称中缀表达式( infix notation),如:4×2+(7-8÷2),运算符在操 作数中间,需要用括号来表示运算顺序 例:计算一位整数、无括号的四则运算7-8:2+ 7操作数-运算符8操作数 此时不能计算7-8,后续可能×或÷,7、8、-分别保存 ÷运算符2操作数+运算符 前一运算符÷可做,因为÷优先于+ 计算8(前一操作数)÷2,运算结果为4 再前一运算符-可做,因为左侧-优先于+ 计算7-4,运算结果为3,保存 2021/1/29 数据结构及其算法第4章栈和队列
•例：表达式求值问题（算符优先法） •一般的算术表达式又称中缀表达式(infix notation)，如：4×2+(7-8÷2)，运算符在操 作数中间，需要用括号来表示运算顺序 •例：计算一位整数、无括号的四则运算7-8÷2+… • 7 操作数 - 运算符 8 操作数 • 此时不能计算7-8，后续可能×或÷，7、8、-分别保存 • ÷ 运算符 2 操作数 + 运算符 • 前一运算符÷可做，因为÷优先于+ • 计算8（前一操作数）÷2，运算结果为4 • 再前一运算符-可做，因为左侧-优先于+ • 计算7-4，运算结果为3，保存 • …… 2021/1/29 数据结构及其算法 第4章 栈和队列 14
·运算符:要和前一个比较优先级》设两个栈 操作数:要和前一个进行计算 表达式求值算法 运算符栈保存暂时不能计算的运算符 操作数栈保存暂时不能计算的操作数或中间结果 虚设一对'#'构成整个表达式的界限符( delimiter) ·读入操作数直接入栈 读入运算符或()或#,进行算符优先级判断和相应操作 2021/1/29 数据结构及其算法第4章栈和队列 15
•运算符：要和前一个比较优先级 •操作数：要和前一个进行计算 •表达式求值算法 • 运算符栈保存暂时不能计算的运算符 • 操作数栈保存暂时不能计算的操作数或中间结果 • 虚设一对'#'构成整个表达式的界限符(delimiter) • 读入操作数直接入栈 • 读入运算符或()或#，进行算符优先级判断和相应操作 2021/1/29 数据结构及其算法 第4章 栈和队列 15 设两个栈
例:计算#4×2+(7-8÷2)#的过程 4×2 2 8÷:2 4 7 7 4 8 OPTR OPND OPTR OPND OPTR OPND 7-4 8+3 3 8 11 OPTR OPND OPTR OPND OPTR OPND 2021/1/29 数据结构及其算法第4章栈和队列
•例：计算#4×2+(7-8÷2)#的过程 2021/1/29 数据结构及其算法 第4章 栈和队列 16 # 4 × 2 + ( 7 - 8 ÷ 2 OPTR OPND + OPTR OPND # 8 ) 4 OPTR OPND # 8 + 7 ( - ) 3 OPTR OPND # 8 + ( ) 3 OPTR OPND # 8 + # 11 OPTR OPND # # 4×2 8÷2 7-4 8+3