Chapter_03 栈和队列

1、算法与数据结构算法与数据结构12014.9-2015.1主讲教师：张翠肖主讲教师：张翠肖联系方式：联系方式：线性结构特点概念：线性表，表长，空表，位序线性表的顺序存储和链式存储第三章第三章 栈与队列栈与队列（5）算法与数据结构算法与数据结构43.1 栈栈3.2 栈栈的应用的应用3.3 栈与递归栈与递归3.4 队列队列3.5 队列的应用队列的应用教学内容教学内容算法与数据结构算法与数据结构5第第3 3章章栈和队列栈和队列1.1.掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2.2.熟练掌握栈的熟练掌握栈的两种存储结构两种存储结构的基本操作实现

2、的基本操作实现算法，特别应注意算法，特别应注意栈满和栈空栈满和栈空的条件的条件3.3.熟练掌握熟练掌握循环队列和链队列循环队列和链队列的基本操作实现的基本操作实现算法，特别注意算法，特别注意队满和队空队满和队空的条件的条件4.4.理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程 教学目标教学目标算法与数据结构算法与数据结构6栈（栈（Stack）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3. 3. 存储结构存储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式队列（队列（Queue）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3. 3. 存储结构存

3、储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式算法与数据结构算法与数据结构73.1 3.1 栈栈1. 1. 定义定义用用顺序栈顺序栈或或链栈链栈存储均可，但以顺存储均可，但以顺序栈更常见序栈更常见3. 3. 存储结构存储结构与线性表相同，仍为与线性表相同，仍为一对一一对一关系关系2. 2. 逻辑结构逻辑结构只能在只能在表的一端表的一端（栈顶栈顶）进行插入）进行插入和删除运算的和删除运算的线性表线性表算法与数据结构算法与数据结构8只能在只能在栈顶栈顶运算，且访问结点时依运算，且访问结点时依照照后进先出后进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）的原则的原则

4、4.4.运算规则运算规则关键是编写关键是编写入栈入栈和和出栈出栈函数，具函数，具体实现依顺序栈或链栈的不同而体实现依顺序栈或链栈的不同而不同不同基本操作有基本操作有入栈、出栈、读栈顶入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空元素值、建栈、判断栈满、栈空等等5.5.实现方式实现方式算法与数据结构算法与数据结构9栈是一种特殊的线性表，它只能在表的一端（栈顶）栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算进行插入和删除运算栈与一般线性表的区别：仅在于栈与一般线性表的区别：仅在于运算规则运算规则不同不同“进进” 压入压入=PUSH=PUSH（) )“出出” 弹出弹出=POP( )

5、=POP( )一般线性表一般线性表 逻辑结构：一对一逻辑结构：一对一 存储结构：顺序表、链表存储结构：顺序表、链表 运算规则：随机运算规则：随机、顺序存取顺序存取栈栈逻辑结构：一对一逻辑结构：一对一 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：后进先出后进先出栈与一般线性表的区别栈与一般线性表的区别算法与数据结构算法与数据结构10“进进” 压入压入=PUSH=PUSH（) )“出出” 弹出弹出=POP( )=POP( ) ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,

6、n 约定an 端为栈顶，a1 端为栈底。 二、栈的抽象数据类型的定义:InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() ADT Stack基本操作：InitStack(&S) 操作结果：构造一个空栈 S。DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否

7、则 FALSE。StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。a1a2an ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 算法与数据结构算法与数据结构18 a a1 1

8、a a2 2 a an n顺序栈顺序栈S S a ai i表头表头表尾表尾栈底栈底basebase栈顶栈顶toptop低地址低地址高地址高地址写入：写入：vivi= = a ai i读出：读出： x= x= vivi 压入：压入：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顺序栈与顺序表顺序栈与顺序表算法与数据结构算法与数据结构19顺序栈的表示顺序栈的表示空栈

9、空栈base = topbase = top 是是栈空标志栈空标志stacksizestacksize = 4 = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的栈顶元素之上栈顶元素之上的下标地址的下标地址栈满时的处理方法：栈满时的处理方法：1 1、报错报错, ,返回操作系统。返回操作系统。2 2、分配更大的空间分配更大的空间，作为栈的存储空，作为栈的存储空间间, ,将原栈的内容移入新栈。将原栈的内容移入新栈。算法与数据结构算法与数据结构20#define MAXSIZE 100typedef struc

