《数据结构》 第三章(上)
《 数据结构》 第三章(上)
第三章栈和队列 数据结构 3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例 3.2.1数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解 3.2.5表达式求值 3.3栈与递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列一队列的链式表示和实现 3.4.3循环队列一队列的顺序表示和实现 tim
数据结构 tjm
数据结构 3.1栈 3.1.1抽象数据类型栈的定义 栈( Stack)是限制在表的一端进行插入和删除 运算的线性表,通常称插入、删除的这一端为栈顶 (Top),另一端为栈底( Bottom)。当表中没有 元素时称为空栈。 假设栈S=(a1,a2,a3,an),则a1称为 栈底元素,an为栈顶元素。栈中元素按a1,a2, a3,,an的次序进栈,退栈的第一个元素应为栈 顶元素
数据结构 tjm
数据结构 例、一叠书或一叠盘子 栈顶 特点:后进先出 (LIFo)。 a2 栈底 G 1 栈的ADT定义参见p45
数据结构 tjm ……
数据结构 3.12栈的表示和实现 顺序栈 由于栈是操作受限的线性表,因此线性表的存 储结构对栈也适应 栈的顺序存储结构简称为顺序栈,可用数组来 实现顺序栈。因为栈底位置是固定不变的,所以可 以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化,故需 用一个指针t。p来指示当前栈顶的位置,通常称 top为栈顶指针。因此,顺序栈的类型定义只需将 顺序表的类型定义中的长度属性改为top指针即可
数据结构 tjm
数据结构 顺序栈的类型定义如下: Define sTAcK INIT SIZE 100 define stacKincrement 10 typedef struct SElemType *base SElemType *top; int stacksizej SSqstack;
数据结构 tjm
数据结构 当栈满时再做进栈运算必定产生空间溢出,简 称“上溢”P当栈空时再做退栈运算也将产生溢 出,简称“下溢”。溢出是一种出错状态,应 该设法避免 栈的几个常用的基本操作的实现: 1、栈的初始化 Initstack操作(P47) 2、进栈Push操作(P47) 3、出栈Pop操作(P47) 4、取栈顶元素 GetTop操作(P47)
数据结构 tjm
数据结构 链栈 栈的链式存储结构称为链栈,它是操作受限的 单链表,其插入和删除操作仅限制在表头位置 上进行。链栈通常用不带头结点的单链表来实 现。栈顶指针就是链表的头指针。 链栈的类型说明如下: typedef struct sNode SElemType datai struct snode *next SSNode LinkStack;
数据结构 tjm
数据结构 1、进栈操作的实现: 栈底 void Push_LS(LinkStack &S, SElem Type e) p=(LinkStack)malloc(sizeof (SNode))i p->data=ej p->next=S S=P;
数据结构 tjm …... ^ 栈底 S S e p
数据结构 2、退栈操作的实现: 栈底 Status Pop_Ls(LinkStack &S, SElemType &e) if(s==NULL) return ERROR; e=s->data: P=Si S=s→>next free(p)i }
数据结构 tjm S …... ^ 栈底 S p
