数据结构课件：第3章栈.ppt

1、数数 据据 结结 构构 测测 绘绘 学学 院院数数 据据 结结 构构 测测 绘绘 学学 院院二、教学要求：二、教学要求：1 1、掌握栈和队列的定义、特性，并能正确应用它、掌握栈和队列的定义、特性，并能正确应用它们解决实际问题；们解决实际问题；2 2、熟练掌握栈的顺序表示、链表表示以及相应操、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；作的实现。特别注意栈空和栈满的条件；3 3、熟练掌握队列的顺序表示、链表表示以及相应、熟练掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针操作的实现。特别是循环队列中队头与队尾指针的变化情况的变化情况数

2、数 据据 结结 构构 测测 绘绘 学学 院院栈和队列是两种特殊的线性表，是栈和队列是两种特殊的线性表，是的线性表，称限定性数据结构。的线性表，称限定性数据结构。 队列的应用队列的应用数数 据据 结结 构构 测测 绘绘 学学 院院3.1 栈（栈（stack）一、一、 栈的定义：限定仅在栈的定义：限定仅在表尾表尾进行插入或删除操进行插入或删除操作的线性表，表尾作的线性表，表尾栈顶栈顶，表头，表头栈底栈底，不含元，不含元素的空表称空栈素的空表称空栈 特点：先进后出（特点：先进后出（FILO）或后进先出（或后进先出（LIFO）ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)

3、数数 据据 结结 构构 测测 绘绘 学学 院院栈的基本操作栈的基本操作1.初始化栈：初始化栈：INISTACK(&S)将栈将栈S置为一个空栈置为一个空栈(不含任何元素不含任何元素)。2.进栈：进栈：PUSH(&S,X)将元素将元素X插入到栈插入到栈S中，也称为中，也称为 “入栈入栈”、 “插入插入”、 “压入压入”。3.出栈：出栈： POP(&S) 删除栈删除栈S中的栈顶元素，也称为中的栈顶元素，也称为”退栈退栈”、 “删除删除”、 “弹出弹出”。4.取栈顶元素：取栈顶元素： GETTOP(S,&e)取栈取栈S中栈顶元素。中栈顶元素。5.判栈空：判栈空： StackEmpty(S)判断栈判断栈

4、S是否为空，若为空，返回值为是否为空，若为空，返回值为true，否则返回值为，否则返回值为false。数数 据据 结结 构构 测测 绘绘 学学 院院例例1：对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，如果输入项序列，如果输入项序列由由ABC组成，试给出所有可能的输出序列。组成，试给出所有可能的输出序列。A进进 A出出 B进进 B出出 C进进 C出出 ABCA进进 A出出 B进进 C进进 C出出 B出出 ACBA进进 B进进 B出出 A出出 C进进 C出出 BACA进进 B进进 B出出 C进进 C出出 A出出 BCAA进进 B进进 C进进 C出出 B出出 A出出 CBA不可能产生输出

5、序列不可能产生输出序列CAB数数 据据 结结 构构 测测 绘绘 学学 院院 43512不可能实现，主要是其中的不可能实现，主要是其中的12顺序不能顺序不能实现；实现； 12345的输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。 答：答：数数 据据 结结 构构 测测 绘绘 学学 院院二、二、 顺序栈顺序栈 由于栈是运算受限的线性表，因此线性表的存储由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底的

6、线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量操作而变化的，故需用一个整型变量top来指示当前来指示当前栈顶的位置，通常称栈顶的位置，通常称top为栈顶指针。为栈顶指针。数数 据据 结结 构构 测测 绘绘 学学 院院因此，顺序栈的类型定义只需将顺序表的类因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为型定义中的长度属性改为top即可。顺序栈即可。顺序栈的类型定义如下（的类

7、型定义如下（静态）静态） # define StackSize 100 typedef struct ElemType dataStackSize; int top; SeqStack; 数数 据据 结结 构构 测测 绘绘 学学 院院/- 栈的顺序存储表示栈的顺序存储表示 -（动态） #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;数数 据据 结结 构构 测测 绘绘 学学 院院top=012

8、3450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为设数组维数为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空栈顶栈顶top 的值为下一个将要进栈的元素下标。的值为下一个将要进栈的元素下标。数数 据据 结结 构构 测测 绘绘 学学 院院 设设S S是是SeqStackS

9、eqStack类型的指针变量。若栈底位置在向类型的指针变量。若栈底位置在向量的低端，即量的低端，即s sdata0data0是栈底元素，那么栈顶指针是栈底元素，那么栈顶指针s stoptop是正向增加的，即进栈时需将是正向增加的，即进栈时需将s stoptop加加1 1，退，退栈时需将栈时需将s stop top 减减1 1。 因此，因此，s stop=0top=0表示空栈，表示空栈， s stop =stacksizetop =stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称，简称“上溢上溢”; ;当栈空时再做退栈运算也将产

