《清华大学》严蔚敏数据结构C语言版配套第三章课件

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,清华大学 严蔚敏数据结构C语言版配套 第三章,第三章 栈和队列,3.1 栈,3.1.1 抽象数据类型栈的定义,3.1.2 栈的表示和实现,3.2 栈的应用举例,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.4 行编辑程序,3.2.5 迷宫求解,3.2.5 表达式求值,3.1.1 栈,3.1.1 栈的定义及基本运算,栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。,假设栈S=(a,1,，a,2,，a,3,，a,n,)，则a,1,称为栈底元素，a,n,为栈顶元素。栈中元素按a,1,，a,2,，a,3,，a,n,的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,3.1.2 顺序栈,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。,栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top,例、一叠书或一叠盘子。,栈的抽象数据类型的定义如下：P,44,a,n,a,n-1,a,2,a,1,栈顶,栈底,top,7 6 5 4 3 2 1,-1,来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：,# define StackSize 100,typedef char datatype;,typedef struct ,datatype datastacksize;,int top;,seqstack;,设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将s,top加1，退栈时需将stop 减1。因此，stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,3、判断栈满,int stackfull(seqstack *s),return(stop=stacksize-1);,4、进栈,void push(seqstack *s，datatype x),if (stackfull(s),error(“stack overflow”);,sdata+stop=x;,1、置空栈,void initstack(seqstack *s),stop=-1;,2、判断栈空,int stackempty(seqstack *s),return(stop=-1);,5、退栈,datatype pop(seqstack *s),if(stackempty(s),error(“stack underflow”);,x=sdatatop;,stop-;,return(x),/return(sdatastop-);,6、取栈顶元素,Datatype stacktop(seqstack *s),if(stackempty(s),error(“stack is enpty”);,return sdatastop;,3.1.3,链栈,栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。,链栈的类型说明如下：,typedef struct stacknode,datatype data,struct stacknode *next,stacknode;,Void initstack(seqstack *p),ptop=null;,int stackempty(linkstack *p),return ptop=null;,Void push(linkstack *p,datatype x),stacknode *q q=(stacknode*)malloc(sizeof(stacknode);,qdata=x;,qnext=ptop;,ptop=p;,Datatype pop(linkstack *p),datatype x;,stacknode *q=ptop;,if(stackempty(p),error(“stack underflow.”);,x=qdata;,ptop=qnext;,free(q);,return x;,datatype stack top(linkstack *p),if(stackempty(p),error(“stack is empty.”);,return ptopdata;,3.2 栈的应用举例,由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。,3.2.1 数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:,N=(n div d)*d+n mod d,( 其中:div为整除运算,mod为求余运算),例如 (,1348),10,=(2504),8,，,其运算过程如下：,n n div 8 n mod 8,1348 168 4,168 21 0,21 2 5,2 0 2,void conversion( ) ,initstack(s);,scanf (“%”,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 行编辑程序,在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。,行编辑程序算法如下:,void lineedit( ),initstack(s);,ch=gether( );,while(ch!=eof),while(ch!=eof & ch!=n),switch(ch),case # : pop(s,c);,case : clearstack(s);,default : push(s,ch);,ch=getchar( );,clearstack(s);,if(ch!=eof),ch=gethar( );,destroystack(s);,3.2.4 迷宫求解,入口,出口,3.4 队列,3.4.1 抽象数据类型队列的定义,队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。,当队列中没有元素时称为空队列。在空队列中依次加入元素a,1,a,2,a,n,之后，a,1,是队头元素，a,n,是队尾元素。显然退出队列的次序也只能是a,1,a,2,a,n,，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队头,队尾,队列的抽象数据定义见书,59,3.4.2 循环队列队列的顺序表示和实现,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队,列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。, 0 1 2 3,Front,rear,a,b,c,Front rear,(a)队列初始为空（b）A,B,C入队,b,c,front rear front,rear,（c) a,出队,(d) b,c,出队，队为空,和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。,为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。,这种循环意义下的加1操作可以描述为：,if(I+1=QueueSize),i=0;,else,i+;,利用模运算可简化为,： i=(i+1)%QueueSize,显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。,如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。,解决此问题的方法至少有三种：,其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；,其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。,#define QueueSize 100,typedef char DataType;,typedef Struct,int front;,int rear;,int count;,datatype dataqueuesize,cirqueue;,（1）置空队,void initqueue(cirqueue *q),qfront=qrear=0;,qcount=0;,（2）判断队空,int queueempty(cirqueue *q) ,return qcount=0;,（3）判断队满,int queuefull(cirqueue *q),return qcount=queuesize;,（4）入队,void enqueue(cirqueue *q,datatype x),if(queuefull(q),error(“queue overflow”);,qcount+;,qdataqrear=x;,qrear=(qrear+1)%queuesize;,（5）出队,datatype dequeue(cirqueue *q),datatype temp;,if(queueempty(q),error(“queue underflow”);,temp=qdataqfront;,qcount-;,qfront=(qfront+1)%queuesize;,return temp;,（6）取头指针,datatype queuefront(cirqueue *q),if(queueempty(q),error(“queue is empty.”);,return qdataqfront;,3.4.3 链队列,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：,typedef struct queuenode,datatype data;,struct queuenode *next;,queuenode;,typedef struct,queuenode *front;,queuenode *rear;,linkqueue;,下面给出链队列上实现的基本运算：,void initqueue(linkqueue *q),qfront=qrear=null;,int queueempty(linkqueue *q),return qfront=null ,void enqueue(linkqueue *q,datatype x),queuenode *p,p=(queuenode * )malloc(sizeof(queuenode);,pdata=x;,pnext=null;,if(queueempty(q),qfront=qrear=p;,else,qrearnext=p;,qrear=p;,Datatype dequeue(linkqueue *q),datatype x;,queuenode *p,if(queueempty(q),error(“queue underflow”);,p=qfront;,x=pdata;,qfront=pnext;,if(qrear=p),qrear=null;,free(p);,return x;,datatype queuefront(linkqueue *q),if(queueempty(q),error(“queue is empty.”);,return qfrontdata;,注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,习题,1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：,（1）若入栈次序为push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？,（2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。,（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。,2、链栈中为何不设头指针？,3、循环队列的优点是什么？如何判断它的空和满？,4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？,5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？,6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？,7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。,8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。,9、指出下列程序段的功能是什么？,(1) void demo1(seqstack *s),int I;arr64;n=0;,while (!stackempty(s) arrn+=pos(s);,for(I=0;n;I+) push(s,arrI);,(2) void demo2(seqstack *s,int m),seqstack t; int i;,initstack(t);,while(! Stackempty(s),if(I=pop(s)!=m) push(t,I);,While(! Stackempty(t) ,i=pop(t);,push(s,I);,