第-3-章-栈和队列课件.ppt

1、数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞1、栈和队列的定义及特点；、栈和队列的定义及特点；2、栈的顺序存储表示；、栈的顺序存储表示；3、队列的顺序存储表示；队列的链接存储表示；、队列的顺序存储表示；队列的链接存储表示；4、栈和队列的应用举例。、栈和队列的应用举例。教学内容教学内容 数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞学习指南 在这一章中，主要是学习如何在求解应用在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列

2、，栈和队列在两种问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。件以及它们的描述方法。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 本章学习目标和重点、难点本章学习目标和重点、难点【】1.掌握栈和队列这两种抽象数据类型的特点，并能在相掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们

3、。应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。理解递归算法执行过程中栈的状态变化过程。【】栈和队列是在程序设计中被广泛使用的两种线性数栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。以便能在应用问题中正确使用。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院

4、 王霞限定仅在表尾进行插入或删除操作。限定仅在表尾进行插入或删除操作。3.1 栈栈 3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 栈的定义栈的定义 a1 a2 an-1 an 栈顶栈顶(top)栈底栈底(bottom)出栈出栈 进栈进栈 栈底元素栈底元素 线性表线性表 后进先出后进先出(LIFO结构结构)。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 栈的抽象数据类型的定义栈的抽象数据类型的定义 ADT Stack 数据对象：数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：数据关系：R|ai-1,aiD,i=2,.,

5、n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。基本操作：基本操作：操作结果：操作结果：构造一个空栈构造一个空栈 S。初始条件：初始条件：栈栈 S 已存在。已存在。操作结果：操作结果：栈栈 S 被销毁。被销毁。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 初始条件：初始条件：栈栈 S 已存在且非空。已存在且非空。操作结果：操作结果：用用 e 返回返回 S 的栈顶元素。的栈顶元素。初始条件：初始条件：栈栈 S 已存在。已存在。操作结果操作结果：若栈若栈 S 为空栈，则返回为空栈，则返回 TRUE，否则，否则 FALSE。初始条件初始条件：栈

6、栈 S 已存在。已存在。操作结果：操作结果：返回返回 S 的元素个数，即栈的长度。的元素个数，即栈的长度。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞初始条件：初始条件：栈栈 S 已存在。已存在。操作结果：操作结果：将将 S 清为空栈。清为空栈。初始条件：初始条件：栈栈 S 已存在。已存在。操作结果：操作结果：插入元素插入元素 e 为新的栈顶元素。为新的栈顶元素。初始条件：初始条件：栈栈 S 已存在且非空。已存在且非空。操作结果：操作结果：删除删除 S 的栈顶元素，并用的栈顶元素，并用 e 返回其值。返回其值。ADT Stack 数据结构数据结构 第三章

7、第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞312 栈的存储表示与算法实现栈的存储表示与算法实现 一、一、栈的顺序存储结构及其算法实现栈的顺序存储结构及其算法实现1栈的生成方式栈的生成方式（1）向下生成的栈。栈顶在）向下生成的栈。栈顶在高地址端，栈底在低地址端。高地址端，栈底在低地址端。如图如图(a)所示。入栈时所示。入栈时top+；出栈时出栈时top-。（2）向上生成的栈。栈顶在）向上生成的栈。栈顶在低地址端，栈底在高地址端。低地址端，栈底在高地址端。如图如图(b)所示。入栈时所示。入栈时top-；出栈时出栈时top+。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：

8、制作：信息科学技术学院 王霞栈的存储表示与算法实现栈的存储表示与算法实现2栈顶指针的两种指示方式。栈顶指针的两种指示方式。栈顶指针指向什么位置，对入栈和出栈时的操作语句有栈顶指针指向什么位置，对入栈和出栈时的操作语句有直接影响。通常有两种指示方式：直接影响。通常有两种指示方式：（1）栈顶指针指向第一个空单元。使用这种指示方式，入）栈顶指针指向第一个空单元。使用这种指示方式，入栈时，先写元素，后修改栈顶指针；出栈时先修改栈顶栈时，先写元素，后修改栈顶指针；出栈时先修改栈顶指针，后读元素。指针，后读元素。（2）栈顶指针指向栈顶处的元素。使用这种指示方式，入）栈顶指针指向栈顶处的元素。使用这种指示方

