计算机软件基础第3章ppt课件.ppt

《计算机软件基础第3章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.4堆栈3.4堆栈及其应用——定义插入、删除只在线性表一端进行的线性表被称为栈。a1a2a3a4....an插入删除后进先出----LIFO(LastInFirstOut)栈顶浮动栈底固定a1a2a3a4出入栈底栈顶(top)3.4堆栈及其应用——特点顺序存储结构：顺序栈链式存储结构：链栈栈顶s^3.4堆栈及其应用——栈的表示和实现3.4.1.顺序栈#defineMAXSIZE100//栈容量typedefstruct{DataTypedata[MAXSIZE];//存储空间inttop;//栈顶指针}SSta

2、ck;3.4.1顺序栈——定义栈空时，top=-1；非空时，top位于栈顶元素的位置顺序栈的空间固定3.4.1顺序栈——实现要点SStack*InitStack(){//构造一个空栈sSStack*S；S=(SStack*)malloc(sizeof(SStack));S->top=-1;returnS;}3.4.1顺序栈——建立算法intEmptySStack(SStack*S){//若栈空，则返回1，否则返回0if(S->top==-1)return1;elsereturn0;}3.4.1顺序栈——判定顺序栈

3、是否空算法intGetTop(SStack*S,DataType*x){//若栈不空，则返回1，否则返回0if(S->top==-1)return0;else{x=(DataType*)malloc(sizeof(DataType));*x=S->data[S->top];return1;}}3.4.1顺序栈——取顺序栈顶元素算法intPush(SStack*S,DataTypex){//插入元素x为新的栈顶元素if(S->top==MAXSIZE-1)return0;else{S->top++;S->data[

4、S->top]=x;return1;}}3.4.1顺序栈——进栈算法intPop(SStack*S,DataType*x){//若栈不空，则删除S的栈顶元素，用x返回其值，并返回1；否则返回0if(S->top==-1)return0;else{x=(DataType*)malloc(sizeof(DataType));*x=S->data[S->top];S->top--;return1;}}3.4.1顺序栈——出栈算法3.4.2.链栈typedefstructlnode{DataTypedata;//存储栈元

5、素structlnode*next;//指针}LSStack;LSStack*top;3.4.2链栈——定义(栈的大小不定)栈空时，top=NULL；非空时，top指向栈顶元素链栈的空间不固定3.4.2链栈——实现要点LSStack*InitStack(){//构造一个空链栈returnNULL;}3.4.2链栈——建立算法intEmptySStack(LSStack*top){//若链栈空，则返回1，否则返回0if(top==NULL)return1;elsereturn0;}3.4.2链栈——判链栈是否为空的

6、算法intGetTop(LSStack*top,DataType*x){//若链栈不空，则返回1，否则返回0if(top==NULL)return0;else{x=(DataType*)malloc(sizeof(DataType));*x=top->data;return1;}}3.4.2链栈——取链栈栈顶元素的算法voidPush(LSStack*top,DataTypex){//插入元素x为新的链栈顶元素LSStack*p;p=(LSStack*)malloc(sizeof(LSStack));p->dat

7、a=x;p->next=top;top=p;}3.4.2链栈——进栈算法intPop(LSStack*top,DataType*x){//若链栈不空,则删除链栈的栈顶元素，用x返回其值，并返回1；否则返回0if(top==NULL)return0;else{x=(DataType*)malloc(sizeof(DataType));*x=top->data;p=top;top=top->next;free(p);return1;}}3.4.2链栈——出栈算法3.4.3栈的应用举例表达式的表示：算术表达式的前缀表示

8、算术表达式的中缀表示算术表达式的后缀表示3.4.3堆栈的应用——表达式求值表达式的组成：4+2*3-10/5#操作数(operand)运算符(operator)界限符(delimiter)3.4.3堆栈的应用——表达式求值操作数(operand)可以是常量,变量,函数,....3.4.3堆栈的应用——表达式求值运算符(operator)算术运算符:+,-,*,/,%,..