数据结构名师课件

数据结构名师课件

ID:5559000

大小:1.15 MB

页数:144页

时间:2017-11-16

数据结构名师课件_第1页
数据结构名师课件_第2页
数据结构名师课件_第3页
数据结构名师课件_第4页
数据结构名师课件_第5页
资源描述:

《数据结构名师课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第三章栈和队列通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列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栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现栈(stack)定义栈是只能在一端插入和删除的线性表特性:后进先出(LIFO)或先进后出(FILO)设栈s=(a1,a2,...,

2、ai,...,an),其中a1是栈底元素,an是栈顶元素。栈顶(top):允许插入和删除的一端;约定top始终指向新数据元素将存放的位置。栈底(bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底3.1栈的类型定义ADTStack{数据对象:D={ai

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

4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:}ADTStackInitStack(&S)DestroyStack(

5、&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果:构造一个空栈S。DestroyStack(&S)初始条件:栈S已存在。操作结果:栈S被销毁。StackEmpty(S)初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TRUE,否则FALE。StackLength(S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。

6、GetTop(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件:栈S已存在。操作结果:将S清为空栈。Push(&S,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。a1a2anan-1……设数组S是一个顺序栈,栈的最大容量stacksize=4,初始状态top=010S[4]2310bases[top]=xtop=to

7、p+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=0top栈满top=stacksize10253040S[4]2310top=4base3.2栈类型的实现顺序栈链栈a1a2top1.顺序栈:一维数组s[M]用顺序存储结构表示的栈。顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素,一般用一维数组表示,设置一个简单变量top指示栈顶位置,称为栈顶指针,它始终指向待插入元素的位置。top=0123450栈空栈顶指针top,指向实际栈

8、顶后的空位置,初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空,此时出栈,则下溢(underflow)top=M,栈满,此时入栈,则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间的初始分配量#defineSTACKINCREMENT10;//存储空间的分配增量typedefstruct{SElemTyp

9、e*base;//栈底指针SElemType*top;//栈顶指针(栈顶元素的下一个位置)intstacksize;//当前分配的存储容量}SqStack;类似于线性表的顺序映象实现,指向表尾的指针可以作为栈顶指针。1)和顺序表一样采用增量式的空间分配;2)操作和栈顶相关: 插入操作(入栈):将待插元素插入到栈顶元素的下一个位置; 删除操作(出栈):删除栈顶元素; 取元素操作:取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关,希望在O(1)时间内能获取操作位置,故可设置专门的栈顶指针top。3

10、)约定:top指向栈顶元素的下一个位置(便于表示空栈)。4)栈顶的初始化:S.top=S.base(在上述3)约定下的空栈形式),5)栈空:S.base==S.top,栈满:S.top-S.base>=S.stacksize6)入栈:*S.top++=e,出栈:e=*--S.top注意:4),5),6)步受3)制约。约定不同,相应的判定和处理也不一样。如假设top就指向栈

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。