第三章 栈和队列上-栈-10-9_第1页
第三章 栈和队列上-栈-10-9_第2页
第三章 栈和队列上-栈-10-9_第3页
第三章 栈和队列上-栈-10-9_第4页
第三章 栈和队列上-栈-10-9_第5页
已阅读5页,还剩53页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

3.1栈

3.1.1抽象数据类型-栈的定义

3.1.2栈的表示和实现3.2栈的应用举例

3.2.1数制转换

3.2.2括号匹配的检验

3.2.4行编辑程序

3.2.5迷宫求解

3.2.6表达式求值3.4队列

3.4.1抽象数据类型-队列的定义

3.4.2链队列-队列的链式表示和实现

3.4.3循环队列-队列的顺序表示和实现第三章栈和队列1重点:熟悉栈和队列的逻辑结构定义和特性,并在各种问题中灵活使用熟练栈在两种存储结构〔顺序存储结构和链式存储结构〕下的实现方法熟练队列在两种存储结构〔循环队列和链队列〕下的实现方法第三章栈和队列2第三章栈和队列难点:栈和队列的在各种问题中灵活使用栈满和栈空的条件以及它们的描述方法队满和队空的描述方法,循环队列中对边界条件的处理3栈、队列、串是常用数据结构从数据元素的逻辑关系看,栈、队列与串是线性表,但从操作方式与种类看,它们与线性表有许多不同。把数据间逻辑关系与相应的操作作为整体看待〔即作为抽象数据类型〕,它们应为新的数据结构。栈与队列是操作受限的线性表,串是元素受限的线性表。尽管它们与线性表有许多共同点,但也有不少特殊性。本章重点介绍这些特殊性,并给出一些典型的应用实例。第三章栈和队列4第三章栈和队列3.1栈53.1.1栈的抽象数据类型定义定义:栈(Stack)是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶(top),表头端称栈底(bottom)S=(a1,a2,…,an),a1端—栈底;an端—栈顶特点:栈的修改是按后进先出(LastInFirstOut,LIFO)的原那么进行的3.1栈an...a2a1栈底出栈进栈an...a2a1栈底栈顶出栈进栈63.1.1抽象数据类型栈的定义例如:◆火车扳道站、进入单车道死胡同的汽车。◆在计算机系统中,栈的例子更是多见。例如,记录中断返回地址〔断点〕的结构就是栈。处理完中断事件后恢复被中断事件的继续执行,记下断点。在允许多级中断的情况下,中断处理过程仍可能被其它中断所中断,因此,系统可能同时要保存多个断点。中断恢复是先恢复最近被打断的过程,所以断点的保存次序与取出次序相反,满足栈的特性。3.1栈7中断处理示意图

0过程0开始中断处理过程1中断处理过程2中断处理过程3断点1断点2断点33.1.1抽象数据类型栈的定义3.1栈83.1栈3.1.1抽象数据类型栈的定义栈的操作置空栈,即栈的初始化进栈,在栈的顶部插入一个新的元素取栈顶元素,在非空栈中读取栈顶元素判断是否空栈退栈,在非空栈中将栈顶元素从栈中删除判断是否满栈9栈的抽象数据类型定义ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。根本操作:InitStack(&S)操作结果:构造一个空栈S。DestroyStack(&S)初始条件:栈S已存在。操作结果:栈S被销毁。3.1.1抽象数据类型栈的定义P453.1栈10ClearStack(&S)初始条件:栈S已存在。操作结果:将S清为空栈。StackEmpty(S)初始条件:栈S已存在。操作结果:假设栈S为空栈,那么返回TRUE,否那么FALSE。StackLength(S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。3.1.1抽象数据类型栈的定义3.1栈11

GetTop(S,&e)

初始条件:栈S已存在且非空。

操作结果:用e返回S的栈顶元素。

Push(&S,e)

初始条件:栈S已存在。

操作结果:插入元素e为新的栈顶元素。

Pop(&S,&e)

初始条件:栈S已存在且非空。

操作结果:删除S的栈顶元素,并用e返回其值。

}ADTStack3.1.1抽象数据类型栈的定义3.1栈123.1.2栈的表示和实现顺序栈:

类似于线性表的顺序映象实现。用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素,同时设top指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。栈顶位置top随着进栈和出栈操作而变化。

