数据结构 C语言版 严蔚敏 李冬梅 吴伟民 第3章 栈和队列

《数据结构 C语言版 严蔚敏 李冬梅 吴伟民 第3章 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021年7月17日北京林业大学信息学院李冬梅数据结构2021年7月17日北京林业大学信息学院3.1栈3.2栈的应用3.3栈与递归3.4队列3.5队列的应用教学内容2021年7月17日北京林业大学信息学院第3章栈和队列掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程教学目标2021年7月17日北京林业大学信息学院栈（Stack）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式队列（Queue）1.定

2、义2.逻辑结构3.存储结构4.运算规则5.实现方式2021年7月17日北京林业大学信息学院3.1栈1.定义用顺序栈或链栈存储均可，但以顺序栈更常见3.存储结构与线性表相同，仍为一对一关系2.逻辑结构只能在表的一端（栈顶）进行插入和删除运算的线性表2021年7月17日北京林业大学信息学院只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则4.运算规则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等5.实现方式2021年7月17日北京林业大学信息学院栈是一种特殊的线性表，它只能在表的一端（

3、栈顶）进行插入和删除运算栈与一般线性表的区别：仅在于运算规则不同“进”＝压入=PUSH（)“出”＝弹出=POP()一般线性表逻辑结构：一对一存储结构：顺序表、链表运算规则：随机、顺序存取栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出栈与一般线性表的区别2021年7月17日北京林业大学信息学院“进”＝压入=PUSH（)“出”＝弹出=POP()2021年7月17日北京林业大学信息学院a1a2……an顺序栈Sai……表头表尾栈底base栈顶top低地址高地址写入：v[i]=ai读出：x=v[i]压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！低地址

4、高地址v[i]a1a2aian……顺序表V[n]……an+1顺序栈与顺序表2021年7月17日北京林业大学信息学院顺序栈的表示空栈base==top是栈空标志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的栈顶元素之上的下标地址栈满时的处理方法：1、报错,返回操作系统。2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。2021年7月17日北京林业大学信息学院#defineMAXSIZE100typedefstruct{SElemType*base;SElemType*top;intst

5、acksize;}SqStack;顺序栈的表示2021年7月17日北京林业大学信息学院构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错误顺序栈初始化basestacksizetops(2)设置栈底和栈顶指针S.top=S.base;(3)设置栈大小2021年7月17日北京林业大学信息学院StatusInitStack(SqStack&S){S.base=newSElemType[MAXSIZE]；if(!S.base)returnOVERFLOW;S.top=S.base;S.stackSize=MAXSIZE;returnOK;}顺序栈初始化2021年7月1

6、7日北京林业大学信息学院判断顺序栈是否为空boolStackEmpty(SqStackS){if(S.top==S.base)returntrue;elsereturnfalse;}basetop31202021年7月17日北京林业大学信息学院求顺序栈的长度intStackLength(SqStackS){returnS.top–S.base;}basetopAB2021年7月17日北京林业大学信息学院StatusClearStack(SqStackS){if(S.base)S.top=S.base;returnOK;}清空顺序栈basetop31202021年7月17日北京林业大

7、学信息学院StatusDestroyStack(SqStack&S){if(S.base){deleteS.base;S.stacksize=0;S.base=S.top=NULL;}returnOK;}销毁顺序栈2021年7月17日北京林业大学信息学院(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1顺序栈进栈StatusPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize)//栈满retu