本课主题： 栈的表示与实现
教学目的： 栈的数据类型定义、栈的顺序存储表示与实现
教学重点： 栈的顺序存储表示与实现方法
教学难点： 栈的定义
授课内容：
一、栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
栈的抽象数据类型定义：
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语言源码
三、总结
栈的定义
栈的顺序存储实现