第三章栈和列队讲述

1、3.1 3.1 栈和队列的定义和特点栈和队列的定义和特点3.2 3.2 案例引入案例引入3.3 3.3 栈的表示和操作的实现栈的表示和操作的实现3.4 3.4 栈与递归栈与递归3.5 3.5 队列的的表示和操作的实现队列的的表示和操作的实现3.6 3.6 案例分析与实现案例分析与实现教学内容教学内容第第3 3章栈和队列章栈和队列 掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用 熟练掌握栈的熟练掌握栈的两种存储结构两种存储结构的基本操作实现的基本操作实现算法，特别应注意算法，特别应注意栈满和栈空栈满和栈空的条件的条件 熟练掌握熟练掌握循环队列

2、和链队列循环队列和链队列的基本操作实现的基本操作实现算法，特别注意算法，特别注意队满和队空队满和队空的的条件条件 理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程 掌握表掌握表达式求值的方法达式求值的方法 教学目标教学目标栈（栈（Stack）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3. 3. 存储结构存储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式队列（队列（Queue）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3. 3. 存储结构存储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式用铁路调度站表示栈用铁路调度站表示栈栈栈3

3、.1 3.1 栈和队列的定义和特点栈和队列的定义和特点1. 1. 定义定义用用顺序栈顺序栈或或链栈链栈存储均可，但以存储均可，但以顺顺序栈序栈更常见更常见3. 3. 存储结构存储结构与线性表相同，仍为与线性表相同，仍为一对一一对一关系关系2. 2. 逻辑结构逻辑结构只能在只能在表的一端表的一端（栈顶栈顶）进行插入）进行插入和删除运算的和删除运算的线性表线性表栈栈只能在只能在栈顶栈顶运算，且访问结点时依运算，且访问结点时依照照后进先出后进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）的原则的原则4.4.运算规则运算规则关键是编写关键是编写入栈入栈和和出栈出栈函数，具函数，具体实

4、现依顺序栈或链栈的不同而体实现依顺序栈或链栈的不同而不同不同基本操作有基本操作有入栈、出栈、读栈顶入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空元素值、建栈、判断栈满、栈空等等5.5.实现方式实现方式队列是一种先进先出队列是一种先进先出(FIFO) 的的线性表线性表. 在表一端插入在表一端插入,在另一在另一端删除端删除),(21naaaqa a1 1a a2 2a a3 3a an n.入队列入队列队头队头队尾队尾),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队

5、尾出队列出队列),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列3.1 3.1 栈和队列的定义和特点栈和队列的定义和特点1. 1. 定义定义用用顺序队列顺序队列或或链队链队存储均可存储均可3. 3. 存储结构存储结构与线性表相同，仍为与线性表相同，仍为一对一一对一关系关系2. 2. 逻辑结构逻辑结构只能在表的一端（只能在表的一端（队尾队尾）进行插入，）进行插入，在另一端（在另一端（队头队头）进行删除运算的）进行删除运算的线性表线性表队列队列先进先出先进先出（FIFOFIFO）4.4.运算规则运算规则关键是编写关键是编写入队入队和和出队出队函数，具

6、函数，具体实现依顺序队或链队的不同而体实现依顺序队或链队的不同而不同不同5.5.实现方式实现方式栈、队列是一种特殊（栈、队列是一种特殊（操作受限操作受限）的线性表）的线性表区别：仅在于区别：仅在于运算规则运算规则不同不同一般线性表一般线性表 逻辑结构：一对一逻辑结构：一对一 存储结构：顺序表、链表存储结构：顺序表、链表 运算规则：运算规则：随机随机、顺序存取顺序存取栈栈逻辑结构：一对一逻辑结构：一对一 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：后进先出后进先出栈、队列与一般线性表的区别栈、队列与一般线性表的区别队列队列逻辑结构：一对一逻辑结构：一对一 存储结构：顺序队、链

7、存储结构：顺序队、链队队运算规则：运算规则：先先进先出进先出3.2 3.2 案例引入案例引入案例案例3.1 3.1 ：一元多项式的运算：一元多项式的运算案例案例3.23.2：号匹配的检验：号匹配的检验案例案例3.3 3.3 ：表达式求值：表达式求值案例案例3.4 3.4 ：舞伴问题：舞伴问题3.3 3.3 栈的表示和操作的实现栈的表示和操作的实现“进进” 压入压入=PUSH=PUSH（) )“出出” 弹出弹出=POP( )=POP( ) a a1 1 a a2 2 a an n顺序栈顺序栈S S a ai i表头表头表尾表尾栈底栈底basebase栈顶栈顶toptop低地址低地址高地址高地址写

