第3章 栈和队列 丽水学院工学院.

Presentation on theme: "第3章 栈和队列 丽水学院工学院."— Presentation transcript:

1 第3章 栈和队列 丽水学院工学院

2 教学内容 3.1 栈和队列的定义和特点 3.2 案例引入 3.3 栈的表示和操作的实现 3.4 栈与递归 3.5 队列的表示和操作的实现
3.6 案例分析与实现 2018年12月6日

3 教学目标 第3章 栈和队列 掌握栈和队列的特点，并能在相应的应用问题中正确选用
第3章　栈和队列 教学目标 掌握栈和队列的特点，并能在相应的应用问题中正确选用 熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件 理解递归算法执行过程中栈的状态变化过程 掌握表达式求值 方法 北京林业大学信息学院 2018年12月6日

4 栈（Stack） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 队列（Queue） 1. 定义 2. 逻辑结构
2018年12月6日

5 栈 用铁路调度站表示栈 2018年12月6日

6 3.1 栈和队列的定义和特点 栈 只能在表的一端（栈顶）进行插入和删除运算的线性表 1. 定义 2. 逻辑结构 与线性表相同，仍为一对一关系
3.1 　栈和队列的定义和特点 栈 只能在表的一端（栈顶）进行插入和删除运算的线性表 1. 定义 与线性表相同，仍为一对一关系 2. 逻辑结构 用顺序栈或链栈存储均可，但以顺序栈更常见 3. 存储结构 2018年12月6日

7 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则
4.运算规则 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同 基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等 5.实现方式 2018年12月6日

8 ... a1 a2 a3 an 队列是一种先进先出(FIFO) 的线性表. 在表一端插入,在另一端删除 入队列 队尾 队头
2018年12月6日

9 出队列 ... a1 a2 a3 an 队头 队尾 2018年12月6日

10 出队列 ... a1 a2 a3 an 队头 队尾 2018年12月6日

11 出队列 ... a1 a2 a3 an 队头 队尾 2018年12月6日

12 3.1 栈和队列的定义和特点 队列 只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表 1. 定义 2. 逻辑结构
3.1 　栈和队列的定义和特点 队列 只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表 1. 定义 与线性表相同，仍为一对一关系 2. 逻辑结构 用顺序队列或链队存储均可 3. 存储结构 2018年12月6日

13 关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同 5.实现方式
4.运算规则 先进先出（FIFO） 关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同 5.实现方式 2018年12月6日

14 栈、队列与一般线性表的区别 栈 一般线性表 队列 栈、队列是一种特殊（操作受限）的线性表 区别：仅在于运算规则不同 逻辑结构：一对一
存储结构：顺序栈、链栈 运算规则：后进先出 一般线性表 逻辑结构：一对一 存储结构：顺序表、链表 运算规则：随机、顺序存取 队列 逻辑结构：一对一 存储结构：顺序队、链队 运算规则：先进先出 2018年12月6日

15 3.2 案例引入 案例3.1 ：数制的转换 案例3.2：括号匹配的检验 案例3.3 ：表达式求值 案例3.4 ：舞伴问题

16 3.3 栈的表示和操作的实现 “进” ＝压入=PUSH（) “出” ＝弹出=POP( ) 2018年12月6日

17 顺序栈与顺序表 前提：一定要预设栈顶指针top！ an+1 写入：v[i]= ai 读出： x= v[i] a1 a2 ai an ……
顺序表V[n] a1 a2 …… an 顺序栈S ai 表头 表尾 an+1 低地址 高地址 v[i] 低地址 高地址 栈底base 栈顶top 写入：v[i]= ai 读出： x= v[i] 压入：PUSH (an+1) 弹出： POP (x) 前提：一定要预设栈顶指针top！ 2018年12月6日