链栈利用链表实现栈,注意链表中指针的方向是从栈顶指向栈底。3.1栈13栈的顺序存贮结构用一维数组模拟连续的存贮空间。由于插入与删除都是针对表的一端进行的,所以用一个top指示插入/删除端的位置,一般称该量为栈顶指针。这种用一维数组与栈顶指针表示栈的结构如以下图所示:LenLen栈底栈底RoomRoom栈顶栈顶LenLen栈底栈底RoomRoom栈顶栈顶栈底栈底RoomRoom栈顶3.1栈3.1.2栈的表示和实现14顺序栈栈空的表示通常用top=0表示,但这与C语言中数组的下标约定相冲突;栈在使用过程中所需空间不定。因此采取措施:1.初始化空栈时不限定栈的最大容量:先分配一个根本容量,需要时再逐渐扩大STACK_INIT_SIZE;STACKINCREMENT2.设置栈底指针base,始终指向栈底。当base=NULL,栈不存在当top=base时,栈空3.1栈3.1.2栈的表示和实现15topbasebasetopbasetopbasetopAABCDEAB空栈

A进栈

BCDE进栈EDC出栈3.1.2栈的表示和实现P463.1栈16栈的顺序存储表示:P46#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;//base=NULL栈不存在SElemType*top;//栈顶指针,设栈顶栈底两指针目的//是便于判断栈是否为空,防止使用top=0intStackSize;//栈的当前已分配的存储空间.}SqStack;3.1.2栈的表示和实现3.1栈17顺序栈的根本操作1:StatusInitStack(SqStack&S);//构造一个空栈SStatusDestroyStack(SqStack&S);栈S被销毁StatusClearStack(SqStack&S);栈S置为空栈StatusStackEmpty(SqStackS)栈为空那么返回TRUE,否那么FALSEIntStackLength(SqStackS)返回S的元素个数,即栈的长度3.1.2栈的表示和实现3.1栈18顺序栈的根本操作2:StatusGetTop(SqStackS,SElemType&e)栈S存在且非空那么用e返回S的栈顶元素,并返回ok,否那么errorStatusPush(SqStack&S,SElemTypee)插入e为新的栈顶元素StatusPop(SqStack&S,SElemType&e)栈S非空那么删除S的栈顶元素并用e返回其值,并返回ok,否那么errorStatusStackTraverse(SqStackS,visit())栈S存在且非空那么从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,那么操作失败3.1.2栈的表示和实现3.1栈19顺序栈的根本操作算法描述1:P47StatusInitStack(SqStack&S){//构造一个空栈

S.base=(SelemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;S.stacksize=STACK_INI_SIZE;returnOK;}//IniStack3.1.2栈的表示和实现3.1栈20顺序栈的根本操作算法描述2:StatusGetTop(SqStackS,SElemType&e);{//栈S存在且非空那么用e返回S的栈顶元素,并返回ok,否那么error。if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTop思考题:GetTop和Pop函数的区别?3.1.2栈的表示和实现3.1栈21顺序栈的根本操作算法描述3:StatusPush(SqStack&S,SElemTypee);{if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));//重新分配内存〔换更大的杯子,装原来的水〕,S.base指向的内存地址会被改变if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//入栈,top++returnOK}//Push3.1.2栈的表示和实现3.1栈22顺序栈的根本操作算法描述4:StatusPop(SqStack&S,SElemType&e);{//栈S非空那么删除S的栈顶元素并用e返回其值,并返回//ok,否那么error。if(S.top==S.base)returnERROR;e=*--S.top;//出栈,--topreturnOK;}//Pop思考题:请说明GetTop和Pop函数的区别,并指出Push和Pop函数中top指针的变化过程的区别?3.1.2栈的表示和实现3.1栈23顺序栈的根本操作算法描述5:StatusClearStack(SqStack&S);{S.top=S.base;}//ClearStackStatusStackEmpty(SqStackS);{if(S.top==S.base)returnTRUE;elsereturnFALSE;}//StackEmpty3.1.2栈的表示和实现3.1栈24顺序栈的“上溢〞和“下溢〞“上溢〞也就是栈顶指针指出栈的外面,显然是出错了。顺序栈好比一个盒子,我们在里头放了一叠书,当我们要用书的话只能从第一本开始拿,那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了,这时就是“上溢〞。“下溢〞本身可以表示栈为空栈。当栈中已没有书时,我们再去拿,看看没书,把盒子拎起来看看盒底,还是没有,这就是“下溢〞。因此可以用它来作为控制转移的条件。3.1.2栈的表示和实现3.1栈253.1栈多栈共享存贮空间栈采用连续存贮结构时,要预分配足够大的存贮空间。假设系统中使用n个栈,每个栈的最大尺寸ni(i=1,2,…,n),那么n个栈要预分配的总存贮容量为如果这n个栈在任何时刻的总的存贮占用量均不会超过N,且有N<那么可考虑令这n个栈共享一块大小为N的存贮区,以节省存贮空间263.1栈两栈共享存贮空间对于两栈共享存贮空间,可以特殊处理,以防止移动元素。方法是将两栈的栈底分别固定在存贮区的两底,两栈指针相向增长栈1栈2栈底1栈底2栈顶1栈顶2273.1栈栈的链式表示—链式栈1〕线性表采用链式存贮,主要有两个目的:防止插入/删除操作带来的移动元素问题,以及存贮区的预申请问题。对于栈,由于插入与删除只在栈顶进行,故不存在第一个问题。所以栈采用链式存贮结构主要目的是防止存贮区的预申请问题。2〕与线性链表类似,链式栈也需要一个描述结点,它作为整个栈的代表。它的主要数据项为指向栈顶元素的指针top,另外可设一个存贮当前长度的量。链式栈中的存贮栈元素结点的结构与线性链表相同。28链栈:栈的链式存储结构称为链栈。1、链栈的类型定义

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。在前面学习了线性链表的插入删除操作算法,不难写出链式栈初始化、进栈、出栈等操作的算法栈顶栈底Datanexttopan-1a1an3.1.2栈的表示和实现3.1栈293.1栈链式栈的结点描述〔栈顶指向栈底〕TypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;PHeadLen栈顶栈底Null栈的链式存储结构称为链栈,它是运算受限的单链表,插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作,故链表没有必要像单链表那样附加头结点。30

