动态顺序栈的C语言实现


大家写的顺序栈一般都是用数组实现，大小固定，一旦压栈数量超过栈大小则会发生越界！现在写一个用malloc和realloc实现的动态顺序栈，当压栈数量超过栈大小时，程序可根据所需求空间自动调节栈大小，以满足要求！代码如下，调试通过，放心使用！

此动态顺序栈的栈底空间设为空，不用来作为存放数据的有效空间，故当输入栈大小为N时栈实际可用空间为（N-1）即只能压栈（N-1）次，否则若将使用空间也定为N的话，将发生类似“DAMAGE:after Normal block(#51) at 0x..........”的错误提示，即“越界”错误，详见文章末！

/************************************************
 运行平台：vc++6.0
 实现功能：利用realloc实现动态顺序栈（栈空间可增大）
************************************************/
 #include<stdio.h>
 #include<stdlib.h>
 #include<malloc.h>
 
typedef int eletype; /* 重新定义元素类型 */
 
#define INIT_SIZE 5  /* 栈初始大小 */
 
/* 定义一个可以操作动态顺序栈的结构体 */
 typedef struct stack
{
    eletype *p_top;    /* 栈顶指针 */
    eletype *p_bottom; /* 栈底指针 */
    int stack_size;    /* 栈大小 */
 }malloc_seqstack;      /* 动态顺序栈malloc_sequence_stack */
 
/*****************栈基本操作函数声明********************/
 void seqstack_init(malloc_seqstack *p_stack, int init_size);
 bool seqstack_full(malloc_seqstack *p_stack);
 bool seqstack_empty(malloc_seqstack *p_stack);
 void seqstack_push(malloc_seqstack *p_stack, int length, eletype value);
 eletype seqstack_pop(malloc_seqstack *p_stack);
 void seqstack_destroy(malloc_seqstack *p_stack);
 /*******************************************************/
 

/********************************************************
 *函数名称：main
 *函数功能：程序入口
 *入口参数：空
 *返 回 值：0
 ********************************************************/
 int main(void)
 {   
    int i = 0;
    int num = 0;
    int value = 0;
   
    /*******在栈中为结构体分配空间*******
    malloc_seqstack stack;
    malloc_seqstack *p_stack = &stack;
    ************************************/
 
    /*******在堆中为结构体分配空间*******/
    malloc_seqstack *p_stack = (malloc_seqstack *)malloc(sizeof(malloc_seqstack));
   

    seqstack_init(p_stack, INIT_SIZE);
   
    printf("请输入需要的动态顺序栈大小：\n");
    scanf("%d", &num);
 
    printf("请输入%d个数值：\n", num-1);   
    for(i=0; i<num-1; i++) 
    {
        scanf("%d", &value);     
        seqstack_push(p_stack, num, value);
    }
   
    printf("依次出栈：\n");
    for(i=0; i<num-1; i++)       
    {
        printf("%3d", seqstack_pop(p_stack));
    }
    printf("\n\n");
   
    seqstack_destroy(p_stack);
   
    return 0;
 }
 
/********************************************************
 *函数名称：seqstack_init
 *函数功能：初始化动态顺序栈
 *入口参数：p_stack为指向结构体指针
            init_size为栈初始大小
 *返 回 值：空
 ********************************************************/
 void seqstack_init(malloc_seqstack *p_stack, int init_size)
 {
    p_stack->p_bottom = (eletype *)malloc(init_size * sizeof(eletype));
   
    if (p_stack->p_bottom == NULL)
    {
        exit(-1);
    }
    p_stack->p_top = p_stack->p_bottom;
    p_stack->stack_size = init_size;
   
    return;
 }
 
/********************************************************
 *函数名称：seqstack_full
 *函数功能：判断栈是否为满
 *入口参数：p_stack为指向结构体指针
 *返 回 值：1为满，0为非满
 ********************************************************/
 bool seqstack_full(malloc_seqstack *p_stack)
 { 
    return p_stack->p_top - p_stack->p_bottom >= p_stack->stack_size-1;
 }
 
/********************************************************
 *函数名称：seqstack_empty
 *函数功能：判断栈是否为空
 *入口参数：p_stack为指向结构体指针
 *返 回 值：1为空，0为非空
 ********************************************************/
 bool seqstack_empty(malloc_seqstack *p_stack)
 {
    return p_stack->p_top <= p_stack->p_bottom;
 }
 
/********************************************************
 *函数名称：seqstack_push
 *函数功能：压栈
 *入口参数：p_stack为指向结构体指针
            length为欲压栈的数据个数
            value为欲压栈的数值
 *返 回 值：空
 ********************************************************/
 void seqstack_push(malloc_seqstack *p_stack, int length, eletype value)
 {
    eletype *p_tmp = p_stack->p_bottom;
   
    if (seqstack_full(p_stack))
    {
        printf("栈已满，系统将为其增加空间！\n");
       
        p_stack->p_bottom =
        (eletype *)realloc(p_stack->p_bottom, length*sizeof(eletype));
       
        if (!p_stack->p_bottom)
        {
            free(p_tmp);
            exit(-1);
        }
        p_stack->stack_size = length;
    }
    (p_stack->p_top)++;
    *(p_stack->p_top) = value;
   
    return;
 }
 
/********************************************************
 *函数名称：seqstack_pop
 *函数功能：出栈
 *入口参数：p_stack为指向结构体指针
 *返 回 值：value为出栈数据
 ********************************************************/
 eletype seqstack_pop(malloc_seqstack *p_stack)
 {
    eletype value = 0;
   
    if (seqstack_empty(p_stack))
    {
        printf("栈已空！\n");
        exit(-1); 
    }
    value = *(p_stack->p_top--);
   
    return value;
 }
 
/********************************************************
 *函数名称：seqstack_destroy
 *函数功能：销毁栈
 *入口参数：p_stack为指向结构体指针
 *返 回 值：空
 ********************************************************/
 void seqstack_destroy(malloc_seqstack *p_stack)
 {
    free(p_stack->p_bottom);
    free(p_stack);
    p_stack->stack_size = 0;
    p_stack->p_bottom = NULL;
    p_stack->p_top = NULL;
    p_stack = NULL; 
   
    return;
 }
 
/***********************程序结束************************/

程序运行结果：

动态顺序栈的C语言实现

栈越界时提示的错误信息：

动态顺序栈的C语言实现

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

  1. Linux-C成长之路（一）：Linux下C编程概要
  2. Linux-C成长之路（二）：基本数据类型
  3. Linux-C成长之路（三）：基本IO函数操作
  4. Linux-C成长之路（四）：运算符
  5. Linux-C成长之路（五）：控制流
  6. Linux-C成长之路（六）：函数要义
  7. Linux-C成长之路（七）：数组与指针
  8. Linux-C成长之路（八）：存储类，动态内存
  9. Linux-C成长之路（九）：复合数据类型
  10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：

相关内容