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

数据结构教程第十课栈的表示与实现2007-05-17本课主题：栈的表示与实现

教学目的： 栈的数据类型定义、栈的顺序存储表示与实现

教学重点： 栈的顺序存储表示与实现方法

教学难点： 栈的定义

授课内容：

一、栈的定义

栈是限定仅在表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
栈的抽象数据类型定义：
ADT Stack{
数据对象:D={ai|ai（- ElemSet,i=1,2,...,n,n>=0}
数据关系:R1={<ai-1,ai>|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;
}
*S.top++=e;
return OK;
} //Push
Status Pop（SqStack &S,SElemType &e）; {
if（S.top==S.base）
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status StackTraverse（SqStack S,Status （*visit）（））; {
}//StackTraverse
以上伪代码的C语言源码

三、总结

栈的定义
栈的顺序存储实现

首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第十课 栈的表示与实现

首页 / 软件开发 / 数据结构与算法 / 数据结构教程第十课栈的表示与实现