资源描述：
《第3章 栈、队列和数组ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法与数据结构阙夏制作§3栈、队列和数组栈和队列都是运算受限的的线性表。下面我们分别讨论栈和队列的定义、基本运算和应用。§3.1栈一、栈的定义和运算1、定义：栈(Stack)：是只能在同一端插入和删除的线性表。2、特点：后进先出（LIFO）。a1a2…an出入a1a2…anana2…a1一、栈的定义和运算－术语下面介绍有关栈的术语：……an－1ana2a1入/进栈(push)出/退栈(pop)栈顶（top）栈底（bottom）top一、栈的定义和运算－运算3、栈的基本运算（1）初始化栈：建空栈；（2）判栈空：若为空，则返回true，否则返回false；（3）判栈满：若为满
2、，则返回true，否则返回false；一、栈的定义和运算－运算（4）读栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。（5）入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？（6）出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？二、顺序栈1、存储结构：——采用顺序表来存储的栈；#definemaxlen最大容量typedefstructseqstack{elementtypedata[maxlen];inttop;}引用：seqstackS;二、顺序栈－图例下图即为一个顺序栈：注意：（1）top==-1时栈为空；（2）栈顶元素是d
3、ata[top]seqstacka1a2a3a4…andatamaxlen-10123topn－1n-1二、顺序栈－图例如图所示：a2a3a1top3210-13210-1top空栈栈顶元素为a3二、顺序栈－运算的实现2、运算的实现：(1)初始化:voidinit_stack(seqstack&S){S.top=-1;}(2)判栈空:boolempty(seqstackS){return(S.top==-1);}top3210-1空栈二、顺序栈－运算的实现栈满(3)判栈满：满返回1，否则返回0boolstack_full(S);{if(S.top==maxlen-1)re
4、turn(1);elsereturn(0);}a2a3a13210-1top二、顺序栈－运算的实现(4)读栈顶元素:voidgettop(seqstackS,elementtype&x){if(S.top==-1)error(“栈空”);elsex=S.data[top];}a2a3a13210-1top二、顺序栈－运算的实现入栈(5)入栈:voidpush_stack(seqstack&S,elementtypex);{if(S.top==maxlen-1)error(“栈满”);else{S.top++;S.data[S.top]=x;}}a2a3a13210-1to
5、px二、顺序栈－运算的实现出栈(6)出栈:elementtypepop_stack(seqstack&S);{if(S.top==-1)error(“栈空”);else{S.top--;return(S.data[S.top+1]);}}a2a3a13210-1topa3三、链栈—采用链表来存储的栈1、类型描述typedefstructnode{elementtypedata;node*next;}引用：node*top,*L;三、链栈链栈结构图：topa1a2a3a4^入栈链栈入栈：a1a2a3a4^topxP×出栈链栈出栈：a1a2a3a4^top×四、栈的应用1、栈
6、的基本应用实例：设栈的输入序列依次为1,2,3,4，则所得的输出序列不可能是________。a1,2,3,4b4,2,3,1c1,3,2,4d3,4,2,1例4321？b四、栈的应用－22、表达式的计算：模拟表达式：12+5*6-4/2的求解过程。例运算符操作数#12+5*6-4/2#操作数运算符各自依次入栈。入栈规则：当前入栈的运算符 比栈顶的运算符优先级高。四、栈的应用－22、表达式的计算：运算符优先级比较：‘*/’>‘+-’>‘#’四、栈的应用－2如上例：#12+5*6-4/2#*＋＃运算符操作数6512-5*6＋＃运算符操作数3012-12+30/-＃运算符操作
7、数2442#4/2-＃运算符操作数242#42-2四、栈的应用－2最终结果：＃运算符操作数40#40四、栈的应用－33、递归与递归的阅读：(1)递归的定义：如果一个函数在完成之前又调用自身，则称之为递归函数。例求整数n的阶乘函数1当n=0时n!=n*(n-1)!当n>0时程序实现：intfact(intn){if(n==0)return(1);elsereturn(n*fact(n-1));}四、栈的应用－3(2)递归的一般形式：voidfname(参数表){if(数据作为递归出口)简单操作;else{简单操作;fname(参
