数据结构严薇敏——栈的链式存储（C语言）

梦里梦外; 2022-05-18 00:35 222阅读 0赞

**栈的链式存储和线性表的链式存储很类似，区别只是线性表的操作比较自由，而栈只能限定在表尾进行插入和删除。可以借助线性表的头插法来理解栈。**

**它的数据定义结构为：**

typedef struct LinkNode
    {
        ElemType data;
        struct LinkNode *next;
    }LinkNode;
    typedef struct LinkStack         //头结点
    {
        LinkNode head;
        int size;
    }LinkStack;

**头文件\#include"LinkStack.h"**

#ifndef LINKSTACK_H_INCLUDED
    #define LINKSTACK_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define TURE 1
    #define FALSE 0
    
    typedef int ElemType;
    typedef struct LinkNode
    {
        ElemType data;
        struct LinkNode *next;
    }LinkNode;
    typedef struct LinkStack
    {
        LinkNode head;
        int size;
    }LinkStack;
    //初始化一个空栈
    LinkStack * Init_Stack()
    {
        LinkStack *S = (LinkStack *)malloc(sizeof(LinkStack));
        S->head.next = NULL;
        S->size = 0;
        return S;
    }
    //销毁栈
    void Destory_Stack(LinkStack *S)
    {
    
        if(IsEmpty_Stack(S))
        {
            printf("栈为空！");
            free(S);
        }
        else
        {
           LinkNode *current = S->head.next;
           LinkNode *Next;
           while (!IsEmpty_Stack(S))
           {
               Next = current ->next;
               free(current);
               current = Next;
    
           }
        }
        S->size = 0;
        free(S);
        printf("\n销毁栈成功！\n");
    
    }
    //请空栈
    void Clear_Stack(LinkStack *S)
    {
        if(IsEmpty_Stack(S))
        {
            printf("栈为空,不需要清空！");
            return;
        }
        else
        {
           LinkNode *current = S->head.next;
           LinkNode *Next;
           while (!IsEmpty_Stack(S))
           {
               Next = current ->next;
               free(current);
               current = Next;
               S->size--;
           }
        }
        S->size = 0;
        S->head.next = NULL;
    
        printf("\n请空栈成功！\n");
    }
    //判断栈是否为空
    int IsEmpty_Stack(LinkStack *S)
    {
        if(S->size == 0)
            return TURE;
        else
            return FALSE;
    }
    //返回栈的长度
    int Length_Stack(LinkStack *S)
    {
        if(IsEmpty_Stack(S))
            return -1;
        return S->size;
    }
    //获得栈顶元素
    ElemType GetTop_Stack(LinkStack *S)
    {
        if(IsEmpty_Stack(S))
        {
            printf("\n栈为空！\n");
            return -1;
        }
        return S->head.next->data;
    }
    //插入栈元素
    void Push_Stack(LinkStack *S,ElemType e)
    {
        LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
        current->data = e;
        current ->next = S->head.next;
        S->head.next = current;
        S->size++;
    }
    //删除栈顶元素
    void Pop_Stack(LinkStack *S)
    {
        if(IsEmpty_Stack(S))
        {
            printf("\n栈为空！\n");
            return;
        }
        LinkNode *current = S->head.next;
        S->head.next =current ->next;
        free(current);
        S->size--;
        printf("\n删除栈顶元素成功！\n");
    }
    void Traverse_Stack(LinkStack *S)
    {
        if(IsEmpty_Stack(S))
        {
            printf("\n栈为空！\n");
            return;
        }
        LinkNode *current = S->head.next;
        int i;
        for( i = S->size; i > 0; i--)
        {
            printf("%d\t",current->data);
            current = current->next;
        }
        printf("\n栈遍历成功！\n");
    }
    #endif // LINKSTACK_H_INCLUDED

**主函数main测试**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #include"LinkStack.h"
    
    void test()
    {
        LinkStack *S =Init_Stack();
        int i;
    
        for(i = 0; i < 5; i++)
        {
            Push_Stack(S,i);
        }
        Traverse_Stack(S);
        Pop_Stack(S);
        Push_Stack(S,5);
        Traverse_Stack(S);
        printf("\n栈顶元素为：%d\n",GetTop_Stack(S));
        printf("\n当前栈的长度为：%d\n",Length_Stack(S));
        Clear_Stack(S);
        printf("\n当前栈的长度为：%d\n",Length_Stack(S));
        Destory_Stack(S);
        printf("\n当前栈的长度为：%d\n",Length_Stack(S));
    }
    int main()
    {
        test();
        system("pause");
        return 0;
    }