第4章 栈和队列2(第9次课).ppt

第9次上机作业 1.实现括号匹配检验算法 2.下列三题任选一题 （1）背包问题求解 （2）后缀表达式求值 （3）把中缀表达式转换为后缀表达式 * 第4章 栈和队列2 栈和队列是对线性表的某些操作加以限定而派生出的结构。它们的操作本身并不难掌握，难点是理解栈和队列的应用思想、掌握其算法的设计技巧。 讲授本章课程大约需6课时。 * 3.2 栈的应用举例 栈在算法设计中占有重要的地位，运用的技巧也性也较高，本节安排五个例子来讨论栈的使用。 * 例二 括号匹配的检验 例三 背包求解 例四 表达式求值 例五 递归函数的实现 * 例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。 * 分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的； 例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。 * 算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。 * bool matching(char exp[]) { int state = 1; ch=*exp++; while (ch!=‘#’ state) { switch (ch) { case (: case [: { Push(S, ch); break; } //左括弧进栈 case ): { // 匹配‘）’ if(!StackEmpty(S)GetTop(S)==() Pop(S,e); else state = 0; break; } case ]: { …… } // 匹配‘]’ } //switch ch=*exp++; }//while if (StackEmpty(S)state) return TRUE; else return FALSE; }//matching * 例三.背包问题: 假设有n件体积分别为w1,w2,…wn的物品和一个能装载体积为T的背包.能否从n件物品中选择若干件恰好装满背包, 即 wi1+wi2+…+wik = T,则背包问题有解； 否则无解. 以W(1,8,4,3,5,2), T=10为例 (1,4,3,2 ), (1,4,5 ), (8,2)和(3,5, 2)是其解。 * 5 4 3 8 1 4 3 5 8 2 2 W T=10 1+4+3+2=10 利用回溯的算法思想求解背包问题 从背包中取出物品再继续有哪些信誉好的足球投注网站的策略称之为回溯，其规则是“后进先出”，即背包以栈的操作完成求解。 * void knapsack(int w[], int T, int n) { // T在算法中是剩余的容积，初值为背包的体积 InitStack(S); k=0; do { while (T0 kn) { if (T-w[k]=0) { // 第k件物品可以进栈 Push(S, k); T─ =w[k]; } k++; }//while if (T==0) StackTraverse(S); // 输出一个解 Pop (S, k); T+ =w[k]; // 退出栈顶物品 k++;