第三章 计算机软件技术基础

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

1、第三章栈与队列数据结构电子教案郇矢宇1栈队列栈的应用：表达式求值栈的应用：递归队列的应用第三章栈与队列2只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a0an-1an-2topbottom3栈的数组存储表示—顺序栈0123456789maxSize-1top(栈空)elements4top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c5topc退栈b退栈a

2、baa退栈空栈topabdd退栈ctopabctoptop6建立一个容量为m的空栈：#include“stdlib.h”Voidinit-stack(s,m,top)ET*s;intm,*top;{s=malloc(m*sizeof(ET));*top=0;return;}7PROCEDUREPUSH(S,m,top,x)//若栈不满,则将元素x插入该栈栈顶,否则溢出处理if(top=m)then{Stackoverflow;RUTURN}//栈满top=top+1;//栈顶指针先加1,再进栈S(top)=x;RE

3、TURNPROCEDUREPOP(S,m,top,y)//退出栈顶元素并返回栈顶元素的值if(top=0)then{Stackunderflow;RETURN}y=S(top);top=top-1;//栈顶指针退1returntrue;//退栈成功};8PROCEDURETOP(S,m,top,y)//若栈不空则返回该栈栈顶元素的地址if(top=0)then{“Stackempty”;RETURN}y=S(top);return;9栈的链接存储表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈

4、的栈顶在链头适合于多栈操作top10链式栈类操作的实现templateLinkedStack::makeEmpty(){//逐次删去链式栈中的元素直至栈顶指针为空。StackNode*p;while(top!=NULL)//逐个结点释放{p=top;top=top->link;deletep;}};templatevoidLinkedStack::Push(Ex){//将元素值x插入到链式栈的栈顶,即链头。11top=newStackNode(x,top);/

5、/创建新结点assert(top!=NULL);//创建失败退出};templateboolLinkedStack::Pop(E&x){//删除栈顶结点,返回被删栈顶元素的值。if(IsEmpty()==true)returnfalse;//栈空返回StackNode*p=top;//暂存栈顶元素top=top->link;//退栈顶指针x=p->data;deletep;//释放结点returntrue;};12templateboolLinkedStack::g

6、etTop(E&x)const{if(IsEmpty()==true)returnfalse;//栈空返回x=top->data;//返回栈顶元素的值returntrue;};templatevoidLinkedStack::output(ostream&os,StackNode*ptr,inti){//递归输出栈中所有元素（沿链逆向输出）if(ptr!=NULL){13if(ptr->link!=NULL)output(os,ptr->link,i++);os<

7、data<

8、DEFGCDEFGfrontrearH进队,溢出16队列的进队和出队原则进队时先将新元素按rear指示位置加入，再将队尾指针加一rear=rear+1。队尾指针指示实际队尾的后一位置。出队时按队头指针指示位置取出元素，再将队头指针进一front=front+1，队头指针指示实际队头位置。队满时再进队将溢出出错（假溢出）；队空时再出队将队空处理。解决假溢出的办