数据结构(C语言版)_栈和队列课件.ppt

数据结构(C语言版)_栈和队列课件.ppt

ID:57001734

大小:499.00 KB

页数:71页

时间:2020-07-26

数据结构(C语言版)_栈和队列课件.ppt_第1页
数据结构(C语言版)_栈和队列课件.ppt_第2页
数据结构(C语言版)_栈和队列课件.ppt_第3页
数据结构(C语言版)_栈和队列课件.ppt_第4页
数据结构(C语言版)_栈和队列课件.ppt_第5页
资源描述:

《数据结构(C语言版)_栈和队列课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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队列类型的实现3.1栈的类型定义ADTStack{数据对象:D={ai

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

3、ai-1,ai∈D,i=2,...,n}约

4、定an端为栈顶,a1端为栈底。基本操作:}ADTStackInitStack(&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被销毁。StackEmpty(S)初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TRUE,否则FALE。StackLength(S)

5、初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。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……3.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例

6、一、数制转换算法基于原理:N=(Ndivd)×d+Nmodd例如:(1348)10=(2504)8,其运算过程如下:NNdiv8Nmod813481684 168210 2125 202计算顺序输出顺序voidconversion(){InitStack(S);scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion例二、括号匹配的检验假设在表达式中([]())或[([][])]等为正确的格式,[(])或([())

7、或(()])均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的;例如:考虑下列括号序列:[([][])]12345678到来的是“不速之客”;直到结束,也没有到来所“期待”的括弧。算法的设计思想:1)凡出现左括弧,则进栈;2)凡出现右括弧,首先检查栈是否空若栈空,则表明该“右括弧”多余,否则和栈顶元素比较,若相匹配,则“左括弧出栈”,否则表明不匹配。3)表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明“左括弧”有余。Statusmatching(string&ex

8、p){intstate=1;while(i<=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);ii++;}else{state=0;}break;}……}if(StackEmpty(S)&&state)returnOK;…...例三、行编辑程序问题如何实现?“每接受一个字符即存入存储器”?并不恰当!设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据

9、区,并假设“#”为退格符,“@”为退行符。在用户输入一行的过程中,允许用户输入出差错,并在发现有误时可以及时更正。合理的作法是:假设从终端接受了这样两行字符:whli##ilr#e(s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行:while(*s)putchar(*s++);while(ch!=EOF&&ch!=''){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getch

10、ar();//从终端接收下一个字符}C

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

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

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