栈的定义及基本操作

附件2：

实验题目栈的定义及基本操作实验时间

一、实验目的、意义

（1）理解栈的特点，掌握栈的定义和基本操作。

（2）掌握进栈、出栈、取栈顶操作的实现方法，熟练掌握顺序栈的操作及应用。

（3）栈的应用：数制转换和中缀表达式转后缀表达式

二、实验内容及要求

说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

说明2：用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制的转换conversion算法，再由conversion调用InitStack、StackEmpty、Push、Pop算法。修改输入数据，预期输出并验证输出的结果，加深对Push和Pop算法的理解。

说明3：编写中缀转后缀表达式程序。

具体要求：

（1）定义顺序栈，完成栈的基本操作：初始化栈、入栈、出栈、取栈顶元素。

（参见教材45页）

（2）实现十进制数与八进制数的转换。（基本任务，必须完成）
（3）实现中缀表达式转后缀表达式。由控制台输入中缀表达式，输出后缀表达式。

（附加任务，鼓励完成。）

三、实验所涉及的知识点

算法

四、实验记录

1

(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)

五、实验结果及分析

（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图

方式给出。）

初始界面

进栈功能

2

遍历功能

出栈功能

判断是否为空

3

数制转换

六、总结与体会
（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）

七、程序清单(包含注释)
/*************************************** 通用头文件
***************************************/

#defineTRUE 1
#defineFLASE 0
#defineOK 1
#defineERROR 0
#defineINFREASIBLE -1
#defineOVERFLOW -2
4

#defineSIZE 100//存储空间初始分配量

//存储空间分配增量

//当前已分配的存储空间

5.栈元素数StackLength(SqStacks)
6.取栈顶元素 GetTop(SqStacks, ElemType &e)
7.进栈 Push(SqStack&s, ElemType e)
8.出栈 Pop(SqStack&s, ElemType &e)
9.遍历
StackTraverse(SqStacks) 10.数值转换Conversion(SqStack*s, ElemType N)
11.中缀转后缀EvaluateExperssion()
*****************************************************/

/*** 1.初始化***/
StatusInitStack(SqStack *s){
//构造一个空栈道S
s->base=(ElemType*)malloc(SIZE*sizeof(ElemType)); if(!s->base)
exit(OVERFLOW);
s->top=s->base;
s->stacksize=SIZE;
returnOK;
}/***END 1.初始化***/

/*** 2.置空***/
StatusClearStack(SqStack *s){
s->top= s->base;
6

returnOK;
}/***END 2.置空***/

/*** 3.销毁***/
StatusDestroyStack(SqStack *s){ ClearStack(s);
free(s->base);
returnOK;
}/***END 3.销毁***/

/*** 4.是否空***/
StatusStackEmpty(SqStack s){
if(s.top== s.base){
returnTRUE;
}
else{
returnFLASE;
}
}/***END 4.是否空***/

/*** 5.栈元素数***/
StatusStackLength(SqStack s){
ElemTypelength;
7

length= s.top - s.base;
returnlength;
}/***END 5.栈元素数***/

/*** 6.取栈顶***/
StatusGetTop(SqStack s,ElemType *e){
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(s.top== s.base){
returnERROR;
}
*e= *(s.top-1);
returnOK;
}/*** END 6.取栈顶***/

/*** 7.进栈***/
StatusPush(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)

//存储分配失败

s->top= s->base + s->stacksize; s->stacksize+= SIZE;
}
*(s->top)++= e;
returnOK;
}/***END 7.进栈***/

/*** 8.出栈***/
StatusPop(SqStack *s,ElemType *e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(s->base== s->top)
returnERROR;
*e= *--s->top;
returnOK;
}/*** END 8.出栈***/

/*** 9.遍历***/
StatusStackTraverse(SqStack s){
while(s.top!= s.base){
printf("%d\t",*--s.top);
}
returnOK;
9

}/***END 9.遍历***/

/***10.数值转换***/
StatusConversion(SqStack *s, ElemType N){ ElemTypee;
while(N){
Push(s,N % 8);
N= N / 8;
}
while(s->top!= s->base){
Pop(s,&e);
printf("%d",e);
}
returnOK;
}

/************************************
* 顺序栈主函数 *
************************************/
#include"SqStack.h"
#include"string.h"
voidmain(){
10

SqStacksq;
InitStack(&sq);
ElemTypee;
ElemTypeN;
intk;
intn = 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.栈元素数
11

***");

6.取栈顶元素

10.数制转换

ClearStack(&sq);
gotoZ;
break;
case3:
DestroyStack(&sq);
gotoZ;
break;
case4:
if(StackEmpty(sq)){
printf("该栈为空!");
}
else
{
printf("该栈非空!");
}
gotoZ;
break;
case5:
printf("栈元素的数目为：%d",StackLength(sq)); gotoZ;
break;
case6:
GetTop(sq,&e);
13

printf("栈顶元素为：%d",e);
gotoZ;
break;
case7:
printf("请输入要进栈的元素：");
scanf("%d",&e);
Push(&sq,e);
gotoZ;
break;
case8:
Pop(&sq,&e);
printf("%d",e);
gotoZ;
break;
case9:
StackTraverse(sq);
gotoZ;
break;
case10:
printf("请输入要转换的十进制数字：");
scanf("%d",&N);
printf("转换后八进制的数字为：");
Conversion(&sq,N);
14

gotoZ;
break;
case0:
exit(0);
break;
default:break;
}
}
}

15