《栈的类型定义》PPT课件

《《栈的类型定义》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5-2讲栈的类型定义主讲人：陈红丽通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈一、抽象数据类型栈的定义1.限定仅在表尾进行插入或删除操作的线性表称为栈，不含元素的空表称空栈。a1a2...an栈底栈顶出栈入栈2.允许插入和删除的一端称为栈顶，另一端称为栈底。3.特点：后进先出(LIFO)。问:堆栈是什么?它与一般线性表有什么不同？答：堆栈是一种特殊的线

2、性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：一对一一对一存储结构：顺序表、链表顺序栈、链栈运算规则：随机后进先出(LIFO)ADTStack{数据对象：D＝{ai

3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack4.栈的抽象数据类型定义InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack

5、(&S)初始条件：栈S已存在。操作结果：将S清为空栈。基本操作：StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S中元素个数，即栈的长度。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回栈顶元素值。StackTraverse(S,visit())初始条件：栈S已存在且非空，visi

6、t()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：435612中到了12顺序不能实现；135426可以实现。例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什

7、么？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，1出即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。例4：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，b答：A、D可以（B、C不行）。讨论：有无通用的判别原则？有。若输入序列是…,Pj…Pk…Pi…(Pj

8、类型的定义#defineSTACK_INIT_SIZE100;typedefstruct{SElemType*base;//存储空间基址SElemType*top;//栈顶指针intstacksize;//允许的最大存储空间//以元素为单位}SqStack;typedefstruct{SElemType*base;//存储空间基址inttop;//栈顶指针intstacksize;//允许的最大存储空间//以元素为单位}SqStack1;dcbas.stacksizes.tops.baseStatusInitStack(SqStack1&S,intmaxsize){//构造一个最大存储容量为m

9、axsize的空栈Sif(maxsize==0)maxsize=STACK_INIT_SIZE;S.base=newSElemType[maxsize];if(!S.base)exit(1);//存储分配失败S.stacksize=maxsize;S.top=0;//空栈中元素个数为0returnOK;}top空栈baseStatusInitStack(SqStack&S){S.base=newS