桟的链式存储结构

╰半夏微凉° 2022-06-16 01:50 181阅读 0赞

#include<stdio.h> 
    #include<stdlib.h>
    #include<malloc.h>
    #define OK 1 
    #define ERROR 0 
    #define OVERFLOW -2 
    #define STACK_INIT_SIZE 100 //栈初始化分配量 
    #define STACKINCREMENT 10 //存储空间的分配增量 
    
    typedef int SElemType ; 
    typedef int Status ; 
    
    typedef struct SNode
    {   
        SElemType data ;    
        struct SNode *next; 
    }SNode ; 
    
    typedef struct
    {   
        SNode *top ; //指向栈顶 
    }Stack; 
    
    //------基本操作---------- 
    Status InitStack(Stack &s); //初始化栈 
    Status DestoryStack(Stack &s);//销毁栈 
    Status ClearStack(Stack &s);//清空栈 
    Status StackEmpty(Stack s); //判断栈是否为空 
    int StackLength(Stack s);//栈的长度 
    Status GetTop(Stack s, SElemType &e);//获取栈顶元素 
    Status Push(Stack &s, SElemType e); //入栈 
    Status Pop(Stack &s , SElemType &e);//出栈 
    Status StackTraverse(Stack s, Status(*visit)());
     void Display(Stack s); 
    
    /*初始化栈*/ 
    Status InitStack(Stack &s)
    {   
        s.top=(SNode*)malloc(sizeof(SNode));    
        if(!s.top) 
            return ERROR ;  
        s.top->next=NULL;   
        return OK; 
    } 
    
    /*清空栈,和清空链表一样的做法*/ 
    Status ClearStack(Stack &s)
    {   
        SNode *pNode, *temp;    
        pNode=s.top->next;  
        while(pNode!=NULL)
        {       
        temp=pNode;         
        pNode =pNode->next;         
        free(temp);     
        }   
        return OK; 
    } 
    
    Status DestoryStack(Stack &s)
    {   
        ClearStack(s);//先清空栈,释放内存   
        free(s.top);//将栈顶释放     
        return OK; 
    } 
    
    Status StackEmpty(Stack s)
    {   
        if(s.top->next==NULL)       
            return OK ;     
        else        
            return ERROR; 
    } 
    
    int StackLength(Stack s)
    {   
        int length=0;   
        SNode *pNode;   
        pNode = s.top->next;    
        while(pNode)
        {       
            length++;       
            pNode =pNode->next;     
        }   
        return length ; 
    } 
    
    Status GetTop(Stack s, SElemType &e)
    {   
        if(s.top->next!=NULL)
        {       
            e= s.top->next->data;       
            return OK;  
        }   
        return NULL; 
    } 
    
    Status Push(Stack &s, SElemType e)
    {   
        SNode *p; 
        p=(SNode *)malloc(sizeof(SNode));   
        if(!p)
            return ERROR;   
        p->data=e;  //插入    
        p->next=s.top->next;    
        s.top->next=p;  
        return OK ; 
    } 
    
    Status Pop(Stack &s , SElemType &e)
    {   
        if(s.top->next==NULL)       
        return ERROR;   
        SNode *p;   
        p=s.top->next;  
        e = p->data;    
        s.top->next=p->next;    
        free(p);    
        return OK; 
    } 
    
    Status StackTraverse(Stack s, Status(*visit)(SElemType data))
    {   
        SNode *p ;  
        p=s.top->next;  
        while(p)
        {       
            visit(p->data);         
            p=p->next;  
        }   
        return OK; 
    } 
    
    Status visit(SElemType data)
    {   
        printf("%d",data);  
            return OK;
    } 
    
    void Display(Stack s)
    {   
        SNode *p ;  
        p=s.top->next;  
        while(p)
        {       
            printf("%d\t",p->data);         
            p=p->next;  
        }   
        printf("\n"); 
    }
    
    //main函数 
    int main()
    { 
        Stack s ;   
        /*初始化*/     
        printf("init stack begin....\n");   
        if(InitStack(s))        
        printf("初始化成功\n");  
        printf("初始栈为空 = %d \n" , StackEmpty(s));    
        printf("初始化时栈的长度= %d\n",StackLength(s));    
        printf("init stack end. \n"); 
        /*入栈*/  
        printf("push element into stack begin.... :\n ");   
        for(int i=0;i<5;i++)
        {       
            Push(s,i); 
        }   
        printf("入栈后不为空 = %d \n" , StackEmpty(s));   
        printf("入栈的后长度=%d\n",StackLength(s)); 
        Display(s);     
        printf("push elements into stack end.\n"); 
        /*出栈*/  
        int e ;     
        Pop(s,e);   
        printf("出栈的元素为= %d\n", e);  
        printf("after Pop......\n");    
        printf("出栈的后长度= %d\n",StackLength(s));  
        Display(s);     
        /*获取栈顶元素*/  
        int f ;     
        GetTop(s,f);    
        printf("栈顶元素为= %d\n", f);   
        Display(s);     
        /*清空栈*/     
        ClearStack(s);  
        printf("栈已清空\n"); 
    }