正文  电脑教程 > 服务器教程 >

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

C语言数据结构之栈简单操作 实验: 编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: (1)初始化顺序栈 (2)插入元...

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("
"); 
  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
", e); 
  printf("元素出栈后事实上并没有清除,依然存在于内存空间,所谓的出栈只是指针移动,出栈的元素是%d
", *s->top);//判断出栈后元素是否还存在于内存中 
  Destroy(s); 
  return 0; 
} 

运行结果:

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