




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章栈☞
3.1什么是栈3.2链栈
3.3栈的应用举例栈栈一、什么是栈栈:限定仅在一端进行插入或删除操作的线性表ana1a2……...栈底栈顶出栈(弹栈)进栈(压栈)栈s=(a1,a2,……,an)
a1为栈底元素
an为栈顶元素
不含元素的栈称空栈二、栈的特点根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
特点
:后进先出
也就是说,栈是一种后进先出的线性表,简称为LIFO(LastInFirstOut)表。例1:有一个栈,进栈序列为A、B、C,试给出所有可能的出栈序列。A进A出B进B出C进C出ABC不可能产生输出序列CABA进A出B进C进C出B出A进B进B出A出C进C出A进B进B出C进C出A出A进B进C进C出B出A出CBAACB
BACBCA例2:一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?
43512不可能实现,主要是其中的12顺序不能实现
12345的输出可以实现,压入一个立即弹出一个即可三、栈的抽象数据类型ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
约定an端为栈顶,a1端为栈底。基本操作:
InitStack(&S)//操作结果:构造一个空栈S。
DestroyStack(&S)
//操作结果:栈S被销毁。
ClearStack(&S)
//操作结果:将S清为空栈
StackEmpty(S)
//操作结果:若栈S为空栈,则返回TRUE,否则FALSE。
StackLength(S)
//操作结果:返回S的元素个数,即栈的长度。
GetTop(S,&e)
//操作结果:用e返回S的栈顶元素。
Push(&S,e)
//操作结果:插入元素e为新的栈顶元素。
Pop(&S,&e)
//操作结果:删除S的栈顶元素,并用e返回其值。}//ADTStack
3.1什么是栈
3.2链栈
3.3栈的应用举例栈栈
3.1什么是栈☞
3.2链栈
3.3栈的应用举例栈栈一、什么是链栈栈的链式存储结构简称为链栈。
注意链表中指针的方向是从栈顶到栈底
没有头结点?……栈顶指针S栈顶栈底ana1因为栈的所有操作在栈顶进行,所以可以不需要头结点,栈顶指针就相当于链表的头指针typedef???SElemType
//由实际需要决定typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*LStack;二、链栈的结构类型LStackS;//定义指向结点的指针sStatusInitStack(LStack&S)StatusGetTop(LStackS,SElemType&e)StatusPush(LStack&S,SElemTypee)StatusPop(LStack&S,SElemType&e)二、链栈的基本操作
(7链栈.cpp)
StatusInitStack(LStack&S){//构造一个空栈S
S=NULL;returnOK;}S……
S栈顶栈底ana1一个空的链栈什么样???StatusGetTop(LStackS,SElemType&e){//
若栈不空,则用e返回S的栈顶元素,并返回OK,否则返回ERRORS96
if(!S)returnERROR;
e=S->data;returnOK;}StatusPush(LStack&S,SElemTypee)S96pe=22{//插入元素e为新的栈顶元素
LStackp;p=(LStack*)malloc(sizeof(SNode));if(!p)exit(OVERFLOW);p->data=e;p->next=S;S=p;returnOK;}StatusPop(LStack&S,SElemType&e){//若栈不空,则删除S的栈顶元素,用e返回其值,
//并返回OK;否则返回ERROR}p2S96e=2
LStackp;if(!S)returnERROR;//
s是空栈
e=S->data;p=S;S=p->next;free(p);
returnOK;
3.1什么是栈
3.2顺序栈
3.3链栈☞3.4栈的应用举例栈栈例二、括号匹配的检验假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等为正确的格式,[(])或([())或()])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列:
[([][])]12345678分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;直到结束,也没有到来所“期待”的。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。4matching.cppstatusmatching(string&exp){intstate=1;//状态标志1表示正常0表示异常
while(i<=length(exp)&&state){switch(exp[i])//i表达式的第几个元素
{case“(":{Push(S,exp[i]);i++;break;}case“)”:{ if(!StackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0;}break;}……}//switch}//whileif(state&&StackEmpty(S))returnOK;elsereturnERROR;}例三、行编辑程序接受用户从终端输入的程序或数据,并存入用户的数据区。如果每接受一个字符即存入用户数据区,做法并不恰当。较好的做法是,设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区。允许用户输入出差错,并在发现有误时可以及时更正。例如,可用一个退格符“#”表示前一个字符无效;可用一个退行符“@”,表示当前行中的字符均无效。例如,假设从终端接受了这样两行字符:whli##ilr#e(s#*s)while(*s)outcha@putchar(*s=#++);则实际有效的是下列两行:while(*s)putchar(*s++);5lineEdit.cppvoid
LineEdit(){InitStack(S); ch=getchar();while(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;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 交通出行行业智能交通系统建设与管理方案
- 员工保密协议合同
- 矿权转让居间合同
- 房产出售委托协议书
- 旅游服务合作协议
- 公路工程投资合伙协议
- 人教版五年级下册数学求最大公因数练习300题及答案
- 铁肩中学门卫合同8篇
- 第1课 殖民地人民的反抗斗争(教学设计) 九年级历史下册同步高效课堂(部编版)
- 第十章 第4节 跨学科实践:制作微型密度计(教学设计)2024-2025学年度人教版(2024)物理八年级下册
- 2024年部编版九年级语文上册电子课本(高清版)
- 探究“双高”背景下高职数学与专业融合创新能力培养教学模式
- 广东省高等教育“创新强校工程”考核指标及评分办法
- 外研版小学五年级上册英语阅读理解专项习题
- 高中二年级下学期数学《导数在不等式恒成立问题中的应用》课件
- 储能项目工具【Excel计算表】用户侧储能电站投资收益分析表(修正版)
- 汽车驾驶员高级工题库与答案
- 《网络安全防护项目教程》课件项目4 数据库安全防护
- 2023年血液安全技术核查指南(医疗机构)
- 手术室标本管理及送检评分标准
- 帮朋友贷款免责协议书范本
评论
0/150
提交评论