软件技术基础教学配套课件张选芳傅茂洺王欣计算机软件技术基础(邮电)1－3

《软件技术基础教学配套课件张选芳傅茂洺王欣计算机软件技术基础(邮电)1－3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课件课件第一章第一章数据结构数据结构第二章第二章操作系统操作系统第三章第三章软件工程软件工程第四章第四章数据库数据库制作者：张选芳制作者：张选芳Email:zhangxuanfang@126.comEmail:zhangxuanfang@126.com电话电话:5182508:51825081计算机软件技术基础–数据结构1第一单元第一单元第二单元第二单元第三单元第三单元第四单元第四单元第五单元第五单元第六单元第六单元第七单元第七单元第八单元第八单元2计算机软件技术基础–数据结构2第三单元第三单元栈和队列栈和队列3计算机软件技术基础–数据结构3§§1.2.21.2.2栈

2、和队列栈和队列设给定栈设给定栈S=(aS=(a00,a,a11,,……aan-11),),则称则称aa0为栈为栈一．栈的定义及基本运算一．栈的定义及基本运算底，底，aan-1为栈顶。为栈顶。11、栈、栈((Stack)Stack)的定义的定义只允许在一端插入和删除的顺序表只允许在一端插入和删除的顺序表插入和删除插入和删除的一端称为的一端称为栈顶栈顶((toptop))，，另一端称另一端称为为栈底栈底((bottombottom))特点特点后进先出后进先出((LIFOLIFO))当表中没有元素时称为空栈。当表中没有元素时称为空栈。4计算机软件技术基础–数据结构4

3、【【例例11--33】】元素是以元素是以aa,a,a,,……,a,a的顺序进的顺序进0011n－11栈栈,,退栈的次序却是退栈的次序却是aa,a,a,,……,a,a,a,a。。n－11n-2210022、栈的基本运算、栈的基本运算(1)(1)InitStackInitStack（（SS））构造一个空栈构造一个空栈SS。。(2)(2)StackEmptyStackEmpty（（SS））判栈空。若判栈空。若SS为空栈，则返回为空栈，则返回TRUETRUE，，否则返回否则返回FALSEFALSE。。(3)(3)StackFullStackFull（（SS））判栈满。若判栈满。若S

4、S为满栈，则返回为满栈，则返回TRUETRUE，，否则返回否则返回FALSEFALSE。。该运算只适用于栈的顺该运算只适用于栈的顺序存储结构。序存储结构。5计算机软件技术基础–数据结构5(4)(4)PushPush（（SS，，xx））进栈。若栈进栈。若栈SS不满，则将元素不满，则将元素xx插入插入SS的的栈顶。栈顶。(5)(5)PopPop（（SS））退栈。若栈退栈。若栈SS非空，则将非空，则将SS的栈顶元的栈顶元素删去，并返回该元素。素删去，并返回该元素。(6)(6)StackTopStackTop（（SS））取栈顶元素。若栈取栈顶元素。若栈SS非空，则返回栈非空，则返

5、回栈顶元素，但不改变栈的状态。顶元素，但不改变栈的状态。二．顺序栈二．顺序栈栈的顺序存储结构简称为顺序栈栈的顺序存储结构简称为顺序栈,,它是它是运算受限的顺序表。运算受限的顺序表。6计算机软件技术基础–数据结构611．．顺序栈的类型定义顺序栈的类型定义##definedefineStackSizeStackSize100100////假定预分配的栈空间最多为假定预分配的栈空间最多为100100个元素个元素structstructSeqStackSeqStack{char{chardata[StackSizedata[StackSize];];////假定栈元素的数据类型为

6、字符假定栈元素的数据类型为字符intinttop;top;};};注意：注意：顺序栈中元素用向量存放，栈底位顺序栈中元素用向量存放，栈底位置是固定不变的，栈顶位置是随着进栈和置是固定不变的，栈顶位置是随着进栈和退栈操作而变化的。退栈操作而变化的。7计算机软件技术基础–数据结构72.2.顺序栈的基本操作顺序栈的基本操作设设SS是是SeqStackSeqStack类型的指针变量。若类型的指针变量。若栈底位置在向量的低端栈底位置在向量的低端,,即即SS--＞＞data[0]data[0]是是栈底元素。栈底元素。(1)(1)进栈操作进栈操作进栈时进栈时,,需要将需要将SS--＞＞

7、toptop加加11。。注意：注意：SS--＞＞top==StackSizetop==StackSize--11表示栈满表示栈满,,““上溢上溢””现象。现象。(2)(2)退栈操作退栈操作退栈时退栈时,,需将需将SS--＞＞toptop减减11。。注意注意::SS--＞＞top<0top<0表示空栈表示空栈,","下溢下溢""现象。现象。8计算机软件技术基础–数据结构833．．顺序栈的基本运算顺序栈的基本运算(1)(1)置栈空置栈空voidvoidInitStackInitStack（（SeqStackSeqSt