第六-八课 第三章 栈与队列.pptVIP

唐山师范学院数学与信息科学系 数据结构 教学目标：掌握栈的定义和顺序实现教学内容：3．1栈 3．1．1抽象数据类型栈的定义 3．1．2栈的表示与实现3．2栈的应用举例 3．2．1数制转换 3．2．2迷宫求解 3．2．3表达式求解3．4队列 3．4．1抽象数据类型队列的定义 3．4．2链队列-----队列的链式表示与实现 3．4．3循环队列-----队列的顺序表示与实现 3．1 栈 一、栈的定义和特性： 栈的定义：是限定在表尾进行插入或删除操作的线性表。 对栈来说，表尾端有特殊含义，称栈顶（top）， 表头端称栈底（bottom）, 不含元素的空表称空栈。 先进后出的线性表（FILO），或后进先出的线性表（LIFO） 假设栈S=（a1,a2,…,an）称an为栈顶元素，a1为栈底元素 栈的特性：栈中元素按a1,a2,…,an次序进栈，退栈的第一个元素应为栈顶元素。按后进先出（Last In First Out）的原则进行。 二、栈的抽象数据类型定义 栈的抽象数据类型定义 ADT stack{ 数据对象：D={ai|ai∈elemset, i=1,2,3，……，n,n≥0} 数据关系：R={ai-1,ai|ai-1,ai∈D,i=2,3,……，n} 约定an为栈顶，a1为栈底 基本操作：initstack(S) 操作结果：构造一个空栈 Destorystack(S) 初始条件：栈S已存在 操作结果：栈S被销毁。 clearstack(S) 初始条件：栈S已存在 操作结果：将S清为空栈 stackempty(S) 初始条件：栈S已存在 操作结果：若栈为空则返回TRUE,否则返回为FALSE stacklength(S) 初始条件：栈S已存在 操作结果：返回S的元素的个数，即栈的长度 getTop(S,e) 初始条件：栈S已存在且非空 操作结果：用e?返回S的栈顶元素 Push (S,e) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 Pop (S,e) 初始条件：栈S已存在且非空 操作结果：删除栈顶元素，并用e返回其值 stacktraverse (S,visit()) 初始条件：栈S已存在且非空 操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()。一旦visit()失败，则操作失败。 }ADT stack 三 、 栈的表示和实现 1、顺序栈： 栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素，约定top为下一次要插入元素的位置。 1、? 顺序栈的表示方法：先为栈分配一个基本空间，在应用过程中，当栈的空间不够使用时再逐段扩大。可设两个常量STACK_INIT_SIZE和STACKINCREMENT。typedef struct { SElemtype *base; SElemtype *top; int stacksize;}SqStack;进栈操作：top增1出栈操作：top减1 。 三 、 栈的表示和实现 2、栈的初始化操作： 按设定的初始分配量进行第一次存储分配，base可称为栈底指针，始终指向栈底，base为NULL则栈不存在。top称栈顶指针，初值指向栈底，top=base则栈空，非空栈中栈顶指针始终指向栈顶元素的下一个位置上。 三 、 栈的表示和实现 3、顺序栈的实现方法： 1）构造一个空栈Status InitStack(SqStack S) { //构造一个空栈 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemtype)); if (!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base; S.stacksize= STACK_INIT_SIZE; return ok;}//InitStack; 三 、 栈的表示和实现 2）销毁栈Status DestoryStack(SqStack S) { //销毁一个栈 free(S.base) S.base