8、入：写入：vi= vi= a ai i读出：读出： x= vix= vi压入：压入：PUSH (PUSH (a an+1n+1) )弹出：弹出： POP (x)POP (x)前提：一定要预设栈顶指针前提：一定要预设栈顶指针toptop！低地址低地址高地址高地址vivi a a1 1 a a2 2 a ai i a an n 顺序表顺序表VnVn a an+1n+1顺序栈与顺序表顺序栈与顺序表顺序栈的表示顺序栈的表示空栈空栈base = topbase = top 是是栈空标志栈空标志stacksize = 4stacksize = 4topAbasebasetopABABCtopbasetop

9、baseABCDbasetop3120top top 指示真正的指示真正的栈顶元素之上栈顶元素之上的下标地址的下标地址栈满时的处理方法：栈满时的处理方法：1 1、报错报错, ,返回操作系统。返回操作系统。2 2、分配更大的空间分配更大的空间，作为栈的存储空，作为栈的存储空间间, ,将原栈的内容移入新栈。将原栈的内容移入新栈。#define MAXSIZE 100typedef structSElemType *base;SElemType *top;int stacksize;SqStack;顺序栈的表示顺序栈的表示 构造一个空栈构造一个空栈 步骤：步骤：(1)(1)分配空间并检查空间分配空间

10、并检查空间是否分配失败，若失败是否分配失败，若失败则返回错误则返回错误顺序栈初始化顺序栈初始化basestacksizetops(2)(2)设置栈底和栈顶指针设置栈底和栈顶指针 S.top = S.base;(3)(3)设置栈大小设置栈大小Status InitStack( SqStack &S )S.base =new SElemTypeMAXSIZE；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;顺序栈初始化顺序栈初始化判断顺序栈是否为空判断顺序栈是否为空bool Stack

11、Empty( SqStack S )if(S.top = S.base) return true; else return false;basetop3120求顺序栈的长度求顺序栈的长度int StackLength( SqStack S )return S.top S.base;basetopABStatus ClearStack( SqStack S )if( S.base ) S.top = S.base;return OK;清空顺序栈清空顺序栈basetop3120Status DestroyStack( SqStack &S )if( S.base )delete S.bas

12、e ;S.stacksize = 0;S.base = S.top = NULL; return OK;销毁顺序栈销毁顺序栈(1)(1)判断是否栈满，若满则出错判断是否栈满，若满则出错(2)(2)元素元素e e压入栈顶压入栈顶(3)(3)栈顶指针加栈顶指针加1 1顺序栈进栈顺序栈进栈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+;ABCtopbase(1)(1)判断是否栈空，若空

13、则出错判断是否栈空，若空则出错(2)(2)获取栈顶元素获取栈顶元素e e(3)(3)栈顶指针减栈顶指针减1 1顺序栈出栈顺序栈出栈Status Pop( SqStack &S, SElemType &e) if( S.top = S.base ) / 栈空栈空 return ERROR; e *-S.top;return OK;-S.top;e=*S.top;ABCtopbase判断是否空栈，若空则返回错误判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素取顺序栈栈顶元素Status GetTop( SqStack S, SEl

14、emType &e) if( S.top = S.base ) return ERROR; / 栈空栈空e = *( S.top 1 );return OK;e = *( S.top - ); ?ABCtopbase435612435612中到了中到了1212顺序不能实现；顺序不能实现；135426135426可以实现。可以实现。1.1.如果一个栈的输入序列为如果一个栈的输入序列为123456123456，能否得到，能否得到435612435612和和135426135426的出栈序列？的出栈序列？练习练习练习练习i n-in-i+1不确定不确定2.2.若已知一个栈的入栈序列是若已知一

15、个栈的入栈序列是1 1，2 2，3 3，n n，其输出序列为，其输出序列为p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，则，则pipi为为练习练习 top不变不变 top=0 top+ top-D3.3.在一个具有在一个具有n n个单元的顺序栈中，假设以地址个单元的顺序栈中，假设以地址高端作为栈底，以高端作为栈底，以toptop作为栈顶指针，则当作进作为栈顶指针，则当作进栈处理时，栈处理时，toptop的变化为的变化为考研试题考研试题b0 t0 t1 b10 m-1V双栈共享一个栈空间双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会优点：互相调剂，灵活性强，减少溢出机

