栈-链式栈-C语言实现

心已赠人 2022-04-02 06:19 327阅读 0赞

#include<stdio.h> //栈完成
    #include<malloc.h>
    #include<stdlib.h>
    #include<stdbool.h>
    typedef struct node{ //定义节点
        int data;
        struct node *pnext;
    }NODE,*PNODE;
    typedef struct Stack{
        PNODE pTop;     //指向栈顶元素
        PNODE pBottom; //指向栈低元素的下一个没有实际意义的元素，类似头结点
    }STACK,*PSTACK;//PSTACK 等价于struct STACK *
    void init(PSTACK);
    void push(PSTACK,int);
    void traverse(PSTACK);
    bool pop(PSTACK,int *);
    void clear(PSTACK);
    int main(){
        STACK S; //内存中已经有了一个栈但是没有初值所以是垃圾值
        int val;
        init(&S);//创造一个空栈
        push(&S,1);
        push(&S,2);
        traverse(&S);
        clear(&S);
        printf("after clear\n");
        pop(&S,&val);
        pop(&S,&val);
        if(pop(&S,&val))
        {
        //pop(&S,&val);//val保存出栈的元素
        printf("出栈成功succes，出栈元素是%d\n",val);
        }else{
            printf("出栈失败failer\n");
    
        }
    }
    void init(PSTACK pS){
        //造出头结点让top和bottom都指向这个头结点，空栈便是构造成功
        //这个头结点中是个垃圾值
        pS->pTop = (PNODE)malloc(sizeof(PNODE));
        if(NULL == pS->pTop)
        {
            printf("动态内存分配失败\n");
            exit(-1);
        }
        else
        {
            //top 已经指向了一个节点，空栈top和bottom指向同一个节点
            pS->pBottom = pS->pTop;
            //把节点的指针域置空
            pS->pTop->pnext =NULL; //pS->Bottom->pnext =NULL;
            
        }
    }
    void push(PSTACK pS,int val){
        //创造一个新的节点
        PNODE pNew =(PNODE)malloc(sizeof(NODE));
        pNew->data =val;
        pNew->pnext =pS->pTop;//新节点指向栈顶节点
        pS->pTop = pNew;    //top指针指向栈顶节点
        return;
    }
    //遍历，制造一个节点指向栈顶元素，输出栈顶元素，节点后移
    void traverse(PSTACK pS){
        PNODE p =pS->pTop;
        while(p!=pS->pBottom)
        {
            printf("%d\n",p->data);
            p= p->pnext;
        }
        printf("\n");
        return;
    }
    //判断栈空
    bool empty(PSTACK pS){
        if(pS->pTop == pS->pBottom)
        {
        return true;
        }
        else
        {
        return false;
        }
    }
    //出栈，把出栈元素存入pVal形参所指向的变量中如果出栈失败，返回false
    bool pop(PSTACK pS,int *pVal){
        //pS本身存放的就是S的地址
        if(empty(pS))
        {
            return false;
        }
        else
        {//定义一个节点指向栈顶元素
            PNODE r =pS->pTop;
            *pVal = r->data; //将元素的值赋给形参
            pS->pTop=r->pnext;//将栈顶指针指向下一个元素
            free(r);//释放栈顶节点
            r=NULL;
            return true;
        }
    }
    //清空
    void clear(PSTACK pS){
        if(empty(pS))
        {
            return;
        }
        else
        {
        PNODE p =pS->pTop;
        PNODE q= NULL;
        //PNODE q = p->pnext;//q指向p的下一个元素
        while(p != pS->pBottom)
        {
            q = p->pnext;
            free(p);
            p=q;
        }
        pS->pTop = pS->pBottom;
        free(p);
        pS->pTop = p->pnext;
        }
    }