数据结构PPT数据结构.ppt

《数据结构PPT数据结构.ppt》由会员分享，可在线阅读，更多相关《数据结构PPT数据结构.ppt（47页珍藏版）》请在三一办公上搜索。

1、第三章 栈和队列,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.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列队列的链式表示和实现 3.4.3 循环队列队列的顺序表示和实现,3.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，an)，

2、则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top,例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P44,栈顶,栈底,top,7 6 5 4 3 2 1,-1

3、,来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#define StackSize 100 typedef char datatype;typedef struct datatype datastacksize;int top;seqstack;,设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空

4、间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,1、置空栈 void initstack(seqstack*s)stop=-1;2、判断栈空 int stackempty(seqstack*s)return(stop=-1);,3、判断栈满 int stackfull(seqstack*s)return(stop=stacksize-1);4、进栈 void push(seqstack*s，datatype x)if(stackf

5、ull(s)error(“stack overflow”);sdata+stop=x;,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.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具

6、。以下是几个栈应用的例子。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

7、(“%d”,e);,3.2.2 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（）（）（）3.2.3 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。,行编辑程序算法如下:void lineedit()initstack(s);ch=gether();while(ch!=eof)while(ch!=eof,ch=getchar();clearstack(s);if(ch!=eof)ch=gethar();destroystack(s);,

8、3.2.4 迷宫求解 入口,出口,伪代码描述迷宫算法,设定当前位置的初值为入口位置；do 若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东邻方块为新的当前位置；否则，若栈不空且栈顶位置还有其他方向未经搜索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一个邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈或栈空；while(栈不空);,表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。在计算机中，任何一个表达式都是由操作数（oper

9、and）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算体符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为单变量。表达式的结束符为“#”。算术四则运算的规则为：（1）先乘除、后加减；（2）同级运算时先左后右；（3）先括号内，后括号外。计算机系统在处理表达式前，首先设置两个栈：（1）操作数栈（OPND）：存放处理表达式过程中的操作数。（2）运算符栈（OPTR）：存放处理表达式过程中的运算符。

10、开始时，在运算符栈中先在栈底压入一个表达式的结束符“#”。表3-1给出了+、-、*、/、（、）、和#的算术运算符间的优先级的关系。,计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读出一个符号后，根据运算规则作如下的处理：（1）假如是操作数，则将其压入操作数栈，并依次读下一个符号。（2）假如是运算符，则：1）假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级，则将其压入运算符栈，并依次读下一个符号。2）假如读出的是表达式结束符“#”，且运算符栈栈顶的运算符也为“#”，则表达式处理结束，最后的表达式的计算结果在操作数栈的栈顶位置。3）假如读出的是“（”，则将

11、其压入运算符栈。4）假如读出的是“）”，则：A）若运算符栈栈顶不是“（”，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈，然后继续执行4）。B）若运算符栈栈顶为“（”，则从运算符栈退出“（”，依次读下一个符号。5）假如读出的运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈。此时读出的运算符下次重新考虑（即不读入下一个符号）。,图3-7给出了表达式5+(6-4/2)*3的计算过程，最后的结果为T4，置于OPRD的栈顶。,算法描述,Opera

12、ndType EvaluateExpression()/设OPTR和OPND分别为运算符栈和运算数栈 Initstack(OPTR);Push(OPTR,#);Initstack(OPND);c=getchar();While(c!=#|Gettop(OPTR)!=#)If(!In(c,OP)Push(OPND,c);c=getchar();/OP是运算符的集合 Else switch(Precede(Gettop(OPTR),c)/Precede是优先关系 case:/退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,O

13、perate(a,theta,b);break;return Gettop(OPND);,3.4 队列3.4.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,

14、a2,an，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：a1a2an,出队,入队,队头,队尾,队列的抽象数据定义见书59,3.4.2 循环队列队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队,列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向

15、队头元素，而尾指针始终指向队尾元素的下一位置。0 1 2 3,Frontrear,Front rear,(a)队列初始为空（b）A,B,C入队,front rear front rear,（c)a出队(d)b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。,为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称

16、这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(I+1=QueueSize)i=0;else i+;利用模运算可简化为：i=(i+1)%QueueSize,显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指

17、针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；,其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。#define QueueSize 100 typedef char DataType;typedef Struct int front;int re

18、ar;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+;q

19、dataqrear=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;,方法二：为了

20、区分循环队列是空还是满，我们可以设定一个标志位s：s=0时为空队列，s=1时队列非空。用C语言定义循环队列结构如下：typedef structElemtype queueMAXNUM;int front;/*队头指示器*/int rear;/*队尾指示器*/int s;/*队列标志位*/qqueue;下面给出循环队列的初始化、入队列及出队列的算法。,（1）初始化队列【算法3.20 循环队列的初始化】int initQueue(qqueue*q)/*创建一个空队列由指针q指出*/if(q=(qqueue*)malloc(sizeof(qqueue)=NULL)return FALSE;q-fr

21、ont=MAXNUM;q-rear=MAXNUM;q-s=0;return TRUE;,（2）入队列操作【算法3.21 循环队列的入队列操作】int append(qqueue*q,Elemtype x)/*将元素x插入到队列q中，作为q的新队尾*/if(q-s=1),（3）出队列操作【算法3.22 循环队列的出队列操作】Elemtype delete(qqueue*q)/*若队列q不为空，则返回队头元素*/Elemtype x;if(q-s=0)return NULL;/*队列为空*/q-front+;if(q-front=MAXNUM)q-front=0;x=q-queueq-front;

22、if(q-front=q-rear)q-s=0;/*置队列空*/return x;,3.4.3 链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedef struct queuenode datatype data;struct queuenode*next;queuenode;,typedef struct queuenode*

23、front;queuenode*rear;linkqueue;下面给出链队列上实现的基本运算：void initqueue(linkqueue*q)qfront=qrear=null;,int queueempty(linkqueue*q)return qfront=null,Datatype dequeue(linkqueue*q)datatype x;queuenode*p;if(queueempty(q)error(“queue underflow”);p=qfront-next;x=pdata;qfront-next=pnext;if(qrear=p)qrear=null;free(p

24、);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()，则出

25、栈的数字序列为什么？（2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？,4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元

26、素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。,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);,