数据结构教程第十课栈的表示与实现

文章作者 100test 发表时间 2007:03:10 18:29:42
来源 100Test.Com百考试题网

本课主题： 栈的表示与实现
教学目的： 栈的数据类型定义、栈的顺序存储表示与实现
教学重点： 栈的顺序存储表示与实现方法
教学难点： 栈的定义
授课内容：
一、栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
栈的抽象数据类型定义：
ADT Stack{
数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
数据关系:R1={|ai-1,ai(- D,i=2,...,n}
基本操作:
InitStack(&.S) 构造一个空栈S
DestroyStack(&.S) 栈S存在则栈S被销毁
ClearStack(&.S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&.e) 栈S存在且非空则返回S的栈顶元素
Push(&.S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&.S,&.e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
}ADT Stack
二、栈的表示和实现
栈的存储方式：
1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
2、链栈:利用链表实现
顺序栈的类C语言定义:
typedef struct{
SElemType *base.
SElemType *top. //设栈顶栈底两指针的目的是便于判断栈是否为空
int StackSize. //栈的当前可使用的最大容量.
}SqStack.
顺序栈的的模块说明:
struct STACK {
SElemType *base.
SElemType *top.
int stacksize.
}.
typedef struct STACK Sqstack.
Status InitStack(SqStack &.S).
Status DestroyStack(SqStack &.S).
Status ClearStack(SqStack &.S).
Status StackEmpty(SqStack S).
int StackLength(SqStack S).
Status GetTop(SqStack S,SElemType &.e).
Status Push(SqStack &.S,SElemType e).
Status Pop(SqStack &.S,SElemType &.e).
Status StackTraverse(SqStack S,Status (*visit)()).

Status InitStack(SqStack &.S) {
S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)).
if(!S.base)exit(OVERFLOW).
S.top=S.base.
S.stacksize=STACK_INI_SIZE.
return OK.
}//IniStack
Status DestroyStack(SqStack &.S). {
}//DestroyStack
Status ClearStack(SqStack &.S). {
S.top=S.base.
} //ClearStack
Status StackEmpty(SqStack S). {
if(S.top==S.base) return TRUE.
else return FALSE.
} //StackEmpty
int StackLength(SqStack S). {
int i. SElemType *p.
i=0.
p=S.top.
while(p!=S.base) {p . i . }
} //stackLength
Status GetTop(SqStack S,SElemType &.e). {
if(S.top==S.base) return ERROR.
e=*(S.top-1).
return OK.
} //GetTop
Status Push(SqStack &.S,SElemType e). {
if(S.top - s.base>=S.stacksize) {
S.base=(ElemType *) realloc(S.base,
(S.stacksize STACKINCREMENT) * sizeof(ElemType)).
if(!S.base)exit(OVERFLOW).
S.top=S.base S.stacksize.
S.stacksize =STACKINCREMENT.
}