数据结构(严蔚敏)精第3章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,第三章,栈和队列,.,【课前思考】,1.什么是线性结构？,简单地说，线性结构是一个数据元素的序列。,2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n 的次序往上叠的，那么使用时候的次序应是什么样的？,必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。,3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？,是排队。在计算机程序中，模拟排队的数据结构是队列。,.,【学习目标】,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=a,i,|a,i,ElemSet，i=1,2,n,n,0,数据关系,：R1=|a,i-1,a,i,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&S),/构造一个空栈,S,S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);,if(!S.base)exit(OVERFLOW);,/为栈分配存储空间失败,S.top=S.base;,/令栈顶指针=栈底指针,/设置栈的当前可使用的最大容量,S.stacksize=STACK_INIT_SIZE;,return OK;,/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,if(!S.base),printf(“Allocate space failure!n“);,return(ERROR);,S.top=S.base;,S.stacksize=STACK_INIT_SIZE;,return(OK);,/InitStack()end,void main(),/main()function,SqStack S;,if(InitStack(S),printf(Success!The stack has been created!n“);,printf(.OK!n“);,getch();,.,（2）取顺序栈的栈顶元素,Status GetTop(SqStack S,SElemType&e),/,如果栈,S,空，返回,ERROR,；如果栈,S,不空，用,e,返回栈,S,的栈顶元素，并返回,OK,。,if(S.top=S.base)return ERROR;,/,如果栈,S,为空，则返回,ERROR,e=*(S.top-1);/,将栈顶指针减,1,后所指向的单元内的值赋给,e,return OK;,/GetTop,.,（3）,将元素压入顺序栈算法（,进栈）,Status Push(SqStack&S,SElemType e),/,将元素,e,插入到栈,S,中，成为新的栈顶元素,if(S.top-S.base S.stacksize),/,如果栈满，则追加存储空间,S.base=(SElemType*)realloc(S.base,(S.stacksixe+STACKINCREMENT*sizeof(SElemType);,if(!S.base)exit(OVERFLOW);/追加存储空间失败,S.top=S.base+S.stacksize;/修改栈顶指针,S.stacksize+=STACKINCREMENT;/修改当前栈的存储空间,/if 结束,*S.top+=e;/先将,e,送入栈顶，然后将栈顶指针加 1,return OK;,/Push,.,（4）,将元素弹出顺序栈算法（,退栈）,Status Pop(SqStack&S,SElemType&e),/,如果栈,S,空，返回,ERROR,；如果栈,S,不空，删除,S,栈顶元素，用,e,返回其值，并返回,OK,。,if(S.top=S.base)return ERROR;,/,如果栈,S,为空，则返回,ERROR,e=*-S.top;,/,先令,top,减,1,，再将,top,所指单元值赋给,e,return OK;,/Pop,.,（5）判栈空否,Int Empty(SqStack S),/,如果栈,S,空，返回,1,；如果栈,S,不空，返回,0,。,if(S.top=S.base)return 1;,/,如果栈,S,为空，则返回,1,else 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 100,Struct duseqstack,elemtype datamaxsize;,int top2;,/两个栈的栈顶指针,int flag;,.,（1）两个栈共享存储单元的进栈算法,Status DuSqStackPush(DuSqStack&S,SElemType x),/栈,S,为共享顺序栈类型 DuSqStack，含 top1、top2 和 data 数组域；,/此算法将元素,x,放入栈,S,中；如果两个栈满，则返回 ERROR,if(S.top1+1)=(S.top2),return ERROR;,/如果两个栈满，则返回 ERROR,else,/如果栈未满，则进行入栈操作,if(S.flag!=1)&(S.flag!=2),return ERROR;,/如果 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,&,S,SElemType,&,x),/栈 S 为共享顺序栈类型 DuSqStack，含 top1、top2 和 data 数组域,/此算法删除栈 S 中栈顶元素，并用 x 返回其值；如果栈空，则返回 ERROR,if(S.flag!=1)&(S.flag!=2),return ERROR;,/如果 flag1,2，则返回 ERROR,el,se,/如果 flag 为 1 或 2，则出栈,switch(S.flag),case 1:,/标志位 flag 为 1,if(S.top1 0),/如果栈 S1 不空，则对 S1 进行操作,S.top1-;,/修改栈 S1 的栈顶指针,x=S.dataS.top1;,/元素 x 出栈,/if 结束,.,else return ERROR;,/如果栈 S1 为空，则返回 ERROR,break;,case 2:,/标志位 flag 为 1,if(S.top2next=NULL;,（b）进栈运算,Status Push_L(LinkStack SElemType e),/,将元素,e,插入到栈,S,中，成为新的栈顶元素,q=(LinkStack)malloc(sizeof(SNode);,if(!q)exit(OVERFLOW);/,存储分配失败,q-data=e;q-next=top-next;top-next=q;,return OK;,/Push_L,.,（c）退栈运算,Status Pop_L(LinkStack&top,SElemType&e),/,如果栈,S,空，返回,ERROR,；如果栈,S,不空，删除,S,的栈顶元素，用,e,返回其值，并返回,OK,。,if(!top-next)return ERROR;,/,如果栈,S,为空，则返回,ERROR,e=top-next-data;/,取出栈顶元素的值,q=top-next;/,q,指向栈顶元素,top-next=q-next;/删除栈顶元素,free(q);/释放栈顶元素所占的空间,return OK;,/Pop_L,.,（d）取栈顶元素,Status GetTop_L(LinkStack top,SElemType&e),/,如果栈,S,空，返回,ERROR,；如果栈,S,不空，用,e,返回栈,S,的栈顶元素，并返回,OK,。,if(!top-next)return ERROR;/,如果栈,S,为空，则返回,ERROR,else,/,如果栈,S,不空，则返回栈顶元素,e=top-next-data;,return OK;,/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、一定是2,C、不可能是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(,while(N0),x=N%8;,Push(/*将转换后的数字压入栈S*/,N=N/8;,while(！StackEmpty(S),Pop(,printf(%d,x);,算法3.1,.,二、括号匹配问题,假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。,解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。,若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,.,int correct(char exp,int n),char stMaxSize;,int top=-1,i=0,tag=1;,while(i-1),tag=0;,/*若栈不空,则不配对*/,return(tag);,.,三、行编辑程序,功能：接收用户从终端输入的数据或程序，并存入用户的数据区。,算法思想：设输入缓冲区为一个栈结构，每当从终端接收一个字符后先作如下判别：若它既不是退格符（#）也不是退行符（）,则将该字符入栈；若是退格符（#），则从栈顶删去一个字符；若是退行符（），则将栈清空。,算法描述如下：,.,void LineEdit(),InitStack(s);,ch=getchar();,While(ch!=EOF),/EOF为全文结束符,while(ch!=EOF&ch!=“n”),switch(ch),case“#”:pop(s,c);break;,/当栈非空时退栈,case“”:clearstack(s);break,;/重置S为空栈,default:push(s,c);break;,/有效字符进栈，但未考虑栈满,ch=getchar();,clearstack(s);,if(ch!=EOF)ch=getchar();,destroystack(s);,.,五、表达式求值,表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(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,之间的优先关系必为下面三种关系之一：,1,2,，,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(,InitStack(,Push(,printf(nnPlease input an expression(Ending with):);,c=getchar();,while(c!=|GetTop(optr)!=),/*GetTop()通过函数值返回栈顶元素*/,.,if(!In(c,OP),Push(,else,switch(Precede(GetTop(optr),c),case:Pop(,.,Pop(,Pop(,v=Execute(a,theta,b);/*对a和b进行op运算*/,Push(,break;,return(GetTop(opnd);,例求表达式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)变成等价的后缀表达式。,现在用栈来实现该运算，栈的变化及输出结果如下,.,步骤,栈中元素,输出结果,说明,1,(,（进栈,2,(,1,输出1,3,(+,1,+进栈,4,(+,1 2,输出2,5,1 2 +,+退栈输出，退栈到（止,6,*,1 2 +,*进栈,7,*(,1 2 +,（进栈,8,*(,1 2 +,（进栈,9,*(,1 2 +8,输出8,10,*(-,1 2 +8,-进栈,.,11,*(-,1 2 +8 2,输出2,12,*(,1 2 +8 2 -,-退栈输出，退栈到（止,13,*(/,1 2 +8 2 -,/进栈,14,*(/(,1 2 +8 2 -,（进栈,15,*(/(,1 2 +8 2 -7,输出7,16,*(/(-,1 2 +8 2 -7,-进栈,17,*(/(-,1 2 +8 2 -7 4,输出4,18,*(/,1 2 +8 2 -7 4 -,-退栈输出，退栈到（止,19,*,1 2 +8 2 -7 4 -/,/退栈输出，退栈到（止,20,1 2 +8 2 -7 4 -/*,*退栈并输出,步骤 栈中元素 输出结果 说明,.,5.后缀表达式的求值,将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：1 2 +8 2 -7 4 -/*的值，,栈的变化情如下：,.,步骤,栈中元素,说明,1,1,1进栈,2,1 2,2进栈,3,遇+号退栈2和1,4,3,1+2=3的结果3进栈,5,3 8,8进栈,6,3 8 2,2进栈,7,3,遇-号退栈2和8,8,3 6,8-2=6的结果6进栈,9,3 6 7,7进栈,10,3 6 7 4,4进栈,.,步骤,栈中元素,说明,11,3 6,遇-号退栈4和7,12,3 6 3,7-4=3的结果3进栈,13,3,遇/号退栈3和6,14,3 2,6/3=2的结果2进栈,15,遇*号退栈2和3,16,6,3*2=6进栈,17,6,扫描完毕，运算结束,从上可知，最后求得的后缀表达式之值为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&j=N-2)/*找到了出口,输出路径*/,printf(迷宫路径如下:n);,for(k=0;k=top;k+),printf(t(%d,%d),Stackk.i,Stackk.j);,if(k+1)%5=0)printf(n);,printf(n);,return;,.,find=0;,while(didata+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=a,i,|a,i,ElemSet，i=1,2,n,n,0,数据关系,：R1=|a,i-1,a,i,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,*Queue