栈的基本操作实验报告

二 实验目的

掌握栈的基本操作

三 实习要求

（1）认真阅读书上给出的算法 （2）编写程序并独立调试

四、给出线性表的抽象数据类型

ADT Stack{

数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}

数据关系：R1={|ai-1,ai∈D, i=1,2, …,n }

约定a1为站定栈顶，an为栈底。 基本操作：

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的栈顶元素 Push(&S, e);

初始条件：栈S已存在

操作结果：插入元素e为新的栈顶元素

Pop(&S, &e);

初始条件：栈S已存在且非空

操作结果：删除S的栈顶元素，并用e返回其值 StackTraverse(S，visit（）);

初始条件：栈S已存在且非空

操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失败

五、详细设计

1、给出本数据的存储结构定义及栈的定义

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define NULL 0

#define OVERFLOW -2

实现栈的抽象数据类型如下:

链式存储实现的抽象数据类型如下：

2.运算的函数声明：

Status InitStack(SqStack &S); //构造造一个空栈S Status DestroyStack(SqStack &S); //销毁栈S Status ClearStack(SqStack &S);//重置栈S

Status StackEmpty(SqStack S); //判断栈S是否为空

Status StackLength(SqStack S);//求栈长

Status GetTop(SqStack S, SElemType &e); //用e返回栈顶元素

Status Push(SqStack &S,SElemType e); //插入元素e为新的栈顶元素

Status Pop(SqStack &S,SElemType &e);//删除栈顶元素，并用e返回其值 Status StackTraverse(SqStack S);//从栈底到栈顶依次调用visit函数

3.给出操作实现的伪码

Status InitStack(SqStack &S) {//构造一个空栈S

S.base = (SElemType * )malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top = S.base;

S.stacksize = STACK_INIT_SIZE; return OK;

}//InitStack

Status DestroyStack(SqStack &S) {//销毁栈S

if (S.base != NULL) {

free(S.base);

S.base = S.top = NULL;

}

}

S.stacksize=0; return OK;

Status ClearStack(SqStack &S) {//重置栈S }

Status StackEmpty(SqStack S) {//判断栈S是否为空 if(S.top==S.base) }

return TRUE; else

return FALSE; S.base=S.top; return OK;

Status StackLength(SqStack S) {//求栈长

int i; SElemType *p;

i=0;

p=S.top;

while(p!=S.base) {

p--; i++;

}

return i;

} //stackLength

Status GetTop(SqStack S, SElemType &e) {//用e返回栈顶元素

if(S.base == S.top)

return ERROR;

e = *(S.top-1); return OK; }//GetTop

Status Push(SqStack &S,SElemType e) {//插入元素e为新的栈顶元素

if(S.top - S.base >=S.stacksize) {//栈满 追加存储空间

S.base

=

(SElemType

* )realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base) exit(OVERFLOW); S.top= S.stacksize+S.base;

S.stacksize+=STACKINCREMENT; }

*S.top++ = e; return OK;

}//push

Status Pop(SqStack &S,SElemType &e)

{//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR

if(S.top == S.base) return ERROR; e=*--S.top; return OK;

}//Pop

Status StackTraverse(SqStack S)

{//从栈底到栈顶依次调用visit函数 }

SElemType *p; {

p=S.base;

while(p!=S.top) printf(\"%5d\p++;

}

return OK;

六、实验环境

1.环境：宿舍。

2.硬件：2048M内存，500G硬盘。 3.系统：Windows 7 64位操作系统

4.软件平台：Microsoft Visual C++ 6.0简体中文版

七、相关文件列表如下

demo.cpp: 主程序文件

Stack.cpp: 操作实现的算法 Stack.h：函数声明 Mydef.h：存储结构的定义

八、程序的运行测试及结果

九、 本次实习总结

1．总结本次实习的收获

通过本次实习，加强了对栈的认识与相关操作的算法、编程实现； 2．本系统的不足之处 （1）系统的健壮行不够强； （2）代码不够优化。

3.遇到的困难

一开始总是有一个错误，便一直找原因，百度，后来发现定义时写的与后面写的不一样，导致错误