您好,欢迎访问三七文档
第三章栈和队列栈和队列是两种重要的线性结构。从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作。队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i,x)Delete(S,n,x)Delete(Q,1,x)1≤i≤n栈和队列的插入、删除操作与线性表的插入、删除操作的比较:3.1栈栈(stack)是一种只允许在一端进行插入和删除的线性表,它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push),而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时,称为空栈。根据栈的定义可知,栈顶元素总是最后入栈的,因而是最先出栈;栈底元素总是最先入栈的,因而也是最后出栈。这种表是按照后进先出(LIFO)的原则组织数据的,因此,栈也被称为“后进先出”的线性表。栈的示意图:a1a2an出栈入栈栈顶top栈底bottom…若输入序列是1,2,3,则可能的输出序列有哪些?1,3,21,2,32,1,33,2,12,3,1栈的应用在各种程序设计语言中都有子程序(或称函数、过程)调用功能。而子程序也可以调用其它的子程序,甚至可以直接或间接地调用自身,即递归。)1()1,0()!1(*1!nnnnn相应的算法:floatfact(intn){if(n==0||n==1)s=1;elses=n*fact(n-1);returns;}下面以求阶乘的递归方法为例,来分析计算机系统是如何处理这种递归调用关系的。求n!的递推公式:若求5!,递归调用执行过程:主函数mani()printf(“fact(5)”)第一层调用n=5s=5*fact(4)第二层调用n=4s=4*fact(3)第三层调用n=3s=3*fact(2)第四层调用n=2s=2*fact(1)第五层调用n=1s=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00每一次递归调用并未立即得到结果,而是进一步向深度递归调用,直到n=1或n=0时,函数fact才有结果为1,然后再一一返回计算,最终得到结果。计算机系统处理上述过程时,其关键是要正确处理执行过程中的递归调用层次和返回路径,也就是要记住每一次递归调用时的返回地址。在系统中用一个线性表动态记忆调用过程中的路径,其处理原则为:(1)在开始执行程序前,建立一个线性表,其初始状态为空。(2)当发生调用(递归)时,将当前调用的返回点地址插入到线性表的末尾;(3)当调用(递归)返回时,其返回地址从线性表的末尾取出。根据以上的原则,可以给出线性表中的元素变化状态如下图所示(以递归调用时n值的变化为例):545453453245321——该线性表就是栈3.1.1栈的类型定义3.1.3栈的应用举例3.1.2栈类型的实现[栈]提要ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:}ADTStack3.1.1栈的类型定义InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())栈的基本操作InitStack(&S)DestroyStack(&S)操作结果:构造一个空栈S。初始条件:栈S已存在。操作结果:栈S被销毁。StackLength(S)StackEmpty(S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TRUE,否则FALE。GetTop(S,&e)ClearStack(&S)a1a2an……初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。初始条件:栈S已存在。操作结果:将S清为空栈。Push(&S,e)a1a2ane……初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)a1a2anan-1……初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。StackTravers(S,visit())初始条件:栈S已存在且非空。操作结果:从栈底到栈顶依次对S的每个数据元素调用visit()。若visit()失败,则操作失效。例一、数制转换例二、括号匹配的检验例三、表达式求值3.1.3栈的应用举例例一、数制转换十进制数N和其他d进制数的转换算法基于以下原理:N=(Ndivd)×d+Nmodd例如:计算顺序输出顺序(1348)10=(2504)8,其运算过程如下:NNdiv8Nmod8134816841682102125202voidconversion(){//输入一个非负的十进制数,输出对应的八进制数InitStack(S);scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。假设在表达式中([]())或[([][])]等为正确的格式,[(])或([())或(()])均为不正确的格式。例二、括号匹配的检验分析可能出现的不匹配的情况:例如:考虑下列括号序列:[([][])]12345678•直到结束,也没有到来所“期待”的括弧。•到来的右括弧并非是所“期待”的;1)凡出现左括弧,则进栈;2)凡出现右括弧,首先检查栈是否空,若栈空,则表明该“右括弧”多余,否则和栈顶元素比较,若相匹配,则“左括弧出栈”,否则表明不匹配。3)表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明“左括弧”有余。算法的设计思想:Statusmatching(stringexp){m=Length(exp);i=0;state=1;while(im&&state){switchexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case’)’:{if(!StackEmpty(S)&&GetTop(S)==’(’){Pop(S,e);i++;}elsestate=0;break;}……}if(StackEmpty(S)&&state)returnTRUE;elsereturnFALSE;}例三、表达式求值(算符优先算法)表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。算术四则运算的规则为:(1)先乘除、后加减;(2)同级运算时先左后右;(3)先括号内,后括号外。表达式::=操作数+运算符+操作数操作数::=简单变量|表达式简单变量::=标识符|无符号整数限于二元(双目)运算符的表达式定义:为实现算符优先算法,设置两个栈:(1)操作数栈(OPRD):存放处理表达式过程中的操作数。(2)运算符栈(OPTR):存放处理表达式过程中的运算符。假定表达式语法正确,且以“#”结束。表达式求值的算符优先算法描述如下:1.初始化操作数栈和运算符栈,置表达式起始符“#”为运算符栈的栈底元素;2.从左到右依次读出表达式中的各个元素(操作数或运算符),每读出一个元素后,根据运算规则作如下的处理:(1)如果是操作数,则将其压入操作数栈,并依次读下一个元素。(2)如果是运算符,则和运算符栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即运算符栈的栈顶运算符和当前读入的元素均为“#”)。最后的表达式的计算结果在操作数栈的栈顶位置。算法见教材P.53算法的计算过程:以表达式:5+(6-4/2)*3#为例OPRDOPTR55#++((66--44//2)/242=22-26=44**33#*34=1212+125=17171)若为“”,则将当前运算符压入运算符栈,并依次读下一个元素。2)若为“==”,则A)若均为“#”,则求值结束;B)运算符栈栈顶为“(”,当前运算符是“)”,则从运算符栈退出“(”,依次读下一个元素;3)若为“”,则从操作数栈连续退出两个操作数,从运算符栈中退出一个运算符,然后作相应的运算,并将运算结果压入操作数栈。此时读出的运算符下次重新考虑(即不读入下一个元素)。运算符栈栈顶运算符的优先权?当前运算符的优先权(运算符间的优先关系请看教材P.53)3.1.2栈类型的实现顺序栈链栈#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;类似于线性表的顺序映象实现,指向表尾的指针可以作为栈顶指针。//-----栈的顺序存储表示-----{//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusInitStack(SqStack&S)S.topS.base…(栈底)(栈顶)S.stacksizeif(S.top-S.base=S.stacksize){//栈满,追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}S.topa1a2anS.base…S.tope…StatusPush(SqStack&S,ElemTypee){//若栈不空,则删除S的栈顶元素,//用e返回其值,并返回OK;//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}S.topa1a2anS.base……S.topStatusPop(SqStack&S,ElemType&e){栈顶指针top∧a1anan-1链栈3.2队列队列(queue)是一种只允许在一端进行插入,而在另一端进行删除的线性表。在表中只允许进行插入的一端称为队尾(rear),只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列,而队列的删除操作则称为出队列或退队列。当队列中无数据元素时,称为空队列。根据队列的定义可知,队头元素总是最先进队列的,也总是最先出队列;队尾元素总是最后进队列,因而也是最后出队列。这种表是按照先进先出(FIFO)的原则组织数据的,因此,队列也被称为“先进先出”表。队列的概念:队列的示意图:入队出队a1a2a3aianfrontrear……队列在计算机系统中的应用也非常广泛。例如:操作系统中的作业排队。在多道程序运行的计算机系统中,可以同时有多个作业运行,它们的运算结果都需要通过通道输出,若通道尚未完成输出,则后来的作业应排队等待,每当通道完成输出时,则从队列的队头退出作业作输出操作,而凡是申请该通道输出的作业都从队尾进入该队列。队列的应用[队列]提要3.2.1队列的类型定义3.2.2队列类型的实现ADTQueu
本文标题:数据结构第二章答案
链接地址:https://www.777doc.com/doc-8686377 .html