数据结构课件C语言版 第3章.ppt

数据结构课件C语言版 第3章.ppt

ID:51622759

大小:244.50 KB

页数:52页

时间:2020-03-26

数据结构课件C语言版 第3章.ppt_第1页
数据结构课件C语言版 第3章.ppt_第2页
数据结构课件C语言版 第3章.ppt_第3页
数据结构课件C语言版 第3章.ppt_第4页
数据结构课件C语言版 第3章.ppt_第5页
资源描述:

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

1、堆栈堆栈的应用队列队列的应用第三章堆栈和队列3.1栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)特点后进先出(LIFO)退栈进栈进栈示例退栈示例栈的基本操作1、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空6、置栈空栈的顺序存储结构顺序栈的定义typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop;}seqstack;栈的基本运算置空栈SETNULL(seqstack*s){s->top=-

2、1;}判栈空intEMPTY(seqstack*s){if(s->top>=0)returnFALSE;elsereturnTRUE;}进栈seqstack*PUSH(seqstack*s,datatypex){if(s->top==maxsize-1){printf(“overflow”);returnNULL;}else{s->top++;s->data[s->top]=x;}returns;}退栈datatypePOP(seqstack*s){if(EMPTY(s)){printf(“underflow”);returnNULL;}else{s->t

3、op--;return(s->data[s->top+1]);}}取栈顶datatypeTOP(seqstack*s){if(EMPTY(s)){printf(“underflow”);returnNULL;}elsereturn(s->data[s->top]);}两个堆栈共享空间0maxsize-1lefttoprighttop栈的链接表示—链式栈链式栈无栈满问题,空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作栈的链接存储结构链栈的结点定义typedefintdatatype;typedefstructnode{datatypedata

4、;structnode*next;}linkstack;链栈的进栈算法linkstack*PUSHLSTACK(linkstack*top,datatypex){linkstack*p;p=malloc(sizeof(linkstack));p->data=x;p->next=top;returnp;}链栈的出栈算法linkstack*POPLSTACK(linkstack*top,datatypedatap){linkstack*p;if(top==NULL){printf(“underflow”);returnNULL;}else{*datap=top->

5、data;p=top;top=top->next;free(p);returntop;}}例:对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成,试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB栈的应用举例--文字编辑器seqstacks;EDIT(){charc;SETNULL(&s);c=getchar();while(c!=‘*’){if(c==‘#’)POP(&s);elseif(c==‘@’)S

6、ETNULL(&s);elsePUSH(&s,c);c=getchar();}}栈的应用--递归函数intFACT(intn){if(n==1)return(1);elsereturn(n*FACT(n-1));}栈的应用--表达式计算中缀表达式:A+(B–C/D)×E后缀表达式:ABCD/-E×+后缀表达式特点1、与相应的中缀表达式中的操作数次序相同2、没有括号后缀表达式的处理过程操作顺序后缀表达式ABCD/-E×+T1←C/DABT1-E×+T2←B–T1AT2E×+T3←T2×EAT3+T4←A+T3T4ABCDE+×-/ABCT1+×-ABT2+×AT3+

7、中缀表达式转换为后缀表达式+-×/()#+>><<<>>->><<<>>×>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=当前运算符栈顶运算符中缀表达式转换为后缀表达式的处理规则1、如为操作数,直接输出到队列;2、如当前运算符高于栈顶运算符,入栈;3、如当前运算符低于栈顶运算符,栈顶运算符退栈,并输出到队列,当前运算符再与栈顶运算符比较;4、如当前运算符等于栈顶运算符,且栈顶运算符为“(”,当前运算符为“)”,则栈顶运算符退栈,继续读下一符号;5、如当前运算符等于栈顶运算符,且栈顶运算符为“#”,当前运算符也为“#”,则栈顶运算符退栈,继续

8、读下一符号

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

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

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