数据结构(第三章-栈和队列).ppt
《数据结构(第三章-栈和队列).ppt》由会员分享,可在线阅读,更多相关《数据结构(第三章-栈和队列).ppt(80页珍藏版)》请在咨信网上搜索。
1、数据结构第3章栈和队列栈和队列栈和队列是在程序设计中被广泛使用的两种特殊的线性表,它们的特殊性在于对栈和队列的插入和删除操作被限制为只能在表的两端(或一端)进行:L=(a1,a2,a3,ai,an)线性表:在表的任意位置进行插入和删除:栈:只能在表尾进行插入和删除:“后进先出”。队列:只能在表尾进行插入,而在表头删除:“先进先出”。和线性表相比,栈和队列的插入和删除操作受更多的约束和限定,故又称为操作受限(或限定性)的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下:线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1/表尾/表尾
2、 Delete(L,i)Delete(S,n)Delete(Q,1)1in/表尾/表头栈和队列3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现主要内容3.1 栈的类型定义栈的定义:限定仅在表尾进行插入或删除操作的线性表。表尾被称为栈顶,表头被称为栈底,不含元素的空表称空栈。栈的特点:后进先出(lastinfirstout,简称LIFO结构)或先进后出(FILO)栈的定义和特点s=(s=(a1,a2,an)ana1a2.栈底栈顶.入栈出栈栈结构示意图3.1 栈的类型定义栈的抽象数据类型定义 ADTStack数据对象:Dai|aiElemSet,i=1
3、,2,.,n,n0数据关系:R1|ai-1,aiD,i=2,.,n约定an端为栈顶,a1端为栈底。基本操作:ADTStack3.1 栈的类型定义栈的基本操作InitStack(&S)DestroyStack(&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被销毁。3.1 栈的类型定义栈的基本操作3.1 栈的类型定义栈的基本操作St
4、ackEmpty(S)初始条件:栈S已存在操作结果:若栈S为空栈,则返回TRUE,否则FALE。StackLength(S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。3.1 栈的类型定义栈的基本操作GetTop(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。ClearStack(&S)初始条件:栈S已存在。操作结果:将S清为空栈。3.1 栈的类型定义栈的基本操作Push(&S,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。a1a2ane 3.1 栈的类型定义栈的基本操作Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的
5、栈顶元素,并用e返回其值。a1a2anan-1 3.2 栈的类型实现顺序栈-栈的顺序存储表示链栈-栈的链式存储表示top=0123450栈空栈顶指针top,指向栈顶元素的下一个空位置,初值为0top123450进栈Atop栈满BCDEF设数组维数为ntop=0,栈空,此时出栈,则下溢top=n,栈满,此时入栈,则上溢toptoptoptoptop出栈123450ABCDEFtoptoptoptoptoptop栈空 类似于线性表的顺序映象实现,可用一维数组实现,定义指向表尾的指针可以作为栈顶指针。a1 an01n-13.2 栈的类型实现顺序栈类型的定义3.2 栈的类型实现用一维数组实现顺序栈的C
6、语言描述栈的顺序存储表示(静态数组)#defineMaxlen100/顺序栈的简单定义IntSMaxlen;/全局变量Inttop;/全局变量,指示栈顶元素位置/结构类型定义typedefstructIntSMaxlen;Inttop;STACK;结构体顺序栈使用例子STACKst;st.Sist.top用静态一维数组实现的缺点:.习惯做法以top=0表示空栈,但是当用C/C+语言表示时,其数组下标从0开始,在实际使用时不方便(无法判断是空栈还是有一个元素)。2.由于栈在使用的过程中,所需最大空间很难确定,用静态数组表示时,限定了最大空间,在实际使用过程中,不能随需求增加。合理的做法:使用动态
7、数组:先为栈分配一个基本量,使用中不够用时再逐步增加。栈的顺序存储表示(动态数组)#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;#defineSElemTypeinttypedefstructSElemType*base;/存储空间基址SElemType*top;/栈顶指针也可inttop;intstacksize;/允许的最大存储空间SqStack;几个约定条件:1.top=base表示栈空(inttop:top=0)2.top-base=stacksize表示栈满(top=stacksize)3.栈顶元素表示:*(top-1)(base
8、top-1)123M0栈空Top=base3.2 栈的类型实现用一维数组实现顺序栈的C语言描述3.2 栈的类型实现顺序栈基本操作的实现StatusInitStack(SqStack&S)/构造一个最大存储容量为STACK_INIT_SIZE的空栈S。S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;S.top=S.base1234:0栈空栈空3.2 栈的类型实现顺序
9、栈基本操作的实现StatusPush(SqStack&S,SElemTypee)/若栈的存储空间不满,则插入元素e为新的栈顶元素,并返回TRUE;否则返回FALSE。if(S.top-S.base=S.stacksize)/栈满,追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/追加的空间可存储元素数量为
10、STACKINCREMENT*S.top+=e;/把e压入栈顶(先压栈,再top加一)returnOK;3.2 栈的类型实现顺序栈基本操作的实现StatusPop(SqStack&S,SElemType&e)/若栈不空,则删除S的栈顶元素,/用e返回其值,并返回OK;/否则返回ERRORif(S.top=S.base)returnERROR;/栈空e=*-S.top;/先top减一,再去掉栈顶元素returnOK;3.2 栈的类型实现顺序栈基本操作的实现boolGetTop(StackS,ElemType&e)/若栈不空,则用e返回S的栈顶元素,/并返回TRUE,否则返回FALSEif(S.t
11、op=S.base)returnFALSE;e=*(S.top-1);/返回非空栈中栈顶元素returnTRUE;intStackLength(StackS);/返回S的元素个数,即栈的长度。return(S.top-S.base);3.2 栈的类型实现顺序栈基本操作的实现 voidClearStack(Stack&S);/将S置为空栈。S.top=S.base;S.stacksize=STACK_INIT_SIZE;boolStackEmpty(StackS);/若栈S为空栈,则返回TRUE,否则返回FALSE。if(S.top=S.base)returnTRUE;elsereturnFAL
12、SE;3.2 栈的类型实现链栈类型的定义结点定义入栈算法StatusPush(Lstack*top,SElemTypee)出栈算法StatusPop(Lstack*top,SElemType&e)typedefstructnodeintdata;structnode*next;LStack;.栈底toptopxptop .栈底topq .top栈底栈顶a1anan-1a1a1anan元素进入链栈(压栈)StatusPush(Lstack*top,SElemTypee)p=(LinkList)malloc(sizeof(LStack);if(!p)return-1;/*申请新结点失败*/p-da
13、ta=e;p-next=top;/*top指针指向栈顶元素*/top=p;returnOK3.2 栈的类型实现链栈基本操作的实现3.2 栈的类型实现链栈基本操作的实现链栈元素出栈(弹栈)StatusPop(Lstack*top,ElemType&e)/*将栈顶元素出栈*/Lstack*p;if(top=NULL)returnERROR;/*栈空,返回错误标志*/p=top;e=p-data;/*取top指针所指的栈顶元素*/top=p-next;/*修改栈顶指针*/free(p);returnOK;例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递
14、归3.3 栈的应用举例3.3 栈的应用举例数制转换不同数制间的转换(例如十进制数d进制数)假设待转换的十进制数为N,转化后的数制为d,则:用d不断地去除待转换的十进制数整数N,直到商等于0为止。然后将各次所得余数,以最后一次的余数为d进制数的最高数位,依次排列,即得到所求的d进制数。算法基于原理:N=(Ndivd)d+Nmodd3.3 栈的应用举例数制转换 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序例如:(1348)10=(2504)8,其运算过程如下:3.3 栈的应用举例数制转换算法描述voidconv
15、ersion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);/这里转化为8进制数N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion 在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个表达式中的括号是否相匹配?匹配思想:从左至右扫描一个字符串(或表达式),则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶删除该左括号。算法思想:设置一个栈,1)当读到左括
16、号时,左括号进栈;2)当读到右括号时,则从栈中弹出一个元素,与读到的左括号进行匹配,若匹配成功,继续读入;否则匹配失败,返回FLASE。3)表达式检验结束时,若栈为空,则匹配正确,否则表明“做括号”多了。3.3 栈的应用举例括号匹配检验3.3 栈的应用举例括号匹配检验算法描述#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆栈初始化*/intMatch_Brackets()charch,x;scanf(“%c”,&ch);while(asc(ch)!=#)/设置#号为结束符if(ch=()|(ch=)push(S,ch);elseif(c
17、h=)x=pop(S);if(x!=)printf(“括号不匹配”);returnFLASE;elseif(ch=)x=pop(S);if(x!=()printf(“(括号不匹配”);returnFLASE;/endwhile括号匹配检验3.3 栈的应用举例括号匹配检验if(S.top!=0)printf(“括号数量不匹配!”);returnFLASE;elsereturnTRUE;/endmain3.3 栈的应用举例行编辑程序问题3.3 栈的应用举例如何实现?思路1:每接收一个字符即存入用户数据区不恰当(不能保证不出差错)思路2:设立一个输入缓冲区(栈结构),用以接受用户输入的一行字符,然后
18、逐行存入用户数据区。在用户输入一行的过程中,允许用户输入出差错,并在发现有误时可以及时更正。行编辑程序问题3.3 栈的应用举例假设从终端接受这样两行字符:whli#ilr#e(s#*s)outchaputchar(*s=#+);(#为退格符,表示前一个字符无效,为退行符,表示当前行中的字符均无效)则实际有效的是下列两行:while(*s)putchar(*s+);行编辑程序问题3.3 栈的应用举例算法描述(行编辑问题)VoidLineEdit()/*利用字符栈S,从终端接收一行并传送至调用过程的数据区*/InitStack(S);/构造空栈Sch=getchar();/从终端接收第一个字符wh
19、ile(ch!=EOF)/EOF为全文结束符while(ch!=EOF&ch!=n)/判断结束或是换行switch(ch)case#:Pop(S,c);break;/仅当栈非空时退栈case:ClearStack(S);break;/重置S为空栈default:Push(S,ch);break;/有效字符进栈,未考虑栈满情形ch=getchar();/从终端接收下一个字符将从栈底到栈顶的栈内字符传送至调用过程的数据区;ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();DestroyStack(S);/LineEdit迷宫问题3.3 栈的应用举例求从迷宫入
20、口到出口的所有(简单)路径是一个经典的程序设计问题。计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。如果所有可能的通路都试探过,还是不能走到终点,那就说明该迷宫不存在从起点到终点的通道。迷宫问题3.3 栈的应用举例#1234567891012345678910i ij j入口出口迷宫问题3.3 栈的应用举例从演示过程可见:1从入口进入迷宫之后,不管在迷宫的哪一个位置上,都是先往东走,如果走得通就继续往东走;如果在某个位置(当前位置)上往东走不通的话,就依次试探往南、往西
21、和往北方向,从一个走得通的方向继续往前直到出口为止;2如果在某个位置上四个方向都走不通的话,就退回到前一个位置,换一个方向再试,如果这个位置已经没有方向可试了就再退一步,如果所有已经走过的位置的四个方向都试探过了,一直退到起始点都没有走通,那就说明这个迷宫根本不通;迷宫问题3.3 栈的应用举例3所谓走不通不单是指遇到墙挡路,还有已经走过的路不能重复走第二次,它包括曾经走过而没有走通的路。显然为了保证在任何位置上都能沿原路退回,需要用一个后进先出的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后,栈中保存的正是一条从入口到出口的路径。迷宫问题3.3 栈的应用举例求迷宫路径算法的基本思想是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第三 队列
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。