数据结构(C语言版)严蔚敏清华大学出版社第三章栈和队列.ppt

1、前一章复习,线性结构特点 概念：线性表，记录，文件，表长，空表，位序 线性表的顺序存储和链式存储,从数据类型角度看，它们是和线性表大不相同的抽象数据类型,从数据结构角度看，栈和队列是两种特殊的线性表，它们是操作受限的线性表，故也称为限定性的数据结构,栈、队列与一般线性表,4 第三章栈与队列内容介绍,第三章要点,栈和队列的定义和特点 熟练掌握栈类型的实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。 能在相应的应用问题中正确选用它们,第三章目录,栈 栈的应用举例 栈和递归的实现 队列,第十讲,数据结构,栈及其实现,主

2、讲：刘立嘉,举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取,1 生活中的栈,a1,a2,an,进栈,出栈,栈顶,栈底,用铁路调度站表示栈,1. 定义 限定只能在表的一端进行插入和删除操作的线性表。特点：后进先出,2. 逻辑结构 与线性表相同，仍为一对一关系,3. 存储结构 用顺序栈或链栈存储均可，但以顺序栈更常见,4. 运算规则 只能在栈顶运算，且访问结点依照后进先出（LIFO）或先进后出（FILO）的原则,5

3、. 实现方式 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同,基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等,2 栈的基本概念,6、栈“上溢” 在栈满时还进行入栈运算，必定会产生空间的溢出,7、栈“下溢” 当栈空时仍进行出栈运算，必定会产生空间的溢出,上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件,栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base,例如： 栈 S= (a , a2 , a

4、3 , .,an-1 , an,插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈,an称为栈顶元素,a1称为栈底元素,强调：插入和删除都只能在表的一端（栈顶）进行,注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务,例1：堆栈是什么？它与一般线性表有什么不同,堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同,一般线性表 堆栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO,进”插入

5、=压入,出”删除=弹出,例2、一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么,解：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性,例3、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢,解： 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一

6、数便立即弹出即可,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底,3 栈的抽象数据类型定义,InitStack( int top; SeqStack,an,问：顺序表和顺序栈的操作有何区别,写入：Si= ai 读出： e= Si,压入(PUSH): Stop+=an 弹出( POP) : e=S-top,an,以线性表 S= (a0 , a1 , . , an-2 , an-1)为例,前提：一定要预设栈顶指针top,top,空栈,top,top,to

7、p,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,栈不存在的条件： base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=MaxSize,入栈口诀：堆栈指针top “先压后加” : Stop+=an 出栈口诀：堆栈指针top “先减后弹” : e=S-top,顺序栈的操作实现,1)初始化栈 void StackInitiate(Seq

8、Stack *S)/*初始化顺序堆栈S*/ S-top = 0; /*定义初始栈顶下标值*/,2)判栈非空否,int StackNotEmpty(SeqStack S) /*判顺序堆栈S非空否，非空则返回1，否则返回0*/ if(S.top = 0)return 0; else return 1;,3)入栈,int StackPush(SeqStack *S, DataType x) /*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0 */ if(S-top = MaxStackSize) printf(堆栈已满无法插入! n); return 0; else S-stackS-t

