栈的顺序表示和实现

数学与计算科学学院实 验 报 告实验项目名称 栈的顺序表示和实现 所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期 2013.11.14 班 级 信计1201 学 号 9 姓 名 成 绩 一、实验概述：【实验目的】掌握栈的特点及顺序栈的基本运算【实验原理】1、栈是限定仅在表尾插入或删除操作的线性表，栈的修改是按后进先出的原则进行的2、栈的顺序存储表示：#define STACK_INIT_SIZE 6 /存储空间初始分配量#define STACKINCREMENT 2 /存储空间分配增量typedef structSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前分配的存储空间，以元素为单位SqStack;【实验环境】VC + 6.0二、实验内容：【实验方案】编写主函数，调用栈的初始化建空栈、取栈顶元素、进栈以及出栈的算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入初始化建空栈、取栈顶元素、进栈、出栈算法和主函数：/栈的顺序存储表示#define STACK_INIT_SIZE 6； /存储空间初始分配量#define STACKINCREMENT 2； /存储空间分配增量typedef structSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前分配的存储空间，以元素为单位SqStack;Status InitStack(SqStack &S)/构造一个空栈S/InitStackStatus GetTop(SqStack S,SElemType &e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素/PushStatus Pop(SqStack &S,SElemType &e)/若栈顶不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR/Popvoid main()2、调试：发现错误：在以下编码中出现多个错误：Status InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);syntax error : missing ) before ;；syntax error : )；illegal indirection；这三个错误主要是由于前面栈的顺序存储表示编码中出现错误，应把“#define STACK_INIT_SIZE 6； #define STACKINCREMENT 2；”中的两个分号去掉；修改之后，继续调试，又发现一个错误： Sqstack : undeclared identifier即Sqstack无定义，查看前面编码发现，是对SqStack进行定义，故这里也要与之相应，需把Sqstack改为SqStack；3、调试到无任何错误，运行：因栈的存储空间初始化分配量为6，故需输入六个数字“2 3 56 7 7 5”，按回车键，得到“2 3 56 7 7 5；e=5”其中e=5表示栈顶元素为5，由此完成了栈的初始化建空栈、取栈顶元素算法；接着输入一个数“23”，表示要插入的元素，回车，得到“2 3 56 7 7 23；e=23；23”，此时“23”已进栈，栈顶元素变为e=23，因存储空间为6，而栈的修改是按后进先出原则进行，所以栈顶元素“23”先出栈，由此完成了栈的进栈、出栈算法；最终栈的顺序表示和实现得以完成。【实验结论】（结果）【实验小结】（收获体会）这次上机，顺利的完成了栈的顺序表示和实现的上机实验任务，但是没有能够独立编写主函数，而是需要在老师和同学的帮助下才能够编写出来，所以自己还要继续努力，争取学会自己编写主函数。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define STACK_INIT_SIZE 6 /存储空间初始分配量#define STACKINCREMENT 2 /存储空间分配增量typedef structSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前分配的存储空间，以元素为单位SqStack;Status InitStack(SqStack &S)/构造一个空栈SS.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus GetTop(SqStack S,SElemType &e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top=S.base) return ERROR;e=*(S.top-1);return OK;/GetTopStatus 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.base+S.stacksize;S.stacksize +=STACKINCREMENT;* S.top+=e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若栈顶不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base) return ERROR;e= * -S.top;return OK;/Popvoid main()SqStack S;int i;SElemType e;InitStack(S); for(i=0;iSTACK_INIT_SIZE;i+)scanf(%d,&S.basei);S.top+;for(i=0;iS.top-S.base;i+)printf(%d ,*(S.base+i); printf(n); GetTop(S,e);printf(e=%dn,e);scanf