计算机软件就是基础 软件基础之数据结构-栈、队

1,作业:P1022.162.172.21(1,2)2.222.23,2,第二章常用数据结构及其运算-栈与队,3,主要内容栈队列这两种结构都是特殊的线性表,4,栈,栈的定义栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。,5,根据栈的定义可知，最先放入栈中的元素在栈底，最后放入栈中的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。没有元素时称为空栈,6,讨论输入序列为123的有关情况：反序：正序：其他:,7,栈的运算,1、初始化栈：INISTACK(typedefstructelemtypeStackStackSize;inttop;seqstack;,11,设S是seqstack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将stop加1，退栈时需将stop减1。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件.,12,栈的五种运算,（1）初始化栈voidinistack(seqstack*s)S-top=-1;,13,top,top,top,top,top,进栈,退栈,栈空,栈满,14,（）进栈voidpush(seqstack,15,（）退栈elemtypepopQstack(qstack*s)if(s-topStack(s-top)-;,16,（）取栈顶元素elemtypegettopQstack(qstack*s)if(s-topStacks-top;,17,（5）判栈空否intNotemptyQstack(qstack*s)if(s-Toptop=MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。,19,3、栈的共享存储单元有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。,20,链栈链栈结构及数据类型栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图。以下的输入序列为an,an-1,a1,21,栈的应用栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。算术表达式的求值算术表达式中包含了算术运算符和算术量(常量、变量、函数)，而运算符之间又存在着优先级，编译程序在求值时，不能简单地进行从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右.,22,因此，要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数（算术量），在进行表达式求值时，编译程序从左到右扫描，遇到操作数，一律进入操作数栈，遇到运算符，则应与运算符栈的栈顶比较，若运算符优先级高于栈顶则进栈，否则退栈，退栈后，在操作数栈中退出两个元素(先退出在运算符右，后退出在运算符左)，然后用运算符栈中退出的栈顶元素进行运算，运算的结果存入操作数栈中，直到扫描完毕。这时运算符栈为空，操作数栈中只有一个元素，即为运算的结果。,23,算术表达式的两种表示方法，即中缀表示法和后缀表示法。中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律.例如，对于下列各中缀表达式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*(a+b)+b)对应的后缀表达式为：（1）35/8+（2）18943+*-（3）25x+aab+*b+*,24,计算表达式:A/B*C+D=?,A,B,C,;,/,*,A,T1,;,/,B*CT1,A,T1,;,/,T2,;,A/T1T2,T2,D,;,+,T3,;,T2+DT3,25,函数的嵌套调用在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执行，因此必须用栈来保存函数中中断的地址，以便调用返回时能从断点继续往下执行。,例设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）。,26,一般情况的示意图,27,28,主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态，进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数a处于挂起状态，进入函数b中执行，函数b中调用函数c，留下一个断点地址t进栈，然后函数b处于挂起状态，进入函数c中执行，函数c执行完后，要返回断点处继续执行，但返回到那一个断点呢?根据栈顶元素来决定。返回时，执行退栈操作，先退出t，故返回t断点继续执行，接着退栈退出s，故返回s断点继续执行，接着退栈退出r，返回r断点继续执行，最后栈为空，算法结束。,29,子程序A,子程序B,子程序C,主过程,调用B,调用A,调用C,返回,返回,返回,结束,r:,s:,t:,30,函数的递归调用函数的递归调用也是一种嵌套,故也必须用栈来保存断点信息，但递归调用相当于同一个函数的嵌套调用，故除了保存断点信息外，还必须保存每一层的参数、局部变量等。,31,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,n=5,32,队列,队列的定义仅允许在一端进行插入，另一端进行删除的线性表，称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（frort）。,队列是一种先进先出（FirstInFirstOut）的特殊线性表，或称FIFO表。若队列中没有任何元素，则称为空队列，否则称为非空队列。,33,队列在生活中的范例。队列体现的思想。,队列的描述可以用如图所示的方式所描述。,34,队列的基本运算队列可定义如下五种基本运算：,1、初始化队列INIQUEUE(/定义队列的最大容量为maxlenstructseqqueueelemtypequeuemaxsize;/将队列中元素定为数组型，元素类型为elemtypeintfront;/队头指针intrear;/队尾指针;,36,顺序队列将队列中元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队尾，将这样的队列看成是顺序队列。,若一维数组中所有位置上都被元素装满，称为队满，即尾指针rear指向一维数组最后,而头指针指向一维数组开头，称为队满。,front,rear,0,1,2,初始情况：,37,但有可能出现这样情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。如下图所示，若队列的最大容量maxsize=9，此时，再进队时将发生溢出。我们将这种溢出称为“假溢出”。,front,rear,38,要克服“假溢出”，1.可以将整个队列中元素向前移动;2.或者每次出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但是，在顺序队列中，这些克服假溢出的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，一般采用下面的循环队列形式。,39,rear=0front=0,rear=3front=3,front=0,rear=5,rear=5,front=3,初始,front=rear,front=rear=0,队满,rear=m,队尾指针指向当前队尾元素实际位置,队头指针指向当前队头元素的前一位置.,40,循环队列为了克服顺序队列中假溢出，通常将一维数组queue0到qmaxsize-1看成是一个首尾相接的圆环，即queue0与queuemaxsize-1相接在一起。将这种形式的顺序队列称为循环队列，见图。,41,0,1,Maxsize-1,front,rear,2,3,4,5,6,7,8,循环队列示意图,42,在循环队列中，若front=rear,则称为队空，若(rear+1)%maxsize=front,则称为队满，这时，循环队列中能装入的元素个数为maxsize-1,即浪费一个存储单元，但是这样可以给操作带来较大方便。,43,4、循环队列上五种运算实现（1）队列初始化VoidINIQUEUE(seqqueue,44,（2）进队列Voidenqueue(seqqueue,45,（3）出队列Voiddlqueue(seqqueue,46,（4）取队头元素elemtypegethead(seqqueueq)if(q.rear=q.front)coutdata;,51,（4）入队列voidpush(linkqueue,52,（5）出队列voidpop(linkqueue,53,队列的应用,队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出几个例子来说明它，其它应用在后面章节中将会遇到。,54,第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。,55,第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来