9、式，入栈时，先修改栈顶指针，后写元素；出栈时先读元素，栈时，先修改栈顶指针，后写元素；出栈时先读元素，后修改栈顶指针。后修改栈顶指针。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞3.1.2 栈的存储表示和算法实现栈的存储表示和算法实现 3.3.栈的顺序存储结构栈的顺序存储结构 利用一组地址连续的存储单元依次存放自利用一组地址连续的存储单元依次存放自 栈底到栈顶的数据元素，同时附设指针栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元指示栈顶元 素在顺序栈中的位置。素在顺序栈中的位置。top base A top B top C top D top E

10、 top 若再进行元若再进行元 素素“出栈出栈”操操 作，将产生作，将产生“下溢下溢”。top 若再进行元若再进行元 素素“入栈入栈”操操 作，将产生作，将产生“上溢上溢”。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈的存储表示与算法实现栈的存储表示与算法实现（1）静态顺序栈。用一维数组Stack 0.MaxSize-1存储表示一个栈，大小MaxSize预先定义。Stack 0 端表示栈底，设置一个栈顶指针int top 指向栈顶。存储结构如图所示：顺序栈的类型描述：顺序栈的类型描述：#define MaxSize 100 /定义栈大小 typedef

11、 SElmeType Stack MaxSize ;/定义栈类型名 int top;/定义栈顶指针 Stack S;/定义栈变量 入栈操作语句：S top+=e;出栈操作语句：e=S-top 。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量线性表存储空间的分配增量typedef struct ElemType *elem;/数组指针，指示线性表的基地址数组指针，指示线性表的基

12、地址 int length;/当前长度当前长度 int listsize;/当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)为单位为单位)SqList;SelemType*base;/栈底指针，它始终指向栈底的位置。栈底指针，它始终指向栈底的位置。SelemType*top;/栈顶指针。栈顶指针。int stacksize;/当前分配的栈可使用的最大存储容量。当前分配的栈可使用的最大存储容量。Sqstack;base 的值为的值为 NULL，表明栈结构不存在。，表明栈结构不存在。#define STACK_INIT_SIZE 100 /栈存储空间的初始分配量栈存储空间

13、的初始分配量#define STACKINCREMENT 10 /栈存储空间的分配增量栈存储空间的分配增量 （2）动态顺序栈数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈的存储表示与算法实现栈的存储表示与算法实现顺序栈基本操作的实现：栈顶的初始化：S.top=S.base栈空：S.base=S.top栈满：S.top-S.base=S.stacksize 入栈：*S.top+=e，出栈：e=*-S.top 数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈的存储表示与算法实现栈的存储表示与算法实现 3双栈。为了共享存储

14、空间，有时将两个栈用一块存储空间存放，两栈的栈顶相对,如图。当base1=top1 且base2=top2 时，两个栈都空.top1=top2 时两个栈都满。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 栈的基本操作在顺序栈中的实现栈的基本操作在顺序栈中的实现#define maxs 9;main()while(top0)e=stacktop-1;top-=1;InitStack Push Pop top 1 2 top top top 2 top GetTop 2 1 Status InitStack(SqStack&S)S.base=(SElemTy