18 顺序栈的表示 栈满时的处理方法： 1、报错,返回操作系统。 2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。 空栈
top base A B C D base top 3 1 2 top A base base top A B A B C top base 空栈 base == top 是栈空标志 stacksize = 4 top 指示真正的栈顶元素之上的下标地址 栈满时的处理方法： 1、报错,返回操作系统。 2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。 2018年12月6日

19 顺序栈的表示 #define MAXSIZE 100 typedef struct { SElemType *base;
SElemType *top; int stacksize; }SqStack; 2018年12月6日

20 s 顺序栈初始化 构造一个空栈 步骤： (1)分配空间并检查空间是否分配失败，若失败则返回错误 (2)设置栈底和栈顶指针
base stacksize top 构造一个空栈 步骤： (1)分配空间并检查空间是否分配失败，若失败则返回错误 s (2)设置栈底和栈顶指针 S.top = S.base; (3)设置栈大小 2018年12月6日

21 顺序栈初始化 Status InitStack( SqStack &S ) {
S.base =new SElemType[MAXSIZE]； if( !S.base ) return OVERFLOW; S.top = S.base; S.stackSize = MAXSIZE; return OK; } 2018年12月6日

22 bool StackEmpty( SqStack S ) { if(S.top == S.base) return true;
判断顺序栈是否为空 bool StackEmpty( SqStack S ) { if(S.top == S.base) return true; else return false; } base top 3 1 2 2018年12月6日

23 int StackLength( SqStack S ) { return S.top – S.base; }
求顺序栈的长度 int StackLength( SqStack S ) { return S.top – S.base; } base top A B 2018年12月6日

24 清空顺序栈 Status ClearStack( SqStack S ) { if( S.base ) S.top = S.base;
return OK; } base top 3 1 2 2018年12月6日

25 销毁顺序栈 Status DestroyStack( SqStack &S ) { if( S.base ) delete S.base ;
S.stacksize = 0; S.base = S.top = NULL; } return OK; 2018年12月6日

26 顺序栈进栈 (1)判断是否栈满，若满则出错 (2)元素e压入栈顶 (3)栈顶指针加1 *S.top=e;
A B C top base Status Push( SqStack &S, SElemType e) { if( S.top - S.base== S.stacksize ) // 栈满 return ERROR; *S.top++=e; return OK; } *S.top=e; S.top++; 2018年12月6日

27 顺序栈出栈 (1)判断是否栈空，若空则出错 (2)获取栈顶元素e (3)栈顶指针减1 --S.top; e=*S.top;
A B C top base Status Pop( SqStack &S, SElemType &e) { if( S.top == S.base ) // 栈空 return ERROR; e＝ *--S.top; return OK; } --S.top; e=*S.top; 2018年12月6日

28 取顺序栈栈顶元素 判断是否空栈，若空则返回错误 否则通过栈顶指针获取栈顶元素 e = *( S.top -- ); ???
A B C top base 判断是否空栈，若空则返回错误 否则通过栈顶指针获取栈顶元素 Status GetTop( SqStack S, SElemType &e) { if( S.top == S.base ) return ERROR; // 栈空 e = *( S.top – 1 ); return OK; } e = *( S.top -- ); ??? 2018年12月6日

29 练习 1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？ 435612中到了12顺序不能实现；
135426可以实现。 2018年12月6日

30 练习 Ｃ Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定
2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ｃ Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 2018年12月6日

31 练习 D Ａ． top不变 Ｂ． top=0 Ｃ． top++ Ｄ． top--
3.在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为　 D Ａ． top不变 Ｂ． top=0 Ｃ． top++ Ｄ． top-- 2018年12月6日

32 typedef struct StackNode { SElemType data; struct StackNode *next;
链栈的表示 运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针 data next 栈顶 栈底 ∧ S typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack; LinkStack S; 2018年12月6日

33 void InitStack(LinkStack &S ) { S=NULL; }
链栈的初始化 ∧ S void InitStack(LinkStack &S ) { S=NULL; } 2018年12月6日

34 判断链栈是否为空 Status StackEmpty(LinkStack S) { if (S==NULL) return TRUE; else return FALSE; } 2018年12月6日

35 链栈进栈 p ∧ S Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月6日

36 链栈进栈 p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月6日

37 链栈进栈 p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月6日

38 链栈进栈 S p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月6日

39 e = S-> data; p = S; S = S-> next;
链栈出栈 ∧ S A e = ‘A’ Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月6日

40 e = S-> data; p = S; S = S-> next;
链栈出栈 ∧ S A e = ‘A’ p Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月6日

41 e = S-> data; p = S; S = S-> next;
链栈出栈 ∧ S A e = ‘A’ p S Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月6日

42 e = S-> data; p = S; S = S-> next;
链栈出栈 e = ‘A’ S ∧ Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月6日

43 SElemType GetTop(LinkStack S) {
取链栈栈顶元素 SElemType GetTop(LinkStack S) { if (S==NULL) exit(1)； else return S–>data; } 2018年12月6日

44 3.4 　栈与递归 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 long Fact ( long n ) { if ( n == 0) return 1; else return n * Fact (n-1); } 2018年12月6日

45 有人送了我金、银、铜、铁、木五个宝箱，我想打开金箱子，却没有打开这个箱子的钥匙。 在金箱子上面写着一句话：“打开我的钥匙装在银箱子里。”
于是我来到银箱子前，发现还是没有打开银箱子的钥匙。 银箱子上也写着一句话：“打开我的钥匙装在铜箱子里。” 于是我再来到铜箱子前，发现还是没有打开铜箱子的钥匙。 铜箱子上也写着一句话：“打开我的钥匙装在铁箱子里。” 于是我又来到了铁箱子前，发现还是没有打开铁箱子的钥匙。 铁箱子上也写着一句话：“打开我的钥匙装在木箱子里。” 2018年12月6日

46 并从木箱里拿出铁箱子的钥匙，打开了铁箱， 从铁箱里拿了出铜箱的钥匙，打开了铜箱， 再从铜箱里拿出银箱的钥匙打开了银箱，
我来到木箱子前，打开了木箱， 并从木箱里拿出铁箱子的钥匙，打开了铁箱， 从铁箱里拿了出铜箱的钥匙，打开了铜箱， 再从铜箱里拿出银箱的钥匙打开了银箱， 最后从银箱里取出金箱的钥匙，打开了我想打开的金箱子。 ……很啰嗦地讲了这么长一个故事。 2018年12月6日

47 void FindKey ( 箱子 ) { if ( 木箱子) return ; else FindKey ( 下面的箱子 ) }
2018年12月6日

48 当多个函数构成嵌套调用时, 遵循 后调用先返回 栈 2018年12月6日

49 以下三种情况常常用到递归方法 递归定义的数学函数 具有递归特性的数据结构 可递归求解的问题 2018年12月6日

50 1. 递归定义的数学函数: 阶乘函数: 2阶Fibonaci数列: 2018年12月6日

51 2. 具有递归特性的数据结构: 3. 可递归求解的问题: 树 广义表 迷宫问题 Hanoi塔问题 Root Rchild Lchild
A=(a,A) 3. 可递归求解的问题: 　迷宫问题　Hanoi塔问题 2018年12月6日

52 用分治法求解递归问题 必备的三个条件 分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的 2、可以通过上述转化而使问题简化 3、必须有一个明确的递归出口，或称递归的边界 2018年12月6日

53 else return n * Fact (n-1); //归纳项}
分治法求解递归问题算法的一般形式： void p (参数表) { if （递归结束条件）可直接求解步骤；-----基本项 else p（较小的参数）；------归纳项 } long Fact ( long n ) { if ( n == 0) return 1;//基本项 else return n * Fact (n-1); //归纳项} 2018年12月6日

54 求解阶乘 n! 的过程 if ( n == 0 ) return 1; else return n * Fact (n-1);
返回 1　参数 0 直接定值 = 1 参数传递 递归调用 结果返回 回归求值 返回 1　参数 1 计算 1*Fact(0) 返回 2　参数 2 计算 2*Fact(1) 返回 6　参数 3 计算 3*Fact(2) 返回 24 参数 4 计算 4*Fact(3) 主程序 main : Fact(4) 2018年12月6日

55 练习 D 设有一个递归算法如下: int X(int n) { if(n<=3) return 1;
else return X(n-2)+X(n-4)+1 } 则计算X(X(8))时需要计算X函数 次. D A B C D.18 2018年12月6日

56 汉诺塔 在印度圣庙里，一块黄铜板上插着三根宝石针。 主神梵天在创造世界时，在其中一根针上穿好了由大到小的64片金片，这就是汉诺塔。
僧侣不停移动这些金片，一次只移动一片，小片必在大片上面。 当所有的金片都移到另外一个针上时，世界将会灭亡。 2018年12月6日

57 A B C Hanoi塔问题 规则: (1) 每次只能移动一个圆盘 (2) 圆盘可以插在A,B和C中的任一塔座上
(3) 任何时刻不可将较大圆盘压在较小圆盘之上 2018年12月6日

58 (1)用 C 柱做过渡，将 A 的(n-1)个移到 B (2)将 A 最后一个直接移到 C
Hanoi塔问题 n = 1，则直接从 A 移到 C。否则 (1)用 C 柱做过渡，将 A 的(n-1)个移到 B (2)将 A 最后一个直接移到 C (3)用 A 做过渡，将 B 的 (n-1) 个移到 C 2018年12月6日

59 跟踪程序，给出下列程序的运行结果，以深刻地理解递归的调用和返回过程
#include<iostream.h> int c=0; void move(char x,int n,char z) {cout<<++c<<","<<n<<","<<x<<","<<z<<endl;} void Hanoi(int n,char A,char B,char C) { if(n==1) move(A,1,C); else {Hanoi(n-1,A,C,B); move(A,n,C); Hanoi(n-1,B,A,C); }} void main(){Hanoi(3,'a','b','c');} 2018年12月6日

60 递归调用树 3,a,b,c 2,a,c,b 2,b,a,c ③,a->c ①,a->c 1,a,b,c 1,c,a,b
2018年12月6日

61 函数调用过程 调用前, 系统完成: (1)将实参,返回地址等传递给被调用函数 (2)为被调用函数的局部变量分配存储区
(3)将控制转移到被调用函数的入口 调用后, 系统完成: (1)保存被调用函数的计算结果 (2)释放被调用函数的数据区 (3)依照被调用函数保存的返回地址将控制转移到调用函数 2018年12月6日

62 递归函数调用的实现 “层次” “递归工作栈” “工作记录” 实在参数,局部变量,返回地址 主函数 第1次调用 第 i 次调用 0层 1层
2018年12月6日

63 递归算法的效率分析 空间效率 与递归树的深度成正比 O(n) 与递归树的结点数成正比 时间效率 O(2n) 2018年12月6日

64 f(n) = 20+21+…+2n-2+ 2n-1f(1) = 2n-1
递归算法的效率分析 f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15 f(n) = 2f(n-1)+1 f(n-1) = 2f(n-2)+1 f(n-2) = 2f(n-3)+1 ...... f(3) = 2f(2)+1 f(2) = 2f(1)+1 20f(n) = 21f(n-1)+20 21f(n-1) = 22f(n-2)+21 22f(n-2) = 23f(n-3)+22 ...... 2n-3f(3) = 2n-2f(2)+ 2n-3 2n-2f(2) = 2n-1f(1)+ 2n-2 f(n) = …+2n-2+ 2n-1f(1) = 2n-1 2018年12月6日

65 64片金片移动次数：264-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？
一年大约有 秒，移完这些金片需要５８００多亿年 世界、梵塔、庙宇和众生都已经灰飞烟灭 …… 2018年12月6日

66 递归的优缺点 优点：结构清晰，程序易读 缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。
递归非递归 2018年12月6日

67 递归巩固练习1 输入一个整数，输出对应的2进制形式 void conversion(int n) { if(n==0) return ;
else { } } void main() { int n; cin>>n; conversion(n); cout<<endl;} if(n>0) {conversion(n/2); cout<<n%2;} conversion(n/2); cout<<n%2; 2018年12月6日

68 if(n>0) { conversion(n/2); cout<<n%2;} void conversion(int n)
{ if(n==1) cout<<n%2; else { conversion(n/2); cout<<n%2; }} if(n>0) { conversion(n/2); cout<<n%2;} 2018年12月6日

69 { n=n/2; conversion(n); cout<<n%2; }
if(n==0) return ; else { n=n/2; conversion(n); cout<<n%2; } if(n==0) return ; else { int i=n%2; conversion(n/2); cout<<i; } 2018年12月6日

70 3.5 　队列的表示和操作的实现 练习 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。 B （A）2 （B） （C）4 （D）6 2018年12月6日

71 队列的抽象数据类型 ADT Queue { 数据对象: 数据关系: 基本操作: (2) DestroyQueue (&Q) //销毁队列
(1) InitQueue (&Q) //构造空队列 (2) DestroyQueue (&Q) //销毁队列 (3) ClearQueue (&S) //清空队列 (4) QueueEmpty(S) //判空. 空--TRUE, 2018年12月6日

72 队列的抽象数据类型 (5) QueueLength(Q) //取队列长度 (6) GetHead (Q,&e) //取队头元素,
(7) EnQueue (&Q,e) //入队列 (8) DeQueue (&Q,&e) //出队列 (9) QueueTraverse(Q,visit()) //遍历 }ADT Queue 2018年12月6日

73 队列的顺序表示－－用一维数组base[M]
#define M //最大队列长度 Typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue; 2018年12月6日

74 队列的顺序表示－－用一维数组base[M]
Q.front Q.rear J 5 6 Q.front 1 2 3 4 5 Q.rear Q.front Q.rear J 3 Q.front Q.rear J 1 2 3 front=rear=0 空队标志：front= =rear 入队：base[rear++]=x; 出队：x=base[front++]; 2018年12月6日

75 存在的问题 设大小为M front0 front=0 rear=M时 rear=M时 再入队—假溢出 再入队—真溢出 5 4 3 2 1
Q.front 1 2 3 4 5 Q.rear J5 J6 J1 J2 J3 J4 Q.front Q.rear J5 J6 front0 rear=M时 再入队—假溢出 front=0 rear=M时 再入队—真溢出 2018年12月6日

76 2018年12月6日

77 解决的方法－－循环队列 base[0]接在base[M-1]之后 若rear+1==M 则令rear=0; 实现：利用“模”运算 入队：
Q.rear Q.front ... 实现：利用“模”运算 入队： base[rear]=x; rear=(rear+1)%M; 出队： x=base[front]; front=(front+1)%M; 2018年12月6日

78 队空：front==rear 队满：front==rear
1 2 3 4 5 front J4,J5,J6出队 rear J4 J5 J6 1 2 3 4 5 front J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 rear 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front 北京林业大学信息学院 2018年12月6日

79 循环队列 #define MAXQSIZE 100 //最大长度 Typedef struct {
QElemType *base; //初始化的动态分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue; 2018年12月6日

80 循环队列初始化 Status InitQueue (SqQueue &Q){ Q.base =new QElemType[MAXQSIZE]
if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; } 2018年12月6日

81 求循环队列的长度 int QueueLength (SqQueue Q){
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } 2018年12月6日

82 循环队列入队 Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } 2018年12月6日

83 循环队列出队 Status DeQueue (LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; } 2018年12月6日

84 链队列 . data next 队头 队尾 Q.front Q.rear 2018年12月6日

85 链队列 typedef struct QNode{ QElemType data; struct Qnode *next;
}Qnode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; 2018年12月6日

86 链队列 (a) 空队列 (b) 元素x入队列 (c) 元素y入队列 (d) 元素x出队列 2018年12月6日

87 链队列初始化 Status InitQueue (LinkQueue &Q){
Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front->next=NULL; return OK; } 2018年12月6日

88 销毁链队列 Status DestroyQueue (LinkQueue &Q){ while(Q.front){
Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK; } 2018年12月6日

89 判断链队列是否为空 Status QueueEmpty (LinkQueue Q){ return (Q.front==Q.rear); }
2018年12月6日

90 求链队列的队头元素 Status GetHead (LinkQueue Q, QElemType &e){
if(Q.front==Q.rear) return ERROR; e=Q.front->next->data; return OK; } 2018年12月6日

91 链队列入队 Status EnQueue(LinkQueue &Q,QElemType e){
p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } p 2018年12月6日

92 链队列出队 Status DeQueue (LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; delete p; return OK; } p 2018年12月6日

93 3.6 案例分析与实现 案例3.1 ：数制的转换 【算法步骤】 ① 初始化一个空栈S。 ② 当十进制数N非零时，循环执行以下操作：
把N与8求余得到的八进制数压入栈S； N更新为N与8的商。 ③ 当栈S非空时，循环执行以下操作： 弹出栈顶元素e； 输出e。 2018年12月6日

94 案例3.1 ：数制的转换 【算法描述】 void conversion(int N)
{//对于任意一个非负十进制数，打印输出与其等值的八进制数 InitStack(S); //初始化空栈S while(N) //当N非零时,循环 { Push(S,N%8); //把N与8求余得到的八进制数压入栈S N=N/8; //N更新为N与8的商 } while(!StackEmpty(S))//当栈S非空时，循环 Pop(S,e); //弹出栈顶元素e cout<<e; //输出e 2018年12月6日

95 案例3.2 ：括号的匹配 【算法步骤】 ① 初始化一个空栈S。
② 设置一标记性变量flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，flag初值为1。 ③ 扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作： 若ch是左括号“[”或“(”，则将其压入栈； 若ch是右括号“)”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“(”，则正确匹配，否则错误匹配，flag置为0； 若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“[”，则正确匹配，否则错误匹配，flag置为0。 ④ 退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。 2018年12月6日

96 案例3.3 ：表达式求值 算术四则运算规则 (1) 先乘除,后加减 (2) 从左算到右 (3) 先括号内,后括号外 2018年12月6日

97 常数 操作数(operand) 标识符 算术 表达式 运算符(operator) 逻辑 关系 括号 界限符(delimiter) 结束符
2018年12月6日

98 表3.1 算符间的优先关系 > > < < < > > > > < <
表3.1　算符间的优先关系 > > < < < > > > > < < < > > > > > > < > > > > > > < > > < < < < < = x > > > > x > > x < < < < < = 2018年12月6日

99 【算法步骤】 设定两栈 ：OPND-----操作数或运算结果 OPTR------运算符
① 初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。 ② 扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作： 若ch不是运算符，则压入OPND栈，读入下一字符ch； 若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理： 若是小于，则ch压入OPTR栈，读入下一字符ch； 若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈； 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于括号匹配成功，然后读入下一字符ch。 ③ OPND栈顶元素即为表达式求值结果，返回此元素。 2018年12月6日

100 OperandType EvaluateExpression( ) {
InitStack (OPTR); Push (OPTR，'#') ; InitStack (OPND); ch = getchar( ); while (ch!= '#' || GetTop(OPTR)! = '#') { if (! In(ch)){Push(OPND,ch); ch = getchar(); } // ch不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch)) { //比较优先权 case '<' : //当前字符ch压入OPTR栈，读入下一字符ch Push(OPTR, ch); ch = getchar(); break; case '>' : //弹出OPTR栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; case '=' : //脱括号并接收下一字符 Pop(OPTR,x); ch = getchar(); break; } // switch } // while return GetTop(OPND);} // EvaluateExpression 北京林业大学信息学院 2018年12月6日

101 OPTR OPND INPUT OPERATE 3*(7-2)# Push(opnd,’3’) # *(7-2)# 3 #
Push(optr,’*’) #,* 3 (7-2)# Push(optr,’(’) #,*,( 3 7-2)# Push(opnd,’7’) #,*,( 3,7 -2)# Push(optr,’-’) #,*,(,－ 3,7 2)# Push(opnd,’2’) #,*,(,－ 3,7,2 )# Operate(7-2) #,*,( 3,5 )# Pop(optr) #,* 3,5 # Operate(3*5) # 15 GetTop(opnd) 2018年12月6日

102 迷宫求解 2018年12月6日

103 求解思想：回溯法 迷宫求解 从入口出发，按某一方向向未走过的前方探索 若能走通，则到达新点，否则试探下一方向 ;
若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探 直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 2018年12月6日

104 迷宫求解 需要解决的问题： 1、表示迷宫的数据结构 2、试探方向 3、栈的设计 4、防止重复到达某点，避免发生死循环 2018年12月6日

105 迷宫求解 1、表示迷宫的数据结构 表示一个m行n列迷宫： 用maze[m][n]表示，0≤i<m,0≤j<n
maze[i][j] = 通路 maze[i][j] = 不通 改进： 用maze[m+2][n+2]表示 且maze[i][j]=1，i=0或m＋1, j=0或n＋1 入口坐标为（1，1），出口坐标为（m，n） 2018年12月6日

106 1 2 3 4 5 6 7 8 9 北京林业大学信息学院 2018年12月6日

107 迷宫求解 迷宫的定义： #define m 8 /*迷宫的实际行*/ #define n 8 /*迷宫的实际列*/
int maze [m+2][n+2] ; 2、试探方向 表示位置的类型PosType定义如下： typedef struct { int x，y; } PosType ; 2018年12月6日

108 (x-1,y) (x,y+1) (x,y-1) (x,y) (x+1,y) 迷宫求解 试探顺序规定为：从正东沿顺时针方向
2018年12月6日

109 迷宫求解 3、栈的设计 栈中每个元素的组成： 通道块在路径上的序号 坐标位置 前进方向（东为1，南为2，西为3，北为4） 栈元素的类型定义：
typedef struct { int ord; PosType seat; int di; }SElemType; 2018年12月6日

110 走过不通之处要加以标记（MarkPrint操作）
迷宫求解 4、防止重复到达某点 走过不通之处要加以标记（MarkPrint操作） 2018年12月6日

111 案例3.4 ：舞伴问题 【案例分析】 设置两个队列分别存放男士和女士入队者
假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。 当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。 此时，若某队仍有等待配对者，则输出此队列中排在队头的等待者的姓名，此人将是下一轮舞曲开始时第一个可获得舞伴的人。 2018年12月6日

112 char sex; //性别，'F'表示女性，'M'表示男性 }Person; //- - - - - 队列的顺序存储结构- - - - -
【数据结构】 // 跳舞者个人信息 typedef struct { char name[20]; //姓名 char sex; //性别，'F'表示女性，'M'表示男性 }Person; // 队列的顺序存储结构 #define MAXQSIZE 100 //队列可能达到的最大长度 Person *base; //队列中数据元素类型为Person int front; //头指针 int rear; //尾指针 }SqQueue; SqQueue Mdancers,Fdancers; //分别存放男士和女士入队者队列 2018年12月6日

113 【算法步骤】 ① 初始化Mdancers队列和Fdancers队列。
④ 如果Mdancers队列为空而Fdancers队列非空，则输出Fdancers队列的队头女士的姓名。 ⑤ 如果Fdancers队列为空而Mdancers队列非空，则输出Mdancers队列的队头男士的姓名。 2018年12月6日

114 队列的其它应用 【例】汽车加油站 结构：入口和出口为单行道，加油车道若干条n 每辆车加油都要经过三段路程，三个队列
1.入口处排队等候进入加油车道 2.在加油车道排队等候加油 3.出口处排队等候离开 若用算法模拟，需要设置n+2个队列。　 2018年12月6日

115 【例】模拟打印机缓冲区 在主机将数据输出到打印机时，主机速度与打印机的打印速度不匹配
为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入缓冲区，写满后主机转去做其他的事情 而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印 2018年12月6日

116 【例】打印杨辉三角形 2018年12月6日

117 EnQueue (q,0); //各行间插入一个0 for ( j=1; j<=i+2; j++ ) {
DeQueue (q,t ); //一个系数出队 EnQueue (q, s+t ); //计算下一行系数，并进队 s = t; if ( j != i+2 ) cout << s << ' '; //第i+2个0 } 北京林业大学信息学院 2018年12月6日

118 优先级队列(priority_queue)---堆
每次从队列中取出的是具有最高优先权的元素 任务优先权及执行顺序的关系 数字越小，优先权越高 2018年12月6日

119 80 75 40 62 73 28 35 50 38 25 47 15 大根堆 2018年12月6日

120 小结 1. 掌握栈和队列的特点，并能在相应的应用问题中正确选用 2. 熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件
3. 熟练掌握循环队列和链队列的进队出队算法，特别注意队满和队空的条件 4. 理解递归算法执行过程中栈的状态变化过程 5. 掌握表达式求值 方法 2018年12月6日

121 算法设计题 （1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：   typedef struct{   int top[2], bot[2]; //栈顶和栈底指针 　 SElemType *V; //栈数组   int m; //栈最大可容纳元素个数   }DblStack; 2018年12月6日

122 答案 //初始化一个大小为m的双向栈s Status Init_Stack(DblStack &s,int m) {
s.V=new SElemType[m]； s.bot[0]=-1; s.bot[1]=m; s.top[0]=-1; s.top[1]=m; return OK; } 2018年12月6日

123 答案 //判栈i空否, 空返回1, 否则返回0 {return s.top[i] == s.bot[i]; }
int IsEmpty(DblStack s,int i) {return s.top[i] == s.bot[i]; } //判栈满否, 满返回1, 否则返回0 int IsFull(DblStack s) { if(s.top[0]+1==s.top[1]) return 1; else return 0;} 2018年12月6日

124 答案 void Dblpush(DblStack &s,SElemType x,int i) {
if( IsFull (s ) ) exit(1); // 栈满则停止执行 if ( i == 0 ) s.V[ ++s.top[0] ] = x; //栈0情形：栈顶指针先加1, 然后按此地址进栈 else s.V[--s.top[1]]=x; //栈1情形：栈顶指针先减1, 然后按此地址进栈 } 2018年12月6日

125 答案 int Dblpop(DblStack &s,int i,SElemType &x)
{if ( IsEmpty ( s,i ) ) return 0; //判栈空否, 若栈空则函数返回0 if ( i == 0 ) s.top[0]--; //栈0情形：栈顶指针减1 else s.top[1]++; //栈1情形：栈顶指针加1 return 1; } 2018年12月6日

126 算法设计题 （10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数；
② 求链表的结点个数； ③ 求所有整数的平均值。 2018年12月6日

127 提示 void main( ){ LinkList L; CreatList(L);
int GetMax(LinkList p){//求链表中的最大整数 if(!p->next) return p->data; else { int max=GetMax(p->next); return p->data>=max ? p->data:max; } void main( ){ LinkList L; CreatList(L); cout<<"链表中的最大整数为："<<GetMax(L->next)<<endl; ……} 2018年12月6日