voidpush(o) //入栈{o.next=p.next;p.next=o}voidpop() //出栈{ifp==Null{printf(“popfails-emptystack}else{a=p.next.data;p=p.next}}voidtop() //返回栈顶元素{ifp==nullprintf(“topfails-emptystack)elsereturnp.data;}2、链栈的根本操作算法描述13.1.2栈的表示和实现3.1栈31

小结

1栈是限定仅能在表尾一端进行插入、删除操作的线性表;

2栈的元素具有后进先出的特点;

3栈顶元素的位置由一个称为栈顶指针的变量指示,进栈、出栈操作要修改栈顶指针。

3.1栈32下一小节

3.2栈的应用举例33

由于栈结构具有的后进先出的固有特性,致使栈成为程序设计中常用的工具。3.2栈的应用举例算法思想:“翻天覆地〞翻天覆地34

例:十进制数N和其它d进制数的转换是计算机计算的根本问题。对于输入的任意一个非负十进制数,显示输出与其等值的八进制数,其解决方法很多,其中一个简单算法基于以下原理:3.2.1数制转换P483.2栈的应用举例思想:除权取余,反向输出35

原理:N=(Ndivd)*d+Nmodd(其中:div为整除运算,mod为求余运算,d为预转换数制)。例如(1348)10=(2504)8,其运算过程如下:

N1348168212Ndiv81682120Nmod84052显示时按从高位到低位的顺序输出3.2栈的应用举例3.2.1数制转换原理计算时从低位到高位顺序产生八进制数的各个数位36

原理:N=(Ndivd)*d+Nmodd3.2栈的应用举例3.2.1数制转换原理

N

Ndiv8Nmod81348168416821021252024052算法分析:当N≠0,将N%r压入栈中;用N/r代替N;假设N>0,那么重复以上步骤,假设N=0,那么栈的内容依次输出。37voidconversion()

{InitStack(s);//建空栈,s为栈顶指针变量

scanf(“%d〞,&x);//输入一个非负十进制整数

while(x!=0){//x不等于零循环

push(s,x%8);//x/8第一个余数进栈x=x/8;//整除运算}

while(!StackEmpty(s))//输出存放在栈中的八制数位{x=pop(s);

printf(“%d〞,x);

}

}3.2栈的应用举例3.2.1数制转换383.2.3行编辑程序P49一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定#为退格符,以表示前一个字符无效,@为退行符,表示当前行所有字符均无效。例:在终端上用户输入为whli##ilr#e(s#*s)

