栈 课 件完整版.pptVIP

栈 课 件数 据 结 构 定义 栈与线性表相同，仍为一对一( 1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。存储结构运算规则实现方式 逻辑结构限定只能在表的一端进行插入和删除运算的线性表。基本操作 建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。 栈 是仅在表尾进行插入、删除操作的线性表。表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！ 栈的基本操作ClearStack(S)： 清除栈S中的所有元素InitStack(S)： 构造一个空栈SStackEmpty(S)：判断栈S是否为空，若为空，则返回 true；否则返回falseGetTop(S) ： 返回S的栈顶元素，但不移动栈顶指针Push(S, x) ：插入元素x为新的栈顶元素（入栈操作)Pop(S) ： 删除S的栈顶元素并返回其值（出栈操作） 顺序栈的存储结构和操作的实现 顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量top来指示栈顶的位置。 a1 a2…… an顺序栈S ai……0n栈底栈顶top压入(PUSH): S[top++]=an+1弹出( POP) : e=S[--top] 顺序栈存储结构的描述：#define Maxsize 100 /*设顺序栈的最大长度为100，可依实现情况而修改*/typedef int datatype;typedef struct{datatype stack[Maxsize];int top； /*栈顶指针*/}SeqStack； /*顺序栈类型定义*/SeqStack *s； /*s为顺序栈类型变量的指针*/ 顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系 栈为空的条件 ： top==0;栈满的条件 ： top-base==Maxsize 若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的堆栈:入栈：栈指针top “先压后加” : S[top++]=an+1出栈：栈指针top “先减后弹” : e=S[--top]顺序栈的基本操作 构造一个空顺序栈 SeqStack *InitStack() { SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack));if(!S) {printf(“空间不足”)； return NULL;}else {S-top=0; return S;}} 取顺序栈栈顶元素 datatype GetTop(SeqStack *S) ?{if (S-top==0) {printf(\n栈是空的!); return FALSE;} else return S-stack[S-top-1]; } 判别空栈int StackEmpty(SeqStack *S) {if(S-top==0) return TRUE; else return FALSE; } 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack*S，datatype x) {if(S-top==Maxsize)??? return NULL; ???else {S-stack[S-top]=x; S-top++; return s;} } Push (B);Push (C);Push (D);toptoptoptop低地址LPush (A);高地址MBCD 顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop ( );顺序栈出栈函数POP()datatype Pop( SeqStack *S) ?{if(S-top==0) {printf(\nThe sequence stack is empty!); return FALSE;}S-to