数据结构 栈(C语言实现)

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


绪论

        时间就是生命,时间就是速度,时间就是气力。——郭沫若;本章继续学习数据结构,本章主要讲了什么是栈以及栈的基本功能和实现方法。

数据结构 栈(C语言实现)

 文章来源地址https://www.toymoban.com/news/detail-492676.html

 话不多说安全带系好,发车啦(建议电脑观看)


附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,多敲);黑色加粗或者其余颜色为次重点;黑色为描述需要


目录

1.栈的实现

1.1栈的结构​编辑

1.2栈的初始化

1.3栈的摧毁

1.4将数据插入栈中(入栈)

1.5将数据从栈中删除(出栈)

1.6查看栈顶元素

1.7查看栈中有几个元素

1.8判断栈是否是空的

2.实现栈的全部代码


知识点:

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶
可以把栈想成是一个水杯,水都是从一端进并从同一端出的(水也是后进的先出),放水进去时是压栈,把水倒出来是出栈。

数据结构 栈(C语言实现)

细节:

 

栈的所要实现的框架有:栈可以由顺序表或者链表来作为底层实现,下面主要讲以顺序表来实现的过程(因为相比于链表,顺序表在尾端插入删除数据的消耗较低)

  1. 栈的结构
    1. 一个数组变量
    2. 记录元素个数的变量
    3. 一个记录容量的变量
  2. 栈所要实现的功能
    1. 初始化栈
    2. 摧毁栈
    3. 入栈
    4. 出栈
    5. 查看栈顶元素
    6. 查看栈中的元素个数
    7. 判断栈是否为空栈

1.栈的实现

1.1栈的结构数据结构 栈(C语言实现)

 

栈的结构:由数组变量、已经两个变量组成

typedef int datetype;//类型重命名,把int 重命名为 datetype 这样方便于改变结构中的存的类型
typedef struct stack//类型重命名
{
	datetype* date;//数组
	int size;//记录元素个数
	int capacity;//容量
}stack;//重命名为stack(避免每次都要写struct的繁琐)

1.2栈的初始化

主要是为了申请空间、以及初始化size、capacity。

void StackInit(stack* ps)
{
    //初始化两个变量
    ps->capacity = 3;//容量初始为3
    ps->size = 0;//元素的个数0

    ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
    //此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
    if (ps->date == NULL)//判断是否申请成功
    {
        perror("malloc");
        return;
    }
}

其中注意点是:把size定义成0这样方便于我们在顺序表中插入数据(插入数据的位置下标就是size),并且这样我们在拿出顶部数据时就需要-1后才能取到顶部数据了(有些程序员会定义成-1这样size就表示栈顶元素的下标,+1为栈中的元素个数)

1.3栈的摧毁

因为此处用的是顺序表来实现所以其摧毁方法就和顺序表一样

void StackDestroy(stack* ps)
{
    assert(ps);//判空
    ps->capacity = ps->size= 0;//置为0
    free(ps->date);//释放所借的空间
    ps->date = NULL;//将用完的指针置为NULL
}

1.4将数据插入栈中(入栈)

在date数组中插入数据,其中已经知道了size下标处就是数组中要插入数据的位置即date[ps->size]

void StackPush(stack* ps, datetype x)
{
    assert(ps);//判空
    if (ps->size== ps->capacity)//注意要检查空间是否足够
    {
        datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
        if (tmp == NULL)//检查是否扩容成功
        {
            perror("realloc");
            return;
        }
        ps->date = tmp;//把tmp扩容好的空间,给到date
        ps->capacity *= 2;//注意别忘把capacity增加
    }
    ps->date[ps->size] = x;//在date的size下标位置处插入数据x
    ps->size++;//元素个数增加
}

1.5将数据从栈中删除(出栈)

对于出栈我们的方法和顺序表一样仅仅只是改变size元素个数

void StackPop(stack* ps)
{
    assert(ps);//为假就会报错
    assert(!StackEmpty(ps));//判断一下栈是不是空的
    ps->size--;//元素个数减一个
}

1.6查看栈顶元素

栈顶元素的下标是元素个数size-1故:

datetype StackTop(stack* ps)
{
    assert(ps);
    return ps->date[ps->size - 1];//返回栈顶元素
}

1.7查看栈中有几个元素

int StackSize(stack* ps)
{
    assert(ps);
    return ps->size;//返回size即可
}

1.8判断栈是否是空的

bool StackEmpty(stack* ps)
{
    assert(ps);
    return ps->size == 0;//等于0返回真,反之则为假
}

2.实现栈的全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

	typedef int datetype;

	typedef struct stack
	{
		datetype* date;
		int size;
		int capacity;
	}stack;



bool StackEmpty(stack* ps)
{
    assert(ps);
    return ps->size == 0;//等于0返回真,反之则为假
}



void StackInit(stack* ps)
{
    //初始化两个变量
    ps->capacity = 3;//容量初始为3
    ps->size = 0;//注意size指向的是下一个堆顶的位置

    ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
    //此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
    if (ps->date == NULL)//判断是否申请成功
    {
        perror("malloc");
        return;
    }
}

