当前位置:   article > 正文

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

c语言堆栈的链式储存

栈-链式存储-链栈


代码实现

#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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/426652
推荐阅读
相关标签
  

闽ICP备14008679号