15、pe*)malloc(STACK_INIT_SIZE*sizeof(SElemtype);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus Push(SqStack&S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemtype);if(!S.base)exit(OVERFLOW)

16、;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top 1);return OK;/GetTop Status Pop(SqStack&S,SElemType&e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;/Pop 数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术

17、学院 王霞二、栈的链式存储结构及其算法实现二、栈的链式存储结构及其算法实现1、存储方式：、存储方式：同一般线性表的单链式存储结构完全相同。那么链表的哪端应该作为栈顶？.top如果链表头作为栈顶，则入、出栈操作的时间复杂性为O(1)，所以，一般把链表头作为栈顶。栈顶.l需要不需要头结？为什么？需要不需要头结？为什么？如果链表尾作为栈顶，会是什么情况？入栈、出栈入栈、出栈O(n)数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈的链式存储结构及其算法实现栈的链式存储结构及其算法实现2栈的链接存储结构定义（链栈）栈的链接存储结构定义（链栈）用不带头结点的单链表表示

18、一个栈，设置一个栈顶指针top。入栈、出栈都在top端进行。如下图所示：类型定义如下：typedef struct SNode SElemTyoe data;struct SNode *next;SNode，*LinkStack;LinkStack top;数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈的链式存储结构及其算法实现栈的链式存储结构及其算法实现（1）置空栈）置空栈 void InitLinkStack（LinkStack&top）top=NULL;（2）判栈空）判栈空Bool LinkStackEmpty（LinkStack top）if（!

19、top）return TRUE;else return FALSE;数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞（3）入栈void Push(LinkStack*top,SElemType e)StackNode *s;s=(SNode*)malloc（sizeof（SNode）;s-data=x;s-next=top;top=s;入栈算法数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞（4）出栈Bool Pop(LinkStack top,SElemType&e)LinkStack p;if(!top)return

20、EEEOR;else p=top;x=top-data;top=top-next;free（p）;return OK;出栈算法数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞int StackLength(LinkStackint StackLength(LinkStack top)top)LinkStack p;int LinkStack p;int n=0;n=0;p=top;p=top;while(p)while(p)/每移动一个结点，个数n加1 n+;p=p-next;n+;p=p-next;return n;return n;（5）求栈长）求栈长数

21、据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞3.2 栈的应用举例栈的应用举例 1 数制转换数制转换 十进制数十进制数 N 和其他和其他 d 进制数进制数 M 的转换是计算机实现的转换是计算机实现 计算的基本问题，其解决方法很多，其中一个简单算法是计算的基本问题，其解决方法很多，其中一个简单算法是 逐次除以基数逐次除以基数 d 取余法，它基于下列原理：取余法，它基于下列原理：N=(N div d)*d+N mod d 具体作法为：具体作法为：首先用首先用 N 除以除以 d，得到的余数是，得到的余数是 d 进制进制 数数 M 的最低位的最低位 M0，接着以前一

22、步得到的商作为被除数，接着以前一步得到的商作为被除数，再除以再除以 d，得到的余数是，得到的余数是 d 进制数进制数 M 的次最低位的次最低位 M1，依，依 次类推，直到商为次类推，直到商为 0 时得到的余数是时得到的余数是 M 的最高位的最高位 Ms（假（假 定定 M 共有共有 s+1 位）。位）。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞例：例：(1348)10=(2504)8，其运算过程如下：，其运算过程如下：N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计计 算算 顺顺 序序 输输 出出 顺

23、顺 序序 数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞bottom top 4 0 5 2 top 1348 168 void conversion()int stack4;int top=0;int N;scanf(“%d”,N);while(N)stacktop=N%8;top+;N=N/8;for(top=top-1;top=0;top-)printf(“%d”,stacktop);21 top 2 top 0 top 2504 InitStack(S)Push(S,N%S)While(!Stackempty(S)Pop(S,e);printf(“

24、%d”,e);数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞2 括号匹配的检验括号匹配的检验 假设表达式中允许括号嵌套，则检验括号是否匹配的假设表达式中允许括号嵌套，则检验括号是否匹配的 方法可用方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。例：例：()1 2 3 4 5 6 7 8 bottom top (top top top top top top top top 可能出现的可能出现的的情况：的情况：盼来的右括号盼来的右括号不是所不是所“期待期待”的；的；到来的是到来的是“不速之客不速之客”（右括号多右括号多）；到结束也未盼

25、来到结束也未盼来所所“期待期待”的括号的括号 （左括号多左括号多）。）。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞算法的设计思想：算法的设计思想：1）凡出现）凡出现左括号左括号，则，则进栈进栈；2）凡出现右括号，首先检查栈是否空。）凡出现右括号，首先检查栈是否空。若栈空，则表明该若栈空，则表明该“右括号右括号”多余；多余；否则和栈顶元素比较，否则和栈顶元素比较，若相匹配，则若相匹配，则“左括号出栈左括号出栈”，否则表明不匹配。否则表明不匹配。3）表达式检验结束时，）表达式检验结束时，若栈空，则表明表达式中匹配正确，若栈空，则表明表达式中匹配正确，否则表

26、明否则表明“左括号左括号”有多余的。有多余的。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞括号匹配问题括号匹配问题算法描述如下：#define STRLEN 255#define STRLEN 255 Bool cheakBool cheak()()char S STRLEN ;char S STRLEN ;/初始化字符栈 intint top=-1;top=-1;char ch char ch=#;=#;while(ch while(ch!=n)/!=n)/重复从键盘读字符，直到读到回车换行符 scanf(“%c”,&ch scanf(“%c”,&ch

27、););switch(ch switch(ch)/根据读入字符的不同情况分别处理 case (:case (:case :case :/ch是(或 时，入栈 S+top=ch S+top=ch;break;break;case ):case ):/处理 ch=)时的情况 if (Stop if (Stop=()top-;=()top-;else if(Stop else if(Stop=)return ERROR;=)return ERROR;break;break;case :case :/处理 ch=时的情况 if (Stop if (Stop=)top-;=)top-;else if(S

28、top else if(Stop=()return ERROR;=()return ERROR;break;break;if(top 0)return TRUE;if(top 0)return TRUE;/栈空时返回真，否则返回假 else return ERROR;else return ERROR;/算法结束数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞中缀表达式求值中缀表达式求值 运算规则运算规则 先乘除，后加减；先乘除，后加减；从左算到右；从左算到右；先括号内，后括

29、号外；先括号内，后括号外；例：例：求表达式求表达式 4+2 3-10/5 的值。的值。计算顺序为：计算顺序为：4+2 3-10/5=4+6-10/5=10-10/5=10-2=8 操作数或结果操作数或结果 运算符运算符#4+2 3 6 10-10/5 82数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞OperandType ExpressionEvaluateOperandType ExpressionEvaluate()()/从键盘输入中缀表达式，计算其值 InitStack InitStack(OPTR);Push(OPTR,#);(OPTR);Pus

30、h(OPTR,#);/初始化运算符栈 InitStackInitStack(OPND);(OPND);/初始化操作数栈 ch=getcharch=getchar();();while(ch!=#&GetTop(OPTR while(ch!=#&GetTop(OPTR)!=#)!=#)/逐个读字符ch且不等于#if(!in(ch if(!in(ch,OP),OP)Push(OPND,ch Push(OPND,ch););/不是运算符入操作数栈 else switch()else switch()/是运算符时分别做不同处理 case case :/ch 的优先级高于栈顶运算符的优先级 Push(O

31、PTR,ch Push(OPTR,ch);break;);break;case=:case=:/ch 的优先级等于栈顶运算符的优先级 Pop(OPTR,c);breck Pop(OPTR,c);breck;case :case 6/(4-2)+3=6/(4-2)+3*2 2=利用栈计算后缀表达式值的演示：利用栈计算后缀表达式值的演示：6 4 2-/3 2 6 4 2-/3 2*+#+#6 6-2 24 4/3 3 2 2*+#9 9=9 96 6 4 4 2 2 -/3 3 2 2 *+=9=9数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞OperandT

32、ype exprEvaluatel(char A )/本函数返回由后缀表达式A表示的表达式运算结果 InitStack(S);ch=*A+;while(ch!=#)if (!In(ch,OP)Push(S,ch);/读入的字符是操作数时入栈 else /是运算符，取出两个操作数 Pop(S,x);Pop (S,y);switch(ch)/对两个操作数进行相应计算 case+：c=a+b;break;case-：c=a-b;break;case*：c=a*b;break;case/：c=a/b;break;case%：c=a%b;break;Push(S,c);/计算结果入栈 ch=*A+;/读

33、下一个字符 Pop(S,c);return c;/返回结果 /算法结束例例4、后缀表达式求值。、后缀表达式求值。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞3.3 栈与递归的实现栈与递归的实现 递归：递归：一个直接调用自己或通过一系列的调用语句间接地调一个直接调用自己或通过一系列的调用语句间接地调 用自己的函数，称做递归函数。用自己的函数，称做递归函数。例：例：阶乘函数阶乘函数 0)1(01)(n nFactnn nFact若若若若相应的相应的 C 语言函数是：语言函数是：float fact(int n)float s;if(n=0)s=1;else

34、s=n*fact(n-1);return(s);若求若求 5!，则有，则有 main()printf(“5!=%fn”,fact(5);数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞一、递归的定义递归是一个数学概念，递归函数即自调用函数，在函数体内直接或间接地自己调用自己。递归本质上也是一种循环的程序结构，它把“较复杂”的计算逐次归结为“较简单”的计算，一直归结到“最简单”的情形的计算，并得到计算结果为止。二、用递归求解问题的条件1.必须有一个明确的函数终止的条件；2.原问题必须能转化为新问题，新问题的解决方法与旧问题的解决方法一样；3.新旧问题一般在形式

35、参数每次获得的值上不一样，或者函数体内测试条件变量的值不同。注意：很多数据结构可以采用递归方式定义，线性表、数组、字符串和树等数据结构原则上都可使用递归方法来定义。使用递归定义方法的数据结构常称为递归数据结构，例如树形结构。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 栈的应用-过程的嵌套调用数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 栈与递归的实现数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王

36、霞 当在一个函数的运行期间调用另一个函数时，在运行当在一个函数的运行期间调用另一个函数时，在运行 该被调用函数之前，需先完成三件事：该被调用函数之前，需先完成三件事：1.将实参等传递给被调用函数，将实参等传递给被调用函数，（）；2.为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区；将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。从被调用函数返回调用函数之前，应该完成：从被调用函数返回调用函数之前，应该完成：1.保存保存被调函数的被调函数的计算结果计算结果；2.释放释放被调函数的被调函数的数据区数据区；按被调函数保存的返回地址（按被调函数保存的返回地址（）将）将控制转

37、移控制转移到调到调 1.用函数。用函数。多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：。此时的内存管理实行此时的内存管理实行“”。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);return(s);递归调用执行过程：递归调用执行过程：主函数主函数main()Printf(fact(5)第一层调用第一层调用n=5s=5*fact(4)第二层调用第二层调用n=4s=4*fact(3)第三层调用第三层调用n=3s=3*fact(2)第四层调用第四层调

38、用n=2s=2*fact(1)第五层调用第五层调用n=1s=1*fact(0)fact(5)=120输出输出 s=120.00 第六层调用第六层调用n=0s=1fact(4)=24fact(3)=6fact(2)=2fact(1)=1fact(0)=1主主 a 5 a 4 a 3 a 2 a 1 a printf(“5!=%fn”,fact(5);base float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);return(s);float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);

39、return(s);float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);return(s);float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);return(s);float fact(int n)float s;if(n=0)s=1;else s=n*fact(n-1);return(s);n=5 n=4 n=3 n=2 n=1 n=0 数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞81 2 3 4 5 6 781234567入口入口出口出

40、口前进方向：前进方向：上上(北北)、下、下(南南)、左、左(西西)、右、右(东东)东东南南北北西西n 走步规则：走步规则：首先从向下开始，按首先从向下开始，按照逆时针方向搜索下一步照逆时针方向搜索下一步可能前进的位置可能前进的位置6 迷宫求解迷宫求解数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈栈81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i迷宫求解迷宫求解数据结构数据结构 第三章第三章 栈和队列栈和队列

41、制作：制作：信息科学技术学院 王霞栈栈81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i (5,2)(5,2)i(5,3)(5,3)i(6,3)(6,3)i(6,4)(6,4)i(8,8)(8,8)iiiiii 迷宫求解迷宫求解数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞求迷宫路径算法的基本思想基本思想是：若当前位置若当前位置“可通可通”，则纳入路径，继续前进，则纳入路径，继续前进;若当前位置若当前位置“不可通

42、不可通”，则后退，换方向继续，则后退，换方向继续探索探索;若四周若四周“均无通路均无通路”，则将当前位置从路径中，则将当前位置从路径中删除出去。删除出去。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞设定当前位置的初值为入口位置；do 若当前位置可通若当前位置可通，则则将当前位置插入栈顶插入栈顶；若若该位置是出口位置，则则算法结束；否则切换否则切换当前位置的东邻方块为 新的当前位置；否则否则 while(栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作

43、：信息科学技术学院 王霞若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为:沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；/从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置，直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞栈初始化栈初始化;将入口点坐标及到达该点的方向（设为）入栈将入口点坐标及到达该点的方向（设为）入栈w

44、hile (while (栈不空栈不空 )栈顶元素弹出到（栈顶元素弹出到（x,y,dx,y,d）出栈出栈 ;求出下一个要试探的方向求出下一个要试探的方向d+;d+;while while（还有剩余试探方向时）（还有剩余试探方向时）if if（d d方向可走）方向可走）则则 （x,y,dx,y,d）入栈）入栈 ;求新点坐标求新点坐标(i,j(i,j););将新点（将新点（i,ji,j）切换为当前点（）切换为当前点（x,yx,y）;if(x,if(x,)=()=(,n),n)结束结束 ;else else 重置重置 d=0;d=0;else d+;else d+;栈的应用举例栈的应用举例例例 3.

45、6 走迷宫问题算法走迷宫问题算法,算法步骤如下：算法步骤如下：数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞算法描述：算法描述：intint path(maze path(maze，move)move)int mazemn int mazemn;item move8;item move8;SqStack SqStack S;S;SElemType SElemType temp;temp;int int x,y,d,i,j ;x,y,d,i,j ;temp.x=1;temp.y=1;temp.d temp.x=1;temp.y=1;temp.d=-1;=-1

46、;Push(S Push(S，temp);temp);while(!StackEmpty while(!StackEmpty(S)(S)Pop(S,temp);Pop(S,temp);x=temp.x;y=temp.yx=temp.x;y=temp.y;d=temp.d+1;d=temp.d+1;while(d 8)while(d 8)i=x+moved.x;j=y+moved.y i=x+moved.x;j=y+moved.y;if(mazeij if(mazeij=0)=0)temp=x,y,d ;temp=x,y,d ;Push(S,temp);Push(S,temp);x=i;y=j;

47、mazexy x=i;y=j;mazexy=-1;=-1;i f (x=m&y i f (x=m&y=n)return 1=n)return 1;/迷宫有路 else d=0;else d=0;else d+;else d+;/while(d8)/while(d 1 前前n-1 个盘个盘:X Y栈与递归数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1 个盘个盘:X Y栈与递归数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 n阶阶Hanoi塔问题塔问题Re

48、cursion:n 1 最大盘最大盘:X Z栈与递归数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞n阶阶Hanoi塔问题塔问题Recursion:n 1 最大盘最大盘:X Z栈与递归数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1个盘个盘:Y Z栈与递归数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1个盘个盘:Y Z栈与递归数据结构数据结构 第三章第三章

49、栈和队列栈和队列 制作：制作：信息科学技术学院 王霞 “四染色四染色”定理是计算机科学中著名定理之一，定理是计算机科学中著名定理之一，即可以用不多于四种颜色对地图着色，使相邻的行政即可以用不多于四种颜色对地图着色，使相邻的行政 区域不重色。区域不重色。补充：地图四染色问题补充：地图四染色问题 算法思想：算法思想：从第一号行政区开始逐一染色，每一从第一号行政区开始逐一染色，每一 个区域逐次用颜色个区域逐次用颜色 1、2、3、4 进行试探。若当前所进行试探。若当前所 取的色数与周围已染色的行政区不重色，则用栈记下取的色数与周围已染色的行政区不重色，则用栈记下 该行政区的色数，否则依次用下一色数进行

50、试探；若该行政区的色数，否则依次用下一色数进行试探；若 出现用出现用 1 至至 4 色均与相邻区域发生重色，则需退栈回色均与相邻区域发生重色，则需退栈回 溯，修改当前栈顶的色数，再进行试探。直至所有行溯，修改当前栈顶的色数，再进行试探。直至所有行 政区域都已分配合适的颜色。政区域都已分配合适的颜色。数据结构数据结构 第三章第三章 栈和队列栈和队列 制作：制作：信息科学技术学院 王霞例例：已知：已知 7 个行政区域地图，对其进行染色。个行政区域地图，对其进行染色。1 2 3 4 5 6 7 1 0 1 1 1 1 1 0 21 0 0 0 0 1 0 31 0 0 1 1 0 0 41 0 1