void StackDestroy(stack* ps)
{
    assert(ps);//判空
    ps->capacity = ps->size = 0;//置为0
    free(ps->date);//释放所借的空间
    ps->date = NULL;//将用完的指针置为NULL
}


void StackPush(stack* ps, datetype x)
{
    assert(ps);//判空
    if (ps->size == ps->capacity)//检查空间是否足够
    {
        datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
        if (tmp == NULL)//检查是否扩容成功
        {
            perror("realloc");
            return;
        }
        ps->date = tmp;//把tmp扩容好的空间,给到date
        ps->capacity *= 2;//注意别忘把capacity增加
    }
    ps->date[ps->size] = x;//在date的top下标位置处插入数据x
    ps->size++;//元素个数增加
}

void StackPop(stack* ps)
{
    assert(ps);//为假就会报错
    assert(!StackEmpty(ps));//判断一下栈是不是空的
    ps->size--;//元素个数减一个
}

datetype StackTop(stack* ps)
{
    assert(ps);
    return ps->date[ps->size - 1];
}

int StackSize(stack* ps)
{
    assert(ps);
    return ps->size;
}

 

如果有任何问题欢迎讨论哈!

如果觉得这篇文章对你有所帮助的话点点赞吧!

持续更新大量数据结构细致内容,早关注不迷路。

 

 

 

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

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

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

相关文章

  • 数据结构 - 绪论

    数据 Data :信息的载体。能被计算机识别并处理的符号的集合。 数据元素 Data element :数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素往往由若干 数据项 组成。数据项是组成数据元素的不可分割的最小单位。 如学生的信息记录就是一个数据元素,它由学

    2023年04月18日
    浏览(48)
  • 【数据结构】实验一:绪论

    实验一  绪论 一、实验目的与要求 1)熟悉C/C++语言(或其他编程语言)的集成开发环境; 2)通过本实验加深对算法时间复杂度的理解; 3)结合具体的问题分析算法时间复杂度。 二、实验内容 设计程序实现统计一个班的学生成绩(学生的人数可以设置3000、5000、8000、1000

    2024年02月15日
    浏览(40)
  • 第一章-数据结构绪论

    数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。 程序设计的实质是选择一个好的结构,再设计一种好的算法。 数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处

    2024年02月13日
    浏览(38)
  • 数据结构绪论(3)

    目录 一、客观题(1) 二、客观题(2)  三、客观题(3) 四、客观题(4)  五、客观题(5)  六、客观题(6) 1、以下与数据的存储结构有关的术语是(D)。 A、有序表   B、线性表   C、有向图   D、顺序表 2、从存储结构上可以把数据结构分成(A)。 A、顺序结构和链式

    2024年02月07日
    浏览(42)
  • 数据结构——第1章 绪论

    目录 1.1 数据结构的研究内容 1.2 基本概念和术语 1.2.1 数据、··元素、··项和··对象 1.2.2 数据结构 1.2.3 数据类型和抽象数据类型 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法的定义与特性 1.4.2 算法的时间复杂度 1.4.3 算法的空间复杂度 1.5 小结 数据: 是客观事

    2024年02月19日
    浏览(39)
  • [数据结构]喵桑,学费了——绪论

    本喵是FW视频封面最终版 宝子,你不点个赞吗?不评个论吗?不收个藏吗? 最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!! 喵喵喵,你对我真的很重要。 目录 前言 绪论 1.1数据结构的研究的内容 1.2数据结构的基本概念和术语 1.2.1 数据,数据元素

    2024年02月06日
    浏览(41)
  • 24考研数据结构-——绪论2

    1.4.1 渐近时间复杂度 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(n),它表示随问题规模n的增大而增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的 渐近时间复杂度 ,简称时间复杂度。 大O表示“同阶”,

    2024年02月16日
    浏览(42)
  • 数据结构与算法【01】—绪论

    专栏地址:数据结构与算法专栏 开源仓库:bigsai-algorithm仓库 ,欢迎支持 针对以前写的数据结构与算法系列重写(针对文字描述、图片、错误修复),改动会比较大,一直到更新完为止 数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有

    2024年02月06日
    浏览(50)
  • 【全面突击数据结构与算法001】绪论篇,数据结构的基本概念

    👑 作 者 主 页 :👉CSDN丨博客园 🏆 学 习 交 流 :👉在下周周ovoの社区 💎全 面 突 击 数 据 结 构 与 算 法 系 列 专 栏: 👉 数据结构与算法专栏 PS:本篇文章主要综合了【王道数据结构与算法】与我的个人笔记与理解,如果文章有任何错误欢迎各位大佬的指出 快期末考

    2024年02月07日
    浏览(47)
  • 数据结构笔记(王道考研) 第一章:绪论

    大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记,该课属于付费课程(不过盗版网盘资源也不难找。。。)。后续又根据23年考研的大纲对内容做了一些调整,将二叉排序树和平衡二叉树的内容挪到了查找一章,并增加了并查集、平衡二叉树的删除、红黑树的内

    2024年02月14日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包