实现一个通用栈（类型是void *）

• 

  文件:	BST_operation.zip
  大小:	3KB
  下载:	下载

  stack_lib.h

/*
* 我也遵循GPL协议
* Copyright (C) 2008 Bob Zhang
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/* ===================================================================================
* 用链式存储结构实现一个栈
* 我们的策略是用栈或者链表的时候， 都是先构造一个节点，
* 然后把节点插入链表或者入栈或者出栈
* 其实就用往header的后面不断的插入数据

* 其实，栈就是单链表的特例，为什么教科书搞的那么复杂呢？
* ==================================================================================*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct node_t {
    void *data_p; //可以兼容所有的数据类型

    struct node_t *next;
}node_t;


//当top = header的时候，说明是空栈

typedef struct stack_t {
    node_t *top;    //栈顶    其实就是相当于链表的header

//    int size;    //元素个数


}stack_t;


//初始化一个节点


#define INIT_NODE(node,ptr) do { node->data_p = ptr; node->next = NULL; } while(0)

//声明一个节点

#define DECLARE_NODE(name,ptr) \
    node_t *name = (node_t *)malloc(sizeof(node_t));\
    INIT_NODE(name,ptr);

//初始化一个栈

#define INIT_STACK_TOP(stack)    \
    stack->top = (node_t *)malloc(sizeof(node_t));        \
    stack->top->next = NULL;
    
    
//声明一个栈

#define DECLARE_STACK(STACK_NAME) \
    stack_t *STACK_NAME = (stack_t *)malloc(sizeof(stack_t)); \
    INIT_STACK_TOP(STACK_NAME); \


/* 函数声明 */
extern int push(stack_t * stack,node_t *node);        //入栈

extern int pop(stack_t *stack,node_t **pop_node);    //出栈,返回值来判断是否成功，pop_node表示弹出的节点

extern int empty_stack(stack_t *stack);                //是否空栈

extern int free_stack(stack_t *stack);


 

• stack_lib.c


//我的这个栈是个通用栈

//因为node->data_p 是个void类型指针，你可以随意存放你想入栈的数据类型

//用法如下：for example

//        

//    DECLARE_NODE(stack_node,pointer); //pointer是要入栈的数据，但是我必须把赋值给一个节点的data_p

//    push(RCHILD_STACK,stack_node);

//            


#include "stack_lib.h"
/* 函数实现 */

//对于push来说比链表更简单， 直接更新top后面的第一个节点就好了

int push(stack_t * stack,node_t *node)    
{
    node->next = stack->top->next;
    stack->top->next = node;
    
    return 0;
    
}

//这里必须传二重指针，试想如果传 node_t *node_p肯定不行

int pop(stack_t *stack, node_t **node_p)
{
    node_t *top = stack->top;
    
    if(!top->next)
    {
        printf("this is empty stack \n");
        return -1;
    }
    
    *node_p = top->next;
    //只需删掉top后面节点即可，并返回给node_p

    top->next = top->next->next;
    
    //这时候已经是孤立的节点了

    (*node_p)->next = NULL;    //这里很关键， 一定要在这里，不能在上面一行，因为这是旧的头结点

    
    return 0;
}

int free_stack(stack_t *stack)
{
    free(stack->top);
    free(stack);
    
    return 0;
}