应为while(*s)3.2栈的应用举例393.2.3行编辑程序行编辑程序算法如下:voidlineedit(){//利用字符栈S,从终端接收一行并传送至调用过程的数据区。initstack(s);//构造空栈Sch=getchar();//从终端接收第一个字符while(ch!=eof){//EOF为全文结束符while(ch!=eof&&ch!=‘\n’){//“\n〞为回车符switch(ch){case‘#’:pop(s,ch);break;//仅当栈非空时退栈case‘@’:clearstack(s);break;//重置S为空栈3.2栈的应用举例403.2.3行编辑程序default:push(s,ch);break;//有效字符进栈,未考虑栈满情形}ch=getchar();//从终端接收下一个字符}//〔程序段略…〕将从栈底到栈顶的字符传送至调用过程的数据区;clearstack(s);//重置S为空栈if(ch!=eof)ch=gethar();}destroystack(s);}3.2栈的应用举例413.2栈的应用举例在计算机中,表达式可以有三种不同的标识方法设Exp=S1+OP+S2那么称OP+S1+S2为表达式的前缀表示法称S1+OP+S2为表达式的中缀表示法称S1+S2+OP为表达式的后缀表示法可见,它以运算符所在不同位置命名的。

例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+3.2.5栈应用——表达式求值P52423.2栈的应用举例结论:操作数之间的相对次序不变运算符的相对次序不同中缀式丧失了括弧信息,致使运算的次序不确定前缀式的运算规那么为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式后缀式的运算规那么为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式3.2.5栈应用——表达式求值433.2栈的应用举例如何从后缀式求值?先找运算符,后找操作数如何从原表达式求得后缀式?分析“原表达式〞和“后缀式〞中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f

运算符#(+/优先数-1011223每个运算符的运算次序要由它之后的一个运算符来定,假设当前运算符的优先数小,那么暂不进行;否那么立即进行3.2.5栈应用——表达式求值44+

2

1

-*/()#+-*/()#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=算符间的优先关系表注:

1

,

2是相邻算符,

1在左,

2在右3.2栈的应用举例3.2.5栈应用——表达式求值45

表达式中任何相邻运算符

1

,

2的优先关系有:

1<

2:

1的优先级低于

2

1=

2:

1的优先级等于

2

1>

2:1的优先级高于

23.2栈的应用举例3.2.5栈应用——表达式求值463.2栈的应用举例表达式求值的规那么:1)

设立运算符栈和操作数栈2)

设表达式的结束符为“#〞,预设运算符栈的栈底为“#〞3)

假设当前字符是操作数,那么进操作数栈4)

假设当前运算符的优先数高于栈顶运算符,那么进栈5)

否那么,退出栈顶运算符作相应运算6)

“(〞对它之前的运算符起隔离作用,“)〞可视为自相应左括弧开始的表达式的结束符。3.2.5栈应用——表达式求值473.2栈的应用举例例子:求值:3*〔7-2〕StepsOPTROPTDInputOperator1 # 3*(7-2)# PUSH(OPTD,’3’)2 # 3 *(7-2)# PUSH(OPTR,’*’)3 #* 3 (7-2)# PUSH(OPTR,’(’)4 #*( 3 7-2)# PUSH(OPTD,’7’)5 #*( 37 -2)# PUSH(OPTR,’-’)6 #*(- 37 2)# PUSH(OPTD,’2’)7 #*(- 372)# operate(’7’,-’,’2’)8 #*( 35 )# POP(OPTR) 9 #* 35 # operate(‘3’,’*’,’5’)10 # 15 #return(GETTOP(OPTD))3.2.5栈应用——表达式求值483.2栈的应用举例OperandTypeEvaluateExpression(){//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合。InitStack(OPTR);Push(OPTR,'#');initStack(OPND);c=getchar();while(c!='#'||GetTop(OPTR)!='#'){if(!In(c,OPTR)){Push((OPND,c);c=getchar();}//不是运算符那么进运算数栈elseswitch(precede(GetTop(OPTR),c){case‘<’://栈顶元素优先权低,〔来的是大官,请进〕Push(OPTR,c);c=getchar();3.2.5栈应用——表达式求值493.2栈的应用举例break;case'='://脱括号并接收下一字符Pop(OPTR,x);c=getchar();break;case‘>’://退栈并将运算结果入栈,〔小官来,那么我先出。〕Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression50例:问题的提出

设计一个小计算器:对键入的表达式进行求值。高级语言中的赋值语句:1〕变量=表达式;2〕表达式的构成:操作数,运算符,界符〔如括号〕3〕表达式的求值:例:5+6(1+2)-4按照四那么运算法那么,上述表达式的计算过程为:5+6(1+2)-4=5+63-4=5+18-4=23-4=1912343.2栈的应用举例3.2.5栈应用——表达式求值51表达式求值示意图:5+6(1+2)-4

topbaseOPTR栈#OPND栈topbase5toptop+top6top×top(top1to

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论