第三章 栈和队列.

Presentation on theme: "第三章 栈和队列."— Presentation transcript:

1 第三章 栈和队列

2 插 入 删 除 线性表 Insert(L, i, x) Delete(L, i) (1≤ i≤ n+1) (1≤ i ≤n) Insert(L, n+1, x) Delete(L, n) Insert(L, n+1, x) Delete(L, 1) 栈 队 列 栈和队列可以看成是“插入” 和“删除” 受限定的线性表。

3 3.1 栈的类型定义 3.2 栈的应用举例 3.3 栈类型的实现 3.4 队列的类型定义 3.5 队列类型的实现 3.6 队列的应用举例

4 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
栈是限定只能在表尾进行插入和删除的线性表。 ADT Stack { }ADT Stack 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } 约定an端为栈顶，a1端为栈底 基本操作：

5 StackTraverse (S, visit( ))
InitStack (&S) (构造空栈 ) DestroyStack(&S) (销毁栈结构) ClearStack (&S) (栈清空) StackEmpty (S) (判空) StackLength(S) (求栈长) GetTop (S, &e) (求栈顶元素) Push (&S, e) (入栈) Pop (&S, &e) (出栈) StackTraverse (S, visit( )) (遍历栈)

6 GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 a1 a2 … … an

7 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入 e 为 栈 S 中新的 栈顶元素。 a1 a2 … … an e

8 Pop(&S, &e) a1 a2 … … an-1 an 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素,
并将它从栈中删除。 a1 a2 … … an-1 an

9 例一、 数制转换 例二、 括号匹配的检验 例三、 迷宫求解 例四、 表达式求值 例五、 实现递归

10 数制转换的原理为： N = (N div d)×d + N mod d
例如：（1348)10 转换成 (2504)8 的运算过程如下： N N div 8 N mod 8 计算顺序 输出顺序

11 void conversion ( ) { // 显示和输入的十进制数对应的八进制数值 InitStack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } // conversion

12 检验含两种括弧的表达式中括弧匹配的正确性。
如表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的匹配， ［（］）或（［（）] 或 [ ( ) ] ) 均为不正确的匹配。 检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之 。

13 [ ( [ ] [ ( ) ] ) ] 例如 考虑下列括号序列： 可见，括弧匹配也遵循“后进先出”的规律。 如何表示下列“不匹配” 的情况？
到来的右括弧非是所“期待”的; 来了一个“不速之客”; 直到结束，也没有等到“期待”的匹配;

14 算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空？ 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较，
若相匹配，则“左括弧出栈” 否则表明不匹配 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余。

15 bool matching(char exp[], int n) {
// 检测长度为 n 的字符序列 exp 中的括弧是否匹配 int i = 0; mat = true; InitStack(S); while ( i<n && mat ) { switch of exp[i] { case 左括弧:{ Push(S,exp[i]); i++; break; } case  )  : { if ( !StackEmpty(S) && GetTop(S) == ( ) { Pop(S, e); i++; } else {mat = false;} break; } //case ) … …

16 计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。

17 # Q

18 # Q

19 结论: 1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北的方向，依着某个走得通的方向继续往前直到出口为止； 2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；

20 求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。

21 求迷宫中一条从入口到出口的路径的算法： 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶；
若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { ｝while (栈不空）； … …

22 若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置；// 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ｝ 若栈空，则表明迷宫没有通路。

23 假设限于二元运算符的表达式的定义为: 表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数 算术运算的规则为: 先乘除后加减; 先左后右; 先括弧内后括弧外; 4+68/(24+54/6) = 8  33

24 设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法
表达式的三种标识方法： 设 Exp = S1 + OP + S2 则称 OP + S1 + S 为前缀表示法 S1 + OP + S 为中缀表示法 S1 + S2 + OP 为后缀表示法

25 例如: Exp = a  b + (c  d / e)  f 前缀式: +  a b   c / d e f
结论: 5) 后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式; 4) 前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式; 1）操作数之间的相对次序不变; 3）中缀式丢失了括弧信息，致使运算的次序被改变; 2）运算符的相对次序不同;

26 如何从后缀式求值？ 先找运算符， 再找操作数 例如： a b  c d e /  f  + c-d/e ab d/e

27 如何从原表达式求得后缀式？ 原表达式: a + b  c  d / e  f 后缀式: a b c  + d e / f  
分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b  c  d / e  f 后缀式: a b c  + d e / f   在后缀式中，优先权高的运算符领先于优先数权的运算符出现。 每个运算符的运算次序要由它之后的一个运算符来定。

28 从原表达式求得后缀式的规律为： 1) 设立暂存运算符的栈; 2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#” 3) 若当前字符是操作数， 则直接发送给后缀式;

