数据结构课件PPT110章全 第三章 栈和队列1.ppt 41页

'第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序3.2.4迷宫求解3.2.5表达式求值 3.3栈与递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现3.5离散事件模拟 3.1.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P45anan-1a2a1……栈顶栈底 3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来表示 top7654321-1 top用来指示当前栈顶的位置，通常称top为栈顶指针。顺序栈的类型定义如下：#defineSTACK_INIT_SIZE#defineSTACKINCREMENTtypedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack; 设S是SqStack类型的指针变量。若栈底位置在向量的低端，即s–>base是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top减1。s–>top==s->base表示空栈，s–>top-s->base==stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。 1、初始化栈算法：1.[构建栈]1.1分配空间并检查空间是否分配失败，若失败则返回错误1.2设置栈底和栈顶指针1.3设置栈大小2.[算法结束] 2、取栈顶元素算法：1.[取元素]1.1判断栈是否是空栈，若是空栈则返回错误1.2通过栈顶指针获取栈顶元素2.[算法结束] 3、入栈算法：1.[初值]获取入栈元素e2.[入栈]2.1判断栈空间是否存在，若无空间则重新分配更大的空间，并调整栈底，栈顶指针以及栈大小。2.2元素e压入栈中的栈顶位置2.3栈顶指针增加13.[算法结束] 4、退栈算法：1.[退栈]1.1判断栈是否为空，为空则返回错误。1.2获取栈顶元素e1.3栈顶指针减12.[算法结束] 3.1.3链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode;typedefstruct{structstacknode*top;}linkstack; voidinitstack(linkstack*p){p–>top=null;}intstackempty(linkstack*p){returnp–>top==null;} Voidpush(linkstack*p,datatypex){stacknode*q;q=(stacknode*)malloc(sizeof(stacknode));q–>data=x;q–>next=p–>top;p–>top=q;} Elemtypepop(linkstack*p){Elemtypex;stacknode*q=p–>top;if(stackempty(p))error(“stackunderflow.”);x=q–>data;p–>top=q–>next;free(q);returnx;} Datatypestacktop(linkstack*p){if(stackempty(p))error(“stackisempty.”);returnp–>top–>data;} 3.2栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.2.1数制转换十进制n和其它d进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:n=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下： nndiv8nmod8134816841682102125202 voidconversion(){initstack(s);scanf(“%d”,n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);}} 3.2.2括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（（）（）（（）））3.2.3行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 行编辑程序算法如下: 3.2.4迷宫求解入口出口 3.4队列3.4.1抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。 下图是队列的示意图：a1a2…an出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2循环队列－队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队 列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。０　１　２　３0123FrontrearabcFrontrear(a)队列初始为空　　　　　　（b）A,B,C入队 ０　１　２　３　　　０　１　２　３bcfrontrearfrontrear（c)a出队(d)b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(i+1==QueueSize)i=0;elsei++;利用模运算可简化为：i=(i+1)%QueueSize 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）； 其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。循环队列的类型定义：#defineMAXQSIZE100typedefstruct{QElemType*base;intfront;intrear;}SqQueue;实现算法见P64-P65 3.4.3链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructQNode{QElemTypedata;structQNode*next;}QNode;typedefstruct{QNode*front;QNode*rear;}LinkQueue; 作业自习3.3栈与递归的实现、3.5离散事件模拟题集3.1，3.7，3.15，3.19题集3.28,3.32'