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

北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级 软件工程3班  学号 9     姓名   郭荣栋          指导教师  余俊杰                               成绩 实验题目 栈的实现与应用                 实验时间  一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 #define INCREASEMENT 10 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef  int SElemType; typedef int Status; typedef struct{ SElemType *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*sizeof(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<=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 (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("转换为十六进制数为："); while(!StackEmpty(S)) { Pop(S,b); printf("%x",b); } printf("\n"); system("pause"); } 3. #include #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW 0  #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef  int SElemType; typedef int Status; typedef float OperandType; typedef struct{ SElemType *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*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 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 == S.top) return ERROR; e = *--S.top; return OK; } char a[7][7]={'>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','\0', '>','>','>','>','\0','>','>', '<','<','<','<','<','\0','='}; int In(char); char Precede(char x,char y) { int i,j; i=In(x); j=In(y); return a[i][j]; } Status operate(int a,char theta,int b) { switch(theta) { 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 ')': n=5; break; case '#': n=6; break; } return n; } OperandType EvaluateExpression() { char c,d[100]; 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; do{ d[i++]=c; c=getchar(); }while(c>='0'&&c<='9'); d[i]='\0'; num=atoi(d); push(Opnd,num); } else{ GetTop(Optr,e); switch(Precede(e,c)){ case '<': push(Optr,c); c=getchar(); break; case '=': Pop(Optr,e); c=getchar(); break; case '>': Pop(Optr,theta); Pop(Opnd,b); Pop(Opnd,a); push(Opnd,operate(a,theta,b)); break; }; } GetTop(Optr,e); } GetTop(Opnd,e); return e; } int main() { printf("表达式结果为：%0.2f\n",EvaluateExpression()); system("pause"); return 0; }