10、tSElemType *base;SElemType *top;int stacksize;SqStack;顺序栈的表示顺序栈的表示算法与数据结构算法与数据结构21知识回顾知识回顾（6） 栈的特点 栈的操作 顺序栈的表示 顺序栈的定义算法与数据结构算法与数据结构22 构造一个空栈构造一个空栈 步骤：步骤：(1)(1)分配空间并检查空间分配空间并检查空间是否分配失败，若失败是否分配失败，若失败则返回错误则返回错误顺序栈初始化顺序栈初始化basestacksizetops(2)(2)设置栈底和栈顶指针设置栈底和栈顶指针 S.top = S.base;(3)(3)设置栈大小设置栈大小算法与数据结构算

11、法与数据结构23Status InitStack( SqStack &S )S.base =new SElemTypeMAXSIZE；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;顺序栈初始化顺序栈初始化算法与数据结构算法与数据结构24判断顺序栈是否为空判断顺序栈是否为空bool StackEmpty( SqStack S )if(S.top = S.base) return true; else return false;basetop3120算法与数据结构算法与数据结构25求顺序栈的

12、长度求顺序栈的长度int StackLength( SqStack S )return S.top S.base;basetopAB算法与数据结构算法与数据结构26Status ClearStack( SqStack S )if( S.base ) S.top = S.base;return OK;清空顺序栈清空顺序栈basetop3120算法与数据结构算法与数据结构27Status DestroyStack( SqStack &S )if( S.base )delete S.base ;S.stacksize = 0;S.base = S.top = NULL; return OK;销毁顺序

