PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

剖车
5 years ago
Views:

数据结构与算法 ( 三 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

1 数据结构与算法 ( 三 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 第 3 章栈与队列栈栈的应用递归到非递归的转换队列 2

3 栈 (Stack) 操作受限的线性表运算只在表的一端进行队列 (Queue) 运算只在表的两端进行 3

4 栈定义后进先出 (Last In First Out) 一种限制访问端口的线性表主要操作进栈 (push) 出栈 (pop) 应用表达式求值消除递归深度优先搜索栈顶栈底出栈 K i+1 K i... k 1 k 0 进栈 4

5 栈的抽象数据类型 template <class T> class Stack { public: // 栈的运算集 void clear(); // 变为空栈 bool push(const T item); // item 入栈, 成功返回真, 否则假 bool pop(t& item); // 返回栈顶内容并弹出, 成功返回真, 否则假 bool top(t& item); // 返回栈顶但不弹出, 成功返回真, 否则假 bool isempty(); // 若栈已空返回真 bool isfull(); // 若栈已满返回真 ; 5

6 火车进出栈问题判断火车的出栈顺序是否合法编号为 1,2,,n 的 n 辆火车依次进站, 给定一个 n 的排列, 判断是否是合法的出站顺序? 5, 4, 3, 2, 1 1, 2, 3, 4, 5 B A 6 车站

7 利用合法的重构找冲突

8 思考若入栈的顺序为 1,2,3,4, 那么出栈的顺序可以有哪些? 从初始输入序列 1,2,,n, 希望利用一个栈得到输出序列 p 1,p 2,,p n ( 它们是 1, 2,,n 的一种排列 ) 若存在下标 i,j,k, 满足 i<j<k 同时 P j <P k <P i, 则输出序列是否合法? 8

9 栈的实现方式顺序栈 (Array-based Stack) 使用向量实现, 本质上是顺序表的简化版栈的大小关键是确定哪一端作为栈顶上溢, 下溢问题链式栈 (Linked Stack) 用单链表方式存储, 其中指针的方向是从栈顶向下链接 9

10 3.1.1 顺序栈顺序栈的类定义 template <class T> class arrstack : public Stack <T> { private: // 栈的顺序存储 int msize; // 栈中最多可存放的元素个数 int top; // 栈顶位置, 应小于 msize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrstack(int size) { // 创建一个给定长度的顺序栈实例 msize = size; top = -1; st = new T[mSize]; arrstack() { // 创建一个顺序栈的实例 top = -1; ~arrstack() { delete [] st; void clear() { top = -1; // 清空栈 10

11 3.1.1 顺序栈顺序栈按压入先后次序, 最后压入的元素编号为 4, 然后依次为 3,2,1 栈顶栈底

12 3.1.1 顺序栈上溢 (Overflow) 顺序栈的溢出当栈中已经有 maxsize 个元素时, 如果再做进栈运算, 所产生的现象下溢 (Underflow) 对空栈进行出栈运算时所产生的现象 12

13 3.1.1 顺序栈压入栈顶 bool arrstack<t>::push(const T item) { if (top == msize-1) { // 栈已满 cout << " 栈满溢出 " << endl; return false; else { // 新元素入栈并修改栈顶指针 st[++top] = item; return true; 13

14 3.1.1 顺序栈从栈顶弹出 bool arrstack<t>::pop(t & item) { // 出栈 if (top == -1) { // 栈为空 cout << " 栈为空, 不能执行出栈操作 "<< endl; return false; else { item = st[top--]; // 返回栈顶, 并缩减 1 return true; 14

15 3.1.2 链式栈用单链表方式存储链式栈的定义指针的方向从栈顶向下链接栈顶 K n-1 K n-2 K 1 K 0 15

16 3.1.2 链式栈链式栈的创建 template <class T> class lnkstack : public Stack <T> { private: // 栈的链式存储 Link<T>* top; // 指向栈顶的指针 int size; // 存放元素的个数 public: // 栈运算的链式实现 lnkstack(int defsize) { // 构造函数 top = NULL; size = 0; ~lnkstack() { // 析构函数 clear(); 16

17 3.1.2 链式栈压入栈顶 // 入栈操作的链式实现 bool lnksstack<t>:: push(const T item) { Link<T>* tmp = new Link<T>(item, top); top = tmp; size++; return true; Link(const T info, Link* nextvalue) {// 具有两个参数的 Link 构造函数 data = info; next = nextvalue; 17

18 3.1.2 链式栈从单链栈弹出元素 // 出栈操作的链式实现 bool lnkstack<t>:: pop(t& item) { Link <T> *tmp; if (size == 0) { cout << " 栈为空, 不能执行出栈操作 "<< endl; return false; item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; 18

19 时间效率顺序栈和链式栈的比较所有操作都只需常数时间顺序栈和链式栈在时间效率上难分伯仲空间效率顺序栈须说明一个固定的长度链式栈的长度可变, 但增加结构性开销 19

20 顺序栈和链式栈的比较实际应用中, 顺序栈比链式栈用得更广泛顺序栈容易根据栈顶位置, 进行相对位移, 快速定位并读取栈的内部元素顺序栈读取内部元素的时间为 O(1), 而链式栈则需要沿着指针链游走, 显然慢些, 读取第 k 个元素需要时间为 O(k) 一般来说, 栈不允许读取内部元素, 只能在栈顶操作 20

21 思考 : STL 中关于栈的函数 top 函数表示取栈顶元素, 将结果返回给用户 pop 函数表示将栈顶元素弹出 ( 如果栈不空 ) pop 函数仅仅是一个操作, 并不将结果返回 pointer = astack.pop()? 错误! STL 为什么这两个操作分开? 为什么不提供 ptop? 21

22 栈的特点 : 后进先出栈的应用体现了元素之间的透明性常用来处理具有递归结构的数据深度优先搜索表达式求值子程序 / 函数调用的管理消除递归 22

23 表达式的递归定义计算表达式的值基本符号集 :{0,1,,9,+,-,*,/,(,) 语法成分集 :{< 表达式 >, < 项 >, < 因子 >, < 常数 >, < 数字 > 中缀表达式 23+(34*45)/(5+6+7) 后缀表达式 * / + 23

24 中缀表达式中缀表达式 4 * x * (2 * x + a) c 运算符在中间需要括号改变优先级 * - c * + * 4 x a 2 x 24

25 中缀表达法的语法公式 < 表达式 > = < 项 > + < 项 > < 项 > - < 项 > < 项 > < 项 > = < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > < 因子 > = < 常数 > ( < 表达式 > ) < 常数 > = < 数字 > < 数字 > < 常数 > < 数字 > =

26 表达式的递归图示表达式项因子项 + - 因子 * / ( 表达式 ) 数字 26

27 后缀表达式后缀表达式 4 x * 2 x * a + * c 运算符在后面完全不需要括号 * - c * + 4 x a * 2 x 27

28 后缀表达式 < 表达式 > = < 项 > < 项 > + < 项 > < 项 > - < 项 > < 项 > = < 因子 > < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > = < 常数 > < 常数 > = < 数字 > < 数字 > < 常数 > < 数字 > =

29 后缀表达式的计算 * / + =? 计算特点? 中缀和后缀表达式的主要异同? * 45 / ( ) =? * / + =? 29

30 待处理后缀表达式 : * / + 栈状态的变化计算结果

31 后缀表达式求值循环 : 依次顺序读入表达式的符号序列 ( 假设以 = 作为输入序列的结束 ), 并根据读入的元素符号逐一分析 1. 当遇到的是一个操作数, 则压入栈顶 2. 当遇到的是一个运算符, 就从栈中两次取出栈顶, 按照运算符对这两个操作数进行计算然后将计算结果压入栈顶如此继续, 直到遇到符号 =, 这时栈顶的值就是输入表达式的值 31

32 后缀计算器的类定义 class Calculator { private: Stack<double> s; // 这个栈用于压入保存操作数 // 从栈顶弹出两个操作数 opd1 和 opd2 bool GetTwoOperands(double& opd1,double& opd2); // 取两个操作数, 并按 op 对两个操作数进行计算 void Compute(char op); public: Calculator(void){ ; // 创建计算器实例, 开辟一个空栈 void Run(void); // 读入后缀表达式, 遇 = 符号结束 void Clear(void); // 清除计算器, 为下一次计算做准备 ; 32

33 后缀计算器的类定义 template <class ELEM> bool Calculator<ELEM>::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) { if (S.IsEmpty()) { cerr << "Missing operand!" <<endl; return false; opnd1 = S.Pop(); // 右操作数 if (S.IsEmpty()) { cerr << "Missing operand!" <<endl; return false; opnd2 = S.Pop(); // 左操作数 return true; 33

34 后缀计算器的类定义 template <class ELEM> void Calculator<ELEM>::Compute(char op) { bool result; ELEM operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result == true) switch(op) { case '+' : S.Push(operand2 + operand1); break; case '-' : S.Push(operand2 - operand1); break; case '*' : S.Push(operand2 * operand1); break; case '/' : if (operand1 == 0.0) { cerr << "Divide by 0!" << endl; S.ClearStack(); else S.Push(operand2 / operand1); break; else S.ClearStack(); 34

35 后缀计算器的类定义 template <class ELEM> void Calculator<ELEM>::Run(void) { char c; ELEM newoperand; while (cin >> c, c!= '=') { switch(c) { case '+': case '-': case '*': case '/': Compute(c); break; default: cin.putback(c); cin >> newoperand; Enter(newoperand); break; if (!S.IsEmpty()) cout << S.Pop() << endl; // 印出求值的最后结果 35

36 目录页思考 1. 栈往往用单链表实现可以用双链表吗? 哪个更好? 2. 请总结前缀表达式的性质, 以及求值过程 36

37 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 三 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 3 章栈与队列栈栈与表达式求值队列栈和队列的应用队列的应用递归到非递归的转换 ( 补充 ) 2 栈 (Stack) 操作受限的线性表运算只在表的一端进行