数据结构 教学课件 ppt 作者 李学刚电子课件源代码 单元3 栈和队列.ppt

《数据结构 教学课件 ppt 作者 李学刚电子课件源代码 单元3 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构教学目标【知识目标】掌握栈的定义及基本运算掌握顺序栈、链栈基本运算的实现算法掌握队列的定义及基本运算掌握循环队列、链队列基本运算的实现算法【能力目标】具有恰当的选择栈或队列作为数据的逻辑结构，顺序栈（队列）、链栈（队列）作为数据的存储结构的能力具有应用栈、队列解决实际问题的能力引例描述——数制转换将十进制数F转换为B进制数。输入任意一个十进制数，可以是整数，也可以是小数，输出对应进制的数。演示执行一、栈的定义及基本操作1.定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为出（退）栈。通常插入、删除的这一端称为

2、栈顶（StackTop），由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top为栈顶指针；另一端称为栈底。当表中没有元素时称为空栈，即Top=-1。栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。3.1栈知识储备2．栈的基本运算（1）置空栈：InitStack(S)构造一个空栈S。（2）判栈空：StackEmpty(S)若S为空栈，则返回1，否则返回0。（3）判栈满：StackFull(S)若S为满栈，则返回1，否则返回0。（4）进栈：Push(S，x)若栈S不满，则将元素x插入S的栈顶。（5）退栈：Po

3、p(S)若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）取栈顶元素：StackTop(S)若栈S非空，则返回栈顶元素，但不改变栈的状态。二、顺序栈及基本操作的实现1．顺序栈（SequenceStack）栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。2．顺序栈的描述#defineStackSize100//假定栈空间最多为100个元素typedefcharDataType;//假定栈元素的类型为字符类型typedefstruct{DataTypedata[StackSize];//栈元素定义inttop;//栈指针定义}SeqStack;SeqStack*S;//栈定义

4、注意：①有元素x进栈时，需要先将S->top加1，然后再将元素进栈，即依次完成下列操作：++S->top;S->data[S->top]=x;；②当栈顶元素做退栈操作后，需要将S->top减1，即完成操作：S->top--;；③条件S->top==StackSize-1表示栈满；S->top==-1表示栈空；④当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免；⑤当栈空时，做退栈运算所产生的溢出现象称为下溢。3．顺序栈上基本运算的算法（1）置栈空（2）判栈空如果栈S为空，则S->top==-1，此时应该返回1，而关系表达式S->top==-1的值为

5、1；如果栈S为非空，则S->top!=-1，此时应该返回0，而关系表达式S->top==-1的值为0，因此，无论怎样只需返回S->top==-1的值。（3）判栈满与判栈空的道理相同，只需返回S->top==StackSize-1。（4）进栈（5）出栈（6）取栈顶元素（1）置栈空voidInitStack(SeqStack*S){//将顺序栈置空S->top=-1;}（2）判栈空intStackEmpty(SeqStack*S){//判栈空returnS->top==-1;}（3）判栈满intStackFull(SeqStack*S){//判栈满returnS->top==Stac

6、kSize-1;}（4）进栈intPush(SeqStack*S,DataTypex){//进栈if(StackFull(S)){puts("栈满");return0;}S->data[++S->top]=x;return1;}（5）出栈intPop(SeqStack*S,DataType*x){//出栈if(StackEmpty(S)){puts("栈空");return0;}*x=S->data[S->top--];return1;}（6）取栈顶元素intStackTop(SeqStack*S,DataType*x){if(StackEmpty(S)){puts("栈空");

7、return0;}*x=S->data[S->top];return1;}【例3-1】元素a1，a2，a3，a4依次进入顺序栈，则下列不可能的出栈序列是A．a4,a3,a2,a1B．a3,a2,a4,a1C．a3,a4,a2,a1D．a3,a1,a4,a2分析：对于A，由于元素a1，a2，a3，a4依次进栈，而a4先出栈，说明a1，a2，a3已经入栈，所以出栈顺序只能是a4，a3，a2，a1，因此A是正确的出栈序列；对于B，C，D，由于都是a3先出栈，说明a1，a2已经入栈，所以