【数据结构】链栈的基本操作(C语言)

这篇具有很好参考价值的文章主要介绍了【数据结构】链栈的基本操作(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

零零总总搜索了一些关于链栈的资料,了解了链栈的基本操作,一直觉得别人写的代码或多或少存在一些问题,所以打算自己写一篇关于链栈的文章,也算是对所学知识的梳理和巩固了。

首先说明本文使用C语言进行链栈的基本操作,链栈是无头结点的。这里补充说明一下,无头结点的意思是,链栈的头结点是存储数据的,有头结点的是头结点不存储数据的,不了解的小伙伴可以先去学习一下单链表的内容。

之所以在这里说明,是因为我看过不少文章写的链栈是带头结点,有的还分不清到底有没有头结点,导致我在学习的时候浪费了不少时间,废话不多说,以下进入正题。

链栈的基本操作包括以下几点:

a. 栈的初始化

b. 栈的判空

c. 入栈

d. 出栈

e. 读栈顶元素

f. 遍历栈

g. 销毁栈

定义一个结构体,用来构造链栈。


typedef struct StackNode{
    int data;//数据域,用来存放数据
    StackNode *next;//指针域,用来指向栈顶的下一个元素
}LinkStack;
LinkStack *LS;//定义一个LinkStack类型的指针

一、初始化栈

链栈初始化首先要构造一个空栈,先创建一个头结点,然后让该头结点的指针指向空,这里使用传参的方式初始化栈。


void StackInit(LinkStack* &S)//这里传入的参数是一个指针
{                            //要对传入的参数进行赋值操作,需要加一个取址符
    S = NULL;//直接让S指向空,不能在这里像下面注释的代码一样分配空间,否则无法完成判空操作
    /*S = (LinkStack *)malloc(sizeof(LinkStack *));
    if(S == NULL)
    {
        printf("Malloc Error!!!\n");
        return false;
    }
    S->next = NULL;
    return true;*/
}

二、栈的判空

直接判断栈顶的地址是否为空


bool StackIsEmpty(LinkStack* S)
{
    if(S == NULL)
        return true;
    return false;
}

三、入栈

入栈需要判断是否为空,若为空栈,第一个入栈元素为栈顶,没有下一元素,指向下一个元素的指针为空。


bool Stack_Push(LinkStack* &S,int PushData)
{
    if(S == NULL)//若栈为空
    {    
        S = (LinkStack *)malloc(sizeof(LinkStack));
        if(S == NULL)
        {
            printf("Malloc Error!!!\n");
            return false;
        }
        S->data = PushData;//给头结点赋值
        S->next = NULL;//没有下一个元素,指向空
        return true;
    }
    //栈不为空
    LinkStack *NewNode = (LinkStack)malloc(sizeof(LinkStack));
    if(NewNode == NULL)
    {
        printf("Malloc Error!!!\n");
        return false;
    }
    NewNode->data = S->data;//用新节点存储当前栈顶元素,包括指针
    NewNode->next = S->next;//让NewNode成为当前栈顶
    S->next = NewNode;//S的下一个元素为NewNode,S成为新的栈顶(S仍为栈顶)
    S->data = PushData;//记录入栈元素
    return true;
}

四、出栈

出栈即为删除栈顶


bool Stack_Pop(LinkStack* &S,int &PopData)//PopData用于记录出栈元素
{
    if(S == NULL)//栈为空
    {
        printf("Stack Is Empty!!!\n");
        return false;
    }

    if(S->next == NULL)//最后一个元素
    {
        PopData = S->data;
        free(S);//释放空间
        S = NULL;//防止成为野指针
        return true;
    }
    
    PopData = S->data;//通过PopData获取出栈(栈顶)数据
    
    /*    此处为写错部分的代码
    LinkStack *TempNode = S->next;//出栈需要释放栈顶,需要定义一个临时变量
    
    S->next = TempNode->next;//栈顶元素出栈,下一个元素成为新的栈顶
    S->data = TempNode->data;
    */

    LinkStack *TempNode = S;//出栈需要释放栈顶,需要定义一个临时变量,存放旧栈顶的地址和指针域
    
    //此时TempNode为栈顶,其指向的下一个栈元素应为新的栈顶
    S = TempNode->next;//栈顶元素出栈,下一个元素成为新的栈顶
    S->data = TempNode->next->data;

    free(TempNode);//释放旧栈顶空间
    TempNode = NULL;//防止成为野指针

    return true;
}

五、读取栈顶元素

读取栈顶元素不同于出栈,只需要读取栈顶元素,不需要释放栈顶空间


bool Stack_Read(LinkStack* S,int &PopData)//PopData用于记录出栈元素
{
    if(S == NULL)//栈为空,没有元素可读,返回false
    {
        printf("Stack Is Empty!!!\n");
        return false;
    }
    PopData = S->data;
    return;
}

六、遍历栈

这里直接打印栈的所有元素,从栈顶到栈底


//遍历栈
void Stack_Traverse(LinkStack* S)
{
    if(S == NULL)//栈为空
    {
        printf("Stack Is Empty!!!\n");
        return;
    }
    if(S->next == NULL)//只有一个元素
    {
        printf("StackTop to StackBottom: %d\n",S->data);
        return;
    }
    LinkStack *p,*q;
    p = S;//p为q是上一个元素
    q = p->next;//q为p的下一个元素
    printf("StackTop to StackBottom: ");
    while(q->next != NULL)
    {
        printf("%d ",p->data);
        p = p->next;
        q = p->next;
    }
    printf("%d %d\n",p->data,q->data);
}

七、销毁栈


void Stack_Destroy(LinkStack* &S)
{
    LinkStack *p = NULL;
    while(S != NULL)
    {
        P = S;
        S = S->next;
        free(p);
    }
    p = NULL;
    S = NULL;
}

需要注意的是,在释放栈空间之后,需要将相应的指针指向空,否则将会成为野指针,并且书写也不规范。学习数据结构的过程中我查阅了许多资料,发现许多博客的代码存在这样的问题,这让有那么一点强迫症的我看的很不舒服,所以就打算自己写。

本文是我第一次写、第一次发表的文章,内容很少,也很简洁,代码完全是在网页敲出来,就看着伪代码敲,有什么不对的请给位看官批评指正,谢谢!文章来源地址https://www.toymoban.com/news/detail-450129.html

到了这里,关于【数据结构】链栈的基本操作(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习——C语言对栈的基本操作

             栈(Stack)是一种常用的数据结构,遵循先进后出(LIFO)的原则,对表尾进行操作,常用于临时存储和撤销等操作,其基本操作包括栈的创建、入栈(也叫压栈Push)、出栈(又称弹栈)、栈的遍历、栈的清空(clear)、栈的销毁(destroy)等。         栈的创建有两种方式,一种是通

    2024年02月07日
    浏览(56)
  • 【数据结构】栈和队列(栈的基本操作和基础知识)

    🌈个人主页: 秦jh__ https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》 https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 目录  前言 栈 栈的概念和结构 栈的实现 ​编辑 数组栈的实现 总的声明 初始化  插入 删除 取栈顶元素 销毁 判断是否为空

    2024年02月03日
    浏览(50)
  • 链栈的基本操作(超详细)

    目录 前言 一.链栈的定义  二、链栈的c++语言结构描述表示 三、链栈中基本操作的实现  3.1链栈的初始化 3.2判断链栈是否为空  3.3求链栈的长度  3.4 链栈的入栈 3.4 链栈的出栈 3.5求栈顶元素  3.6销毁栈 四.链栈的具体实现  五.测试结果 六、总结  本文参考王卓老师的数据结

    2023年04月25日
    浏览(39)
  • 数据结构:使用顺序栈的基本操作,实现十进制转为二进制,十六进制的转换

    使用系统环境: 1:win10,使用工具dev 2:使用系统win10 3:参考书籍数据结构(C语言版——严蔚敏 吴伟民) ( 注意:此文章默认,学习者拥有一定的数据机构栈,C语言的知识,书籍第20页,2.1算法的代码进行一个简化。)

    2024年02月05日
    浏览(64)
  • 【数据结构】顺序栈的基本操作:出栈、入栈、取栈顶元素、输出所有栈中元素、括号匹配题目

    栈是限定仅在表位进行插入或删除操作的线性表。栈的表尾称为栈顶,表头称为栈底。不含元素的栈称为空栈。 左图为栈的示意图,右图为用铁路调度表示栈。 如下是入栈至栈满再进行出栈的过程示意图。值得注意的是,栈满后,top指针指向的不是顶端元素,而是顶端的下

    2024年02月07日
    浏览(52)
  • 数据结构--图的基本操作

    使用的存储模式: 图的基本操作: • Adjacent(G,x,y):判断图G是否存在边x, y或(x, y)。 • Neighbors(G,x):列出图G中与结点x邻接的边。 • InsertVertex(G,x):在图G中插入顶点x。 • DeleteVertex(G,x):从图G中删除顶点x。 • AddEdge(G,x,y):若无向边(x, y)或有向边x, y不存在,则向图G中添加该

    2024年02月16日
    浏览(50)
  • 数据结构--串的基本操作

    第五话 数据结构之串 文章目录 一、了解什么是串 二、串的基本特征 三、串的基本操作 串的初始化 串的输出  四、串的匹配模式 五、总结 串(即字符串)是一种特殊的线性表,在信息检索、文本编辑等领域有广泛的应用。其特殊性体现在组成线性表的每个数据元素是单个

    2023年04月17日
    浏览(53)
  • 【数据结构】图的基本操作

    一、问题描述 分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: 增加一个新结点v,Insert(G,v); 删除顶点v及其相关的边,Delete(G,v); 增加一条边v,w,Insert(G,v,w); 删除一条边v,w,Delete(G,v,w); 二、设计思路 1、邻接矩阵实现:         邻接矩阵实现图的基本

    2024年02月06日
    浏览(45)
  • (数据结构)链队列的基本操作

    2024年02月08日
    浏览(41)
  • 【数据结构】串的基本操作及应用

    分别定义两个结构体——串的定长顺序存储、串的堆式顺序存储   问题: 1、编写函数,串用定长顺序存储表示来实现串的基本操作; 2、 编写串的匹配算法,实现查找功能。 算法思想阐述: BF 算法:首先S[1] 和T[1] 比较,若相等,则再比较S[2] 和T[2] ,一直到T[M] 为止;若

    2023年04月26日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包