9、op = x; S-top +; return 1;,4)出栈,int StackPop(SeqStack *S, DataType *d) /*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/ if(S-top top -; *d = S-stackS-top; return 1;,5)取栈顶数据元素,int StackTop(SeqStack S, DataType *d) /*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/ if(S.top = 0) printf(堆栈已空! n); return 0; else *d = S.stac

10、kS.top - 1; return 1;,例：用堆栈存放（A，B，C，D,A,A,C B A,B A,顺序栈入栈函数的核心语句： S-stackS-top = x; S-top,低地址L,高地址M,B,C,D,例：从栈中取出B,顺序栈出栈函数的核心语句： S-top -; *d = S-stackS-top; 注：DataType *d； SeqStack *S,两个堆栈共享空间,b0 t0 t1 b1,0 maxSize-1,V,变化：考虑栈大小通常无法确定的情况下 （1）首先确定一个基本容量STACK_INIT_SIZE， （2）一旦超过，每次再增加一定容量STACKINCREMENT。

11、 改进的顺序栈结构 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 Typedef struct datatype *base, *top; int stacksize; SqStack,第十一讲,数据结构,栈的链式实现及栈的应用(1,主讲：刘立嘉,1、 链栈的存储结构 以头结点为栈顶，在头结点处插入或删除,栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈,链栈中每个结点由两个域构成： data域和next域，其定义为,typedef struct snode DataType data; struct snode * next

12、; LSNode,1、 栈的链式表示和实现,2、链式堆栈的操作实现,入栈 int StackPush(LSNode *head, DataType x) LSNode *p; if(p = (LSNode *)malloc(sizeof(LSNode) = NULL) printf(内存空间不足无法插入! n); return 0; p-data = x; p-next = head-next;/*新结点链入栈顶*/ head-next = p; /*新结点成为新的栈顶*/ return 1;,2)出栈,int StackPop(LSNode *head, DataType *d) LSNod

13、e *p = head-next; if(p = NULL) printf(堆栈已空出错！); return 0; head-next = p-next;/*删除原栈顶结点*/ *d = p-data; /*原栈顶结点元素赋予d*/ free(p); /*释放原栈顶结点内存空间*/ return 1; 注： 由此可以看出：一个链栈由其栈顶指针唯一指定 设head指向栈顶元素，则head=NULL 表示栈空,在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。 一般不会出现栈满情况；除非没有空间导致malloc分配失败。 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修

14、改指针即可完成。 采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式,几点说明,由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子,数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理,N=(N div d)*d+N mod d (其中:div为整除运算,mod为求余运算,2、 栈的应用举例,N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,计算顺序 从低到高,输出顺序 从高到低,例如：

15、（1348)10 = (2504)8 ，其运算过程如下,十进制数N和d进制数之间转换的算法原理： N=( N / d ) * d + N % d 即,an-1,a1,a0,top,N % d,N / d N,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);,2,5,0,4,栈s,N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,假设在表达式中 （

16、）或（ ） 等为正确的格式,括号匹配的检验,）或（ ）或 （） 均为不正确的格式,我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论,1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,回文游戏：顺读与逆读字符串一样（不含空格,1.读入字符串 2.去掉空格

