一、实验目的:
通过该实验,掌握栈的基本操作,熟练掌握链栈的具体实现方法及基本操作实现算法。特别注意栈满和栈空的条件以及它们的描述方法。
二、实验要求:
1、阅读程序,给出详细的注解;
2、运行程序,分析程序结果;
3、改写程序并且实现。
三、实验内容:
定义顺序栈的基本数据结构,完成相应的栈操作,包括初始化,判别栈空与栈满,入栈,出栈,取栈顶元素等操作。
四、实验原理:
status initstack(sqstack &s)为构造一个空栈;status gettop(sqstack s,selemtype &e)若栈不空,则用e返回s的栈顶元素,并返回OK,否则返回ERROR;status push(sqstack &s,selemtype e)是插入元素e为新的栈顶元素;status pop(sqstack &s,selemtype &e)是删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR; int stackempty(sqstack s)是判栈空,若栈空则返回1,否则返回0。在主函数中,首先构造一个空栈,然后通过scanf输入元素,通过for循环用push插入到栈中,每次插入的元素作为栈顶元素,最后通过while循环和stackempty判栈空删除栈的栈顶元素,并通过printf输出,最后输出的元素顺序与输入顺序相反。
五、程序代码:
#include
#include
#include
#include
#include"malloc.h"
#include"process.h"
#define list_init_size 100
#define listincrement 10
#define ERROR -1
#define OK 1
#define OVERFLOW -2
#define NULL 0
typedef int elemtype;
typedef int selemtype;
typedef int status;
typedef struct basect{
selemtype *base;
selemtype *top;
int stacksize;
}sqstack;
status initstack(sqstack &s)
{//构造个空栈
s.base=(selemtype *)malloc(list_init_size *sizeof(elemtype));
if(!s.base)
exit(OVERFLOW);
s.top=s.base;
s.stacksize=list_init_size;
return OK;
}
status gettop(sqstack s,selemtype &e)
{//若栈不空,则用e返回S的栈顶元素e,并返回OK;否则返回ERROR
if(s.top==s.base)
return ERROR;
e=*(s.top-1);
return OK;
}
status push(sqstack &s,selemtype e)
{//插入元素为新的栈顶元素
if(s.top-s.base>=s.stacksize)
{
s.base=(elemtype*)realloc(s.base,(s.stacksize+listincrement)*sizeof(elemtype));
if(!s.base)
exit(OVERFLOW);
s.top=s.base+s.stacksize;
}
*s.top++=e;
return OK;
}
status pop(sqstack &s,selemtype &e)
{//若栈不空,则删除s的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
if(s.top==s.base)
return ERROR;
e=*--s.top;
return OK;
}
int stackempty(sqstack s)
{//判栈空
if(s.base==s.top)
return 1;
else return 0;
}
void main()
{sqstack s;
int n,e,i;
initstack(s);
printf("\n 请输入元素个数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&e);
push(s,e);
}
printf("\n");
while(!stackempty(s))
{
pop(s,e);
printf("%d",e);
}
}
六、实验结果
本文来源:https://www.2haoxitong.net/k/doc/72772e51bb1aa8114431b90d6c85ec3a87c28bae.html
文档为doc格式