第3章堆栈和队列ppt课件.ppt

《第3章堆栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章主要内容:堆栈堆栈的应用队列队列的应用第三章堆栈和队列13.1栈(Stack)只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)退栈进栈2栈的存储结构顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组长度为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)t

2、optoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空3栈的基本操作1、初始化Initiate(s)2、进栈push(s,x)3、退栈pop(s)4、取栈顶元素gettop(s)5、判栈是否非空Notempty(s)6、置空栈SETNULL(s)4栈的顺序存储结构顺序栈的定义typedefintelemtype;#definemaxsize64typedefstruct{elemtypedata[maxsize];inttop;}seqstack;5栈的基本运算

3、初始化initiate(seqstack*s){s->top＝0;}判栈空intnotEMPTY(seqstack*s){if(s->top>0)return1;elsereturn0;}6进栈seqstack*PUSH(seqstack*s,datatypex){if(s->top==maxsize){printf(“overflow”);returnNULL;}else{s->data[s->top]＝x;s->top++;}returns;}7退栈datatypePOP(seqstack*

4、s){if(s->top<=0){printf(“underflow”);returnNULL;}else{s->top--;return(s->data[s->top]);}}8取栈顶datatypeTOP(seqstack*s){if(s->top<=0){printf(“underflow”);returnNULL;}elsereturn(s->data[s->top-1]);}9栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作1

5、0栈的链接存储结构链栈的结点定义typedefintelemtype;structslnodetype{elemtypedata;structslnodetype*next;};11链栈的进栈算法slnodetype*PUSHLSTACK(slnodetype*top,elemtypex){slnodetype*p;p＝malloc(sizeof(slnodetype));p->data＝x;p->next＝top;returnp;}^…...栈底hhxp12链栈的出栈算法slnodetype*PO

6、PLSTACK(slnodetype*top,datatype*datap){slnodetype*p;if(top->next==NULL){printf(“underflow”);returnNULL;}else{p＝top;*datap＝p->data;top=top->next;free(p);returntop;}}top^…...栈底top13例递归的执行情况分析递归过程及其实现递归：函数直接或间接的调用自身实现：建立递归工作栈voidprint(intw){inti;if(w!=0

7、){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：1，2，2，3，3，3，3.2栈的应用当w=314递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3t

8、opw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)15表达式求值中缀表达式a*b+ca+b*ca+(b*c+d)/e中缀表达式：操作数栈和运算符栈例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符-12(1)对每种运算符赋予一个优先数，如：运算符：*/+-优先数：2211语句结束符