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

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;
}

运行结果：

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！