链栈

链栈顾名思义,采用链表实现,其优点是不存在栈满上溢出的情况,其操作都是在头结点之后进行的,入栈类似与头插法建立链表。

非空链式栈的一般形式缺点:进出栈时间开销大,进栈需要找到最后一个结点,出栈时删除最后一个结点。

stack.png

解决办法:将指针次序颠倒过来,top指向an
stack.png

1.进栈时将新结点作为首结点;
2.出栈时删除首结点。
优点:进出栈时间开销为常数。

数据结构

#include <stdlib.h>
typedef int ElemType;
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackNode, *ListStack;

初始化

//初始化建立空栈
void stack_init(ListStack *stack) {
    *stack = (StackNode *)malloc(sizeof(StackNode));
    (*stack)->next = NULL;
}

结点

//创建结点
ListStack NewStackNonde(ElemType data) {
    ListStack new = (StackNode *)malloc(sizeof(StackNode));
    new->data = data;
    new->next = NULL;
    return new;
}

判空

//判空
int stack_empty(ListStack stack) {
    if (stack->next == NULL) {
//        printf("空栈...\n");
        return 0;
    }
    else {
        printf("非空栈...\n");
        return -1;
    }
}

进栈

//入栈
void stack_push(ListStack *stack, ElemType data) {
    ListStack new = NewStackNonde(data);
    new->next = (*stack)->next;
    (*stack)->next = new;
}

出栈

//出栈
int stack_pop(ListStack *stack) {
    if ((*stack)->next == NULL) {
//        printf("空栈...\n");
        return -1;
    }
    else {
        int tmp;
        ListStack s = (*stack)->next;
        tmp = s->data;
        (*stack)->next = s->next;
        free(s);//释放空间
        return tmp;
    }
}

获取栈顶元素

//获取栈顶元素
int stack_get(ListStack *stack) {
    ListStack s = (*stack)->next;
    if (s == NULL) {
        printf("空栈...\n");
        return -1;
    }
    int data = s->data;
    return data;
}

销毁栈

//销毁栈
void stack_destroy(ListStack *stack) {
    ListStack p = *stack;
    while (p != NULL) {
        *stack = (*stack)->next;
        free(p);
        p = *stack;
    }
}

进制转换

//进制转换 N传入需要转换进制的数, d需要转换的进制,2,8,16
void conversion(ListStack *stack, unsigned int N, const unsigned int d) {
    if (*stack == NULL) {//当传入参数为指针
        exit(-1);
    }
    int tmp;//保存mod=N%d;
    printf("...将10进制的%d转化为%d进制后...", N, d);
    while (N) {
        tmp = N % d;
        stack_push(stack, tmp);
        N = N / d;
    }
    int data;
    while ((data=stack_pop(stack)) >= 0) {
        printf("%d", data);
    }
    printf("\n");
}

测试

//测试
void test_stack_link() {
    StackNode node;
    ListStack top = &node;
    stack_init(&top);
//    stack_empty(top);
//    stack_push(&top, 23);
//    stack_push(&top, 34);
//    stack_push(&top, 45);
//    stack_push(&top, 60);
//    printf("%d\n", stack_get(&top));
//    stack_pop(&top);
//    printf("%d\n", stack_get(&top));
//    stack_destroy(&top);
    conversion(&top, 16, 16);
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 该系列文章主要作数据结构(C语言版)学习的笔记。里面代码的注释很详细,同时提供给大家参考,欢迎指正和指教。 栈的链...
    NotFunGuy阅读 4,072评论 0 7
  • 链栈,即用链表实现栈存储结构。链栈的实现思路同顺序栈类似,顺序栈是将数顺序表(数组)的一端作为栈底,另一端为栈顶;...
    北徯阅读 494评论 0 1
  • 链栈的好处就是,不用考虑栈满的情况了 链栈需要用头插法的方式,来入栈,因为如果使用尾插法的话,进栈好进,但是出栈的...
    放心笑阅读 1,553评论 1 4
  • C#数据结构:链栈 1、自定义链栈结构: 链栈节点类 链栈类 链栈测试用例: 输出结果: 注意: 1、链栈即采用链...
    lijianfex阅读 503评论 0 0
  • vocabulary preview elves : the plural of the word elf, li...
    Lancer_fanfan阅读 567评论 1 0