13、栈销毁顺序栈算法与数据结构算法与数据结构28(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算法与数据结构算法与数据结构29(1)(1)判断是否栈空，若空则出错判断是否栈空，若空则出错(2)(2)获取栈顶元素获

14、取栈顶元素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算法与数据结构算法与数据结构30(1)(1)判断是否空栈，若空则返回错误判断是否空栈，若空则返回错误(2)(2)否则通过栈顶指针获取栈顶元素否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素取顺序栈栈顶元素Status GetTop( SqStack S, SElemType &

15、e) if( S.top = S.base ) return ERROR; / 栈空栈空e = *( S.top 1 );return OK;e = *( S.top - ); ?ABCtopbase算法与数据结构算法与数据结构31435612435612中到了中到了1212顺序不能实现；顺序不能实现；135426135426可以实现。可以实现。1.1.如果一个栈的输入序列为如果一个栈的输入序列为123456123456，能否得到，能否得到435612435612和和135426135426的出栈序列？的出栈序列？练习练习算法与数据结构算法与数据结构32练习练习i n-in-i+1不确定不确定

16、2.2.若已知一个栈的入栈序列是若已知一个栈的入栈序列是1 1，2 2，3 3，n n，其输出序列为，其输出序列为p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，则，则pipi为为算法与数据结构算法与数据结构33练习练习 top不变不变 top=0 top+ top-D3.3.在一个具有在一个具有n n个单元的顺序栈中，假设以地址个单元的顺序栈中，假设以地址高端作为栈底，以高端作为栈底，以toptop作为栈顶指针，则当作进作为栈顶指针，则当作进栈处理时，栈处理时，toptop的变化为的变化为算法与数据结构算法与数据结构34将编号为将编号为0 0和和1 1的两个栈存放于一个数组空

17、间的两个栈存放于一个数组空间VmVm 中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈号栈的栈顶指针的栈顶指针top0top0等于等于-1-1时该栈为空，当第时该栈为空，当第1 1号号栈的栈顶指针栈的栈顶指针top1top1等于等于m m时该栈为空。两个栈时该栈为空。两个栈均从两端向中间增长（如下图所示）均从两端向中间增长（如下图所示） 。考研试题考研试题bot0 top0 top1 bot10 m-1V算法与数据结构算法与数据结构35typedef structint top2, bot2; /栈顶和栈底指针栈顶和栈底指针SElemTypeSElemType * *

18、V; V; /栈数组栈数组 intint m; m; /栈最大可容纳元素个数栈最大可容纳元素个数 DblStackDblStack; ;数据结构定义如下数据结构定义如下考研试题考研试题算法与数据结构算法与数据结构36void 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, 否则返回否则返回0in

19、t IsFull(DblStack s) ；/判栈满否判栈满否, 满返回满返回1, 否则返回否则返回0试编写判断栈空、栈满、进栈和出栈四试编写判断栈空、栈满、进栈和出栈四个算法的函数个算法的函数(函数定义方式如下）函数定义方式如下）考研试题考研试题算法与数据结构算法与数据结构37链栈的表示链栈的表示算法与数据结构算法与数据结构38链栈的表示链栈的表示运算是受限的单链表，只能在链表头部进行操作，故运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针没有必要附加头结点。栈顶指针就是链表的头指针 typedef struct StackNode SElemTyp

20、e data; struct StackNode *next; StackNode, *LinkStack;LinkStack S; data next 栈顶栈顶栈底栈底S算法与数据结构算法与数据结构39链栈的初始化链栈的初始化void InitStack(LinkStack &S )S=NULL;S算法与数据结构算法与数据结构40判断链栈是否为空判断链栈是否为空Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; else return FALSE;算法与数据结构算法与数据结构41链栈进栈链栈进栈Status Push(LinkSta

21、ck &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; pS算法与数据结构算法与数据结构42链栈进栈链栈进栈pSeStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 算法与数据结构算法与数据结构43链栈进栈链栈进栈pSeSta

22、tus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 算法与数据结构算法与数据结构44链栈进栈链栈进栈pSeSStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 算法与数据结构算法与数据结构4

23、5链栈出栈链栈出栈SAe = AStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 算法与数据结构算法与数据结构46 2022年5月18日 链栈出栈链栈出栈SAe = ApStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 算法与数

24、据结构算法与数据结构47链栈出栈链栈出栈SAe = ApSStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 算法与数据结构算法与数据结构48链栈出栈链栈出栈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算法与数据

25、结构算法与数据结构49取链栈栈顶元素取链栈栈顶元素SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else return Sdata; 算法与数据结构算法与数据结构503.2 3.2 栈的应用栈的应用例例1 1：数制转换（十转数制转换（十转N N）用栈暂存低位值用栈暂存低位值例例2 2：括号匹配的检验括号匹配的检验用栈暂存左括号用栈暂存左括号例例3 3：表达式求值表达式求值用栈暂存运算符用栈暂存运算符例例4 4：迷宫求解（自学）：迷宫求解（自学） 用栈实现递归调用用栈实现递归调用简化了程序设计的问题简化了程序设计的问题 N N div 8

26、N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序从低到高输出顺序从高到低例如：（1348)10 = (2504)8 ，其运算过程如下：十进制数十进制数N和和d进制数之间转换的算法原理：进制数之间转换的算法原理：N=( N / d ) * d + N % d即即an-1a1a0topN % dN / d N1122110nndadadaaNvoid conversion( ) Initstack(S); scanf (“%d”,n); while(n) Push(S,n%8); n=n/8; while(! Stackempty(S) Pop(S,e); p

27、rintf(“%d”,e); 2504栈sN N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）均为不正确的格式。算法与数据结构算法与数据结构54算法的设计思想：1）凡出现）凡出现左括弧，则，则进栈；2）凡出现）凡出现右括弧，首先检查栈是否空，首先检查栈是否空 若若栈空，则表明该，则表明该“右括弧”多余， 否则否则和栈顶元素比较，比较， 若若相匹配，则，则“左括弧出栈” ， 否则表明否则表明不匹配。3）表达式检验检验结束时， 若若栈空，则表明表达式中，则表明表达式中匹配正确， 否则表明否

28、则表明“左括弧”有余。Status matching(string exp) int state = 1; while (i=Length(exp) & state) switch of expi case 左括弧左括弧:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); i+; else state = 0; break; if (StackEmpty(S)&state) return OK; . 回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串读入字符串2.去掉空格

29、（原串）去掉空格（原串）3.压入栈压入栈4.原串字符与出栈字符依次比较原串字符与出栈字符依次比较 若不等，非回文若不等，非回文 若直到栈空都相等，回文若直到栈空都相等，回文字符串：字符串：“madam im adam”算法和程序留作作业算法和程序留作作业算法与数据结构算法与数据结构57表达式求值表达式求值算法与数据结构算法与数据结构58u中缀中缀(infix)表示表示 如如 A+B；u前缀前缀(prefix)表示表示 ，如如 +AB；u后缀后缀(postfix)表示表示 ，如如 AB+；算法与数据结构算法与数据结构59rst1rst2rst3rst4rst5rst6算法与数据结构算法与数据结构

30、60rst1rst2rst3rst4rst5rst6算法与数据结构算法与数据结构61rst1rst2rst3rst4rst5rst6算法与数据结构算法与数据结构62顺序扫描表达式的每一项，根据它的类顺序扫描表达式的每一项，根据它的类型做如下相应操作：型做如下相应操作：u若该项是若该项是操作数操作数，则将其，则将其压栈压栈；u若该项是若该项是操作符操作符，则则连续从栈中连续从栈中退出两个操作数退出两个操作数Y和和X，形成运算指令形成运算指令XY，并将计算结果重新并将计算结果重新压栈压栈。当表达式的所有项都扫描并处理完后，当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。栈顶存放的就

31、是最后的计算结果。算法与数据结构算法与数据结构63后缀表达式的处理过程后缀表达式的处理过程操作顺序后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4中缀表达式：A + ( B C / D) E后缀表达式：ABCD/E+算法与数据结构算法与数据结构64void calculate(string str) Initstack(S); i=0;while (stri!=0) if stri 是操作数是操作数 Push(S,stri); else pop(S,a1);pop(S,a2); 计算计算 sum=a2 strii a1; pu

32、sh(S,sum); i+; Pop(S,e); printf(“%d”,e); 算法与数据结构算法与数据结构65编程几点注意事项编程几点注意事项 如何判断是操作符还是操作数？ 字符型操作数如何转换成整型？ 如何处理表达式中的2位数？ 结果或中间计算结果中能不能为2位数或多位数？算法与数据结构算法与数据结构66算法与数据结构算法与数据结构67中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#=当前运算符栈顶运算符算法与数据结构算法与数据结构68操作符 ch # ( *, /, % +, - - )isp (栈内栈内) 0 1 7 5 3 8icp (栈外栈外) 0 8 6 4 2

33、1算法与数据结构算法与数据结构69算法与数据结构算法与数据结构70算法与数据结构算法与数据结构71步骤步骤中缀表达式中缀表达式STACK输出输出1A(BCD)E# #2(BCD)E# #A3(BCD)E# # A4BCD)E# # (A5CD)E# # (AB6CD)E# # +(AB7D)E# # (ABC8D)E# # (/ABC9)E# # (/ABCD算法与数据结构算法与数据结构72步骤步骤中缀表达式中缀表达式STACK输出输出10E# # (ABCD/11E# # (ABCD/ 12E# # ABCD/ 13E# # ABCD/ 14# # ABCD/ E15# # =ABCD/ E

34、 16# #ABCD/ E 算法与数据结构算法与数据结构73表达式求值表达式求值算术四则运算规则算术四则运算规则(1) (1) 先乘除先乘除, ,后加减后加减(2) (2) 从左算到右从左算到右(3) (3) 先括号内先括号内, ,后括号外后括号外算法与数据结构算法与数据结构74【算法思想算法思想】（1）初始化）初始化OPTR栈和栈和OPND栈，将栈，将 “#”压入压入OPTR（2）依次读入字符）依次读入字符ch，循环执行（，循环执行（3）至（）至（5） （3）取出）取出OPTR的栈顶元素，当的栈顶元素，当OPTR的栈顶元素和的栈顶元素和ch均为均为“#”时，表达式求值完毕，时，表达式求值完毕

35、，OPND栈顶元素为表达式的值栈顶元素为表达式的值设定两栈设定两栈 ：OPND-OPND-操作数或运算结果操作数或运算结果OPTR-OPTR-运算符运算符（4） if (ch是操作数是操作数) 则则ch进进OPND，读入下一字符，读入下一字符ch（5） else 比较比较OPTR栈顶元素和栈顶元素和ch的优先级的优先级case ch 大大: 运算符运算符ch 进进OPTR，读入下一字符，读入下一字符chcase=: 脱括号（弹出左括号），读入下一字符脱括号（弹出左括号），读入下一字符chcase ch 小小: 栈顶运算符退栈、计算，结果进栈顶运算符退栈、计算，结果进OPND算法与数据结构算法与

36、数据结构75 2022年5月18日 OperandType EvaluateExpression( ) InitStack (OPND); ch = getchar( ); while (ch!= # | GetTop(OPTR)! = #) if (! In(ch,OP)Push(OPND,ch); ch = getchar(); / ch不是运算符则进栈不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch) /比较优先权比较优先权 case : /弹出弹出OPTR栈顶的运算符运算，并将运算结果入栈栈顶的运算符运算，并将运算结果入栈 Pop(OPTR,

37、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算法与数据结构算法与数据结构76OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,

38、()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)算法与数据结构算法与数据结构77思考思考 操作数栈是什么类型 操作符栈是什么类型 如何处理2位数的中间结果 如何处理表达式中出现的2位数算法与数据结构算法与数据结构78实验二实验二 题目：表达式求值基本要求： 1.表达式中的操作数都是个位数。 2.中间结果可以是2位数 3.有括号奖励要求： 表达

39、式的操作数可以含有多位数算法与数据结构算法与数据结构79知识回顾知识回顾（7） 栈的应用表达式求值 算法与数据结构算法与数据结构803.3 3.3 栈与递归栈与递归n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, ,或用它自己给自己定义或用它自己给自己定义, ,则称这个对象是则称这个对象是递归的；若一个过程递归的；若一个过程直接地或间接地调用自己直接地或间接地调用自己, , 则称这个过程是递归的过程。则称这个过程是递归的过程。算法与数据结构算法与数据结构81当多个函数构成嵌套调用时当多个函数构成嵌套调用时, , 遵循遵循后调用先返回后调用先返回栈栈算法与数据结构算

40、法与数据结构82n以下三种情况常常用到递归方法以下三种情况常常用到递归方法递归定义的数学函数递归定义的数学函数具有递归特性的数据结构具有递归特性的数据结构可递归求解的问题可递归求解的问题算法与数据结构算法与数据结构831. 递归定义的数学函数递归定义的数学函数: 阶乘函数阶乘函数: 0n ) 1(0n 1)(若若nFactnnFact 2阶阶Fibonaci数列数列: )2() 1(1n 10n 0)(其它若若nFibnFibnFib算法与数据结构算法与数据结构84 树树 2. 2. 具有递归特性的数据结构具有递归特性的数据结构: :RootRootLchildLchildRchildRchi

41、ld 广义表广义表 A=(A=(a,Aa,A) )3. 3. 可递归求解的问题可递归求解的问题: : HanoiHanoi塔问题塔问题 算法与数据结构算法与数据结构85求解递归问题算法的一般形式：求解递归问题算法的一般形式： void p (参数表参数表) if （递归结束条件）可直接求解步骤；（递归结束条件）可直接求解步骤；-基本项基本项 else p（较小的参数）；（较小的参数）；-归纳项归纳项 long Fact ( long n ) if ( n = 0) return 1;/基本项基本项 else return n * Fact (n-1); /归纳项归纳项算法与数据结构算法与数据结

42、构86返回返回 2参数参数 2 计算计算 2*Fact(1)返回返回 1参数参数 1 计算计算 1*Fact(0)返回返回 1参数参数 0 直接定值直接定值 = 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)算法与数据结构算法与数据结构87算法与数据结构算法与数据结构88规则规则: :(1) (1) 每次只能移动一个圆盘每次只能移动一个圆盘(2) (2) 圆

43、盘可以插在圆盘可以插在A,BA,B和和C C中的任一塔座上中的任一塔座上(3) (3) 任何时刻不可将较大任何时刻不可将较大圆盘压在较小圆盘之上圆盘压在较小圆盘之上Hanoi塔问题塔问题ABC算法与数据结构算法与数据结构89 2022年5月18日 Hanoi塔问题塔问题 n = 1n = 1，则直接从，则直接从 A A 移到移到 C C。否则。否则 (1)用用 C 柱做过渡，将柱做过渡，将 A 的的(n-1)个移到个移到 B(2)将将 A 最后一个直接最后一个直接移到移到 C (3)用用 A 做过渡，将做过渡，将 B 的的 (n-1) 个移到个移到 C算法与数据结构算法与数据结构90#incl

44、udeint c=0;void move(char x,int n,char z)cout+c,n,x,zc算法与数据结构算法与数据结构92调用前调用前, , 系统完成系统完成: :(1)(1)将将实参实参, ,返回地址返回地址等传递给被调用函数等传递给被调用函数(2)(2)为被调用函数的为被调用函数的局部变量局部变量分配存储区分配存储区(3)(3)将控制转移到被调用函数的将控制转移到被调用函数的入口入口调用后调用后, , 系统完成系统完成: :(1)(1)保存被调用函数的计算保存被调用函数的计算结果结果(2)(2)释放被调用函数的释放被调用函数的数据区数据区(3)(3)依照被调用函数保存的依

45、照被调用函数保存的返回地址返回地址将控制转移到将控制转移到调用函数调用函数算法与数据结构算法与数据结构93“层次层次”主函数主函数第第1 1次调用次调用第第 i i 次调用次调用0 0层层1 1层层i i 层层“递归工作栈递归工作栈”“工作记录工作记录”实在参数实在参数, ,局部变量局部变量, ,返回地址返回地址递归函数调用的实现递归函数调用的实现算法与数据结构算法与数据结构94空间效率空间效率时间效率时间效率O(2n)与递归树的结点数成正比与递归树的结点数成正比与递归树的深度成正比与递归树的深度成正比O(n)递归算法的效率分析递归算法的效率分析算法与数据结构算法与数据结构95 1 2 3 4

46、f(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) = 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递归算法的效率分析递归算法的效率分析算法与

47、数据结构算法与数据结构966464片金片移动次数：片金片移动次数：假如每秒钟一次，共需多长时间呢？假如每秒钟一次，共需多长时间呢？一年大约有一年大约有31536926秒，移完这些金片需要秒，移完这些金片需要多亿年多亿年世界、梵塔、庙宇和众生都已经灰飞烟灭世界、梵塔、庙宇和众生都已经灰飞烟灭 !算法与数据结构算法与数据结构97优点：结构清晰，程序易读优点：结构清晰，程序易读缺点：每次调用要生成工作记录，保存状缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。态信息。时间开销大。递归的优缺点递归的优缺点递归递归非递归非递归算

48、法与数据结构算法与数据结构983.4 3.4 队列队列队列是一种先进先出队列是一种先进先出(FIFO) 的线性表的线性表. 它只允许在它只允许在表的一端进行插入表的一端进行插入,而在另一端删除元素而在另一端删除元素),(21naaaqa a1 1a a2 2a a3 3a an n.入队列入队列队头队头队尾队尾算法与数据结构算法与数据结构99),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列算法与数据结构算法与数据结构100),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列算法与数据结构算法与数据结

