SUN数据结构第3章栈和队列(第8讲).ppt

1,绪 言,从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。,2,3.1 栈,栈，也叫堆栈，是最常用也是最重要的数据结构之一。 栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 举例： 栈操作的特点：后进先出，先进后出。 因此，栈称为后进先出表（LIFO, Last In First Out）。,3,栈顶,入栈,出栈,进栈出栈示意图,栈底,4,初始化栈InitStack(S) 设置一个空栈S。 压栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素。 判栈空Empty(S) 若栈S为空栈，结果为1，否则结果为0。,2栈的基本运算,在栈顶插入元素,在栈顶删除元素,5,3.1.2 栈的顺序存储结构和基本运算的实现,栈有两种存储表示方法:顺序存储和链式存储 （1）栈的顺序存储结构 采用顺序存储结构的栈简称为顺序栈。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设整型变量top指示栈顶元素在顺序栈中的位置。,6,顺序栈数据类型的C语言描述如下：,top:栈顶指针。取值范围为0MaxSize-1。 top=-1表示栈空，top=MaxSize-1表示栈满。,#define MaxSize 100 typedef char SElemType; typedef struct SElemType dataMaxSize; int top; STACK;,顺序栈的几种状态（最大长度MaxSize为4）,栈空； 压栈； 栈满； 出栈。,8,栈的基本运算在顺序存储结构的实现,初始化栈InitStack(S) int InitStack(STACK *S) S-top=-1; return 1; ,9,int Push(STACK *S,SElemType x) if(S-top=MaxSize-1) printf(“n Stack is full!“); exit(1); S-top+; S-dataS-top=x; return 1; ,压栈前应先判断是否栈满 且注意压栈顺序： （1）top指针加1； （2）元素压入,压栈Push(S,x),10,int Empty(STACK *S) return (S-top=-1?1:0); ,判栈空EmptyStack(S),11,int Pop(STACK *S,SElemType *x) if(EmptyStack(S) printf(“n Stack is free!“); exit(1); *x=S-dataS-top;记住要删除的元素值 S-top-; return 1; ,传址,自定义函数一次只能有一个返回值,出栈Pop(S,x),12,SElemType GetTop(STACK *S) SElemType x; if(Empty(S) printf(“n Stack is free!“); return 0; x=S-dataS-top; return x； ,取栈顶元素GetTopStack(S,x),exit(1);,13,课堂练习,1.栈和队列都是（ ）。 A.顺序存储的线性结构 B.限制存取点的线性结构 C.链接存储的线性结构 D.限制存取点的非线性结构,B,14,2.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当出栈时，top变化为 。 A. top不变 . top-n C. toptop-1 D. top=top+1,C,课堂练习,15,C,课堂练习,3.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4,4、假设以S和X分别表示进栈和退栈操作，则对输入序列1,2,3,4,5进行一系列栈操作SXSSXSSXXX之后，得到的输出序列为 。,13542,试找出所有可能的出栈序列,共14种,16,课堂练习,5.若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3,pn，若p1=n，则pi为( )。 A.i B.n-i+1 C.n-i D.不确定,B,17,课堂练习,6.判定一个栈ST（MaxSize=n）为空的条件是( ) 。 ST-top!=-1 ST-top=-1 ST-top!=n ST-top=n,B,18,栈的链式存储结构和基本运算的实现,（1）栈的链式存储结构 通常将采用链式存储的栈称为链栈。,链栈结构示意图：,top栈顶指针，惟一的确定一个链栈。 链栈通常带有一个表头结点，所以top-next才指示栈顶元素。,19,栈的链式存储结构及其基本运算的实现,链栈的C语言描述如下： typedef struct Snode /定义链栈结点类型 SElemType data; struct Snode *next; LinkSTACK; LinkSTACK *top;,top的后继指针指向栈顶元素。,20,链栈的几种状态:,21,向一个栈顶指针为hs的带头结点的链栈中插入一个*s结点时，则执行（ ）。 hs-next=s; s-next=hs-next; hs-next=s; C. s-next=hs；hs=s; D. s-next=hs; hs=hs-next;,课堂练习,B,22,栈的应用举例 应用栈解决数制的转换问题,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,将十进制数转换为八进制数的算法。 typedef int SElemType; void DecToOctal(int n) int x; STACK st; /*定义一个顺序栈*/ InitStack( ,思考：若将十进制数转换为二进制时，是否直接将算法中的8换为2就可以了； 若是将十进制转换为十六进制数时直接将8换为16可以吗？,可以,不可以,24,栈的应用举例 应用栈解决数制的转换问题,char B=“0123456789ABCDEF”; void DecToOthers(int n,int b) int x; STACK st; InitStack( ,16进制数时！,25,表达式的三种表示方法：,设 Exp = S1 OP S2,则称 OP S1 S2 为前缀表示法,S1 OP S2 为中缀表示法,S1 S2 OP 为后缀表示法,例如: Exp = a b + (c d / e) f,前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,栈的应用举例 表达式求值,26,“算符优先法” 的基本思想： （1）操作数栈置为空栈，表达式起始符“#”为运算符栈的栈底元素。 （2）从左到右扫描表达式，依次读入表达式中每个字符。若所读字符为“#”，且操作符的栈顶元素也为“#”时，则输出操作数栈中的栈顶数据，即为运算的结果，结束处理。否则，进行下面处理。 （3）若为操作数，入操作数栈；若为操作符，则要将当前操作符和操作符栈中的栈顶操作符进行优先级比较。,栈的应用举例 表达式求值,27,如果当前操作符的优先级大于栈顶操作符的优先级，则将当前操作符压人操作符栈中；转第(2)步。 如果当前操作符的优先级等于栈顶操作符的优先级，则将当前操作符栈顶的操作符出栈。转第(2)步。 如果当前操作符的优先级小于栈顶操作符的优先级，将当前操作符栈顶的操作符出栈。并从操作数栈中顺次出栈两个操作数（先退出作为运算符的右操作数，后退出作为运算符的左操作数）。用刚出栈的操作符对两个操作数进行计算求值，将所得值压入操作数栈中。转第(3)步。,栈的应用举例 表达式求值,28,算术表达式3（7-2）求值的动态过程,中缀表达式转换为等价的后缀表达式,中缀表达式 等价后缀表达式 0.3(52+1) 0.3 5 21+/ 16-9(4+3) 16 9 4 3+- 2(x+y)/(1-x) (25+x) (a(a+b)+b),25 x+a a b+b+,2 x y +1 x-/,30,先找运算符，再找操作数。,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何从后缀式求值？,31,中缀表达式与后缀表达式求值比较,分别以中缀表达式求值和后缀表达式求值的方式对表达式 5+(7*8-6) 计算结果，比较运算过程。,32,3.3 栈与递归,递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。,例：汉诺塔的递归过程,33,void Hanoi (int n,char one,char two,char three) if (n = = 1) move(one,1,three); else Hanoi ( n-1, one, three, two); move(one,n,three); Hanoi ( n-1, two, one, three); ,算 法,34,队列的定义和基本运算,1队列的定义 队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。 队列特点： 先进先出(FIFOFirst In First Out),35,2.队列的基本运算,队列初始化InitQueue(Q) 设置一个空队列SQ。 入队列EnQueue(Q，x) 将x插入到队列SQ的队尾。 出队OutQueue(Q，x) 将队头元素赋给x，并删除队头元素。 取队头元素GetHeadQueue(Q，x) 由x返回队头结点的值。 判队列空EmptyQueue(Q) 队列SQ是否为空。若为空返回1，否则返回0。,36,队列的顺序表示和基本运算的实现,队列有两种存储表示方法:顺序存储和链式存储 1队列的顺序存储结构 队列的顺序存储结构简称顺序队。 顺序队是用一维数组依次存放队列中的元素和分别指示队列的首端和队列的尾端的两个变量组成。这两个变量分别称为“队头指针”和“队尾指针”。,顺序队列的数据类型定义如下,#define MaxSize typedef struct QElemType dataMaxSize; int front,rear; QUEUE;,与顺序表、顺序栈比较,37,顺序队列的设置,队列中元素用一维数组存储，数组的低下标一端为队头，高下标一端为队尾。 头指针front总是指向队头的前一位置，尾指针rear总是指向队尾元素的位置。 队列的存储空间从data1到datamaxsize-1。 若front=rear=0称为队空。 若一维数组中所有位置上都被元素装满，即尾指针rear指向一维数组最后，头指针指向一维数组开头，称为队满。 这种存储方式会产生假溢出。,38,（1）表示空队列， rear=front=0。 （4）A出队后，rear=front=3。再插入元素时，会出现假溢出的情况。,顺序队列（ MaxSize=5 ）的几种状态,克服假溢出的方法：（1）将队列中的所有元素均向最前端的位置移动； （2）采用循环队列。,39,（a）表示空队列， rear= =front= =0。 （b）元素A入队后， rear=1， front=0。 （c）B，C依次入队后， rear=3， front=0。 （d）A,B,C出队后, front=3 ,rear=3。队列又为空,循环队列的物理存储未发生任何改变，其只是充分利用数组空间，想象将数组的首尾连接起来，形成一个循环队列。,循环队列为空的判定条件为：front= =rear;,40,循环队列基本运算的实现,1、队列初始化 int InitQueue(QUEUE *Q) SQ-rear=SQ-front=0; return 1; ,41,循环队列基本运算的实现,2、入队列,（rear+1）%MaxSize,42,循环队列基本运算的实现,2、入队列 int EnQueue(QUEUE *Q,QElemType x) if(Q-rear+1)%MaxSize=Q-front) printf(“n Queue is full!“); return 0; Q-rear=(Q-rear+1)%MaxSize; Q-dataQ-rear=x; return 1; ,43,3.判队列空 int Empty(SQUEUE *SQ) return(SQ-rear=SQ-front)?1:0; ,循环队列基本运算的实现,44,4.出队 int OutQueue(QUEUE *Q,QElemType *x) if(EmptyQueue(Q) printf(“n Queue is free“); return 0; Q-front=(Q-front+1)%MaxSize; *x=Q-dataQ-front; return 1; ,（front +1）%MaxSize,45,5.取队头元素GetHeadQueue(Q，x) int OutQueue(QUEUE *Q,QElemType *x) if(EmptyQueue(Q) printf(“n Queue is free“); return 0; x=Q-data(Q-front+1)%MaxSize; return 1; ,循环队列基本运算的实现,46,循环队列中的常用基本操作,（1）队列判空条件：rear=front; （2）队列判满条件：(rear+1)%MaxSize=front; （3）入队操作： 第步，先判断队列是否已满； 第步，rear=(rear+1)%MaxSize； 第步：尾指针位置赋值相应元素； （4）出队操作： 第步，先判断队列是否已空； 第步，front=(front+1)%MaxSize；,47,循环队列中的常用基本操作,（5）计算循环队列中元素的个数： 分两种情况讨论，如图所示。,(rear-front+MaxSize)%MaxSize。,48,循环队列中的常用基本操作,（6）会判断一个队列中的元素，哪个是队头，哪个是队尾。 判断原则：一般情况下，头指针front总是指向队头的前一位置，尾指针rear总是指向队尾元素的位置。,49,队列的链式表示和实现,1. 队列的链式存储结构 队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指