数据结构严蔚敏ppt课件第3章.ppt

第三章栈和队列,【课前思考】,简单地说，线性结构是一个数据元素的序列。,必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。,是排队。在计算机程序中，模拟排队的数据结构是队列。,【学习目标】,1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法。 4. 理解递归算法执行过程中栈的状态变化过程。,栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。,【知识点】,顺序栈、链栈、循环队列、链队列,【重点和难点】,【学习指南】,在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3.1 栈,3.2 栈的应用举例,3.4 队列,目 录,3.3 栈与递归的实现,3.1 栈,一、栈的定义,栈(stack)作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。 通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 插入：最先放入栈中元素在栈底，最后放入的元素在栈顶； 删除：最后放入的元素最先删除，最先放入的元素最后删除。 栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。,图3.1 栈,例：设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,二、栈的主要操作,1.初始化栈：InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。3.出栈： POP(&S，&e) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素： GETTOP(S，&e)取栈S中栈顶元素。5.判栈空： EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。,三、栈的抽象数据类型描述,ADT Stack 数据对象： D=ai| ai ElemSet，i=1,2,n,n 0 数据关系： R1= | ai-1 , ai D, i=1,2,n 基本操作： InitStack(&S) 操作前提： S为未初始化的栈。 操作结果： 将S初始化为空栈。 ClearStack(&S) 操作前提： 栈S已经存在。 操作结果： 将栈S置成空栈。 StackEmpty(S) 操作前提： 栈S已经存在。 操作结果： 若栈S为空，则返回TRUE,否则FALSE。,StackLength(S) 操作前提：栈S已经存在。 操作结果：返回S的元素个数即栈的长度。 IsFull(S) 操作前提： 栈S已经存在。 操作结果： 判栈满函数，若S栈已满，则函数值为TRUE， 否则为FALSE。 StackTraverse(S,visit() 操作前提：栈S已经存在且非空。 操作结果：从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败，则操作失效。,Push(&S,e) 操作前提：栈S已经存在。 操作结果：在S的顶部插入(亦称压入)元素e；若S栈未满，将e插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。 Pop(&S,&e) 操作前提：栈S已经存在。 操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。 GetTop(S, &e) 操作前提： 栈S已经存在。 操作结果：取栈S的顶部元素。与Pop(&S, &e)不同之处在于GetTop(S,&e)不改变栈顶的位置。ADT Stack,1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性， 还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0或 top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。 栈的顺序存储结构定义如下：,四、 栈的表示和实现,#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef struct SElemType *base; /在栈构造前和销毁后base值为NULL SElemType *top; /栈顶指针 int stacksize; SqStack; /当前已分配存储空间或简单定义如下： #define M 100 int sM; int top;,图3.2 顺序栈中的进栈和出栈,Top指向栈顶元素初态：top=-1; 空栈，栈中无元素，进栈：top=top+1; stop=x;退栈：取stop; top=top-1;栈满：top=M-1;栈溢出（上溢），不能再进栈（错误状态）top=-1时不能退栈，下溢（正常状态，常作控制条件）,（1）构造空顺序栈算法:初始化栈Status InitStack ( SqStack / InitStack,2.顺序栈基本操作的实现如下:,程序描述：/This program is to initialize a stack # include # include # include # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType; typedef struct /define structure SqStack() SElemType *base; SElemType *top; int stacksize; SqStack;,int InitStack(SqStack ,（2） 取顺序栈的栈顶元素 Status GetTop ( SqStack S, SElemType / GetTop,（3）将元素压入顺序栈算法（进栈）Status Push ( SqStack / Push,（4）将元素弹出顺序栈算法（退栈）Status Pop ( SqStack / Pop,（5） 判栈空否 Int Empty ( SqStack S) / 如果栈 S 空，返回 1 ；如果栈 S 不空，返回 0 。if ( S.top = = S.base ) return 1; / 如果栈 S 为空，则返回 1else return 0; / 如果栈 S 为空，则返回 0 / Empty end,3栈的共享有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。,栈空：top1=0,top2=M-1;栈满：top1+1=top2,两个栈共享存储单元可用如下C语句描述：#define MAXSIZE 100 #define DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE; int top1; /top1 is the pointer of DuSqStack S1 int top2; /top2 is the pointer of DuSqStack S2 int flag;DuSqStack; /或：#define MAXSIZE 100Struct duseqstack elemtype datamaxsize; int top2 ; /两个栈的栈顶指针 int flag; ,（1）两个栈共享存储单元的进栈算法Status DuSqStackPush ( DuSqStack / 如果 flag 不为 1,2，则返回 ERROR else / 如果 flag 为 1 或 2，则入栈 switch ( S.flag ) case 1 : / 标志位 flag 为 1,S.dataS.top1 = x; / 元素 x 入栈 S1 S.top1+; / 修改栈 S1 的栈顶指针 break; case 2 : / 标志位 flag 为 2 S.dataS.top2 = x; / 元素 x 入栈 S2 S.top2- -; / 修改栈 S2 的栈顶指针 break; / switch 结束 return OK; / else 结束 / else 结束 / DuSqStackPush,（2）两个栈共享存储单元的退栈算法Status DuSqStackPop ( DuSqStack / 元素 x 出栈 / if 结束,else return ERROR; / 如果栈 S1 为空，则返回 ERROR break; case 2 : / 标志位 flag 为 1 if ( S.top2MAXSIZE-1 ) /若栈 S2 不空，对 S2 进行操作 S.top2+; / 修改栈 S2 的栈顶指针 x = S.dataS.top2; / 元素 x 出栈 / if 结束 else return ERROR; / 如果栈 S2 为空，则返回 ERROR break; / switch结束 return OK; / else结束 / DuSqStackPop,4.链栈（1）链栈结构及数据类型栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图3-4。,typedef struct SNode /define structure LinkStack SElemType data; struct SNode *next; SNode,*LinkStack,（2）链栈的五种栈运算,（a）栈初始化void inistack(LinkStack top) top = ( LinkStack ) malloc ( sizeof ( SNode ) ); top-next=NULL;（b）进栈运算Status Push_L ( LinkStack / Push_L,（c）退栈运算Status Pop_L ( LinkStack / Pop_L,（d）取栈顶元素Status GetTop_L ( LinkStack top, SElemType / else 结束 / GetTop_L,（5）判栈空int empty(LinkStack *top) if(top-next=NULL) return(1); else return(0);,课 前 复 习,设n 个元素的进栈序列是P1，P2，P3， Pn，其输出序列是1,2，3，n，若P1=3，则P2的值 ()。 A、可能是2B、一定是2C、不可能是1D、一定是1,一、 数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步， 直到N等于零： X = N mod d (其中mod为求余运算)N = N div d (其中div为整除运算) 计算过程从低位到高位，打印输出从高位到低位,3.2 栈的应用举例 栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。,void Conversion(int N)/*对于任意的一个非负十进制数N， 打印出与其等值的8进制数*/ Stack S; int x; /* S为顺序栈或链栈 */ InitStack( 算法3.1,二、括号匹配问题 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。 解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (in ,if (expi=) /*遇到,若栈顶是, 则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若栈顶是 ,则继续处 理,否则以不配对返回*/ if (sttop=) top-; else tag=0; i+; /*表达式扫描完毕*/ if (top-1) tag=0; /*若栈不空,则不配对*/ return(tag); ,三、行编辑程序功能：接收用户从终端输入的数据或程序，并存入用户的数据区。算法思想：设输入缓冲区为一个栈结构，每当从终端接收一个字符后先作如下判别：若它既不是退格符（#）也不是退行符（）,则将该字符入栈；若是退格符（#），则从栈顶删去一个字符；若是退行符（），则将栈清空。算法描述如下：,void LineEdit()InitStack(s);ch=getchar();While(ch!=EOF) /EOF为全文结束符 while(ch!=EOF,五、 表达式求值,表达式求值是高级语言编译中的一个基本问题， 是栈的典型应用实例。 任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数， 也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、 关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。,1.无括号算术表达式求值,表达式计算 程序设计语言中都有计算表达式的问题， 这是语言编译中的典型问题。 (1) 表达式形式： 由运算对象、 运算符及必要的表达式括号组成； (2) 表达式运算： 运算时要有一个正确的运算形式顺序。由于某些运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格的从左到右， 见图3.5。,图3.5 表达式运算及运算符优先级,图3.6 无括号算术表达式的处理过程,2. 算术表达式处理规则 (1) 规定优先级表。 (2) 设置两个栈： OVS(运算数栈)和OPTR(运算符栈)。 (3) 自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符OPTR栈顶, 当前操作符进OPTR栈；当前操作符OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。 例： 实现A/BC+D*E的运算过程时栈区变化情况如图3.7所示。,图3.7 A/BC+D*E运算过程的栈区变化情况示意图,+,*,3. 带括号算术表达式 假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符， 界限符有左右括号和表达式起始、结束符“”，如： （7+15）*（23-28/4）。 引入表达式起始、 结束符是为了方便。 要对一个简单的算术表达式求值， 首先要了解算术四则运算的规则， 即： (1) 从左算到右；(2) 先乘除， 后加减；(3) 先括号内， 后括号外。,运算符和界限符可统称为算符，它们构成的集合命名为OPTR。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一： 12， 1的优先权高于2。,表 3-1 算符之间的优先关系,实现算符优先算法时需要使用两个工作栈： 一个称作optr， 用以存放运算符；另一个称作opnd，用以存放操作数或运算的中间结果。 算法的基本过程如下： 首先初始化操作数栈opnd和运算符栈optr， 并将表达式起始符“”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈opnd， 若是运算符，则与运算符栈optr的栈顶运算符进行优先权比较，并做如下处理： ,(1) 若栈顶运算符的优先级低于刚读入的运算符， 则让刚读入的运算符进optr栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈opnd退栈两次，得到两个操作数a、b，对a、 b进行运算后， 将运算结果作为中间结果推入opnd栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。,算法具体描述如下：,int ExpEvaluation()/*读入一个简单算术表达式并计算其值。 operator和operand分别为运算符栈和运算数栈， OPS为运算符集合*/ InitStack( while(c!=|GetTop(optr)! =) /* GetTop()通过函数值返回栈顶元素*/, if(!In(c,OP) Push(,Pop(,例求表达式1+2*3-4/2的值，栈的变化如下。,步骤 操作数栈 运算符栈 说明,开始,两栈均为空,1,1,1进入操作数栈,+进入运算符栈,2进入操作数栈,*进入运算符栈,3进入操作数栈,退栈,2*3进入操作数栈,退栈,1+6进入操作数栈,2,3,4,5,6,7,8,9,1,+,1,2,+,1,2,+,1,1,1,7,+,*,2,3,6,+,*,+,步骤 操作数栈 运算符栈 说明,10,7,-进入运算符栈,4进入操作数栈,/进入运算符栈,2进入操作数栈,退栈,4/2进入操作数栈,退栈,7-2进入操作数栈,11,12,13,14,15,16,17,7 4,-,7 4,- /,7 4 2,- /,7,7 2,-,-,-,5,当然，算术表达式除了简单求值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律，,例如，对于下列各中缀表达式：（1） 3/5+8（2） 18-9*(4+3)（3） (25+x)*(a*(a+b)+b)对应的后缀表达式为：(1)3 5 / 8 +(2)18 9 4 3 + * -(3)25 x + a a b + * b + *,4.中缀表达式变成等价的后缀表达式 将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。 将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。 现在用栈来实现该运算，栈的变化及输出结果如下,步骤 栈中元素 输出结果 说明,5.后缀表达式的求值 将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下：,从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。,五、 求解迷宫问题 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。,为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下: int mgM+1N+1= /*M=10,N=10*/ 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;,while (栈不空)若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； / 此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的北邻方块为新的当前位置； 否则若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置；/ 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ,算法描述：,void mgpath()/*路径为:(1,1)-(M-2,N-2)*/ int i,j,di,find,k; top+; /*初始方块进栈*/ Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1; while (top-1) /*栈不空时循环*/ i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; if (i=M-2 ,find=0; while (di4 ,if (find=1) /*找到了下一个可走方块*/ Stacktop.di=di; /*修改原栈顶元素的di值*/ top+; /*下一个可走方块进栈*/ Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1; mgij=-1;/*避免重复走到该方块*/ else /*没有路径可走,则退栈*/ mgStacktop.iStacktop.j=0; /*让该位置变为其他路径可走方块*/ top-; printf(没有可走路径!n); ,3.3 栈与递归的实现,1、什么是递归 在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。,例 以下是求n!(n为正整数)的递归函数。 int fun(int n) int x; if (n=1) /*语句1*/ x=1;/*语句2*/ else /*语句3*/ x=fun(n-1)*n;/*语句4*/ return(x);/*语句5*/ 在该函数fun(n)求解过程中,直接调用fun(n-1)(语句4)自身,所以它是一个直接递归函数。又由于递归调用是最后一条语句,所以它又属于尾递归。,2 、何时使用递归 在以下三种情况下,常常要用到递归的方法。 1) 定义是递归的 有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。,2) 数据结构是递归的 有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。,对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); ,3)问题的求解方法是递归的 有些问题的解法是递归的,典型的有Hanoi问题求解,该问题描述是：设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分解的过程是：,Hanoi(n,a,b,c),Hanoi(n-1,a,c,b)；move(n,a,c):将第n个圆盘从a移到c；Hanoi(n-1,b,a,c),图 Hanoi塔的递归函数运行示意图,3、 递归模型 递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。,实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。,求解fun(5)的过程如下：5!,4 递归问题的优点 通过上面的例子可看出，递归既是强有力的数学方法， 也是程序设计中一个很有用的工具。其特点是对递归问题描述简捷，结构清晰，程序的正确性容易证明。 5、消除递归的原因 其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低且费时。 其二： 无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN语言中无递归机制 。 其三：递归算法是一次执行完，这在处理有些问题时不合适， 也存在一个把递归算法转化为非递归算法的需求。 ,3.4 队列,队列简称队,它也是一种运算受限的线性表,其限制仅允许在表的一端进行插入,而在表的另一端进行删除。 我们把进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。 向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。,二、队列的基本运算 1. 初始化操作：InitQueue(&Q) 。设置一个空队列。 2. 判空操作：QueueEmpty(Q)。若队列为空， 则返回TRUE， 否则返回FALSE。 3.进队操作：EnQueue(&Q，x) 。在队列Q的队尾插入x。 操作成功，返回值为TRUE， 否则返回值为FALSE。 4. 出队操作：DeQueue(&Q,&x) 。使队列Q的队头元素出队， 并用x带回其值。 操作成功，返回值为RUE， 否则返回值为FALSE。 , 5. 取队头元素操作：GetHead（Q,&x）。用x取得队元素的值。操作成功，返回值为TRUE，否则返回值为FALSE。 6. 队列置空操作：ClearQueue(&Q) 。将队列Q置为空队列。 7. 队列销毁操作DestroyQueue(&Q) 。释放队列的空间。 8. 求队列长度操作：QueueLength(Q)。返回队列Q的元素个数，即队列Q的长度。 ,三、 队列的抽象数据类型描述 队列的抽象数据类型可描述为： ADT QUEUE 数据元素： D=ai| ai ElemSet，i=1,2,n,n 0 数据关系： R1= | ai-1 , ai D, i=1,2,n 基本操作： InitQueue(&Q)： 初始化操作。 设置一个空队列。 QueueEmpty(Q)： 判空操作。 若队列为空， 则返回TRUE， 否则返回FALSE。 EnQueue(&Q，x)：进队操作。在队列Q的队尾插入x。 操作成功，返回值为TRUE， 否则返回值为FALSE。 ,DeQueue(&Q,&x)： 出队操作。使队列Q的队头元素出队， 并用x带回其值。 操作成功，返回值为RUE， 否则返回值为FALSE。 GetHead（Q,&x）： 取队头元素操作。用x取得队元素的值。操作成功，返回值为TRUE，否则返回值为FALSE。ClearQueue(&Q)： 队列置空操作。 将队列Q置为空队列。DestroyQueue(&Q)： 队列销毁操作。 释放队列的空间。QueueLength(Q)。返回队列Q的元素个数，即队列Q的长度。ADT Queue,四、队列的表示和实现,1. 链队列,图3.14 链队列,队列的链式存储，称为链队列。一个链队列显然需要两个分别指示队头（头指针）和队尾（尾指针）指针才能唯一确定。,与前面介绍的单链表类似，但为了使头指针，尾指针统一起来，链队列可以定义如下：,typedef struct QNode QElemType data; /*数据域*/ struct QNode *next; /*指针域*/ Qnode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear;LinkQueue;,链队列的基本操作（1） 初始化操作。 int InitQueue(LinkQueue ,（2） 入队操作。 Status EnQueue(LinkQueue ,（3） 出队操作。 int DeQueue(LinkQueue ,2. 循环队列:队列的顺序表示和实现,图3.15 队列的基本操作,用一组连续的存储单元依次存放队列的元素，并设两个指针front、rear分别指示队头和队尾元素的位置。front：指向实际的队头；rear：指向实际队尾的下一位置。初态： frontrear0；队空： frontrear;队满： rearM; 入队： qrear=x; rear rear+1; 出队：x=qfront;front=front+1;,图3.16 循环队列,假溢出的解决方法：（1）将队中元素向队头移动；（2）采用循环队列：q0接在QM-1之后初态： frontrear0或M-1；队空： frontrear;入队： qrear=x； rear( rear+1)%M; 出队： x=qfront; front=(front+1)%M;队满： 留一个空间不用(rear+1)%M=front; 或另设一个标志以区分队空和队满。,循环队列的类型定义： define MAXSIZE 100 /*队列的最大长度*/typedef struct QElemType elementMAXSIZE; /* 队列的元素空间*/ int front; /*头指针指示器*/ int rear ; /*尾指针指示器*/SeqQueue;,循环队列的基本操作：（1） 初始化操作。 void InitQueue（SeqQueue ,（2） 入队操作。 int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素x入队*/ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了*/ return ERROR; Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return OK; /*操作成功*/,（3） 出队操作。 int DeQueue(SeqQueue /*操作成功*/ ,键盘输入循环缓冲区问题,有两个进程同时存在于一个程序中。 其中第一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户键入的字符并保存到输入缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。 当用户键入一个逗号（，）时，表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程， 重新显示字符“A”，同时用户又可以继续键入字符，直到用户输入一个分号（；），才结束第一个进程， 同时也结束整个程序。,五、队列的应用举例,define MAXSIZE 16define QueueElementType chardefine TRUE 1define FALSE 0include stdio.hinclude conio.hinclude dos.hmain()/*模拟键盘输入循环缓冲区*/ char ch1,ch2; SeqQueue Q; int f; InitQueue() ,for(;) /*第一个进程*/ printf(A); if (kbhit() ) ch1=bdos(7,0,0); /* 通过DOS命令读入一个字符*/ f= EnQueue( /* 循环队列满时， 强制中断第一个进程*/ ,if(ch1=;|ch1=,) break; /*第一个进程正常结束*/ while(! QueueEmpty(Q) /*第二个进程*/ DeQueue( /*置空ch1， 程序继续*/ ,六、 队列的其它应用,队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。,第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要