49、构101),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列算法与数据结构算法与数据结构102设栈设栈S S和队列和队列Q Q的初始状态为空，元素的初始状态为空，元素e1e1、e2e2、e3e3、e4e4、e5e5和和e6e6依次通过依次通过S S，一个元素出栈后即，一个元素出栈后即进入进入Q Q，若，若6 6个元素出队的序列是个元素出队的序列是e2e2、e4e4、e3e3、e6e6、e5e5和和e1e1，则栈，则栈S S的容量至少应该是（）。的容量至少应该是（）。 （A）2 （B）3 （C）4 （D）6练习练习B算法与数据结构算法与数据结构103

50、 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作： 抽象数据类型队列的类型定义抽象数据类型队列的类型定义 ADT Queue算法与数据结构算法与数据结构104队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQ

51、ueue(&Q, e)算法与数据结构算法与数据结构105InitQueue(&Q) 操作结果：构造一个空队列构造一个空队列Q。DestroyQueue(&Q)初始条件：队列队列Q已存在。已存在。 操作结果：队列队列Q被销毁，被销毁， 不再存在。不再存在。算法与数据结构算法与数据结构106 QueueEmpty(Q)初始条件：队列队列Q已存在。已存在。 操作结果：若若Q为空队列，则为空队列，则返回返回TRUE，否则返回否则返回FALSE算法与数据结构算法与数据结构107 QueueLength(Q) 初始条件：队列队列Q已存在。已存在。 操作结果：返回返回Q的元素个数的元素个数，即队列的长度。，

