【精选】数据结构

2023-10-22 09:35| 来源: 网络整理| 查看: 265

文章目录 🎄链式栈 🎄链式栈的基础操作实现 ⭐1.链式栈的初始化 ⭐2.链式栈入栈操作 ⭐3.链式栈出栈操作 ⭐4.判断链式栈是否空 ⭐5.遍历打印链式栈中元素 ⭐6.计算链式栈元素个数 ⭐7.动态内存释放 🎄栈

本文中涉及的完整代码及各操作测试代码均已提交至Gitee，大家可以点击链接参考。因本人为编程初学者，文中及代码中难免出错，请同志们批评指正！在这里插入图片描述

🎄链式栈

上文我们讲述了顺序栈的实现，既然有顺序存储的栈，那么肯定就有链式存储的栈，本文将简要介绍链式栈的实现。其实，和单链表的实现几乎一模一样，所不同的只是链表中插入、删除被限定在链表的一端。那么把栈顶放在链表的头部还是尾部呢?由于单链表有头指针，而栈则需要栈顶指针，所以可以直接把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

所以本文中的链表是没有头结点的。这一点在编程的时候需要注意与带头结点的链表是不同的。

带头结点的单链表初始化时开辟一个动态内存的结点作为头结点，这个头结点在初始化时数据域是不需要存储数据的，指针域要置NULL。最后返回开辟的头结点的指针。

不带头结点的单链表初始化时无需开辟动态空间，只需要返回NULL即可。但也正因为如此，在main函数中如果要调用其他函数，那函数中链表指针需要考虑传址调用。这一点我在代码中使用了二级指针来实现，具体可以看看下面的代码。

🎄链式栈的基础操作实现

这里，最主要的是实现入栈、出栈的操作，具体地我们来实现下面几个功能：

链式栈的初始化；linkStack stack_init(); 链式栈入栈操作；int stack_push(linkStack *s, data_t val); 链式栈出栈操作；data_t stack_pop(linkStack *s); 判断链式栈是否空；int stack_empty(linkStack *s); 遍历打印链式栈中元素；void stack_show(linkStack *s); 计算链式栈元素个数；int stack_len(linkStack *s); 动态内存释放；int stack_free(linkStack *s);

⭐1.链式栈的初始化

初始化之前，我们考虑一下链栈的结点模型，其实和单链表完全一样。需要一个数据域和指针域。

typedef struct stackNode { data_t data; struct stackNode* next; }stackNode, * linkStack;

因为我们准备采用不带头结点的链表，所以初始化时也不需要创建头结点，直接返回个空指针就行了：

//1. 链式栈的初始化； linkStack stack_init() { linkStack s = NULL; return s; } 在主函数中是这样定义一个链表的： linkStack pstack = stack_init();

也正是因为在初始化时没有开辟空间，而只返回了空指针，所以main函数中的代表栈的地址的指针变量pstack也是空指针，如果在其他函数调用传参时直接传入pstack，那么就是传值传参，那样的话即使在某个函数内部为pstack开辟了空间，函数结束后，pstack在主函数中还是变回了NULL。所以需要注意在其他功能函数调用参数时应使用传址传参，即传入&pstack。这一点请看下面的代码中是怎么写的。

⭐2.链式栈入栈操作

因为栈只允许一端插入，所以这里我们固定在链表头插入新数据。那么在函数内部应该考虑这样的步骤：

判断链表是不是空的，如

【本文地址】

公司简介

联系我们