栈的定义及基本操作.doc

附件2：北京理工大学珠海学院实验报告ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY班级 学号 姓名 指导教师 成绩实验题目 栈的定义及基本操作 实验时间一、实验目的、意义（1）理解栈的特点，掌握栈的定义和基本操作。（2）掌握进栈、出栈、取栈顶操作的实现方法，熟练掌握顺序栈的操作及应用。（3）栈的应用：数制转换和中缀表达式转后缀表达式二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。说明2：用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制的转换conversion算法，再由conversion调用InitStack、StackEmpty、Push、Pop算法。修改输入数据，预期输出并验证输出的结果，加深对Push和Pop算法的理解。说明 3：编写中缀转后缀表达式程序。具体要求：（1）定义顺序栈，完成栈的基本操作：初始化栈、入栈、出栈、取栈顶元素。（参见教材45页）（2）实现十进制数与八进制数的转换。（基本任务，必须完成）（3）实现中缀表达式转后缀表达式。由控制台输入中缀表达式，输出后缀表达式。（附加任务，鼓励完成。） 三、实验所涉及的知识点算法四、实验记录 (调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)五、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 初始界面进栈功能遍历功能出栈功能判断是否为空数制转换六、总结与体会（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）七、程序清单(包含注释)/*通用头文件*/#define TRUE 1#define FLASE 0#define OK 1#define ERROR 0#define INFREASIBLE -1#define OVERFLOW -2#define SIZE 100/存储空间初始分配量#define INCREMENT 10/存储空间分配增量typedef int Status;typedef int ElemType;/*顺序栈头文件*/#include DataStructure.h#include stdio.h#include stdlib.h#include string.htypedef structElemType *top;/栈顶指针ElemType *base;/栈底指针int stacksize;/当前已分配的存储空间SqStack;/*基本操作的函数说明1.初始化InitStack(SqStack &s)2.置空ClearStack(SqStack &s)3.销毁DestroyStack(SqStack &s)4.是否空StackEmpty(SqStack s)5.栈元素数StackLength(SqStack s)6.取栈顶元素GetTop(SqStack s, ElemType &e)7.进栈Push(SqStack &s, ElemType e)8.出栈Pop(SqStack &s, ElemType &e)9.遍历StackTraverse(SqStack s)10.数值转换Conversion(SqStack *s, ElemType N)11.中缀转后缀EvaluateExperssion()*/* 1.初始化*/Status InitStack(SqStack *s)/构造一个空栈道Ss-base=(ElemType *)malloc(SIZE*sizeof(ElemType);if(!s-base)exit(OVERFLOW);s-top=s-base;s-stacksize=SIZE;return OK;/* END 1.初始化*/* 2.置空 */Status ClearStack(SqStack *s)s-top = s-base;return OK;/* END 2.置空*/* 3.销毁 */Status DestroyStack(SqStack *s)ClearStack(s);free(s-base);return OK;/* END 3.销毁*/* 4.是否空 */Status StackEmpty(SqStack s)if(s.top = s.base)return TRUE;elsereturn FLASE;/* END 4.是否空*/* 5.栈元素数 */Status StackLength(SqStack s)ElemType length;length = s.top - s.base;return length;/* END 5.栈元素数*/* 6.取栈顶*/Status GetTop(SqStack s,ElemType *e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(s.top = s.base)return ERROR;*e = *(s.top-1);return OK;/* END 6.取栈顶*/* 7.进栈*/Status Push(SqStack *s, ElemType e)/插入元素e为新的栈顶元素if(s-top - s-base = s-stacksize)/栈满，追加存储空间s-base = (ElemType *)realloc(s-base,(s-stacksize+SIZE)*sizeof(ElemType);if(!s-base)exit(OVERFLOW);/存储分配失败s-top = s-base + s-stacksize;s-stacksize += SIZE;*(s-top)+ = e;return OK;/* END 7.进栈*/* 8.出栈*/Status Pop(SqStack *s,ElemType *e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(s-base = s-top)return ERROR;*e = *-s-top;return OK;/* END 8.出栈*/* 9.遍历 */Status StackTraverse(SqStack s)while(s.top != s.base)printf(%dt,*-s.top);return OK;/* END 9.遍历*/* 10.数值转换 */Status Conversion(SqStack *s, ElemType N)ElemType e;while(N)Push(s, N % 8);N = N / 8;while(s-top != s-base)Pop(s, &e);printf(%d, e);return OK;/*顺序栈主函数 */#include SqStack.h#include string.hvoid main()SqStack sq;InitStack(&sq);ElemType e;ElemType N;int k;int n = 0;/*功能界面 */Z:printf(nt*);printf(nt* 请你输入相应的操作序号进行操作 *);printf(nt*1.初始化 *);printf(nt*2.置空 *);printf(nt*3.销毁 *);printf(nt*4.是否空 *);printf(nt*5.栈元素数 *);printf(nt*6.取栈顶元素 *);printf(nt*7.进栈 *);printf(nt*8.出栈 *);printf(nt*9.遍历 *);printf(nt*10.数制转换 *);printf(nt*0. 退出 *n);printf(t*);printf(n请选择功能：);scanf(%d,&k);switch(k)case 1:InitStack(&sq);goto Z;break;case 2:ClearStack(&sq);goto Z;break;case 3:DestroyStack(&sq);goto Z;break;case 4:if(StackEmpty(sq)printf(该栈为空!);elseprintf(该栈非空!);goto Z;break;case 5:printf(栈元素的数目为：%d, StackLength(sq);goto Z;break;case 6:GetTop(sq, &e);printf(栈顶元素为：%d, e);goto Z;break;case 7:printf(请输入要进栈的元素：);scanf(%d, &e);Push(&sq, e);goto Z;break;case 8:Pop(&sq,&e);prin