16、会 将编号为将编号为0 0和和1 1的两个栈存放于一个数组空间的两个栈存放于一个数组空间VmVm中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈号栈的栈顶指针的栈顶指针top0top0等于等于-1-1时该栈为空，当第时该栈为空，当第1 1号号栈的栈顶指针栈的栈顶指针top1top1等于等于m m时该栈为空。两个栈时该栈为空。两个栈均从两端向中间增长（如下图所示）均从两端向中间增长（如下图所示） 。考研试题考研试题bot0 top0 top1 bot10 m-1Vtypedef structint top2, bot2; /栈顶和栈底指针栈顶和栈底指针SElemType

17、 SElemType * *V; V; /栈数组栈数组 int m; int m; /栈最大可容纳元素个数栈最大可容纳元素个数DblStack;DblStack;数据结构定义如下数据结构定义如下考研试题考研试题void Dblpush(DblStack &s,SElemType x,int i) ；/把把x插入到栈插入到栈i的栈的栈int Dblpop(DblStack &s,int i,SElemType &x) ； /退掉位于栈退掉位于栈i栈顶的元素栈顶的元素int IsEmpty(DblStack s,int i) ；/判栈判栈i空否空否, 空返回空返回1, 否则

18、返回否则返回0int IsFull(DblStack s) ；/判栈满否判栈满否, 满返回满返回1, 否则返回否则返回0试编写判断栈空、栈满、进栈和出栈四试编写判断栈空、栈满、进栈和出栈四个算法的函数个算法的函数(函数定义方式如下）函数定义方式如下）考研试题考研试题b0 t0 t1 b10 m-1V栈空：栈空：topi = boti itopi = boti i表示栈的编号表示栈的编号 栈满：栈满：top0+1=top1 top0+1=top1 或或top1-1=top0top1-1=top0提示提示链栈的表示链栈的表示运算是受限的单链表，只能在链表头部进行操作，故运算是受限的单链表，只能在链

19、表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针没有必要附加头结点。栈顶指针就是链表的头指针 typedef struct StackNode SElemType data; struct StackNode *next; StackNode, *LinkStack;LinkStack S; data next 栈顶栈顶栈底栈底S链栈的初始化链栈的初始化void InitStack(LinkStack &S )S=NULL;S判断链栈是否为空判断链栈是否为空Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; el

20、se return FALSE;链栈进栈链栈进栈Status Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; pS链栈进栈链栈进栈pSeStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return

21、 OK; 链栈进栈链栈进栈pSeStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 链栈进栈链栈进栈pSeSStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 链栈出栈

22、链栈出栈SAe = AStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 链栈出栈链栈出栈SAe = ApStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 链栈出栈链栈出栈SAe = ApSStat

23、us Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 链栈出栈链栈出栈Status Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; e = AS取链栈栈顶元素取链栈栈顶元素SElemType GetTop(LinkSta

24、ck S) if (S=NULL) exit(1)； else return Sdata; 3.4 3.4 栈与递归栈与递归n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, , 或用它自己给自己定义或用它自己给自己定义, , 则称这个对则称这个对象是递归的；若一个过程象是递归的；若一个过程直接地或间接地调用直接地或间接地调用自己自己, , 则称这个过程是递归的过程。则称这个过程是递归的过程。long Fact ( long n ) if ( n = 0) return 1; else return n * Fact (n-1); 1. 递归定义的数学函数递归定义的

25、数学函数: 阶乘函数阶乘函数: 0n ) 1(0n 1)(若若nFactnnFact 2阶阶Fibonaci数列数列: )2() 1(21n 1)(其它或若nFibnFibnFib 树树 2. 2. 具有递归特性的数据结构具有递归特性的数据结构: :RootRootLchildLchildRchildRchild 广义表广义表 A=(a,A)A=(a,A)3. 3. 可递归求解的问题可递归求解的问题: : 迷宫问题迷宫问题, Hanoi, Hanoi塔问题塔问题 返回返回 2参数参数 2 计算计算 2*Fact(1)返回返回 1参数参数 1 计算计算 1*Fact(0)返回返回 1参数参数 0

26、 直接定值直接定值 = 1if ( n = 0 ) return 1;else return n * Fact (n-1); 求解阶乘求解阶乘 n! n! 的过程的过程 main : Fact(4)返回返回 24 参数参数 4 计算计算 4*Fact(3)返回返回 6参数参数 3 计算计算 3*Fact(2) 1 2 3 4f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15f(n) = 2f(n-1)+1f(n-1) = 2f(n-2)+1f(n-2) = 2f(n-3)+1.f(3) = 2f(2)+1f(2) = 2f(1)+120f(n)

27、= 21f(n-1)+2021f(n-1) = 22f(n-2)+2122f(n-2) = 23f(n-3)+22.2n-3f(3) = 2n-2f(2)+ 2n-32n-2f(2) = 2n-1f(1)+ 2n-2f(n) = 20+21+2n-2+ 2n-1f(1) = 2n-1递归算法的时间效率分析（递归算法的时间效率分析（hanoi塔问题）塔问题）空间效率空间效率时间效率时间效率与递归树的结点数成正比与递归树的结点数成正比与递归树的深度成正比与递归树的深度成正比O(n)递归算法的效率分析递归算法的效率分析优点：结构清晰，程序易读优点：结构清晰，程序易读缺点：每次调用要生成工作记录，保存

28、状缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。态信息。时间开销大。递归的优缺点递归的优缺点递归递归非递归非递归尾递归尾递归循环结构循环结构long Fact ( long n ) if ( n = 0) return 1; else return n * Fact (n-1); long Fact ( long n ) t=1; for(i=1; i=n; i+) t=t*i; return t; long Fib ( long n ) / Fibonacci数列数列 if(n=1 | n=2) return 1;

29、 else return Fib (n-1)+ Fib (n-2);单向递归单向递归循环结构循环结构虽然有一处以上的递归调用语句，但各次递归调虽然有一处以上的递归调用语句，但各次递归调用语句的参数用语句的参数只和主调函数只和主调函数有关，相互之间参数有关，相互之间参数无关，并且这些无关，并且这些递归调用语句处于算法的最后递归调用语句处于算法的最后。 )2() 1(21n 1)(其它或若nFibnFibnFib尾递归、单向递归尾递归、单向递归循环结构循环结构long Fib ( long n ) if(n=1 | n=2) return 1; else return Fib (n-1)+ Fib

30、 (n-2);long Fib ( long n ) if(n=1 | n=2) return 1; else t1=1; t2=1; for(i=3; inext=NULL; return OK;链队列初始化链队列初始化Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;销毁链队列销毁链队列 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); 判断链队列

31、是否为空判断链队列是否为空Status GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;求链队列的队头元素求链队列的队头元素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 O

32、K;链队列入队链队列入队Q.frontQ.rearxypStatus 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;链队列出队链队列出队Q.frontQ.rearxyp3.6 3.6 案例分析与实现案例分析与实现案例案例3.1 3.1 ：数制的转换：数制的转换【算法步骤算法步骤】 初始化一个空栈初始

33、化一个空栈S。 当十进制数当十进制数N非零时，循环执行以下操作：非零时，循环执行以下操作：l把把N与与8求余得到的八进制数压入栈求余得到的八进制数压入栈S；lN更新为更新为N与与8的商。的商。 当栈当栈S非空时，循环执行以下操作：非空时，循环执行以下操作：l弹出栈顶元素弹出栈顶元素e；l输出输出e。【算法描述】【算法描述】void conversion(int N)/对于任意一个非负十进制数，打印输出与其等值的八进制数对于任意一个非负十进制数，打印输出与其等值的八进制数 InitStack(S);/初始化空栈初始化空栈S while(N)/当当N非零时非零时,循环循环 Push(S,N%8);

34、/把把N与与8求余得到的八进制数压入栈求余得到的八进制数压入栈S N=N/8;/N更新为更新为N与与8的商的商 while(!StackEmpty(S)/当栈当栈S非空时，循环非空时，循环 Pop(S,e);/弹出栈顶元素弹出栈顶元素e coutx=xx表表3.13.1算符间的优先关系算符间的优先关系【算法步骤算法步骤】 初始化初始化OPTR栈和栈和OPND栈，将表达式起始符栈，将表达式起始符“#”压入压入OPTR栈。栈。 扫描表达式，读入第一个字符扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至，如果表达式没有扫描完毕至“#”或或OPTR的栈顶元素不为的栈顶元素不为“#”时，则循环执

35、行以下操作：时，则循环执行以下操作：l 若若ch不是运算符，则压入不是运算符，则压入OPND栈，读入下一字符栈，读入下一字符ch；l 若若ch是运算符，则根据是运算符，则根据OPTR的栈顶元素和的栈顶元素和ch的优先级比较结果，的优先级比较结果，做不同的处理：做不同的处理： 若是小于，则若是小于，则ch压入压入OPTR栈，读入下一字符栈，读入下一字符ch； 若是大于，则弹出若是大于，则弹出OPTR栈顶的运算符，从栈顶的运算符，从OPND栈弹出两个数，进行栈弹出两个数，进行相应运算，结果压入相应运算，结果压入OPND栈；栈； 若是等于，则若是等于，则OPTR的栈顶元素是的栈顶元素是“(”且且ch

36、是是“)”，这时弹出，这时弹出OPTR栈栈顶的顶的“(”，相当于括号匹配成功，然后读入下一字符，相当于括号匹配成功，然后读入下一字符ch。 OPND栈顶元素即为表达式求值结果，返回此元素。栈顶元素即为表达式求值结果，返回此元素。设定两栈设定两栈 ：OPND-OPND-操作数或运算结果操作数或运算结果OPTR-OPTR-运算符运算符 2022年3月19日 北京林业大学信息学院北京林业大学信息学院OperandType EvaluateExpression( ) InitStack (OPTR); Push (OPTR，#) ; InitStack (OPND); ch = getchar( );

37、 while (ch!= # | GetTop(OPTR)! = #) if (! In(ch)Push(OPND,ch); ch = getchar(); / ch不是运算符则进栈不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch) /比较优先权比较优先权 case : /弹出弹出OPTR栈顶的运算符运算，并将运算结果入栈栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; case = : /脱括号

38、并接收下一字符脱括号并接收下一字符 Pop(OPTR,x); ch = getchar(); break; / switch / while return GetTop(OPND); / EvaluateExpressionOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,

39、5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)迷宫求解迷宫求解从入口出发，按某一方向向未走过的前方探索从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向若能走通，则到达新点，否则试探下一方向 ; ; 若所有的方向均没有通路，则沿原路返回前一点，若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探换下一个方向再继续试探直到所有可能的通路都探索到，或找到一条通路，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。或无路可走又返回到入口点。求解思想：求解思想：回溯法回溯法迷宫求解迷宫求解需要

40、解决的问题：需要解决的问题：1、表示迷宫的数据结构、表示迷宫的数据结构2、试探方向、试探方向3、栈的设计、栈的设计4、防止重复到达某点，避免发生死循环、防止重复到达某点，避免发生死循环迷宫求解迷宫求解1、表示迷宫的数据结构、表示迷宫的数据结构表示一个表示一个m行行n列迷宫：列迷宫：用用mazemn表示，表示，0im,0jnmazeij = 0 通路通路mazeij = 1 不通不通改进：改进：用用mazem+2n+2表示表示且且mazeij=1，i=0或或m1, j=0或或n1入口坐标为（入口坐标为（1，1），出口坐标为（），出口坐标为（m，n） 迷宫求解迷宫求解012345678901111

41、111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111迷宫的定义：迷宫的定义：#define m 8 /*迷宫的实际行迷宫的实际行*/#define n 8 /*迷宫的实际列迷宫的实际列*/int maze m+2n+2 ;2、试探方向、试探方向表示位置的类型表示位置的类型PosType定义如下：定义如下：typedef struct int x，y; PosType ; 迷宫求解迷宫求解迷宫求解迷宫求解3、栈的设计、栈的设计栈中每个元素的

42、组成：栈中每个元素的组成：通道块在路径上的序号通道块在路径上的序号坐标位置坐标位置前进方向（东为前进方向（东为1，南为，南为2，西为，西为3，北为，北为4）栈元素的类型定义：栈元素的类型定义： typedef struct int ord; PosType seat; int di;SElemType;迷宫求解迷宫求解4、防止重复到达某点、防止重复到达某点走过不通之处要加以标记（走过不通之处要加以标记（MarkPrint操作）操作）迷宫求解迷宫求解【案例分析案例分析】l设置两个队列分别存放男士和女士入队者设置两个队列分别存放男士和女士入队者l假设男士和女士的记录存放在一个数组中作假设男士和女士

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

44、题：舞伴问题【数据结构数据结构】/- - - - - 跳舞者个人信息跳舞者个人信息- - - - - typedef struct char name20;/姓名姓名 char sex;/性别，性别，F表示女性，表示女性，M表示男性表示男性Person;/- - - - - 队列的顺序存储结构队列的顺序存储结构- - - - - #define MAXQSIZE 100/队列可能达到的最大长度队列可能达到的最大长度typedef struct Person *base;/队列中数据元素类型为队列中数据元素类型为Person int front;/头指针头指针 int rear;/尾指针尾指针S

45、qQueue;SqQueue Mdancers,Fdancers;/分别存放男士和女士入队者队列分别存放男士和女士入队者队列【算法步骤】【算法步骤】 初始化初始化MdancersMdancers队列和队列和FdancersFdancers队列。队列。 反复循环，依次将跳舞者根据其性别插入反复循环，依次将跳舞者根据其性别插入MdancersMdancers队列或队列或FdancersFdancers队列。队列。 当当MdancersMdancers队列和队列和FdancersFdancers队列均为非空时，反复循环，依次队列均为非空时，反复循环，依次输出男女舞伴的姓名。输出男女舞伴的姓名。 如果

46、如果MdancersMdancers队列为空而队列为空而FdancersFdancers队列非空，则输出队列非空，则输出FdancersFdancers队队列的队头女士的姓名。列的队头女士的姓名。 如果如果FdancersFdancers队列为空而队列为空而MdancersMdancers队列非空，则输出队列非空，则输出MdancersMdancers队队列的队头男士的姓名。列的队头男士的姓名。【例例】汽车加油站汽车加油站结构：入口和出口为单行道，结构：入口和出口为单行道，加油车道若干条加油车道若干条n n每辆车加油都要经过三段路程，三个队列每辆车加油都要经过三段路程，三个队列1.1.入口处排

47、队等候进入加油车道入口处排队等候进入加油车道2.2.在加油车道排队等候加油在加油车道排队等候加油3.3.出口处排队等候离开出口处排队等候离开若用算法模拟，需要设置若用算法模拟，需要设置n+2n+2个队列个队列。队列的其它应用队列的其它应用【例例】模拟打印机缓冲区模拟打印机缓冲区在主机将数据输出到打印机时，主机在主机将数据输出到打印机时，主机速度与打印机的打印速度不匹配速度与打印机的打印速度不匹配为打印机设置一个为打印机设置一个打印数据缓冲打印数据缓冲区区，当主机需要打印数据时，先将，当主机需要打印数据时，先将数据依次写入缓冲区，写满后主机转数据依次写入缓冲区，写满后主机转去做其他的事情去做其他

48、的事情而打印机就从缓冲区中按照而打印机就从缓冲区中按照先进先先进先出出的原则依次读取数据并打印的原则依次读取数据并打印【例例】打印杨辉三角形打印杨辉三角形 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 EnQueue (q,0);/各行间插入一个各行间插入一个0for ( j=1; j=i+2; j+ ) DeQueue (q,t ); /一个系数出队一个系数出队 EnQueue (q, s+t );/计算下一行系数，并进队计算下一行系数，并进队 s = t; if ( j != i+2 )

49、 cout s ;/第第i+2个个0 任务编号任务编号 1 2 3 4 5 优先权优先权 20 0 40 30 10 执行顺序执行顺序 3 1 5 4 2808075754040626273732828353550503838252547471515大根堆大根堆1. 1. 掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2. 2. 熟练掌握栈的熟练掌握栈的顺序栈顺序栈和链栈的进栈出栈算法和链栈的进栈出栈算法，特别应注意，特别应注意栈满和栈空栈满和栈空的条件的条件3. 3. 熟练掌握熟练掌握循环队列循环队列和链队列的进队出队算法和链队列的进队出

50、队算法，特别注意，特别注意队满和队空队满和队空的条件的条件4. 4. 理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程5. 5. 掌握掌握表达式求值表达式求值 方法方法小结小结（1 1）将编号为）将编号为0 0和和1 1的两个栈存放于一个数组空间的两个栈存放于一个数组空间VmVm中，栈中，栈底分别处于数组的两端。当第底分别处于数组的两端。当第0 0号栈的栈顶指针号栈的栈顶指针top0top0等于等于-1-1时时该栈为空；当第该栈为空；当第1 1号栈的栈顶指针号栈的栈顶指针top1top1等于等于m m时，该栈为空。时，该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、两个栈均从两端向中间增长。试编