17、（原串） 3.压入栈 4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam,回文字符串,如何实现行编辑程序,每接受一个字符即存入存储器”,并不恰当,行编辑程序,合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=,则实际有效的是下列两行： while (*s) putchar(*s,行编辑程序算法如下

18、: void LineEdit( ) initstack(s); ch=getchar( ); while(ch!=eof) while(ch!=eof,ch=getchar( ); / 从终端接收下一个字符 /将从栈底到栈顶的字符传送至调用过程的数据区； clearstack(s); if(ch!=eof) ch=getchar( ); destroystack(s);,本节结束,第十二讲,数据结构,栈的应用(2,主讲：刘立嘉,出口,入口,迷宫求解,1、 栈的应用举例,通常用的是“穷举求解”的方法,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口

19、位置，则算法结束； 否则切换当前位置的东邻方块为新的 当前位置；,求迷宫中一条从入口到出口的路径的算法,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块,若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；,若栈空，则表明迷宫没有通路,while (栈不空,否则,Typedef struct Int ord;/通道块在路径上的“序号” PosType seat;/通道块在迷宫的“坐标位置” Int di;/从此通道块走向下一通道块的“方向”

20、SElemType;/栈的元素类型,Status MazePath(MazeType maze,PosType start,PosType end) InitStack(S);curpos=start;/设置“当前位置”为“入口位置” Curstep=1;/探索第一步 Do If(Pass(curpos)/当前位置可通，即是未曾走到过的通道块 footPrint(curpos);/留下足迹 e=(curstep,curpos,1); Push(S,e);/加入路径 If(curpos=end) return (TRUE);/到达终点 curpos=NextPos(curpos,1);/下一位置

21、是当前位置的东邻 Curstep+;/探索下一步,Else当前位置不可通 If(!StackEmpty(S) Pop(S,e); While(e.di=4,用不多于四种的颜色对地图着色，使相邻的行政区域不重色 基本思想：行政区与颜色分别编号，从（1）号行政区开始，每个区域依次用颜色进行试探，若当前颜色与周围区域不重色，则用栈记下该区域的颜色序号，否则用下一颜色进行试探；若用四种颜色试探均重色，则需退栈回溯，修改栈顶颜色序号，再进行试探。直到满足要求,地图染色问题,地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黄色 3# 红色 4# 绿色,已知n件物品各自的体

22、积，背包容积为T，要求从n件中找出若干物物品，其体积之各恰好等于背包容积，看是否有解。 解决思路： 顺序栈S用来存放放入背包内的物品序号（最多有n个元素）； 参数T动态计算背包还可装入的重量； 依次装入试验，不满足时从后往前回溯,背包问题,初始容量T=10，6件物品重分别为(4,7,3,5,4,2,4,7,3,5,4,2,W,S,T=10,top,4,7,3,5,4,2,1,W,S,T=6,top,4,7,3,5,4,2,1,3,W,S,T=3,top,4,7,3,5,4,2,1,W,S,T=6,top,4,7,3,5,4,2,1,4,W,S,T=1,top,4,7,3,5,4,2,1,W,S

23、,T=6,top,4,7,3,5,4,2,1,5,W,S,T=2,top,4,7,3,5,4,2,1,5,6,W,S,T=6,top,表达式求值,一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 算术表达式有三种表示： 中缀(infix)表示 ，如 A+B； 前缀(prefix)表示 ，如 +AB； 后缀(postfix)表示 ，如 AB,表达式的中缀表示,a + b * ( c - d ) - e f / g 表达式中相邻两个操作符的计算次序为： 优先级高的先计算； 优先级相同的自左向右计算； 当使用括号时从最内层括号开始计算,rst1,rst2,rst3,rst4

24、,rst5,rst6,应用后缀表示计算表达式的值,从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。 在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。 计算例 a b c d - * + e f g /,rst1,rst2,rst3,rst4,rst5,rst6,通过后缀表示计算表达式值的过程,顺序扫描表达式的每一项，根据它的类型做如下相应操作： 若该项是操作数，则将其压栈； 若该项是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令XY，并将计算结果重新压栈。 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果,后缀表达式的处理过程

25、,中缀表达式：A + ( B C / D) E 后缀表达式：ABCD/E,本节结束,第十三讲,数据结构,栈的应用(3)与递归函数,主讲：刘立嘉,利用栈将中缀表示转换为后缀表示,使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。 为了实现这种转换，需要考虑各操作符的优先级,1、 栈的应用举例,中缀表达式转换为后缀表达式,当前运算符,栈顶运算符,中缀表达式转换为后缀表达式的处理规则,1、如为操作数，直接输出到队列； 2、如当前运算符高于栈顶运算符，入栈； 3、如当前运算符低于栈顶运算符，栈顶运算符退栈， 并输出到队列，当前运算符再与栈顶运算符比较； 4、如当前运算符等于栈顶运算符，且栈顶运算

26、符为 “（”，当前运算符为“）”，则栈顶运算符退栈， 继续读下一符号； 5、如当前运算符等于栈顶运算符，且栈顶运算符为 “#”，当前运算符也为“#”，则栈顶运算符退栈， 继续读下一符号,各个算术操作符的优先级,isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“;”号与输入流最后的“;”号配对时,中缀表达式转换为后缀表达式的算法,操作符栈初始化，将结束符;进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch = ;，同时栈顶的操作符也是;，停止循环。 若c

27、h是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp,若 icp (ch) isp (op)，令ch进栈，读入下一个字符ch。 若 icp (ch) isp (op)，退栈并输出。 若 icp (ch) = isp (op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。 算法结束，输出序列即为所需的后缀表达式,中缀算术表达式求值,使用两个栈，操作符栈OPTR (operator)，操作数栈OPND(operand)， 对中缀表达式求值的一般规则： (1) 建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个“;”

28、 (2) 从头扫描中缀表达式，取一字符送入ch。 (3) 当ch != “;” 时, 执行以下工作, 否则结束算法。此时在OPND栈的栈顶得到运算结果,若ch是操作数，进OPND栈，从中缀表达式取下一字符送入ch； 若ch是操作符，比较icp(ch)的优先级和isp(OPTR)的优先级： 若icp(ch) isp(OPTR)，则ch进OPTR栈，从中缀表达式取下一字符送入ch； 若icp(ch) isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出, 形成运算指令 (a1)(a2)，结果进OPND栈； 若icp(ch) = isp(OPTR) 且ch = “)”，则从OPTR栈退

29、出栈顶的“(”，对消括号，然后从中缀表达式取下一字符送入ch,以表达式 A*B + C/D 为例说明利用栈的求值过程。 操作数：A B C D 算符（运算符和界限符）： # * + / 优先级：*# +# /+ #/ #+ #=,表达式为#A*B + C/D,top2,NS运算数栈，OS运算符栈,InitStack(OPTR);Push(OPTR,#); /OPTR运算符栈，OPND运算数栈 InitStack(OPND); c=getchar(); While(c!=#|GetTop(OPTR)!=#) If(!In(c,OP)Push(OPND,c);c=getchar();不是运算符则进

30、栈 Else Switch(Precede(GetTop(OPTR),c) Case : /栈顶元素优先级低 Push(OPTR,c);c=getchar();Break; Case =: /脱括号接收下一字符 Pop(OPTR,x);c=getchar();break,OperandType EvaluateExpression(,Case : /退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); Break; return GetTop(OPND);,OPTR运算符栈，OPND

31、运算数栈,将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务,2、 栈与函数调用机制,保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数,从被调用函数返回调用函数之前，应该完成下列三项任务,多个函数嵌套调用的规则是,此时的内存管理实行“栈式管理,后调用先返回,例如： void main( ) a( ); /main,Main的数据区,函数a的数据区,函数b的数据区,void a( ) b( ); /

32、 a,void b( ) / b,r,主程序,函数的嵌套,递归函数：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,递归算法：描述递归定义的函数或求解递归问题的过程称为递归算法。 递归算法的实质，是将较复杂的处理归结为较简单的处理，直到最简单的处理,3、 栈结构与递归函数,递归算法优缺点： 优点：结构清晰，易读，在高级语言中，由系统管理堆栈，用户编程调试方便。 缺点：运行效率低，执行过程中反复入栈、出栈，时间、空间开销大，算法优化困难,递归工作栈：整个递归函数运行期间使用的数据存储区,递归函数运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数,当前环境指针：活动

33、记录的栈顶指针,工作记录：每一层递归所需信息。包括实在参数、所有局部变量以及上一层的返回地址,活动记录：当前执行层的工作记录必是递归工作栈栈顶的工作记录,递归函数,int f(x) int x; int y,z; . z=f(x); return (2*z);,f函数,调用f函数,直接调用,int f1(x) int x; int y,z; . z=f2( y); return (2*z);,int f2(t) int t; int a,c; . c=f1(a); return (3+c);,间接调用,特点:是无终止的递归调用，因此，应该给定一个限制递归次数的条件,float fac(int

34、n) float f; if(n0) printf(“n0,data error!n”); else if(n= =0|n= =1) f=1; else f=fac(n-1)*n ; return f;,例如：写一函数求n,以求4的阶乘为例,fac(4)=4*fac(3,fac(3)=3*fac( 2,fac(2)=2*fac( 1,fac(1)=1,fac(4)=4*3*2*1,fac(2)=2*1,fac(3)=3*2*1,下 推,回 代,利用栈实现递归调用,0，1，1，2，3，5，8，13，21，33,int Fib(int n) int fib; if (n= =0) fib=0; e

35、lse if (n= =1) fib=1; else fib=Fib(n-1) + Fib(n-2); return(fib);,5,3,4,3,Fib(5,Fib(4,Fib(5,5,4,3,Fib(2,2,1,1,0,Fib(1,Fib(0,5,3,4,3,Fib(2,2,1,1,0,5,3,4,3,2,1,1,0,Fib(4,Fib(5,Fib(2,Fib(1,2,1,0,Fib(4,Fib(5,Fib(2,Fib(0,5,3,4,3,2,1,1,0,Fib(3,Fib(5,2,1,0,Fib(3,Fib(5,Fib(2,2,1,5,3,Fib(3,Fib(5,Fib(2,Fib(1,2

36、,1,1,0,Fib(3,Fib(5,Fib(1,Fib(3,Fib(5,Fib(2,Fib(3,Fib(5,Fib(2,Fib(0,5,3,2,1,1,0,Fib(5,Fib(3,Fib(5,假设有3个分别命名为x、y和z的塔座，在塔座x上插有n个直径大小各不相同、依小到大编号为l，2，n的圆盘，现要求将x轴上的n个圆盘移至z轴上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： (1)每次只能移动一个圆盘； (2)圆盘可以插在x、y和z中的任一塔座上； (3)任何时刻都不能将一个较大的圆盘压在较小圆盘之上,n阶Hanoi塔问题,如何实现移动圆盘的操作呢? 当n=1时，问题比较简单，只要将编号

37、为l的圆盘从塔座x直接移至塔座z上即可； 当n1时，需利用塔座y作辅助塔座，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座x(依照上述法则)移至塔座y上，则可先将编号为n的圆盘从塔座x移至塔座z上，然后再将塔座y上的n-1个圆盘(依照上述法则)移至塔座z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模变小，因此可以用同样的方法求解。 由此可得如算法所示的求解n阶Hanoi塔问题的递归函数,算法分析,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至

38、n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 if (n=1) 3 move(x, 1, z); / 将编号为的圆盘从x移到z 4 else 5 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 6 move(x, n, z); / 将编号为n的圆盘从x移到z 7 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 8 9,0 3 a b c,返址 n x y z,6 2 a c b,6 1 a b c,8 1 c a b,void hanoi (int n, char x, char y

39、, char z) 1 2 if (n=1) 3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y, x, z); 8 9,递归工作栈（工作记录，活动记录，当前环境指针,main() int m; printf(Input number of disks”); scanf(%d, (8) (9),main() int m; printf(Input the number of disks scanf(%d, (8) (9),main() int m; printf(Input the num

40、ber of disks scanf(%d, (8) (9),main() int m; printf(Input the number of disks scanf(%d, (8) (9),本节结束,第十四讲,数据结构,队列及其实现,主讲：刘立嘉,队列定义,只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表,队尾插入,队头删除,与线性表相同，仍为一对一关系,顺序队列或链队列，以循环顺序队列更常见,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同,基本操作：入队或出队，建空队列，判队空或队满等操作,队列 内

41、容及重点,1、 队列的定义,队列：是先进先出（FIFO）的线性表。只允许在表的一端进行插入，而在另一端进行删除元素的线性表,a1, a2, a3 , a4, an-1,an,图3.8 队列示意图,队头,队尾,队列的定义与运算,允许插入的一端叫队尾，允许删除的一端称为队头。 假设队列q=(a1, a2, ,an） a1是队头元素,an队尾元素,出队列,入队列,注：队列的实现方式是本节重点，关键是掌握入队和出队操作。具体实现依存储结构（链队列或顺序队列）的不同而不同,离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 3.

42、 简化程序设计,答,问：为什么要设计队列？它有什么独特用途,举例1：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。 举例2：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标，拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应,ADT Queue 数据对象：Dai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾

43、,基本操作： InitQueue( （3）插入一个新的队尾元素，称为入队； （4）删除队头元素，称为出队,一个链队列显然需要两个分别指示队头和队尾的指针（头指针，尾指针）才能唯一确定。 为了操作方便，给链队列添加一个头结点，并令头指针指向头结点。 空的链队列的判决条件为头指针和尾指针均指向头结点,链队列队列的链式表示和实现,链队列：用链表表示的队列,2、 链队列,Q.front Q.rear,Q.front Q.rear,空队列,链队列,链队列示意图,队头,队尾,typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QN

44、ode, *QueuePtr,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue,单链队列队列的链式存储结构,ADT Queue的表示和实现,Status InitQueue (LinkQueue,基本操作的算法描述,销毁队列,a1,a2,an,Q.rear,Q.front,Status DestroyQueue(LinkQueue,算法见下页,插入一个元素（入队,e,a1,a2,an,Q.rear,算法见下页,Status EnQueue (LinkQueue,an,a2,a1,an,a2

45、,a1,删除一个元素（出队,队头,队尾,p,算法见下页,Status DeQueue (LinkQueue,一般情况下，删除队头元素仅需修改头结点中的指针，但当队列中最后一个元素被删后，队列尾指针丢失，需对队尾指针重新赋值（指向头结点,本节结束,第十五讲,数据结构,顺序循环队列与队列应用(1,主讲：刘立嘉,在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，需附设两个front和rear分别指示队列头元素及队列尾元素的位置,循环队列队列的顺序表示和实现,为在c语言中描述方便起见，在此约定：初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时

46、，尾指针增1；每当删除队列头元素时，头指针增1,在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置,1、 顺序循环队列,3 2 1 0,a)rear=front=0(队空,e3,e4,e1,e2出队，e4入队，队满,Q.rear =4,e1,e2,e3,Q.rear,Q.front,b)e1,e2,e3入队,队空时， 令rear=front=0，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置,Q.front,Q.front,不能继续插入，数组会越界,顺序队列的“假溢出”问题,1)假

47、溢出 顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。 (2)如何解决顺序队列的假溢出问题？ 可采取四种方法： 1)采用循环队列； 2)按最大可能的进队操作次数设置顺序队列的最大元素个数； 3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置； )修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作,Q.rear,Q.front,队空：front=rear 队满：front=rear,队空,一般情况,队满,初始状态,顺序循环队列的队空和队满判断问题 新问题：在循环队列中，空队特征是front=rear；队满时也

48、会有front=rear；判决条件将出现二义性！解决方案有三： 使用一个计数器记录队列中元素个数（即队列长度）； 判队满：count0 / 初始化的动态分配存储空间 int front; / 头指针，若队列不空，指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素的下一个位置 SqQueue,循环队列队列的顺序存储结构,Status InitQueue (SqQueue,Status EnQueue (SqQueue,Status DeQueue (SqQueue,优先级队列带有优先级的队列。 、顺序优先级队列 、优先级队列和一般队列的主要区别 优先级队列的出队列操

49、作不是把队头元素出队列，而是把队列中优先级最高的元素出队列。 如下表：任务优先权及执行顺序的关系,数字越小，优先权越高,2、优先级队列,include #include #include const int maxPQSize = 50; /缺省元素个数 template class PQueue private: Type *pqelements; /存放数组 int count; /队列元素计数public,优先队列的类定义,PQueue ( ); PQueue ( ) delete pqelements; void Insert ( const Type,template PQueue

50、: PQueue ( ) : count (0) pqelements = new TypemaxPQSize; assert ( pqelements != NULL ); template void PQueue : Insert ( const Type/判队满断言,优先队列部分成员函数的实现,for ( int j = count-1; j = 0; j- ) if ( pqelementsj int PQueue : RemoveMin ( ) if ( IsEmpty ( ) ) return 0; for ( int i = 1; i count; i+ ) pqelements

51、i-1 = pqelementsi; count-; return 1;,template Type PQueue : GetFront ( ) if ( IsEmpty ( ) ) return NULL; else return pqelements0;,举例1】模拟打印机缓冲区。 在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次

52、读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构,3、队列应用举例,举例2】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作,举例3】：编程序判断一个字符序列是否是

53、回文。 编程思想： 设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文,include #include #define MaxQueueSize 100 #define MaxStackSize 100 typedef char DataType; #include SeqCQueue.h #include SeqStack.h“ void HuiWen(char str) SeqCQueue myQueue; SeqStack myStack; char

54、x, y;int i, length,length = strlen(str); QueueInitiate(,if(QueueNotEmpty(myQueue) | StackNotEmpty(myStack) printf(%s不是回文!n, str); else printf(%s是回文!n, str); void main(void) char str1 = ABCDEDCBA; char str2 = ABCDEDCAB; HuiWen(str1); HuiWen(str2);,本节结束,第十六讲,数据结构,队列应用(2)与实验安排,主讲：刘立嘉,1 2 3 4 5 6 7 8,1

55、2 3 4 5 6,举例4】：求迷宫的最短路径,1、队列应用举例,需要解决的问题1：如何从某一坐标点出发搜索其四周的邻点,需要解决的问题2：如何存储搜索路径,需要解决的问题3：如何防止重复到达某坐标点,需要解决的问题4：如何输出搜索路径,define r 64 #define m2 10 #define n2 10 int mm2-2,nn2-2; typedef struct int x,y; int pre; sqtype; sqtype sqr,struct moved int x,y; move8; int mazem2n2,int SHORTPATH(int maze2) int i

56、,j,v,front,rear,x,y; sq1.x1; sq1.y1; sq1.pre0; front1; rear1; maze11-1; while(front=rear) xsqfront.x; ysqfront.y; for (v=0;v8;v+) ix+movev.x; jy+movev.y; if (mazei,j=0) rear+ sqrear.xi; sqrear.yj; sqrear.prefront; mazeij-1;,if (i=m),PRINTPATH(sqtype sq,int rear) int i; i=rear; do printf(“n(%d,%d)”,s

57、qi.x,sqi.y); isqi.pre; while (i!=0);,举例5】：逐行打印二项展开式 (a + b)i 的系数,分析第 i 行元素与第 i+1行元素的关系,从前一行的数据可以计算下一行的数据,i = 2,i = 3,i = 4,0 1 3 3 1 0,1 4 6 4 1,0 1 2 1 0,0 1 1 0,s,t,s+t,从第 i 行数据计算并存放第 i+1 行数据,1 2 1 0 1 3 3 1 0 1 4 6,s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1,s+t s=t s=t s=t s=t s=t s=t s=t s=t,s+

58、t s+t s+t s+t s+t s+t s+t s+t,利用队列打印二项展开式系数的程序 #include #include #include queue.h void YANGVI ( int n ) Queue q; /队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1); int s = 0,for ( int i = 1; i = n; i+ ) /逐行计算 cout endl; q.EnQueue (0); for ( int j = 1; j = i+2; j+ ) /下一行 int t = q.DeQueue ( ); q.E

59、nQueue ( s + t ); s = t; if ( j != i+2 ) cout s ;,举例6】：划分子集问题 问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少,例 A=1,2,3,4,5,6,7,8,9 R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,

60、7), (6,3) 可行的子集划分为： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9,算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组 所用数据结构 冲突关系矩阵 rij=1, i,j有冲突 rij=0, i,j无冲突 循环队列cqn 数组resultn存放每个元素分组号 工作数组newrn,工作过程 初始状态：A中元素放于cq中，result和newr数组清零，组号group=1 第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在new