顺序栈和链栈的实现

以你之姓@ 2023-02-13 14:59 49阅读 0赞

#include "stdio.h"
    #include "stdlib.h"
    #define maxSize 100
    typedef struct{
        
        int data[maxSize];
        int top;
    }SqStack;
    typedef struct{
        
        int data;
        struct Lnode *next;
    }LNode;
    int main(){
        
        //顺序栈基本函数
        void initStack(SqStack* st);
        int isEmpty(SqStack* st);
        int push(SqStack* st,int x);
        SqStack* pop(SqStack* st,int *x);
        void Output(SqStack* st,int* x);
    
        //链栈基本函数
        void initLStack(LNode*lst);
        int isLEmpty(LNode* lst);
        void LPush(LNode* lst,int x);
        void LOutput(LNode* lst,int *x);
    
        LNode* lst;
        int* y;
        initLStack(lst);
        if(isLEmpty(lst) == 1)
            printf("栈为空\n");
        else printf("栈不为空\n");
        for(int i = 0;i < 5;i++){
        
            LPush(lst,i);
        }
        if(isLEmpty(lst) == 1)
            printf("栈为空\n");
        else printf("栈不为空\n");
        LOutput(lst,y);
    
        //顺序栈测试
    //    SqStack* st;
    //    int* x;
    //    initStack(st);
    //    if(isEmpty(st) == 1)
    //        printf("栈为空\n");
    //    else printf("栈不为空\n");
    //
    //    for(int i = 0;i < 10;i++)
    //        push(st,i);
    //
    //    if(isEmpty(st) == 1)
    //        printf("栈为空\n");
    //    else printf("栈不为空\n");
    //    Output(st,x);
    
        return 0;
    }
    
    //链栈
    //链栈的初始化
    void initLStack(LNode*lst){
        
        lst = (LNode*)malloc(sizeof(LNode));
        lst->next = NULL;
    }
    //判断栈空的代码
    int isLEmpty(LNode* lst){
        
        if(lst->next == NULL){
        
            return 1;
        } else{
        
            return 0;
        }
    }
    //进栈代码
    void LPush(LNode* lst,int x){
        
        LNode* p;
        p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
    
        //头插法
        p->data = x;
        p->next = lst->next;
        lst->next = p;
    }
    //出栈代码
    int* LPop(LNode* lst,int *x){
        
        LNode* p;
        if (lst->next == NULL){
        
            return NULL;
        }
    
        //单链表的删除操作
        p = lst->next;
        x = p->data;
        lst->next = p->next;
        free(p);
        return x;
    }
    void LOutput(LNode* lst,int *x){
        
        printf("输出栈内元素：\n");
        while (1){
        
            printf("%d ",LPop(lst,x));
            if (lst->next == NULL){
        
                break;
            }
        }
        printf("\n");
    }
    
    //顺序栈
    //初始化栈
    void initStack(SqStack* st){
        
        st->top = -1;
    }
    //判断栈空代码
    int isEmpty(SqStack* st){
        
        if(st->top == -1){
        
            return 1;
        }
        return 0;
    }
    //进栈代码
    int push(SqStack* st,int x){
        
        if(st->top == maxSize - 1){
        
            return 0;
        }
        ++(st->top);
        st->data[st->top] = x;
        return 1;
    }
    //出栈代码
    SqStack* pop(SqStack* st,int *x){
        
        if(st->top == -1){
        
            return NULL;
        }
        x = st->data[st->top];
        --(st->top);
        return x;
    }
    //打印栈内元素
    void Output(SqStack* st,int* x){
        
        printf("输出栈内元素：\n");
        for(int i = 0;i < maxSize;i++){
        
            printf("%d ",pop(st,x));
            if (st->top == -1){
        
                break;
            }
        }
        printf("\n");
    }