数据结构严蔚敏----顺序栈基本操作9个
编程语言:C
编译环境:Dev-C++
栈(stack)是限定仅在表尾(栈顶top)进行插入或删除操作的线性表,相应地,另一端称为表头(栈底base),base类似于顺序表中的基址
栈的顺序存储表示:
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 5
typedef struct{
ElemType *base;//基址,在栈构造之前和销毁之后,base的值为NULL
ElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间
}SqStack;
源代码:
//实现书P45 ADT Stack 基本操作9个,用顺序存储结构实现
//栈(stack)是限定仅在表尾(栈顶top)进行插入或删除操作的线性表,相应地,另一端称为表头(栈底base),base类似于顺序表中的基址
//1.Status InitStack(SqStack *S) 构造一个空栈S
// base赋值(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)),判断是否赋值成功,if(!(*S).base) exit(OVERFLOW);
// 令top=base;stacksize=STACK_INIT_SIZE;return OK;
//2.Status DestroyStack(SqStack *S) 销毁栈,前提S存在
// 释放基址base,base和top置为NULL,stacksize置为0,return OK;
//3.Status ClearStack(SqStack *S) 清空栈,前提S存在
// 令top=base,return OK;
//4.Status StackEmpty(SqStack S) 探空,前提S存在
// if((*S).top==(*S).base) return TRUE;否则return FALSE;
//5.int StackLength(SqStack S) 返回栈中元素的个数,前提S存在
// return S.top-S.base;
//6.Status GetTop(SqStack S,ElemType *e) 若栈不空,用e返回栈顶元素,前提S存在
// if(S.top==S.base) return ERROR;否则*e=*(S.top-1);return OK;
//7.Status Push(SqStack *S,ElemType e) 入栈(插入元素e为新的栈顶元素),前提S存在
// 先判断栈是否已满if((*S).top-(*S).base>=(*S).stacksize),若已满,增加分配空间
// base赋新值(ElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(ElemType))
// 判断是否赋值成功,if(!(*S).base) exit(OVERFLOW);
// 令top=base+stacksize;stacksize+=STACKINCREMENT;
// 然后进行插入,*((*S).top++)=e;(先插入,栈顶指针再加1)return OK;
//8.Status Pop(SqStack *S,ElemType *e) 出栈(若栈不空,删除栈顶元素,并用e返回其值),前提S存在
// if(S.top==S.base) return ERROR;否则进行删除,*e=*(--(*S).top);(先栈顶指针减1,再取元素)return OK;
//9.Status StackTraverse(SqStack S) 顺序栈的遍历:依次访问栈中每一个元素,前提S存在
// if(S.top==S.base) printf("栈为空!\n");
// else int i=0;while(i<S.top-S.base) printf("%d ",*(S.base+i));
// 最后printf("\n");return OK;
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
//栈的顺序存储表示
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 5
typedef struct{
ElemType *base;//基址,在栈构造之前和销毁之后,base的值为NULL
ElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间
}SqStack;
//1.构造一个空栈S
Status InitStack(SqStack *S)
{
(*S).base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
//2.销毁栈,前提S存在
Status DestroyStack(SqStack *S)
{
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
return OK;
}
//3.清空栈,前提S存在
Status ClearStack(SqStack *S)
{
(*S).top=(*S).base;
return OK;
}
//4.探空,前提S存在
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
//5.返回栈中元素的个数,前提S存在
int StackLength(SqStack S)
{
return S.top-S.base;
}
//6.若栈不空,用e返回栈顶元素,前提S存在
Status GetTop(SqStack S,ElemType *e)
{
if(S.top==S.base) return ERROR;
*e=*(S.top-1);
return OK;
}
//7.入栈(插入元素e为新的栈顶元素),前提S存在
Status Push(SqStack *S,ElemType e)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(ElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top++)=e;
return OK;
}
//8.出栈(若栈不空,删除栈顶元素,并用e返回其值),前提S存在
Status Pop(SqStack *S,ElemType *e)
{
if((*S).top==(*S).base) return ERROR;
*e=*(--(*S).top);
return OK;
}
//9.顺序栈的遍历:依次访问栈中每一个元素,前提S存在
Status StackTraverse(SqStack S)
{
if(S.top==S.base)
printf("栈为空!");
else
{
int i=0;
while(i<S.top-S.base)
{
printf("%d ",*(S.base+i));
i++;
}
}
printf("\n");
return OK;
}
int main()
{
SqStack S;
int i;
ElemType e=0;
printf("测试第一个基本操作\n");
InitStack(&S);
printf("构造空栈后,栈中的元素为:");
StackTraverse(S);
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
GetTop(S,&e);
printf("栈顶元素为(0表示无栈顶元素):%d\n",e);
for(i=1;i<=5;i++)
Push(&S,i);
printf("\n\n测试第七个基本操作\n");
printf("将1~5依次入栈后,栈中的元素为:");
StackTraverse(S);
printf("第九个基本操作测试成功!\n");
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
e=0;
GetTop(S,&e);
printf("栈顶元素为(0表示无栈顶元素):%d\n",e);
for(i=6;i<=11;i++)
Push(&S,i);
printf("继续测试第七个基本操作\n");
printf("再将6~11依次入栈后,栈中的元素为:");
StackTraverse(S);
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
e=0;
GetTop(S,&e);
printf("栈顶元素为(0表示无栈顶元素):%d\n",e);
printf("第六个基本操作测试成功!\n");
printf("\n\n测试第八个基本操作\n");
e=0;
Pop(&S,&e);
printf("出栈后栈中的元素为:");
StackTraverse(S);
printf("删除的栈顶元素为:%d\n",e);
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
printf("\n\n测试第五个基本操作\n");
printf("栈中元素的个数为:%d\n",StackLength(S));
printf("\n\n测试第三、第四个基本操作\n");
printf("栈是否为空(1为空,0为不空):%d\n",StackEmpty(S));
ClearStack(&S);
printf("清空栈后,栈是否为空(1为空,0为不空):%d\n",StackEmpty(S));
printf("\n\n测试第二个基本操作\n");
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
if(DestroyStack(&S)==OK)
printf("成功销毁栈!\n");
printf("S.base=%d,S.top=%d,S.stacksize=%d\n",S.base,S.top,S.stacksize);
return 0;
}
运行结果:
觉得有帮助的话,留下你们的赞哦。
如果有任何建议欢迎底下评论,我会努力改进的!