栈的定义及基本操作
附件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.h"
typedef struct{
ElemType *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){
//构造一个空栈道S
s->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;
}
else{
return 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；否则返回ERROR
if(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；否则返回ERROR
if(s->base == s->top)
return ERROR;
*e = *--s->top;
return OK;
}/*** END 8.出栈***/
/*** 9.遍历 ***/
Status StackTraverse(SqStack s){
while(s.top != s.base){
printf("%d\t",*--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.h"
void main(){
SqStack sq;
InitStack(&sq);
ElemType e;
ElemType N;
int k;
int n = 0;
/****** 功能界面 ********/
Z:
{
printf("\n\t***************************************** ***");
printf("\n\t*** 请你输入相应的操作序号进行操作***");
printf("\n\t*** 1.初始化
***");
printf("\n\t*** 2.置空
***");
printf("\n\t*** 3.销毁
***");
printf("\n\t*** 4.是否空
***");
printf("\n\t*** 5.栈元素数
***");
printf("\n\t*** 6.取栈顶元素
***");
printf("\n\t*** 7.进栈
***");
printf("\n\t*** 8.出栈
***");
printf("\n\t*** 9.遍历
***");
printf("\n\t*** 10.数制转换
***");
printf("\n\t*** 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("该栈为空!");
}
else
{
printf("该栈非空!");
}
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);
printf("%d", e);
goto Z;
break;
case 9:
StackTraverse(sq);
goto Z;
break;
case 10:
printf("请输入要转换的十进制数字：");
scanf("%d", &N);
printf("转换后八进制的数字为：");
Conversion(&sq, N);
goto Z;
break;
case 0:
exit(0);
break;
default:break;
}
}
}