C语言-数据结构-堆栈(链栈)

我会带着你远行 2022-05-18 09:35 237阅读 0赞

该程序使用C语言 编译环境Dev++  
功能: 实现栈的相关操作,

/\*  
本程序是解释栈堆的定义  
下面的变量是在内存的stack中写的, 如k m \*p,  
stack是静态分配内存,通过压栈出栈的方式 (先进后出,相当与一个箱子,向里面放书)  
栈的分类:  
1 静态栈  
2 动态栈  
malloc开辟的空间是在heap 堆里面写的

init m;
    double *p = (double*)malloc(200);

stack应用:  
函数调用  
中断  
表达式求值  
内存分配  
缓冲处理  
迷宫  
\*/

#include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h" //存放bool和false true头文件 
    
    typedef struct Node
    {
        int data;
        struct Node *p_next; 
    } Node, *PNode; 
    
    typedef struct Stack
    {
        PNode p_top;
        PNode p_bottom;
    } Stack, *PSta//建立一个无用的头结点,最后一个p_bottom 无效

/\* 函数声明区 \*/

int InitStack(PStack);//初始化栈stack 
    int PushStack(PStack, int);  //向栈中压入int 
    int StackTraverse(PStack); //打印
    bool StackPop(PStack, int*val); //出栈到val 
    bool StackEmpty(PStack);//判断栈是否为空,为空返回1 
    void StackClear(PStack);  //清空 stack 
    
    int main()
    {
        Stack S;  //内存中有个空间有两个元素,内存一个P_top和p_bottom 
        int val; 
        InitStack(&S);
        printf("是否为空栈? 为空返回1: %d\n",StackEmpty(&S)); 
    // StackTraverse(&S);
        PushStack(&S,22);
        PushStack(&S,33);   
        PushStack(&S,66);
        PushStack(&S,34);   
        PushStack(&S,53);
        PushStack(&S,76);   
        PushStack(&S,87);
        PushStack(&S,98);
        StackTraverse(&S);
        if(StackPop(&S,&val))
        {
            printf("Pop Success: %d\n",val);
        }else printf("Pop ERROR\n");
    
        StackClear(&S); 
        StackClear(&S);
        StackTraverse(&S);
    
        printf("Hello World!!\n");
        return 0; 
    } 
    
    /* 初始化栈 */
    int InitStack(PStack p_stack)
    {
        p_stack->p_top = (PNode)malloc(sizeof(Node));
        if(NULL == p_stack->p_top)
        {
            printf("内存分配失败!!\n"); return -1;
        } 
    
        p_stack->p_bottom = p_stack->p_top;
        p_stack->p_top->p_next = NULL; 
        return 1; 
    }
    
    /* 压栈 */ 
    int PushStack(PStack p_stack, int val)  //向栈中压入int 
    {
        PNode p_new = (PNode)malloc(sizeof(Node));  //新建节点 
        if(NULL == p_new)
        {
            printf("内存分配失败!!\n"); return -1;
        }   
        p_new->data = val;
    
        p_new->p_next = p_stack->p_top;
        p_stack->p_top = p_new;
        return 1; 
    } 
    
    /* 遍历打印 */ 
    int StackTraverse(PStack p_stack)
    {
        PNode p = p_stack->p_top;
        if(p == p_stack->p_bottom)
        {
            printf("空栈!!\n");return false; 
        }
        while( p != p_stack->p_bottom)
        {
            printf("%d ",p->data);
            p = p->p_next;      
        }
        printf("\n");
        return 1; 
    } 
    
    bool StackPop(PStack p_stack, int* val) //出栈到val 
    {
        if(StackEmpty(p_stack)) //if(1 == StackEmpty(p_stack)) 
        {
            printf("空栈!!\n");return false; 
        }
    
        *val = p_stack->p_top->data;
    
        PNode Temporary = p_stack->p_top;
        p_stack->p_top = p_stack->p_top->p_next;
    // Temporary = NULL;
        free(Temporary); 
    
        return true;    
    } 
    
    /* 判断栈是否为空 */ 
    bool StackEmpty(PStack p_stack)
    {
        return ( p_stack->p_top == p_stack->p_bottom ) ? true : false;
    } 
    
    
    /* 清空栈 */ 
    void StackClear(PStack p_stack)
    {
        if(StackEmpty(p_stack)) return;
    
        PNode p = p_stack->p_top;
        PNode q = NULL;
        while(p != p_stack->p_bottom )
        {
            printf("%d ",p->data);
            q = p->p_next;
            free(p);
            p = q;      
        }
        p_stack->p_top = p_stack->p_bottom;
        return; 
    }