数据结构精品课程

1、1,Stacks Stack Examples Pushing/Popping a Stack Class Stack (vector/miniVector) Using a Stack to Create a Hex # Uncoupling Stack Class Stack (array) Class Stack (LinkedList) Recursive code RPN Infix Notation,Lecture 5 Stacks,2,Stacks,A stack is a sequence of items that are accessible at only one end

2、 of the sequence.,3,Further Stack Examples,4,Pushing/Popping a Stack,Because a pop removes the item last added to the stack, we say that a stack has LIFO (last-in/first-out) ordering.,5,Stack Implementation,template class miniStack public: miniStack(); void push(const T,6,Stack Implementation,templa

3、te miniStack:miniStack() template void miniStack:push(const T ,7,Stack Implementation (vector),template T ,8,Using a Stack to Create a Hex Number,9,Using a Stack to Create a Hex Number,String multibaseOutput(int num, int b) string digitChar=“0123456789ABCDEF”, numStr=“ ”; stack stk; do stk.push(digi

4、tCharnum % b); num/=b; while(num!=0); while(!stk.empty() numstr+=stk.top(); stk.pop(); return numStr; ,10,Uncoupling Stack Elements,11,Uncoupling Stack Elements,12,Uncoupling Stack Elements,13,Uncoupling Stack Elements,14,Uncoupling Stack Elements,15,Uncoupling Stack Elements,16,Uncouple Algorithm,T

5、emplate Bool uncouple(stack ,17,18,19,20,Stack Implementation (array),const MAXSTACKSIZE=50; template class bStack /有限栈 public: bStack(); void push(const T,7 6 5 4 3 2 1 0 -1,21,Stack Implementation (array),template bStack:bStack()topIndex=-1; template void bStack:push(const T ,22,Stack Implementati

6、on (array),template T ,23,Stack Implementation (array),template bool bStack:full() const return topIndex =MAXSTACKSIZE-1; template int bStack:size() const return topIndex+1; ,24,Stack Implementation (LinkedList),#include“d_node.h” template class LinkedStack public: LinkedStack(); void push(const T,H

7、eader,25,Stack Implementation (LinkedList),template LinkedStack:LinkedStack()count=0;Header=NULL; template void LinkedStack:push(const T ,26,Stack Implementation (LinkedList),template T ,27,Stack Implementation (LinkedList),template int LinkedStack:size() const return count; ,28,Recursive Code and t

8、he Running Stack,递归求解问题： f(n)=n! 递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解。 递归的两个主要特点： 1.递归式（可分解性），如何将原问题划分成子问题。 2.递归出口（可终止性），递归终止的条件，即最小子 问题的求解。 因为f(n)=n!, f(n-1)=(n-1)! 所以f(n)=n!=n*(n-1)!=n*f(n-1),29,Recursive Code and the Running Stack,Int main() int factValu

9、e; factValue=fact(4); cout“Value fact(4)=”factValueendl; return 0; Int fact(int n) if(n=0) return 1; else return n*fact(n-1); ,RetLoc1,RetLoc2,f(x)=n!,30,31,Postfix expressions：逆波兰表达式，后缀表达式,Infix: a+b*c postfix: abc*+ Infix: (a+b)*c postfix: ab+c* Infix: (a*b+c)/d+e postfix: ab*c+d/e+ Rule 1: Scan t

10、he infix expression from left to right. Immediately record an operand as soon as you identify it in the express. Rule 2: Record an operator as soon as you identify its operands. 注：波兰逻辑学家 J.Lukasiewicz于1929年提出的一种表示表达式的方法。,32,33,PostfixEval Class,class postfixEval public: postfixEval(); string getPost

11、fixExp() const; void setPostfixExp(const string,34,PostfixEval Class,void postfixEval:getOperands(int ,35,PostfixEval Class,int postfixEval:compute(int left, int right, char op) const int value; switch(op) case +: value = left + right; break; case -: value = left - right; break; case *: value = left

12、 * right; break; case %: if (right = 0) throw expressionError(postfixEval: divide by 0); value = left % right; break; case /: if (right = 0) throw expressionError(postfixEval: divide by 0); value = left / right; break; case : if (left = 0 ,36,PostfixEval Class,bool postfixEval:isOperator(char ch) co

13、nst return ch = + | ch = - | ch = * | ch = % | ch = / | ch = ; postfixEval:postfixEval() string postfixEval:getPostfixExp() const return postfixExpression; void postfixEval:setPostfixExp(const string ,37,PostfixEval Class,int postfixEval:evaluate() int left, right, expValue; char ch; int i; for (i=0

14、; i = 当前元素，出栈并顺序输出运算符直到 栈顶元素 + B. Rank of an expression: Rank of an operand: 1 Rank of the binary operators +, ,*, /, %, : -1 Rank of left and right parentheses: 0 C. The cumulative rank of a valid infix expression is between 01,40,Infix-to-postfix Conversion,Example 1: a+b*c Example 2: a*b/c+d Exam

15、ple 3: abc is right-associative, so bc first new strategy: different precedence value input precedence 4 stack precedence 3 Example 4: a*(b+c) new strategy: different precedence value ( input precedence 5 ( stack precedence -1 ) input precedence 0 ) stack precedence 0 Attention: +, precedence is 1,

16、*,/,% precedence is 2 input precedence and stack precedence are same,设计符号栈实现符号优先级排序，保证优先级高的运算符总是处于栈顶，以保证其最先出栈，最先运算,41,Infix Expression Rules The figure below gives input precedence, stack precedence, and rank used for the operators +, -, *, /, %, and , along with the parentheses. Except for the expo

17、nential operator , the other binary operators are left-associative and have equal input and stack precedence.,42,Rules for Infix Expression Evaluation,It needs an operator stack and a postfix string to implement the conversion Rule 1: the cumulative rank must be in the range from 0 to 1. Rule 2: ope

18、rand to the postfix string; Rule 3: operator or left parenthesis: input precedence ? stack precedence of the top stack = input operator out of stack to postfix string; stack= (const expressionSymbol expressionSymbol:expressionSymbol() ,44,Infix-to-Postfix Evaluation: Object Design,expressionSymbol:e

19、xpressionSymbol(char ch) op = ch; switch(op) case +: case -: inputPrecedence = 1; stackPrecedence = 1; break; case *: case %: case /: inputPrecedence = 2; stackPrecedence = 2; break; case : inputPrecedence = 4; stackPrecedence = 3; break; case (: inputPrecedence = 5; stackPrecedence = -1; break; cas

20、e ): inputPrecedence = 0; stackPrecedence = 0; break; ,45,Infix-to-Postfix Evaluation: Object Design,char expressionSymbol:getOp() const return op; bool operator= (const expressionSymbol ,46,Infix-to-Postfix Evaluation: Object Design,class infix2Postfix public: infix2Postfix(); infix2Postfix(const s

21、tring,47,Infix-to-Postfix Evaluation: Object Design,void infix2Postfix:outputHigherOrEqual(const expressionSymbol ,48,Infix-to-Postfix Evaluation: Object Design,infix2Postfix:infix2Postfix() infix2Postfix:infix2Postfix(const string ,49,Infix-to-Postfix Evaluation: Object Design,string infix2Postfix:

22、postfix() expressionSymbol op; int rank = 0, i; char ch; for (i=0; i 1) throw expressionError(infix2Postfix: Operator expected); ,50,Infix-to-Postfix Evaluation: Object Design,else if (isOperator(ch) | ch = () if (ch != () rank-; if (rank 0) throw expressionError(infix2Postfix: Operand expected); else