10、生溢当栈空时再做退栈运算也将产生溢出，简称出，简称“下溢下溢”。上溢是一种出错状态，应该设法。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。为程序控制转移的条件。数数 据据 结结 构构 测测 绘绘 学学 院院1 1、置空栈、置空栈 void initstack(seqstack void initstack(seqstack * *s)s) s stop=0;top=0; 2 2、判断栈空、判断栈空 int

11、stackempty(seqstack int stackempty(seqstack * *s)s) return(s return(stop=0);top=0); 数数 据据 结结 构构 测测 绘绘 学学 院院3、判断栈满、判断栈满 int stackfull(seqstack *s) return(stop=stacksize); 4、进栈、进栈 void push(seqstack *s，ElemType x) if (stackfull(s) error(“stack overflow”); sdatastop+=x; 数数 据据 结结 构构 测测 绘绘 学学 院院5 5、退栈、退栈

12、 void pop(seqstack void pop(seqstack * *s,ElemType s,ElemType * *x)x) if(stackempty(s) if(stackempty(s) error( error(“stack underflowstack underflow”);); s stop-;top-; * *x=sx=sdatatop;datatop; 数数 据据 结结 构构 测测 绘绘 学学 院院6 6、取栈顶元素、取栈顶元素 ElemType stacktop(seqstack *s) if(stackempty(s) error(“stack is emp

13、ty”); return sdatastop-1; 数数 据据 结结 构构 测测 绘绘 学学 院院3.1.3 链栈链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表可以没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： 数数 据据 结结 构构 测测 绘绘 学学 院院栈的链接存储结构链栈的结点定义链栈的结点定义typedef struct node ElemType data; struct node *next; LinkStack; 数数 据据 结结 构构 测测 绘绘 学学 院院栈的链

14、接表示 链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作数数 据据 结结 构构 测测 绘绘 学学 院院在链栈中在链栈中,栈的基本运算算法如下栈的基本运算算法如下: (1)初始化栈初始化栈initStack(&L) 建立一个空栈建立一个空栈L。实际上是创建链栈的头结点。实际上是创建链栈的头结点,并将其并将其next域置为域置为NULL。对应算法如下。对应算法如下: void InitStack(ListStack *&L) L=(ListStack *)malloc(sizeof(ListStack);L-next=NULL; 数数 据据 结结

15、构构 测测 绘绘 学学 院院 (2)销毁栈销毁栈ClearStack(&L) 释放栈释放栈L L占用的全部存储空间。对应算法如下占用的全部存储空间。对应算法如下: : void ClearStack(ListStack *&L) ListStack *p=L-next;while (p!=NULL)free(L);L=p;p=p-next; 数数 据据 结结 构构 测测 绘绘 学学 院院 ( (3)求栈的长度求栈的长度StackLength(L) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,用用i记录访问的记录访问的数据结点个数数据结点个数,最后返回最后返回i值。对应算法如下

16、值。对应算法如下: int StackLength(ListStack *L) int i=0;ListStack *p;p=L-next;while (p!=NULL) i+;p=p-next; return(i); 数数 据据 结结 构构 测测 绘绘 学学 院院 (4)判断栈是否为空判断栈是否为空StackEmpty(L) 栈栈L为空的条件是为空的条件是L-next=NULL,即单链表中即单链表中没有数据结点。对应算法如下没有数据结点。对应算法如下: int StackEmpty(ListStack *L) return(L-next=NULL); 数数 据据 结结 构构 测测 绘绘 学学

17、 院院 (5)进栈进栈Push(&L,e) 将新数据结点插入到头结点之后。对应算法如下将新数据结点插入到头结点之后。对应算法如下: void Push(ListStack *&L,ElemType e) ListStack *p;p=(ListStack *)malloc(sizeof(ListStack);p-data=e;p-next=L-next; /*插入插入*p结点作为第一个数据结点结点作为第一个数据结点*/L-next=p; 数数 据据 结结 构构 测测 绘绘 学学 院院 (6)出栈出栈Pop(&L,&e) 在栈不为空的条件下在栈不为空的条件下,将头结点后继数据结点的数据域将头结点

18、后继数据结点的数据域赋给赋给e,然后将其删除。对应算法如下然后将其删除。对应算法如下: int Pop(ListStack *&L,ElemType &e) ListStack *p;if (L-next=NULL) return 0; /*栈空的情况栈空的情况*/p=L-next; /*p指向第一个数据结点指向第一个数据结点*/e=p-data;L-next=p-next;free(p);return 1; 数数 据据 结结 构构 测测 绘绘 学学 院院 (7)取栈顶元素取栈顶元素GetTop(L) 在栈不为空的条件下在栈不为空的条件下,将头结点后继数据结点的数据将头结点后继数据结点的数据域

19、赋给域赋给e。对应算法如下。对应算法如下: int GetTop(ListStack *L,ElemType &e) if (L-next=NULL) return 0; /*栈空的情况栈空的情况*/e=L-next-data;return 1; 数数 据据 结结 构构 测测 绘绘 学学 院院 (8)显示栈中元素显示栈中元素DispStack(L) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,并输出当前访并输出当前访问结点的数据域值。对应算法如下问结点的数据域值。对应算法如下: void DispStack(ListStack *L) ListStack *p=L-next;

20、while (p!=NULL)printf(%c ,p-data);p=p-next;printf(n); 数数 据据 结结 构构 测测 绘绘 学学 院院 3.2 栈的应用举例栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用成为程序设计中常用的工具。以下是几个栈应用的例子。的例子。一、栈的应用举例一、栈的应用举例-数制转换数制转换 十进制十进制N和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计算的基本问题算的基本问题,其解决方法很多其解决方法很多,其中一个简单算其中一个简单算法基于下列原

21、理法基于下列原理: 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 (“%d”,&n); while(n) push(s, n%8); n=n/8; while(! Stackemp

22、ty(s) pop(s,e); printf(“%d”,e); 数数 据据 结结 构构 测测 绘绘 学学 院院( 这是栈应用的典型例子这是栈应用的典型例子 ) 这里，这里，表达式求值的算法是表达式求值的算法是 “算符优先算符优先法法”。例如：例如：3*（7 2 ） （1）要正确求值，首先了解算术四则运算的规）要正确求值，首先了解算术四则运算的规则：则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 15四、栈的应用举例表达式计算四、栈的应用

23、举例表达式计算数数 据据 结结 构构 测测 绘绘 学学 院院（2）根据上述三条运算规则，在运算的）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符每一步中，对任意相继出现的算符 1和和 2 ，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见见教材教材P53表表3.1 （是提供给计算机用的表！）（是提供给计算机用的表！）栈的应用（表达式求值）栈的应用（表达式求值）数数 据据 结结 构构 测测 绘绘 学学 院院（3）算法思想：）算法思想： 设定两栈：操作符栈设定两栈：操作符栈 OPTR ，操作数栈，操作数栈 OPND 栈初

24、始化：设操作数栈栈初始化：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈底元素为表达式起始符的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入依次读入字符：是操作数则入OPND栈，是操作符栈，是操作符则要判断：则要判断： if 操作符操作符 栈顶元素栈顶元素，压入，压入OPTR栈。栈。数数 据据 结结 构构 测测 绘绘 学学 院院OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#

25、Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)数数 据据 结结 构构 测测 绘绘 学学 院院Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#);c=getchar(); while(c!=#)&(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,

26、c); c=getchar(); else switch(compare(c,GetTop(OPTR) case : Push(OPTR , c); c=getchar();break; case =: Pop(OPTR);c=getchar();break; case : op=Pop(OPTR); b=Pop();a=Pop(); /退栈退栈 c=getchar();break; /switch /while result=GetTop(OPND);/EvaluateExpression此函数此函数在哪里？在哪里？数数 据据 结结 构构 测测 绘绘 学学 院院五、实现递归五、实现递归 将所

27、有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：数数 据据 结结 构构 测测 绘绘 学学 院院 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：数数 据据 结结 构构 测测 绘绘 学学 院院多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：例如：void main( ) void a(

28、) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 数数 据据 结结 构构 测测 绘绘 学学 院院例例 递归的执行情况分析递归的执行情况分析 v递归过程及其实现l递归：函数直接或间接的调用自身叫l实现：建立递归工作栈void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i1 时时, 则设法将则设法将 前前 n 1 个盘子个盘子 借助借助 z ，从，从 x 移到移到 y 柱上，把柱上，把 盘子盘子 n 从从 x 移到移到 z 柱上；柱上； 把把n 1 个盘子个盘子 从从

29、y 移到移到 z 柱上。柱上。数数 据据 结结 构构 测测 绘绘 学学 院院l执行情况：u递归工作栈保存内容：形参n,x,y,z和返回地址u返回地址用行编号表示n x y z 返回地址 即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题数数 据据 结结 构构 测测 绘绘 学学 院院Void Hanoi ( int n, char x, char y, char z ) /将将 n 个个 编号从上到下为编号从上到下为 1n 的盘子从的盘子从 x 柱，借助柱，借助 y 柱移到柱移到 z 柱柱 if ( n = = 1 ) mov

30、e ( x , 1 , z ) ; /将编号为将编号为 1 的盘子从的盘子从 x 柱移到柱移到 z 柱柱 else /将将 n -1个个 编号从上到下为编号从上到下为1n-1的盘子从的盘子从 x 柱，借柱，借助助 y 柱移到柱移到 z 柱柱 Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; /将编号为将编号为 n 的盘子从的盘子从 x 柱移到柱移到 z 柱柱 /将将 n -1个个 编号从上到下为编号从上到下为 1n-1的盘子从的盘子从 y 柱，借柱，借助助 x 柱移到柱移到 z 柱柱 Hanoi ( n-1 , y , x , z ); /Hanoi