数据结构栈的定义及基本操作

1、 北京理工大学珠海学院实验报告ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY班级 软件工程3班 学号 150202102309 姓名 郭荣栋 指导教师 余俊杰 成绩实验题目 栈的实现与应用 实验时间 一、实验目的、意义（1）理解栈的特点，掌握栈的定义和基本操作。（2）掌握进栈、出栈、清空栈运算的实现方法。（3）熟练掌握顺序栈的操作及应用。二、实验内容及要求1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。3. 调用栈的基本操作，实现表达式求值，如输入3

2、*（7-2）#，得到结果15。三、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释)1、2.#include<iostream>#include<cmath>#include<stdlib.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2 #define MAXSIZE 100 #define INCREASEMENT 10#define STACK_INIT_SIZE 100#define STAC

3、KINCREMENT 10typedef int SElemType;typedef int Status;typedef structSElemType *base;SElemType *top;int stacksize;Sqstack;void StackTraverse(Sqstack S) while (S.top != S.base) cout << *(S.top-1) << endl; S.top-; Status InitStack(Sqstack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*si

4、zeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status GetTop(Sqstack &S, SElemType &e) if (S.top = S.base) return ERROR; e = *(S.top - 1); cout<<e<<endl;cout << "The stack is:" << endl; StackTraverse(S); return O

5、K; Status push(Sqstack &S,SElemType e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(INCREASEMENT+S.stacksize)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(Sqstack &S, SElemType &e) if

6、(S.base = S.top) return ERROR; e = *-S.top; return OK; Status StackEmpty(Sqstack S) return (S.top = S.base); void main()Sqstack S;int a,b,e;InitStack(S);printf("请键入栈的十进制数值：");cin>>a;while(a)push(S,a%16);a=a/16;printf("此时栈顶元素为：");GetTop(S,e);printf("转换为十六进制数为：");wh

7、ile(!StackEmpty(S)Pop(S,b);printf("%x",b);printf("n");system("pause");3.#include<iostream>#include<stdio.h>#include<malloc.h>#include<stdlib.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW 0 #define STACK_INIT_SIZE 100#define ST

8、ACKINCREMENT 10typedef int SElemType;typedef int Status;typedef float OperandType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;void StackTraverse(SqStack S) while (S.top != S.base) cout << *(S.top-1) << endl; S.top-; Status InitStack(SqStack &S)S.base=(SElemType

9、 *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S) if(S.top=S.base)return OK;return ERROR;Status GetTop(SqStack S, SElemType &e) if (StackEmpty(S) return ERROR; e = *(S.top - 1); return OK; Status

10、push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(STACKINCREMENT+S.stacksize)*sizeof(SElemType);if(!S.base)return OVERFLOW;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S, SElemType &e) if (S.base

11、 = S.top) return ERROR; e = *-S.top; return OK; char a77='>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>',

12、9;>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','0','>','>

13、','>','>','0','>','>','<','<','<','<','<','0','='int In(char);char Precede(char x,char y)int i,j;i=In(x);j=In(y);return aij;Status operate(int a,char theta,int b)switch(thet

14、a)case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;Status In(char theta)int n;switch(theta)case '+':n=0;break;case '-':n=1;break;case '*':n=2;break;case '/':n=3;break;case '(':n=4;break;case ')

15、':n=5;break;case '#':n=6;break;return n;OperandType EvaluateExpression()char c,d100;int i,e,a,b,theta,num;SqStack Optr,Opnd;InitStack(Optr);push(Optr,'#');InitStack(Opnd);printf("请输入一串表达式并以'#'结尾：");c=getchar();GetTop(Optr,e);while(c!='#'|e!='#')if(c>='0'&&c<='9')|c='.')i=0;dodi+=c;c=getchar();while(c>='0'&&c<='9');di='0'num=atoi(d);push(Opnd,num);elseGetTop(Optr,e);switch(Precede(e,c)case '<':push(Optr,c);c=getchar();break;case '=':Pop(Optr,e);c