北京理工大学珠海学院实验报告
ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋
指导教师余俊杰成绩
实验题目栈的实现与应用实验时间
一、实验目的、意义
（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<cout << "The stack is:" << endl;
StackTraverse(S);
return OK;
}
Status push(Sqstack &S,SElemType e){
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(INCREASEMENT+S.stac ksize)*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;
