数据结构chapter3a.ppt

《数据结构chapter3a.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列3.1栈（stack）3.1.1栈的定义及基本运算栈(Stack):限定仅只能在表尾进行插入和删除的线性表。栈顶(Top):表尾。栈底(Bottom):表头。不含元素的空表称空栈。栈和队列是两种特殊的线性表，是操作受限的线性表。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈中元素按a1，a2，a3，…an的次序进栈

2、，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。栈顶栈底an…a1a2...an进栈出栈抽象数据类型栈的定义：ADTStack{数据对象:数据关系:约定an端为栈顶，a1端为栈底。基本操作:InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：

3、若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack栈的存储方式：1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈

4、顶元素在顺序栈中的位置。★栈底元素是最先进入的，实际上是线性表的第一个元素。2、链栈:利用链表实现。3.1.2栈的表示和实现#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intStackSize;//栈的当前已分配的存储空间.}SqStack;顺序栈的定义:空栈base==top是栈空标志stacksize

5、=5topbaseAtopbaseABCDEbaseABtoptopbase31204插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。栈满顺序栈的图示anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEnn-1i-1i-210nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZE初始化操作图示初始化操作图示StatusInitStack(SqSta

6、ck&S){//构造一个空栈SreturnOK;}S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INI_SIZE;nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEnn-1i-1i-210S.topS.stacksizeS.baseST

7、ACK_INIT_SIZEanaiai-1a2a1置空栈操作图示S.base=S.top表明栈为空置空前置空后StatusClearStack(SqStack&S);{//将S清为空栈}If(!S.base)returnERROR;S.top=S.base;StatusStackEmpty(SqStackS);{//若栈S为空栈，则返回TRUE，否则FALE。}If(!S.base)returnERROR;If(S.top==S.base)returnTRUE;elsereturnFALSE;S.top=nu

8、llS.stacksizeS.base=null0nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE销毁前销毁后销毁栈操作图示StatusDetroyStack_Sq(SqStack&S)//销毁一个已存在的栈;{returnOK;}If(!S.base)returnERROR;free(S.base);//回收栈空间S.bas