【C语言数据结构】栈-链式存储(链栈)

Myth丶恋晨 2024-02-27 06:00 81阅读 0赞

--------------------

#### 栈-链式存储-链栈 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    #define ElemType char
    
    //定义链栈结构体，并规定栈顶就是链头，一切操作只能在链头进行
    typedef struct LNode {
        
        //定义数据，这里一个结构体存储一个数据，所以不需要什么指针啊数组之类的乱七八糟的，就一个变量就够了
        ElemType data;
        //定义下一个结点
        struct LNode *next;
    } LNode, *LinkStack;
    
    //初始化栈
    void InitStack(LinkStack *stack) {
        
        //一开始栈里啥也没有，不需要设置头结点
        *stack = NULL;
    }
    
    //判断栈空
    bool StackEmpty(LinkStack stack) {
        
        if (stack == NULL)
            return true;
        return false;
    }
    
    //入栈操作
    bool Push(LinkStack *stack, ElemType e) {
        
        //因为是链表，所以不用判断是否溢出，基本不可能溢出，直接插入头结点
        //建立一个新的结构体结点
        LinkStack new = (LinkStack) malloc(sizeof(LNode));
        if (new == NULL)
            //虽然不会溢出，但是内存可能分配失败，还是要顾及一下代码的健壮性的
            return false;
        //把数据元素放到结构体里面
        new->data = e;
        //让新结构体的下一个指针指向链头
        new->next = *stack;
        //把链头移动到新结构体
        *stack = new;
    
        return true;
    }
    
    //出栈操作
    bool Pop(LinkStack *stack, ElemType *e) {
        
        //先判断一下栈是否为空
        if (StackEmpty(*stack))
            return false;
        //先将数据元素赋值给E
        *e = (*stack)->data;
        //保存一下链头结构体，不然一会儿不好释放内存
        LinkStack old = *stack;
        //转移链头到下一个结点位置
        *stack = (*stack)->next;
        //释放原来的链头内存空间
        free(old);
    
        return true;
    }
    
    //获取栈顶元素
    bool GetTop(LinkStack stack, ElemType *e) {
        
        //先判断栈是否为空
        if (StackEmpty(stack))
            return false;
    
        //获取栈顶元素
        *e = stack->data;
    
        return true;
    }
    
    //销毁栈
    void DestroyStack(LinkStack *stack) {
        
        //不能只销毁链头，要把整个链表全部释放
        while (*stack != NULL) {
        
            LNode *new = *stack;
            *stack = (*stack)->next;
            free(new);
        }
    }
    
    //-------------------顺便写一道王道课后题代码---------------------
    /*P67栈04题;设单链表表头指针为L，结点由data和next两个域构成，其中data域为字符型。
    试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称*/
    
    bool match(LinkStack stack, int n) {
         //n是题目中给出的字符的总数
        int i;
        //建立一个字符数组，存储前半个链表中的数据元素，用来对比后半个链表中的元素是否相等
        char data[n / 2];
    
        //for循环将前半个链表存储到data字符数组中
        for (i = 0; i < n / 2; i++) {
        
            data[i] = stack->data;
            stack = stack->next;
        }
    
        i--;
    
        //要区分字符总数是奇数个还是偶数个
        //如果是偶数个字符
        if(n%2 == 0){
        
            for(;i>0;i--){
        
                if(data[i] != stack->data)
                    return false;
                stack = stack->next;
            }
    
            return true;
        }
        //如果是奇数个字符
        else{
        
            for(;i>0;i--){
        
                if(data[i] != stack->data)
                    return false;
                stack = stack->next;
            }
        }
    }
    
    //为了方便后面的实验，写一个计算栈长的函数
    int Length(LinkStack stack){
        
        int num = 0;
        while(stack != NULL){
        
            num++;
            stack = stack->next;
        }
        return num;
    }
    int main() {
        
        //定义链表
        LinkStack stack;
        ElemType Elem;
        //初始化链表
        InitStack(&stack);
    //
    //    //插入元素
    //    Push(&stack, 1);
    //    Push(&stack, 2);
    //    Push(&stack, 3);
    //
    //    //获取栈顶元素
    //    GetTop(stack, &Elem);
    //    printf("当前栈顶元素为%d\n", Elem);
    //
    //    //依次出栈元素
    //    printf("出栈元素为:");
    //    Pop(&stack, &Elem);
    //    printf("%d ", Elem);
    //    Pop(&stack, &Elem);
    //    printf("%d ", Elem);
    //    Pop(&stack, &Elem);
    //    printf("%d\n", Elem);
    
    
        //将ElemType改为char后，测试题目代码
        Push(&stack, 'a');
        Push(&stack, 'b');
        Push(&stack, 'a');
    
        if(match(stack,Length(stack)))
            printf("该链表为中心对称\n");
        else
            printf("该链表不是中心对称\n");
    
        Push(&stack, 'a');
        Push(&stack, 'b');
        Push(&stack, 'a');
    
        if(match(stack,Length(stack)))
            printf("该链表为中心对称\n");
        else
            printf("该链表不是中心对称\n");
    
        Push(&stack, 'a');
    
        if(match(stack,Length(stack)))
            printf("该链表为中心对称\n");
        else
            printf("该链表不是中心对称\n");
    
        //销毁链栈
        DestroyStack(&stack);
    
        return 0;
    }