52、即队列的长度。算法与数据结构算法与数据结构108 GetHead(Q, &e) 初始条件：Q为非空队列。为非空队列。 操作结果：用用e返回返回Q的队头的队头元素。元素。a1a2an 算法与数据结构算法与数据结构109 ClearQueue(&Q)初始条件：队列队列Q已存在。已存在。 操作结果：将将Q清为空队列。清为空队列。算法与数据结构算法与数据结构110 EnQueue(&Q, e) 初始条件：队列队列Q已存在。已存在。 操作结果：插入元素插入元素e为为Q的的新的队尾元素。新的队尾元素。a1a2ane 算法与数据结构算法与数据结构111 DeQueue(&Q, &e) 初始条件：Q为非空队列

53、。为非空队列。 操作结果：删除删除Q的队头元素的队头元素，并用，并用e返回其值。返回其值。a1a2an 算法与数据结构算法与数据结构112队列的主要运算：队列的主要运算： （1 1）设置一个空队列；）设置一个空队列；（2 2）读取队头元素）读取队头元素; ;（3 3）插入一个新的队尾元素，称为）插入一个新的队尾元素，称为入队入队；（4 4）删除队头元素，称为）删除队头元素，称为出队出队。算法与数据结构算法与数据结构113#define M 100 /最大队列长度最大队列长度Typedef struct QElemType *base; /初始化的动态分配存储空间初始化的动态分配存储空间 int

