数据结构习题与实训教程(C语言描述)

栈和队列基本知识提要栈和队列是我们日常编程中最简单、最常用的数据结构之一。本章将重点阐述栈和队列的概念、具体实现以及与栈和队列有关的应用。3.1.1知识结构图栈和队列栈栈的定义、性质(栈底、栈顶、空栈、满栈)栈的逻辑运算(入栈、出栈、取栈顶)栈的实现(顺序栈、链栈)队列队列的定义、性质(队头、队尾、空队)队列的逻辑运算(入队、出队、取队头)队列的实现(顺序队、链队、循环队列)重点知识整理1.栈和队列的基本概念栈和队列是两种操作受限的线性表。栈（Stack）是限定在表的一端进行插入和删除操作的线性表，通常把插入、删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈按照后进先出（LastInFirstOut,LIFO）的原则进行操作，假设栈S=(a1,a2,…,an)，若栈中元素按a1,a2,…,an的次序进栈，其中a1是栈底元素，an为栈顶元素，则出栈顺序为an,an-1,…,a1。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。通常把允许插入的一端称为队尾(rear)，允许删除的另一端称为队头(front)。队列按照先进先出（FirstInFirstOut,FIFO）的原则进行操作。若在空队列中插入元素a1,a2,…,an，其中a1是队头元素，an为队尾元素，则出队顺序为a1,a2,…,an。2.栈和队列的基本逻辑运算1）栈的基本逻辑运算栈的基本运算有以下6种。（1）置空栈Init_Stack(S)：将已有的栈S置空。（2）判断栈是否为空Stack_Empty(S)：返回栈S是否为空栈。（3）判断栈是否满IsFull(S)：返回栈S是否为满栈。（4）入栈Push_Stack(S，X)：在栈不满的情况下，将元素X压入栈S中。（5）出栈Pop_Stack(S)：在栈不空的情况下，将栈顶元素弹出栈S。（6）取栈顶元素Gettop_Stack(S)：返回栈顶元素的值，但是不改变栈顶指针。2）队列的基本逻辑运算队列的运算同栈的运算类似，不同的是删除运算在表的头部进行。（1）置空队Init(Q)：将已有的队列Q置空。（2）判断队列是否为空IsEmpty(Q)：返回队列Q是否为空队列。（3）判断队列是否满IsFull(Q)：返回队列Q是否为满队列。（4）入队Push(Q,X)：在队列不满的情况下，将元素X压入队列Q中。（5）出队Pop(S)：在队列不空的情况下，将队头元素弹出队列Q。（6）取队头元素GetFront(Q)：返回队头元素的值，但是不改变队头指针。3.栈和队列的存储结构显然，以上栈和队列的基本逻辑运算只是人为规定的运算定义，只是为了我们在程序中能更好地应用栈和队列这类数据结构。计算机中用来实现定义、存储栈和队列的方式有两种——顺序表实现和链表实现。1）顺序栈栈是操作受限的线性表，由栈的定义可知，栈底的位置是不变的，只有栈顶的位置随着进栈和出栈的操作变化，只需要用一个整型变量指示栈顶的位置就可以。因此，顺序栈的定义如下：#definedatatypechar#defineMAXSIZE100typedefstruct{datatypedata［MAXSIZE］;inttop;}SEQSTACK;定义一个指向顺序栈的指针：SEQSTACK*s;s是SEQSTACK类型的顺序栈，s-data［0］是栈底元素，s-data［top］是栈顶元素，栈是正向增长的，进栈时需将s-top加1，出栈时需将s-top减1，s-top0表示空栈，s-top=MAXSIZE-1表示栈满。当栈满时再作进栈操作将产生空间溢出，简称“上溢”，当栈空时再进行出栈操作，则产生“下溢”。2）链栈为了克服由顺序存储分配固定空间所产生的溢出和空间浪费，可以采用链式存储结构来存储栈，这样的栈称为链栈。链栈的类型定义如下：#definedatatypechartypedefstructstacknode{datatypedata;structstacknode*next;}StackNode*LinkStack;LinkStacktop;对于链栈的操作和链表类似，只需要保证进栈和出栈操作放在链表的头部。3）顺序循环队列队列的顺序存储结构称为顺序队列。随着入队出队操作的进行，整个队列整体向后移动，系统作为队列用的存储区还没有满，但队列却发生了溢出，我们把这种现象称为“假溢出”。解决这一问题的常用方法是采用循环队列，将队列存储空间的最后一个位置绕到第一个位置，即将q-data［0］接在q-data［MAXSIZE-1］之后，形成逻辑上的环状空间，存储在其中的队列称为循环队列（CircularQueue）。#defineMAXLENGTH10#definedatatypecharstructQueue{datatypeQueue_Temp［MAXLENGTH］;intFront,Rear;};对一个循环队列而言，由于入队时，队尾指针Q.Rear向前追赶队头指针Q.Front，出队时队头指针追赶队尾指针，因此队列无论是空还是满，都满足Q.Front==Q.Rear条件。为解决无法判断队空或者队满的问题，常用的有三种方法。一是设立一个标识位已区别队列是空还是满。二是设置一个计数器记录队列中元素的个数。三是少用一个元素空间，即尾指针Q.Rear所指向的单元始终为空，约定入队前，测试一下队尾指针是否等于队头指针，若相等则队满；出队时测试队头指针是否等于队尾指针，若相等则认为队空。4）链队列队列的链式存储结构简称为链队，是一个仅在表头删除和表尾插入的单链表。为了操作方便我们分别用两个指针表示队列头和队列尾，我们将队列头和队列尾指针封装在一起。具体链队的定义如下：typedefstructQueuenode{datatypedata;structQueuenode*next;}Linknode;/*链队结点的类型*/typedefstruct{Linknode*front,*rear;}LINKQUEUE;/*将头尾指针封装在一起的链队列*/定义一个指向链队列的指针：LINKQUEUE*q;对于链队的操作和链表类似，只需要保证入队操作在链表的头部进行和出队操作放在链表的尾部。3.2典型题解析例3.1一个栈的入栈序列为1，2，3，4，则下列序列中不可能是该栈的出栈序列的是（）。A.1,2,3,4B.2,1,3,4C.1,4,3,2D.4,3,1,2例题解析：对于此类题目，需要根据栈的后进先出的性质，逐一选项验证是否为正确的出栈序列。根据栈的定义可知，对于栈S=(a1,a2,…,an)，若栈中元素按a1,a2,…,an的次序进栈，则出栈顺序为an,an-1,…,a1。对于A选项，在1，2，3，4入栈的时刻立刻出栈，这样出栈顺序即为1，2，3，4，故A正确。对于B选项，先让1，2入栈，然后2出栈、1出栈，再让3入栈、出栈，4入栈、出栈，这样得到的出栈序列即为2，1，3，4故B正确。对于C选项，先让1入栈、出栈，然后2，3，4全部入栈，再全部出栈，即可得到1，4，3，2的出栈顺序，故C正确。对于D选项，若想让4最先出栈，则必须让1，2，3，4全部入栈。此时，只能按照4，3，2，1的顺序出栈，而选项D中在4，3出栈后，栈顶元素为2，不为1，故根据栈的特点选项D这种出栈序列不可能出现，故本题答案为D。例3.2利用两个栈s1，s2模拟一个队列时，如何用栈的运算实现队列的插入、删除以及判队空运算。请简述这些运算的算法思想。例题解析：栈的特点是后进先出，队列的特点是先进先出。对于一组数据组成的队列，要求插入操作在队尾进行，删除操作在队头进行。下面分别针对队列的插入、删除和判队空进行处理。首先初始时设栈s1和栈s2均为空且容量相等（这里假设为3）。利用s1作为入队功能栈，s2作为出队功能栈。设将ABCDE依次入队，然后依次出队。（1）对于队列的插入操作。分以下三种情况讨论：第一种情况，若s1未满，则元素入s1栈；如ABC入队时，s1都处于未满状态，直接入栈A、入栈B、入栈C。如图3-1所示。第二种情况，若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；当D入队时，需要将s1中的数据出栈，然后入栈s2。如图3-2所示。图3-1s1栈未满图3-2s1栈满第三种情况，若s1满，s2不空（已有出队列元素），则不能入队。如图3-3所示。图3-3不能入队情况（2）用栈s1和s2模拟队列出队（删除）：针对于模拟入队的三种情况，模拟出队也分为三种情况。第一种情况，若栈s2不空，退栈，即是队列的出队；第二种情况，若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。第三种情况，若栈s1为空并且s2也为空，队列空，不能出队。（3）判队空，若栈s1为空并且s2也为空，才是队列空。讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。例3.3顺序队列一般组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray［0..n-1］，队列头指针为front，队列尾指针为rear，则listarray［rear］表示下一个可以插入队列的位置。请解释其原因。例题解析：循环队列(见图3-4)解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如，在队列长为10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空呢，一般采取牺牲一个单元的做法或设标记法。即假设front==rear为队空，而（rear+1）%MaxSize==front为队满，或通过设标记tag。若tag=0，front==rear则为队空；若tag=1，因入队而使得front==rear，则为队满。图3-4循环队列本题中队列尾指针rear，指向队尾元素的下一位置，listarray［rear］表示下一个入队的元素。在这种情况下，可规定，队头指针front指向队首元素。当front==rear时为队空，当（rear+1）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n。具体入队、出队操作请参见教材第3章。例3.4假设以顺序存储结构实现一个双向栈(见图3-5)，即在一维数组的存储空间中存在两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化initstack(tws)，入栈push(tws,i,x)和出栈pop(tws,i)，其中i为0或1，用以分别指示设在数组两端的两个栈。typedefstruct/*两栈共享一向量空间*/{datatypev［m］;/*栈可用空间为0~m-1*/inttop［2］}twostack;图3-5双向栈例题解析：(1)voidinitstack(twostack*s)/*两栈共享向量空间，本算法是初始化栈操作*/{typedefstruct/*两栈共享一向量空间*/{datatypev［m］;/*栈可用空间为0~m-1*/inttop［2］}twostack;s-top［0］=0;s-top［1］=m;}/*算法结束*/(2)intpush(twostack*s,inti,datatypex)/*两栈共享向量空间，i是0或1，表示两个栈，x是进栈元素，*//*本算法是入栈操作*/{if(abs(s-top［0］-s-top［1］)=