C语言数据结构之栈简单操作

2020-01-26 14:02:59

字体：大中小

来源：转载

供稿：网友

C语言数据结构之栈简单操作

实验：

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈

分析:

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。

出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。

注意：

（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

顺序栈的实现：

#include <stdio.h> #include <malloc.h>  typedef int SElemType; typedef int Status; #define INIT_SIZE 100 #define STACKINCREMENT 10 #define Ok 1 #define Error 0 #define True 1 #define False 0 typedef struct {   SElemType *base;   SElemType *top;   int stacksize; }SqStack;  //初始化栈 Status InitStack(SqStack *s) {   s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));   if(!s->base)   {     puts("存储空间分配失败！");     return Error;   }   s->top = s->base;   s->stacksize = INIT_SIZE;   return Ok; }  //清空栈 Status ClearStack(SqStack *s)  {   s->top = s->base;   return Ok;  }  //栈是否为空 Status StackEmpty(SqStack *s)  {   if(s->top == s->base)    return True;   else    return False;  }  //销毁栈 Status Destroy(SqStack *s) {   free(s->base);   s->base = NULL;   s->top = NULL;   s->stacksize=0;   return Ok; }  //获得栈顶元素 Status GetTop(SqStack *s, SElemType &e) {   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 = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));     if(!s->base)     {       puts("存储空间分配失败！");       return Error;     }     s->top = s->base + s->stacksize;//修改栈顶位置     s->stacksize += STACKINCREMENT;//修改栈长度    }   *s->top++ = e;   return Ok; }  //弹栈 Status Pop(SqStack *s, SElemType *e) {   if(s->top == s->base) return Error;   --s->top;   *e = *(s->top);   return Ok; }  //遍历栈 Status StackTraverse(SqStack *s,Status(*visit)(SElemType))  {    SElemType *b = s->base;//此处不能直接用base或top移动，即不能改变原栈的结构    SElemType *t = s->top;   while(t > b)    visit(*b++);   printf("/n");   return Ok;  }  Status visit(SElemType c)  {   printf("%d ",c);   return Ok;  }

测试代码：

int main() {   SqStack a;   SqStack *s = &a;   SElemType e;   InitStack(s);   int n;   puts("请输入要进栈的个数：");   scanf("%d", &n);   while(n--)   {     int m;     scanf("%d", &m);     Push(s, m);   }   StackTraverse(s, visit);   puts("");   puts("8进栈后：");   Push(s, 8);   StackTraverse(s, visit);   puts("");   Pop(s, &e);   printf("出栈的元素是：%d/n", e);   printf("元素出栈后事实上并没有清除，依然存在于内存空间，所谓的出栈只是指针移动，出栈的元素是%d/n", *s->top);//判断出栈后元素是否还存在于内存中   Destroy(s);   return 0; }

运行结果：