Microsoft PowerPoint - 4.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 4.pptx"

京姬
5 years ago
Views:

1 第 4 章栈和队列运算受限的线性表栈表达式求值搜索与回溯队列队列的应用

2 4.1 栈只在称为栈顶 (top) 的一端插入和删除的线性表另一端称为栈底 (bottom) 数据通过栈的顺序后进先出 (LIFO) top bottom a n-1 a n-2 a 0

3 栈的抽象数据类型 class Stack { public: Stack ( ) { ; ~Stack ( ) { ; int push (char x); int pop (char* px); bool isempty ( ); bool isfull ( );

4 用数组实现栈 template <class Type> class Stack { private: Type *stk; // 栈元素数组 int top; // 栈顶指针 int MAXN; // 栈最大容量 public: Stack (int size) { MAXN = size; stk = new Type[MAXN]; top = -1; // 构造函数 ~Stack ( ) { delete stk; int push (Type x) { // 进栈 if(top >= MAXN 1) return 1; // 栈满, 进栈失败 stk [++top] = x; return 0; int pop (Type* px) { // 出栈 if(top == -1) return 1; *px = stk [top -- ]; return 0; Type gettop () { // 取栈顶 if(top == -1) return NULL; return stk [top]; int isempty ( ) const { return top == -1; int isfull ( ) const { return top == MAXN 1 ;

5 两个栈共用一个栈空间为避免栈满时溢出, 需为栈设立一个足够大的空间如果栈中实际只有几个元素, 是一种浪费当要两个栈时, 可定义一足够大的空间两个栈的栈顶都向空间伸展, 直到两个栈的栈顶相遇, 发生溢出一个栈可能进栈元素多而体积大些, 另一个则可能小些两个栈互相调剂, 灵活性强

6 程序 4-2 DoubleStack 类的定义 template <class Type> class DoubleStack { private: int MAXN; Type *space ; int t[2], b[2]; // 设立栈顶和栈底指针数组 t[2] 和 b[2] public: DoubleStack() { t[0] = b[0] = -1; MAXN = 50; t[1] = b[1] = MAXN; space=new Type[MAXN]; ~DoubleStack() { delete [MAXN] space; int Push (Type x, int i) { if ( t[0]+1 == t[1] ) return 0; // 栈满条件 :t[0]+1 == t[1], 栈顶指针相遇 if ( i == 0 ) t[0]++; else t[1]--; space[t[i]] = x; return 1; int Pop (Type *px, int i) { if ( t[i] == b[i] ) return 0; // 栈空条件 :t[0] = b[0] 或 t[1] = b[1] *px = space[t[i]]; if ( i == 0 ) t[0]--; else t[1]++; return 1;

7 链式栈如果多个栈共享同一个空间, 可能有的栈占用空间多, 很快就产生溢出, 其它栈可能还有空闲空间通过移动某些栈为较满的栈腾出空间的调整代价较高链式栈是一个更好的选择链式栈只要内存有空间就可扩充 ; 链式栈的栈顶设在链头 ;

8 程序 4-3 LStack 类的定义 template <class Type> struct Node { Type data; Node<Type> *link; ; template <class Type> class LStack { private: Node<Type> *top; public: LStack () { top = NULL; void push(type x) { Node<Type> *p; P = new Node<Type>; p->data = x; p->link = top; top = p; int pop(type *x) { Node<Type> *p; if(top == NULL) return 1; *x = top->data; p=top; top = top->link; delete p; return 0; ~LStack ( ) { while ( top!= NULL ) {Node<Type>*p = top; top = top->link; delete p;

9 栈的应用表达式求值一个表达式由操作数操作符和分界符组成算术表达式有三种表示 : 中缀 (infix) 表示 < 操作数 > < 操作符 > < 操作数 >, 如 A+B; 前缀 (prefix) 表示 < 操作符 > < 操作数 > < 操作数 >, 如 +AB; 后缀 (postfix) 表示 < 操作数 > < 操作数 > < 操作符 >, 如 AB+;

10 表达式示例中缀表达式 a + b * c - d / e * f 后缀表达式 a b c * + d e / f * - 中缀表达式中相邻两个操作符的计算次序依赖于操作符的优先级和括号 : 优先级高的先计算 ; 优先级相同的自左向右计算 ; 括号从最内层开始计算

11 后缀表达式的计算从左向右处理表达式, 用一个栈暂存遇到的操作数或计算结果后缀表达式已体现了加括号的效果, 因此后缀表达式不包含括号中缀表达式 a + b *(c- d ) - e / f 后缀表达式 abcd- *+ef/ - rst1 rst2 rst3 rst6 rst4 rst5

12 后缀表达式的处理过程顺序逐项扫描表达式, 根据遇到的项的类型 : 该项是操作数, 则该项入栈 ; 该项是双目操作符, 则连续从栈中退出两个操作数, 计算后将结果入栈 ; 当处理完表达式的所有项后, 栈中应该只有一项内容, 就是表达式的计算结果

13 程序 4-4 Expression 类的定义 class Expression { public: Expression (char *posexpression,int *val) { pos_e = posexpression; v = val; ~Expression ( ) { int evaluate(int *p_y) { int i, j, k, x, y, z; Stack<int> s(100); char c; i = 0; c = pos_e[0]; while(c!='\0') { if(islower(c)) s.push(v[c-'a']); else switch (c) { case '+' : s.pop(&x); s.pop(&y); s.push(x+y); break; case '-' : s.pop(&x); s.pop(&y); s.push(y-x); break; case '* : s.pop(&x); s.pop(&y); s.push(x*y); break; case '/ : s.pop(&x); s.pop(&y); s.push(y/x); break; case '^ : s.pop(&x); s.pop(&y); if(y==0) return 1; if(x==0) s.push(1); else { if(x>0) j = x; else j = -x; for(z=1, k = 1; k<=j; k++) z* = y; if(x<0) z = 1/z; s.push(z); break; default: return 1; c = pos_e[++i]; s.pop(p_y); if(s.isempty()) return 0; else return 1;

14 用栈将中缀表示转为后缀表示用栈可将中缀表达式转换成对应的后缀表达式为实现这种转换, 需考虑操作符的优先级字符 ^ *, /, % +, - ( $ 栈中优先级栈外优先级

15 中缀表达式转换为后缀表达式的算法操作符栈初始化, 将结束符 $ 进栈然后读入中缀表达式字符流的首字符重复读入下一字符 ch, 直到遇到 \0 若 ch 是操作数直接输出, 读入下一个字符若 ch 是 (, 则入栈若 ch 是运算符 ( +, -, *, /, ^ ), 则将它的 ( 进栈前 ) 优先级别与栈顶字符的 ( 栈中 ) 优先级别进行比较如果当前的运算符的优先级别小于等于栈顶字符的优先级别, 那么退出栈顶字符并输出这样的过程一直进行到当前的运算符的优先级别大于栈顶字符的为止, 然后让当前的运算符进栈若当前的字符是 ), 则从栈中依次退出运算符并输出, 直到 ( 为止, 然后退出 (, 但不输出 ( 若当前的字符是 \0, 则从栈中依次退出所有运算符并输出, 直到 $ 为止, $ 不退栈, 也不输出

16 图 4-5 中缀表达式转换成等价后缀表达式的处理过程中缀表达式 :(a+b*c)^d^(e*f/g)-h*i

17 程序 4-5 Mid2Pos 类的定义 class Mid2Pos { public: int icp(char c) { switch (c) { case '^' : return 4; case '*': case '/': return 2; case '+': case '-': return 1; int isp(char c){ switch (c) { case '^': return 3; case '*': case '/': return 2; case '+': case '-' : return 1; case '(' : return 0; case '$' : return -1; int mid_to_pos(char mid_e[], char pos_e[]) { Stack<char>; s(100) char c; int i, j; j = 0; i = 0; c = mid_e[0]; s.push('$'); while(c!='\0 ) { if(islower(c)) pos_e[j++] = c; else switch (c) { case '+' : case '-' : case '*' : case '/' : case '^' : while(icp(c) <= isp(s.gettop())) s.pop(&(pos_e[j++])); s.push(c); break; case '(' : s.push( c ); break; case ')' : while((*(s.gettop()))!= '(') s.pop(&(pos_e[j++])); break; default: return 1; c = mid_e[++i ]; while(s.pop(&pos_e[j++])== 0); pos_e[j-2] = '\0'; return 0;

18 用栈求解迷宫问题在给定的迷宫中找出一条从入口到出口的路径

19 迷宫的表示迷宫可用矩阵 ( 二维数组 ) maze[m+2][n+2] 表示 maze[i][j] 为 1 表示该位置是墙壁, 不通 ; maze[i][j] 为 0 表示该位置是通路 ; 1 i m, 1 j n 数组的第 0 行和第 m+1 行第 0 列和第 n+1 列是迷宫的围墙

20 用二维数组表示的迷宫入口出口在迷宫中任一时刻的位置可用数组下标 i 与 j 来表示

21 8 个可能的前进方向西北 [i-1][j-1] 西 [i][j-1] [i+1][j-1] 西南北 [i-1][j] X [i][j] [i+1][j] 南东北 [i-1][j+1] [i][j+1] 东 [i+1][j+1] 东南用前进方向表来表示这 8 个可能的前进方向

22 前进方向表 move[q].dir move[q].a move[q].b 北 -1 0 东北 -1 1 东 0 1 东南 1 1 南 1 0 西南 1-1 西 0-1 西北 -1-1 例如当在 [i][j] 时, 若向东北方向走, 下一相邻位置 [g][h] 为 : g = i+move[1].a = i-1; h = j+move[1].b = j+1;

23 用栈来存储在试探的过程用栈存储在试探的过程中所走过的路径一旦需要回退, 可以根据栈中保存的记录进行回溯, 再尝试其它允许方向如果栈空, 则表示已回退到最初出发位置栈中数据用三元组表示 : struct items { int x, y, d;

24 标志矩阵 mark 防止走重复路 int mark[m+2][n+2] 其中所有元素都初始化为 0 标志矩阵的含义 mark[i][j] 为 1 表示该位置已走过 ; mark[i][j] 为 0 表示该位置尚未走过

25 迷宫问题的算法 (1) 程序 4-6 #define MAX 50 typedef struct element {int x, y, d; Element; typedef struct move {int a, b; MOVE; Stack <Element> s(max*max); class Maze { int maze[max][max]; int mark[max][max]; MOVE mv[8];

26 迷宫问题的算法 (2) public: int m,n; Maze() { cout << "input m and n of the maze" << endl; cout << "m = "; cin >> m; cout << "n = "; cin >> n;

27 迷宫问题的算法 (3) void setmove( ) { mv[0].a = -1; mv[0].b = 0; mv[1].a = -1; mv[1].b = 1; mv[2].a = 0; mv[2].b = 1; mv[3].a = 1; mv[3].b = 1; mv[4].a = 1; mv[4].b = 0; mv[5].a = 1; mv[5].b = -1; mv[6].a = 0; mv[6].b = -1; mv[7].a = -1; mv[7].b = -1;

28 迷宫问题的算法 (4) void inputmaze ( ) { int i, j; cout<<"input maze: "<<endl; for(i=0;i<=m+1;i++) for(j=0; j<=n+1;j++) maze[i][j] = 1; for(i=1;i<=m;i++) { for(j=1; j<=n;j++) cin >> maze[i][j]; cout << endl; // 换行

29 迷宫问题的算法 (5) void outputmaze ( ){ int i, j; cout<<"output maze : "<<endl; for(i=0; i<=m+1; i++) { for(j=0; j<=n+1; j++) cout<<maze[i][j]<< " "; cout<<endl;

30 迷宫问题的算法 (6) void setmark( ) { int i, j; for(i=0; i<=m+1; i++) for(j=0; j<=n+1; j++) mark[i][j] = 0;

31 迷宫问题的算法 (7) int getmazepath ( ) { int i, j, k, g, h, t; Element current; if(maze[1][1]!=0 maze[m][n]!=0) return 1; current.x = 1; current.y = 1; current.d = 1; s.push(current); mark[1][1] = 1; while(!s.isempty() ) { s.pop(&current); i = current.x; j = current.y; k = current.d; while(k<7) { g = i + mv[++k].a; h = j + mv[k].b; if(g==m && h==n) { cout<<"path in maze : "<<endl; cout<< i<<" "<<j<<" "<<k<<" "; while(!s.isempty() ) { s.pop(&current); cout<<current.x<<" "<<current.y<<" "<<current.d<<" "; return 0; if(maze[g][h] == 0 && mark[g][h] == 0) { mark[g][h] = 1; current.x = i; current.y = j; current.d = k; s.push(current); i = g; j = h; k = -1; return 1;

32 4.2 队列 (Queue ) front q 0 q 1 q 2 q n-1 rear 定义 : 队列是一种先进先出 (FIFO, First In First Out) 的线性表只允许在一端删除, 允许删除的一端叫做队头 (front) 只允许在另一端插入, 允许插入的一端叫做队尾 (rear)

33 程序 4-7 Queue 类的定义 template <class T> class Queue { public: Queue ( ) {; // 构造函数 ~Queue ( ) {; // 析构函数 virtual int enqueue (const T& x) = 0; // 进队 virtual int dequeue (T& x) = 0; // 出队

34 4.2.2 用数组实现队列 front rear 空队列 A B front rear B 进队 B C D front rear A 退队 C D E F G front rear E,F,G 进队 A front rear A 进队 A B C D front rear C, D 进队 C D front rear B 退队 C D E F G front rear H 进队, 溢出

35 队列的进队和出队原则进队时队尾指针先进一 rear = rear + 1, 再将新元素按 rear 指示位置加入队尾指针指示实际队尾队列非空时可出队, 出队时队头指针先进一 front = front + 1, 再将下标为 front 的元素取出队头指针指示实际队头的前一位置队空时,front == rear 队满时 (rear == maxsize), 再进队将溢出, 但这可能是假溢出, 因为前端可能有空间 ; 解决办法之一 : 将队列元素存放数组首尾相接, 形成循环 ( 环形 ) 队列

36 循环队列 (Circular Queue) 存放队列的数组作为首尾相连的表队列操作时要配合取模 ( 余数 ) 运算出队 : front = (front+1) % size; 进队 : rear = (rear+1) % size; 队列初始化 :front = rear = 0; 队空条件 :front == rear; 队满条件 :(rear+1) % size == front

37 rear 6 7 front 6 7 front 6 7 front Rear A 1 4 rear rear 3 C 2 A B 空队列 A 进队 B, C 进队 C 2 A 退队 B front rear C 2 B 退队 0 1 front F G H I E D C 3 2 队满 front rear

38 程序 4-8 CircleQueue 类的定义 template <class Type > class CircleQueue { private: Type *q; int front, rear, size; public: CircleQueue(int maxsize) { size = maxsize; q = new Type[size]; front = 0, rear = 0; ~CircleQueue() { delete [size]q; int enqueue(type x) // 结点 x 进队 { rear = (rear + 1) % size; if(rear ==front) { if(rear == 0) rear = size - 1; else rear--; return 1; // 队满, 不能进队, 返回 1 q[rear] = x; return 0; int dequeue(type* py) { if(front == rear) return 1; // 队空不能出队 front = (front + 1) % size; *py = q[front]; return 0;

39 说明在到达队满状态时, 实际还有一个空闲存储单元如果不想让这个单元空闲, 则队满和队空的状态都是 front == rear 为了区别, 就需要加一个标志, 当 front == rear 时, 根据这个标志判断队列是满还是空但这增加了计算工作, 在频繁使用的队列中一般不提倡使用

40 程序 4-9 带标记的循环队列的进队和出队操作 ( 略 )

41 双向队列允许在两端进行插入和删除的线性表称为双向队列双向队列没有队首和队尾之分, 可用两个指针 left 和 right 分别指向双向队列中左端和右端结点双向队列空的标志为 left>right 为了使得左右两端在一开始都能进行插入, 取中间位置 m = (MAXN 1)/2, 并置 left = m + 1, right = m 作为双向队列的初始状态左端满的标志为 left = 0; 右端满的标志为 right = MAXN 1 在一端满而另一端不满的情况下, 为了使得在满的一端能插入新结点, 可以把整个队列向不满的一端移动如要避免整个队列的移动, 还可把存放双向队列的数组首尾元素连接起来, 构成环形双向队列如固定一端不动, 插入和删除都在另一端进行, 这样的双向队列就是一个栈 ; 如果双向队列一端可以进行插入和删除, 而另一端只能进行删除, 这样的双向队列称为限制输入的双向队列 ; 如果双向队列一端可以进行插入和删除, 而另一端只能进行插入, 这样的双向队列称为限制输出的双向队列

42 队列的链接存储表示链式队列 front rear 队头在链头, 队尾在链尾进队时只要内存有空间就无队满问题操作时要检查队空, 队空条件为 front == NULL

43 程序 4-10 用链表实现的队列的类定义 template <class Type> struct node { Type data; struct node *link; template <class Type> class LinkedQueue { typedef node<type> NODE; private: NODE *head, *tail; public: LinkedQueue() { head = tail = NULL; void enqueue(type x) { NODE *p; p = new NODE(); p->data = x; p->link = NULL; if(head == NULL) head = p; else tail->link = p; tail = p; int dequeue(type *py) { NODE *p; if(head == NULL) return 1; *py = head->data; p = head; head = head->link; delete p; return 0;

44 优先级队列优先级队列 : 每次选择队列中具有最高优先级的元素出队常用于各种形式的调度优先级一般用数字表示, 数字越小, 优先级越高最高优先级的元素同时有多个时, 按它们在队列中的先后顺序出队例 : 优先级及出队顺序编号优先级出队顺序

45 优先级队列的定义 template <class T> class PrQueue { protected: T *elements; // 存放数组, 内容为元素优先级 int count; // 队列元素计数 int maxsize; // 最大元素个数 public: PrQueue (int sz) : maxsize(sz), count(0){ elements = new T[maxSize]; ; // 构造函数 ~PrQueue ( ) {delete [] elements; ; // 析构函数 virtual int enqueue (const T& x); // 进队 virtual int dequeue (T& x) ; // 出队

46 优先级队列的存储表示和实现 template <class T> bool PrQueue<T> :: enqueue (const T& x){ if( count == maxsize) return false; // 队满 for ( int j = count-1; j >= 0; j-- ) // 向前找插入位 if ( elements[j] <= x ) break; else elements[j+1] = elements[j]; elements[j+1] = x; count++;

47 template <class T> bool PrQueue<T> :: dequeue (T& x) { if ( count == 0 ) return false; x = elements[0]; // 取出 0 号元素 for ( int i = 1; i < count; i++ ) elements[i-1] = elements[i]; // 整个队列前移填补空位 count--; return true;

48 队列应用队列有广泛的应用前面的迷宫问题就可用队列代替栈求解后面的树图的广度遍历中也需要用到队列以下利用队列打印杨辉 3 角形的例子来自殷人昆的数据结构

49 队列应用举例逐行打印二项展开式 (a + b) i 的系数杨辉三角形 (Pascal s triangle) 1 1 i =

50 分析第 i 行元素与第 i+1 行元素的关系 s i = t s+t i = 3 i = 从前一行的数据可以计算下一行的数据

51 从第 i 行数据计算并存放第 i+1 行数据 s=0t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1 s+t s=t s=t s=t s=t s=t s=t s=t s=t s+t s+t s+t s+t s+t s+t s+t s+t

52 利用队列打印二项展开式系数的程序 #include <stdio.h> #include <iostream.h> #include "queue.h" void YANGHVI ( int n ) { Queue q(n+1); // 队列初始化 int i = 1, j, s = k = 0, t, u; q.enqueue (i); q.enqueue (i); for ( i = 1; i <= n; i++ ) { // 逐行计算 cout << endl; q.enqueue (k); for ( j = 1; j <= i+2; j++ ) { // 下一行 q.dequeue (t); u = s + t; q.enqueue (u); s = t; if ( j!= i+2 ) cout << s << ' ';

53 小结栈表达式求值搜索与回溯队列普通队列双端队列优先级队列

54 进阶导读介绍了 STL 中的栈和队列的实现接口定义与传统教科书上的有些差异思考 :STL 中为什么这样设计? 有什么好处?

ebook39-5

ebook39-5 5 3 last-in-first-out, LIFO 3-1 L i n e a r L i s t 3-8 C h a i n 3 3. 8. 3 C + + 5.1 [ ] s t a c k t o p b o t t o m 5-1a 5-1a E D 5-1b 5-1b E E 5-1a 5-1b 5-1c E t o p D t o p D C C B B B t o p A b o