数据结构第3章 栈与队列ppt课件.ppt

《数据结构第3章 栈与队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列出进排队汉诺塔栈和队列是两种重要的线性结构栈和队列是操作受限的线性表出进3.1栈（stack）1.栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)例1：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BAC

2、A进B进B出C进C出A出BCAA进B进C进C出B出A出CBA例2：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：2.栈的抽象数据类型的定义InitStack(&S)结果:构造一个空栈S。ClearStack(&S)结果:将S重置为空栈。条件:栈S已存在。数据对象:D={ai

3、ai∈ElemSet，i=1,2,…,n}数据关系:R1={}；约定a1为栈底，an为栈顶。基本操作:A

4、DTStack{}ADTStackDestroyStack(&S)结果:销毁栈S。条件:栈S已存在。主要基本操作包括:StackEmpty(S)StackLength(S)GetTop(S，&e)Push(&S，e)Pop(&S，&e)StackTraverse(S，visit())3.栈的表示与实现顺序栈：ABCbasetop顺序栈的存储结构:typedefstruct{SElemType*base；//栈底指针SElemType*top；//栈顶指针intstacksize；//栈容量}SqStack；实现：一维数

5、组s[M]topbasebasetopbasetopbasetopAABCDEAB空栈A进栈BCDE进栈，栈满EDC出栈top=base空栈......100栈初始化S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))；if(!S.base)exit(OVERFLOW)；//存储分配失败S.top=S.base；S.stacksize=STACK_INIT_SIZE；returnOK；StatusInitStack(SqStack&S){//构造一个空

6、栈}#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量取栈顶元素if(S.top==S.base)returnERROR；//空栈e=*(S.top–1)；returnOK；StatusGetTop(SqStackS，SElemType&e){//若栈不空,用e返回s的栈顶元素，并返回OK，否则返回ERROR}ABCbasetoptop-1例删除栈顶元素B和A删除BbaseABtoptop=top-1插入A删除Atop=basee=

7、Be=A插入A删除CERROR出栈：删除栈顶元素StatusPop(SqStack&S，SElemType&e){//若栈不空，则s栈顶元素出栈，用e返回其值，并返回OK；否则返回ERROR}returnOK；if(S.top==S.base)returnERROR；//空栈e=*--S.top；例在栈中插入元素A和Btop=base初始Abasetop=top+1插入A插入A插入A插入BBtop=top+1入栈:插入元素e为新的栈顶元素StatusPush(SqStack&S，SElemTypee){//入栈*S.t

8、op++=e；returnOK；}if(S.top–S.base>=S.stacksize)//越界处理；//栈满，追加空间S.base=(SElemType*)realloc(S.base，(S.stacksize+STACKINCREMENT)*sizeof(SElemType))；if(!S.base)exit(OVERFLOW)；S.top=S.base+S.stacksize；S.stacksize+=STACKINCREMENT；越界处理链栈typedefstructSNode{SElemTypedata；

9、structSNode*next；}SNode，*LinkStack；DatanextS栈顶栈底an-1a1an入栈^…...栈底SSxp出栈^…...栈底SqS3.2栈的应用3.2.1数制转换我们学习过各种数制的转换问题。十--八进制转换十--二进制转换等。下面我们设计一程序,实现十--八进制数的自动转换。该程序功能为：对于输入