第二 栈和队列 操作受限的线性表 3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示与实现 3.2栈的应用举例 3.2.1数制转换 3.2.4迷宫求解 3.2.5表达式求值 *3.3栈和递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列—队列的链式表示与实现 3.4.3循环队列—队列的顺序表示与实现
3.1 栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示与实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.4 迷宫求解 3.2.5 表达式求值 *3.3 栈和递归的实现 3.4 队列 3.4.1抽象数据类型队列的定义 3.4.2 链队列 -- 队列的链式表示与实现 3.4.3 循环队列 -- 队列的顺序表示与实现 第三章 栈和队列 ----- 操作受限的线性表
3.1栈 3.1.1抽象数据类型栈的定义 栈( stack):先进后出(FLO)的线性表。 或后进先出(LIFO)的线性表。 或仅在表尾进行插入和删除操作的线性表 栈顶(top):线性表的表尾端,即可操作端。 栈底( bottom):线性表的表头 栈底 栈顶 出栈(pop) a1 a, a 3 an-lan 入栈(push)
栈（stack）: 先进后出( FILO）的线性表。 • 或后进先出（ LIFO）的线性表。 • 或仅在表尾进行插入和删除操作的线性表。 栈顶（top）: 线性表的表尾端，即可操作端。 栈底（bottom）: 线性表的表头。 3.1 栈 3.1.1 抽象数据类型栈的定义 栈底 栈顶 a ...... 1 a2 a3 an-1 an 入栈(push) 出栈(pop)
栈的抽象数据类型 ADT Stack i 数据对象:D={a1|a1属于 Elemnet, 1,2,,n,n≥0) 数据关系:项a为栈 a1a1,>la1a1属于 D,(-23,,n)} 基本操作: InitStack(&s) DestroyStack(&s) ClearStack(&s); StackEmpty(s); StackLength(S); GetTop(s, &e); Push(&s,e); Pop(&s, &e); StackTraverse(S, visit O) ADT Stack
栈的抽象数据类型 ADT Stack { 数 据 对 象 ： D = {ai | ai 属 于 Elemset, (i=1,2,…,n, n≥0)} 数据关系 ： R1 = { ＜ ai-1 ,ai ＞ |ai-1 ,ai 属 于 D,(i=2,3,…,n)} 约定an为栈顶, a1为栈底。 基本操作： • InitStack(&S); DestroyStack(&S); • ClearStack(&S); StackEmpty(S); • StackLength(S) ; GetTop(S,&e); • Push(&S,e); Pop(&S,&e); • StackTraverse(S,visit ()) }ADT Stack
栈的基本操作(之一) InitStack(&s) 操作结果:构造一个空的栈S。 DestroyStack(&s) 初始条件:栈S已经存在。 操作结果:销毁栈S。 ClearStack(&s) 初始条件:栈S已经存在。 操作结果:将栈S重置为空栈
栈的基本操作(之一) InitStack(&S) • 操作结果:构造一个空的栈S。 DestroyStack(&S) • 初始条件: 栈S已经存在。 • 操作结果: 销毁栈S。 ClearStack(&S) • 初始条件: 栈S已经存在。 • 操作结果: 将栈S重置为空栈
栈的基本操作(之二) StackEmpty(s) 初始条件:栈S已经存在 操作结果:若栈S为空栈,则返回TURE:否则 返回 FALSE。 StackLength(S 初始条件:栈S已经存在。 操作结果:返回栈S中的数据元素个数。 GetTop(s, &e) 初始条件:栈S已经存在且非空。 操作结果:用e返回栈S中栈顶元素的值
栈的基本操作(之二) StackEmpty(S) • 初始条件: 栈S已经存在。 • 操作结果: 若栈S为空栈，则返回TURE;否则 返回FALSE。 StackLength(S) • 初始条件: 栈S已经存在。 • 操作结果: 返回栈S中的数据元素个数。 GetTop(S,&e) • 初始条件: 栈S已经存在且非空。 • 操作结果: 用e返回栈S中栈顶元素的值
栈的基本操作(之三) Push(&s, e) 初始条件:栈S已经存在 操作结果:插入元素e为新的栈顶元素。 Pop(&s, &e) 初始条件:栈S已经存在且非空。 操作结果:删除S的栈顶元素并用e返回其值。 StackTraverse(S,visit O) 初始条件:栈S已经存在且非空。 操作结果:从栈底到栈顶依次对S的每个元素 调用函数 visit O。一旦 visit失败,则操作 失败
栈的基本操作(之三) Push(&S,e) • 初始条件: 栈S已经存在。 • 操作结果: 插入元素e为新的栈顶元素。 Pop(&S,&e) • 初始条件: 栈S已经存在且非空。 • 操作结果: 删除S的栈顶元素并用e返回其值。 StackTraverse(S,visit()) • 初始条件: 栈S已经存在且非空。 • 操作结果: 从栈底到栈顶依次对S的每个元素 调用函数visit ()。一旦visit ()失败，则操作 失败
312栈的顺序表示与实现 (顺序栈) typedef struct( SElem Type *base *在栈构造之前和销毁之后,base的值为NULL*/ SElem Type*top;,*栈顶指针*/ int stacksize;/*当前已分配的存储空间,以元素为单位* iSqstack #define STaCK INIT SIzE 100 #define STaCKIncrement 10 #define oK 1 #define oVerfloW-1 #define error o
3.1.2 栈的顺序表示与实现--- (顺序栈) typedef struct{ SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL*/ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -1 #define ERROR 0
顺序栈示意图 顺序栈 *top a stacksize 初始空栈 *base op stacksize top=*base stacksize= STACK INIT SIZE
顺序栈示意图 *base *top stacksize ...... a1 ... ai an *base *top stacksize 初始空栈 *top = *base; stacksize = STACK_INIT_SIZE 顺序栈
顺序栈的操作实现举例 Initstack/*构造一个空的栈S* 口 Status initstack〈 Sqstack*s) i s-base=( selemType *)malloc 口( STACK INIT SIZE水 sizeof( SElemType) o if(s-> base) return(OVERFLOW) 口s->top base stacksize= STACK INIT SIze D return OK }/菜 Initstack米/
顺序栈的操作实现举例 InitStack /* 构造一个空的栈S*/ Status InitStack(SqStack *s) { s->base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType)); if(!s -> base) return(OVERFLOW); s -> top = s -> base; s -> stacksize = STACK_INIT_SIZE; return OK; } /* InitStack */
顺序栈的操作实现( GetTop) 栈S非空,则用e返回栈S中栈顶元素的值 并返回OK,则返回 ERROR。 Status GetTop(sqstack S, SElemType *e) if (s. top== s base)return ERROR 米e=(s.tOp-1) return OK 3 * Get Top x s*base 来e=米(s.top-1) ai op 1 stacksize
顺 序 栈 的 操 作 实 现 (GetTop) 栈 S 非 空 , 则 用 e 返回栈 S 中 栈 顶 元 素 的 值 ， 并返回OK, 则返回ERROR。 Status GetTop(SqStack s, SElemType *e) { if (s.top == s.base)return ERROR; *e = *(s.top-1); return OK; } /* GetTop */ *base *top stacksize ...... a1 ... ai an s e *e = *(s.top-1);