《数据结构》课件第三章

第三章栈和队列内容提要栈存储方式基本操作栈举例队列队列的存储方式循环队列3.1栈的概念栈和队列也是线性表，其特殊性在于栈和队列是操作受限的线性表。栈是限定仅在表尾进行插入或删除的线性表。表尾称为栈顶，表头称为栈底。...a2a1an栈顶栈底出栈入栈基本操作GetTop（S，&e)返回栈顶元素Push（&S，e）插入新元素ePop（&S,&e)删除栈顶元素e后进先出（LIFO）3.1.2栈的表示和实现栈的存储分为顺序栈和链式栈两种顺序栈是指栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附指针top指示栈顶元素在顺序栈中的位置ana4a3a2a10123…n-1maxsize-1datatopS一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。STACK_INIT_SIZE(存储空间初始分配量)STACKINCREMENT(存储空间分配增量)#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10；typedefstruct{SElemType*baseSElemType*top；intstacksize；}SqStack；Base为空则无栈结构Top=base则表示空栈构造一个空栈Statusinitstack(sqstack&s){s.base=(selemtype*)malloc(STACK_INIT_SIZE*sizeof(elemtype));If(!s.base)exit(overflow);s.top=s.base;s.stacksize=STACK_INIT_SIZE;ReturnOK;}AtopbasebasetopABCDEFbasetopABCDEtopbase入栈时的指针变化P47算法出栈时的指针变化栈空的判断：s->top=s->base栈满的判断：S.top-S.base>=S.stacksize堆栈的第二种表示方法堆栈用数组进行表示栈顶和栈底用整数而不是指针来表示空栈:top=0;满栈:top=Max(Max为数组长度上限)进栈出栈链栈用动态方式来存储栈可节省空间采用链表存储的栈为链栈