54、 front; /头指针头指针 int rear; /尾指针尾指针SqQueue; 队列的顺序表示用一维数组队列的顺序表示用一维数组baseM算法与数据结构算法与数据结构114队列的顺序表示用一维数组队列的顺序表示用一维数组baseMQ.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearQ.frontQ.frontQ.rearQ.rearJ J1 1J J2 2J J3 3Q.frontQ.frontQ.rearQ.rearJ J3 3Q.frontQ.frontQ.rearQ.rearJ J5 5J J6 6front=rear=0空队标志：空队标志：fro

55、nt= =rear入队：入队：baserear+=x;出队：出队：x=basefront+;算法与数据结构算法与数据结构115Q.frontQ.frontQ.rearQ.rearJ5J5J6J6Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearJ5J5J6J6J1J1J2J2J3J3J4J4存在的问题存在的问题设数组大小为设数组大小为Mfront=0rear=M时时再入队再入队真溢出真溢出front 0rear=M时时再入队再入队假溢出假溢出算法与数据结构算法与数据结构116解决的方法循环队列解决的方法循环队列1 10 0Q.rearQ.rearQ.fro

56、ntQ.front.base0接在接在baseM-1之后之后若若rear+1=M则令则令rear=0;实现：利用实现：利用“模模”运算运算入队：入队： baserear=x; rear=(rear+1)%M;出队：出队： x=basefront; front=(front+1)%M; 算法与数据结构算法与数据结构117 2022年5月18日 J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=

57、rear解决方案：解决方案：1.1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2 2. .少用一个元素空间少用一个元素空间： 队空：队空：front=rearfront=rear 队满：队满：( (rear+1)%M=frontrear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出队出队rearrear算法与数据结构算法与数据结构118循环队列循环队列#define MAXQSIZE 100 /最大队列长度最大队列长

58、度Typedef struct QElemType *base; /初始化的动态分配存储空间初始化的动态分配存储空间 int front; /头指针头指针 int rear; /尾指针尾指针SqQueue; 算法与数据结构算法与数据结构119Status InitQueue (SqQueue &Q) Q.base =new QElemTypeMAXQSIZE if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;循环队列初始化循环队列初始化算法与数据结构算法与数据结构120求循环队列的长度求循环队列的长度int QueueLength

59、(SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; 算法与数据结构算法与数据结构121Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;循环队列入队循环队列入队算法与数据结构算法与数据结构122Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear)

60、 return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;循环队列出队循环队列出队算法与数据结构算法与数据结构123naaa,21. . . .datadatanextnext队头队头队尾队尾Q.frontQ.frontQ.rearQ.rear链队列链队列算法与数据结构算法与数据结构124typedef struct QNode QElemType data; struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front; /队头指针队头指