29 从原表达式求得后缀式的规律为： 4) 若当前运算符的优先数高于栈顶运算符，则进栈; 5) 否则，退出栈顶运算符发送给后缀式; 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。

30 a  ( b  ( c + d / e ) - f ) # a b c d e / +  f -  # / / + + (   - (  #

31 … … void transform(char suffix[ ], char exp[ ] ) {
InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S)) { if (!IN(ch, OP)) Pass( Suffix, ch); else { } if ( ch!= # ) { p++; ch = *p; } } // while } // CrtExptree … …

32 switch (ch) { case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) { Pass( Suffix, c); Pop(S, c) } break; defult : while(Gettop(S, c) && ( precede(c,ch))) { Pass( Suffix, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); } // switch

33 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前， 需先完成三项任务：
将所有的实在参数、返回地址等信息传递给被调用函数保存; 为被调用函数的局部变量分配存储区; 将控制转移到被调用函数的入口。

34 从被调用函数返回调用函数之前，应该完成下列三项任务：
保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转移到调用函数。

35 多个函数嵌套调用的规则是: 后调用先返回 ！ 此时的内存管理实行“栈式管理” 例如：
void main( ){ void a( ){ void b( ){ … … … a( ); b( ); c( ); … … }//main }// a }// b 函数b的数据区 函数c的数据区 函数a的数据区 main的数据区

36 递归函数执行的过程可视为同一函数进行嵌套调用，例如：
递归工作栈：递归过程执行过程中占用的 数据区。 递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。

37 void hanoi (int n, char x, char y, char z) {
// 将塔座x上按直径由小到大且至上而下编号为1至n // 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n==1) move(x, 1, z); // 将编号为１的圆盘从x移到z 3 else { hanoi(n-1, x, z, y); // 将x上编号为１至n-1的 //圆盘移到y, z 作辅助塔 move(x, n, z); // 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); // 将y上编号为１至n-1的 //圆盘移到z, x作辅助塔 7 }//else 8}

38 void hanoi (int n, char x, char y, char z)
{ 1 if (n==1) 2 move(x, 1, z); 3 else { 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 } 8 } c a b a b c a c b a b c 返址 n x y z

39 一、顺序栈 // 结构定义 typedef struct { ElemType *base; int top; int stacksize;
S.base S.top S.stacksize

40 二、链栈 S.top // 结构定义 typedef struct { LNode *top; // 栈顶指针 int length;
an an-1 a1  // 结构定义 typedef struct { LNode *top; // 栈顶指针 int length; // 栈的长度 }Stack

41 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
队列是限定只能在表尾进行插入和在表头进行删除的线性表。 ADT Queue { }ADT Queue 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } 约定an端为队尾，a1端为队头 基本操作：

42 QueueTraverse (Q, visit( ))
InitQueue (&Q) (构造空队列 ) DestroyQueue(&Q) (销毁队列结构) ClearQueue (&Q) (队列清空) QueueEmpty (Q) (判队空) QueueLength(Q) (求队列长度) GetHead (Q, &e) (求队头元素) EnQueue (&Q, e) (入队列) DeQueue (&Q, &e) (出队列) QueueTraverse (Q, visit( )) (遍历队列)

43 一、链队列 … 空队列 结构定义 typedef SLink QueuePtr; Q.front Q.rear Q.front Q.rear
∧ … a1 an Q.front Q.rear 空队列 Q.front ∧ a1 Q.rear 结构定义 typedef SLink QueuePtr; typedef struct { QueuePtr front; // 队列的头指针 QueuePtr rear; // 队列的尾指针 int length; }Queue; // 链队列

44 bool InitQueue (Queue &Q) { // 构造一个空队列 Q, 若空间分配失败，
基本操作接口(函数声明) bool InitQueue (Queue &Q) { // 构造一个空队列 Q, 若空间分配失败， // 则返回 FALSE, 否则返回TRUE; } Q.front = Q.rear = new Lnode; if (!Q.front) return FALSE; Q.front->next = NULL; Q.length = 0; return TRUE;

45 入队列操作 ∧ e s a1 ∧ an … Q.front Q.rear

46 bool EnQueue (Queue &Q, QElemType e) {
//若存储分配成功，则在当前队列的尾元素之 //后插入 e为新的队列尾元素，并返回 TRUE, // 否则返回 FALSE } s = new LNode; if ( !s ) return FALSE; // 存储分配失败 s->data = e; s->next = NULL; Q.rear->next = s; // 修改尾结点的指针 Q.rear = s; // 移动队尾指针 ++Q.length; // 队列长度增 1 return TRUE;

47 a1 a2 an … Q.front Q.rear ∧ 出队列操作 p an Q.front Q.rear ∧ Q.rear p ∧

48 bool DeQueue (Queue &Q, QElemType &e) { // 若队列不空，则删除当前队列Q中的头元素，
//用e返回其值，并返回TRUE；否则返回FALSE }//DeQueue if ( Q.front == Q.rear ) // 队列为空 return FALSE; p = Q.front->next; e = p->data; // 返回被删元素 Q.front->next = p->next; // 修改头结点指针 delete p; // 释放被删结点 return TRUE; if (Q.rear == p) Q.rear = Q.front;

49 二、循环队列 ——队列的顺序映象 // 结构定义 typedef struct { QElemType *elem; // 存储空间基址
int rear; // 队尾指针 int front; // 队头指针 int queuesize; // 允许的最大存储空间 } Queue; // 基本操作接口(函数声明)

50 Q.elem e f g Q.rear Q.front Q.rear Q.rear Q.elem Q.front Q.front
1 2 3 4 5 6 7 8 a b c d Q.elem e f g Q.rear Q.front Q.rear Q.rear 1 2 3 4 5 6 7 8 a b c d Q.elem Q.front Q.front Q.front Q.front Q.front Q.rear 1 2 3 4 5 6 7 8 a b c d e f g Q.elem h j Q.rear Q.rear Q.rear Q.front

51 bool InitQueue (SqQueue &Q，int maxsize ){
//构造一个最大存储空间为maxsize的空队列Q }//InitQueue if (maxsize == 0) maxsize = MAXLISTSIZE; Q.elem = new QElemType[maxsize]; // 为循环队列分配存储空间 if (!Q.elem) return FALSE; // 存储分配失败 Q.queuesize = maxsize; Q.front = Q.rear = 0; return TRUE;

52 bool DeQueue (Queue &Q, QElemType &e) {
//用e返回其值并返回TRUE；否则返回FALSE } if (Q.front == Q.rear) return FALSE; e = Q.elem[Q.front]; Q.front = (Q.front+1) % Q.queuesize; return TRUE;

53 bool EnQueue (Queue &Q, QElemType e) {
// 若当前队列不满，这在当前队列的尾元素 //之后插入元素 e 为新的队列尾元素, // 并返回TRUE,否则返回FALSE Q.elem[Q.rear] = e; Q.rear = (Q.rear+1) % Q.queuesize; return TRUE; } if ((Q.rear + 1) % Q.queuesize == Q.front ) return FALSE;

54 —循环队列应用举例 编写“逐行输出前 n 行二项式系数”的算法。 二项式系数表 第 1 行 1 1 第 2 行 1 2 1
第 1 行 第 2 行 第 3 行 第 4 行 … … … … … … 设第 i-1 行的值: (a[0]=0) a[1], …a[i], (a[i+1]=0) 则第 i 行的系数: b[j] = a[j-1]+a[j], j=1,2,…,i

55 s + e = 利用“循环队列”计算二项式系数的过程 输出: 1 1 2 1 1 2 1 1 1 1 1 3 1 2 1 3 1 do {
2 1 1 1 1 1 3 1 2 1 3 1 do { DeQueue(Q, s); GetHead(Q, e); if (e!=0) cout << e; EnQueue(Q, s+e); } while (e!=0); 1 2 3 4 5 1 1 3 3 1 1 2 Q.rear Q.rear Q.front Q.rear Q.front Q.rear Q.front Q.rear Q.front Q.front Q.rear Q.rear Q.rear Q.front Q.rear Q.rear Q.front Q.front 输出: 1 1 1 2 1

56 void yanghui ( int n ) { // 打印输出杨辉三角的前 n ( n > 0 )行 Queue Q; InitQueue(Q, n+2); EnQueue(Q, 0 ); // 添加行界值 EnQueue( Q, 1); EnQueue_Sq ( Q, 1 ); k = 1; while ( k < n ) { EnQueue ( Q, 0 ); // 行界值“0”入队列 do { // 输出第 k 行，计算第 k+1 行} while (e!=0); k++; }//while } // yanghui … … …

57 DeQueue ( Q, e ); // 行界值“0”出队列
while (!QueueEmpty (Q) ) { // 单独处理第 n 行的值的输出 DeQueue_Sq ( Q, e ); cout<<e<<‘ ’； }//while

58 　1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。
　2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。 　3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。