…top入栈和出栈就是表头结点的插入和删除操作链栈为空：S->top=null?有链栈为满的情况出现么?链栈的类型定义如下： Typedefstructnode {Elemtypedata;//数据域；

structnode*next;//指针域； }ListNode; TypedefListNode*LinkStack; LinkStacktop;//定义一个栈的栈顶指针变量

3.2栈的应用举例（一）数制转换问题voidconversion(){//对于输入的任意一个非负十进制整数，打

//印输出与其等值的八进制数

InitStack(S)；//构造空栈

scanf(”％d”，N)；while(N){Push(S，N％8)；//取余N=N／8；}//取商while(!StackEmpty(S)){Pop(S,e)；printf(“%d”，e)；}}//Conversion3.2栈的应用举例（二）迷宫求解求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。入口出口假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。回溯法的基本思想回溯法的应用——马步问题AB2143561234122121-1-21234dxdy在k方向上u=i+dx(k)v=j+dy(k)(1,1)(m,n)回溯法解决马步问题AA是一个n*m的整型矩阵,标志(i,j)点是否已经走过R(u,v)是一个函数,标志(u,v)点是否已经不在棋盘范围内3.2栈的应用举例表达式求值（算符优先的应用）表达式的表示方法波兰式E=E1E2θ逆波兰式E=θ

E1E2E.G.(2+X*Y)/3波兰式:(2xy*+)3/逆波兰式:/(+2*xy)3N*((M+4)/2)波兰式:N((M4+)2/)*逆波兰式:*N(/(+M4)2)?表达式分为3个部分：操作数（operand）、运算符（operator）和界限符运算符——算术运算符、关系运算符和逻辑运算符界限符——左右括号和表达式结束符把运算符和界限符都称为算符（OP），两个相继的运算符θ1和θ2有三种关系(θ1为栈顶元素，θ2为当前读入元素)：θ1

优先级低于θ2θ1优先级等于θ2优先级高于θ2算法的思路压栈继续读下一个运算符θ1出栈θ1运算符出栈，操作数出栈，进行运算表达式求值（算符优先的应用）OPTROPND#依次读入每个字符，若字符为操作数则存在OPND中，若字符为算符则和OPTR栈中的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（读入字符为#）需要特别留意“算符优先关系表”的内容判断当前元素操作数运算符与OPTR当前栈顶元素比较优先级大小大于压入栈OPTR等于OPTR栈顶元素出栈，读下一个元素小于操作数、运算符都出栈，进行运算，并将结果压进栈OPND压入栈OPND以正常顺序输入表达式的求值算法3*（7-2）的求值过程#读入33读入*栈顶元素#与读入元素*比较优先级#*33读入(栈顶元素与读入元素比较优先级#*（#*（37读入737读入-#*（—栈顶元素与读入元素比较优先级#*（—读入2372#*35读入)栈顶元素与读入元素比较优先级#作了7-2的操作15作了3*5的操作3.3栈与递归在程序中实现递归是栈的重要的运用之一递归函数——一个直接调用自己或者通过一系列的调用语句间接调用自己的函数函数调用前，系统完成三项工作：将所有实参和返回地址等信息传递给被调用的函数保存为被调用的函数的局部变量分配存储区将控制转移到被调用函数的入口子函数返回主函数之前，系统需要做的是：保存子函数的计算结果释放子函数的数据区依照子函数保存的返回地址将控制转移到主函数嵌套调用时按照后调用先返回的原则系统将整个程序运行时需要的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区；每当一个函数退出时，释放它的存储区；当前运行的函数必须在栈顶阶乘函数已知F（n）函数（n为自然数）的定义如下： =1若n=0=n*F（n-1）若n>0程序如何编写？函数如何递归调用，如何返回？

F（n）汉诺塔问题(Hanoi)相传在某一座古庙有三根木桩，有24个铁盘从下到上，由大到小地全部放置在其中一个木桩上。庙中流传着一个传说：“如果有一天能把24个铁盘，从一根木桩移动到另一根木桩，且必须遵守如下这两个原则:每天只能搬动1个铁盘，而且只能从最上面的铁盘开始搬动;必须维持较小的铁盘在上方的原则。 当24个铁盘完全搬至另一个木桩时，世界就会永久和平”这就是著名的汉诺塔问题。思考3个铁盘的操作步骤，由此推广到n个铁盘n个铁盘的操作过程前n-1个盘从源桩x搬到辅助桩y第n个盘从源桩x搬到目标桩z将前n-1个盘从辅助桩y搬到目标桩z需要一个辅助桩y完成Voidhanoi(intn,charx,chary,charz){if(n==1)Move(x,1,z)Else{hanoi(n-1,x,z,y);

//将1到n-1的盘移到y,z为辅助桩Move(x,n,z)

//将编号为n的盘从x移到zHanoi(n-1,y,x,z);

//将1到n-1的盘移到z,x为辅助桩}}3.4队列队列是只允许在一端进行插入，在另一端进行删除。an…ai+1…a2a1队头队尾出队列（删除）入队列（插入）先进先出队列的存储方式队列的存储方式有两种：用链表示的队列称为链队列。一个链队列需要两个分别指示队头和队尾的指针才能惟一确定。空的链队列的判决条件为头指针和尾指针均指向头结点单链队列的插入和删除的操作只需修改尾指针或头指针。另一种存储方式为顺序存储∧

Q.frontQ.rear队头头结点队尾∧

Q.frontQ.rear空队列链队列空：Q->front=Q->rear

Q.frontQ.rearx

y∧

删除x（P62）

Q.frontQ.rearx

y∧

插入x(P62)

Q.forntQ.rearx∧

∧

Q.frontQ.rearStatusEnQueue(LinkQueue&Q，QElemTypee){

//插入元素e为Q的新的队尾元素

p=(QueuePtr)malloc(sizeof(QNode))；//为结点分配空间if(!p)exit(OVERFLOW)；p->data=e；p->next=NULL；Q.rear->next=p；Q.rear=p；returnOK；}进队列StatusDeQueue(LinkQueue&Q，QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其值,并返回OK,//否则返回ERROR；if(Q.front==Q.rear)returnERROR；p=Q.front->next；//指向头结点之后的结点e=p->data；Q.front->next=p->next；if(Q.rear==p)Q.rear=Q.front；free(p)；returnOK；}出队列543210Q.rearQ.front543210J1J2J3Q.rearQ.front543210J3Q.frontQ.rear543210J5J6Q.frontQ.rear01 … …其他种类的队列结构循环队列队列元素用数组存储；Q.rear和Q.front均设为整数。根据“队尾进，队头出”的原则，Q.rear走得始终比Q.front快。01 … …Maxsize-1Q.frontQ.rearQ.rearQ.front0J5 …1J6Maxsize-1循环队列为空：Q.rear=Q.front循环队列满：Q.front=(Q.rear+1)%maxsize1Maxsize-10J3 …J1J2Q.rearQ.front0J3 …Q.rear1Q.frontMaxsize-1StatusEnQueue(SqQueue&Q，QElemTypee){

//插入元素e为Q的新的队尾元素

if((Q.rear+1)％MAXQSIZE==Q.front)returnERROR；//队列满

Q.base[Q.rear]=e；Q.rear=(Q.rear+1)％MAXQSIZE；returnOK；}Status