栈的基本操作实验报告

学号姓名实验日期2012-12-6实验室计算机软件技术实验指导教师设备编号401实验内容栈的基本操作一实验题目实现栈的基本操作的代码实现二实验目的掌握栈的基本操作三实习要求（1）认真阅读书上给出的算法（2）编写程序并独立调试四、给出线性表的抽象数据类型ADTStack{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}约定a1为站定栈顶，an为栈底。基本操作：InitStack(&S); 操作结果:创造一个空栈SDestroyStack(&S);初始条件：栈S已存在操作结果：栈S被销毁ClearStack(&S);初始条件：栈S已存在操作结果：将S清为空栈StackEmpty(S);初始条件：栈S已存在操作结果：若S为空栈，则返回TURE，否则FALSEStackLength(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、给出本数据的存储结构定义及栈的定义#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW-2实现栈的抽象数据类型如下:链式存储实现的抽象数据类型如下：2.运算的函数声明：StatusInitStack(SqStack&S); //构造造一个空栈SStatusDestroyStack(SqStack&S);//销毁栈SStatusClearStack(SqStack&S);//重置栈SStatusStackEmpty(SqStackS);//判断栈S是否为空StatusStackLength(SqStackS);//求栈长StatusGetTop(SqStackS,SElemType&e);//用e返回栈顶元素StatusPush(SqStack&S,SElemTypee);//插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);//删除栈顶元素，并用e返回其值StatusStackTraverse(SqStackS);//从栈底到栈顶依次调用visit函数3.给出操作实现的伪码StatusInitStack(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; returnOK;}//InitStackStatusDestroyStack(SqStack&S){//销毁栈S if(S.base!=NULL) { free(S.base); S.base=S.top=NULL; } S.stacksize=0; returnOK;}StatusClearStack(SqStack&S){//重置栈S S.base=S.top; returnOK;}StatusStackEmpty(SqStackS){//判断栈S是否为空 if(S.top==S.base) returnTRUE; else returnFALSE;}StatusStackLength(SqStackS){//求栈长 inti;SElemType*p; i=0; p=S.top; while(p!=S.base) { p--; i++; } returni; }//stackLengthStatusGetTop(SqStackS,SElemType&e){//用e返回栈顶元素 if(S.base==S.top) returnERROR; e=*(S.top-1); returnOK;}//GetTopStatusPush(SqStack&S,SElemTypee){//插入元素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; returnOK;}//pushStatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR if(S.top==S.base) returnERROR; e=*--S.top; returnOK;}//PopStatusStackTraverse(SqStackS){//从栈底到栈顶依次调用visit函数 SElemType*p; p=S.base; while(p!=S.top) { printf("%5d",*p); p++; } returnOK;}六、实验环境1.环境：宿舍。2.硬件：2048M内存，500G硬盘。 3.系统：Windows764位操作系统4.软件平台：MicrosoftVisualC++6.0简体中文版七、相关文件列表如下demo.cpp:主程序文件Stack.cpp:操作实现的算法Stack.h：函数声明Mydef.h：存储结构的定义八、程序的运