C如何参考C++中的链表功能定义进行实现?

嵌入式ARM 2023-06-02 14:46

一、前言

链表是一种在计算机科学中常用的数据结构,它在C语言中具有重要的作用。本文将介绍链表的定义、用途以及如何在C语言中实现链表,包括如何参考C++中的链表定义进行实现。

二、介绍

链表是由节点组成的数据结构,每个节点包含数据和指向下一个节点的指针。相比于数组,链表的长度可以动态地增长或缩小,这使得它在处理不确定数量的数据或需要频繁插入和删除操作的场景中非常有用。

下面是一个简单的链表节点的定义:

struct Node {
    int data;
    struct Nodenext;
};

在上述定义中,struct Node 表示节点的结构体,包含一个整数类型的数据字段 data,以及一个指向下一个节点的指针 next

三、用途

链表在很多场景中都有广泛的应用。以下是一些链表常见的用途:

  1. 数据存储和管理:链表可以用于存储和管理各种类型的数据,无论是整数、浮点数、字符串还是自定义的数据结构,链表都能灵活地适应。

  2. 动态内存分配:链表允许动态地分配和释放内存,这在处理不确定数据量或需要频繁插入和删除操作的情况下非常有用。

  3. 队列和栈的实现:链表可以用来实现队列和栈等抽象数据类型,这些数据结构在算法和数据处理中扮演着重要的角色。

  4. 图的表示:链表也可以用于表示图的数据结构,其中每个节点代表一个图中的顶点,并通过指针连接相邻的顶点。

四、简单方式进行实现

在C语言中,链表的实现主要依赖于指针和动态内存分配。下面是一个简单的示例,演示如何创建链表并添加节点:

#include 
#include 

struct Node {
    int data;
    struct Nodenext;
};

void insertNode(struct Node** head, int value) {
    struct NodenewNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

void displayList(struct Node* head) {
    struct Nodecurrent = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
}

int main() {
    struct Nodehead = NULL;

    insertNode(&head, 3);
    insertNode(&head, 7);
    insertNode(&head, 9);
    insertNode(&head, 2);

    printf("Linked list: ");
    displayList(head);

    return 0;
}

五、参考C++链表进行实现

首先,我们需要了解C++中的链表有哪些功能,以双向链表为例,以下是C++中链表常见的功能:

  1. 插入节点:可以在链表的任意位置插入新的节点,将新节点链接到链表中。

  2. 删除节点:可以删除链表中的指定节点,调整链表的链接关系。

  3. 遍历链表:可以通过遍历链表,访问链表中的每个节点,并对节点进行操作。

  4. 搜索节点:可以按照特定的条件搜索链表中符合要求的节点。

  5. 反转链表:可以将链表中的节点顺序颠倒,使链表的尾部成为头部。

  6. 获取链表长度:可以计算链表中节点的数量,获取链表的长度信息。

  7. 获取链表中的数据:可以获取链表中指定节点的数据值,进行读取或修改操作。

  8. 合并链表:可以将两个链表合并成一个更长的链表,保持节点的顺序。

  9. 清空链表:可以删除链表中的所有节点,使链表变为空链表。

  10. 检测链表是否为空:可以判断链表是否为空链表。

  11. 迭代器:提供了一种统一的访问容器中元素的方式

扩展功能:根据实际需求,还可以在链表中添加其他自定义的功能,如排序、切分等。

通过上述常见功能,通过C语言实现双向链表大概需要实现以下的功能(之后还会新增):

typedef struct stcotListItem
{

    struct stcotListItem *pPrev;
    struct stcotListItem *pNext; 
    void *pData;
} cotListItem_t;

typedef struct
{

    uint8_t nodeBufNum;
    cotListItem_t *pNodeBuf;
    cotListItem_t node; 
} cotList_t;

// 迭代器使用(自动指向下一个)
#define for_list_each(item, list) for (const cotListItem_t *item = cotList_Begin(&list); item != cotList_End(&list); item = cotList_Next(item))

// 反向迭代器使用(自动指向下一个)
#define for_list_each_r(item, list) for (const cotListItem_t *item = cotList_rBegin(&list); item != cotList_rEnd(&list); item = cotList_rNext(item))

// 迭代器使用(需要在循环内调用 item = cotList_Next(item) 指向下一个)
#define for_list(item, list) for (const cotListItem_t *item = cotList_Begin(&list); item != cotList_End(&list);)

// 反向迭代器使用(需要在循环内调用 item = cotList_rNext(item) 指向下一个)
#define for_list_r(item, list) for (const cotListItem_t *item = cotList_rBegin(&list); item != cotList_rEnd(&list);)

// 获取迭代器中的数据指针
#define item_ptr(type, item)    ((type *)item->pData)

/*
+ 迭代器
   + 正向迭代器
      + cotList_Begin(cotList_t *pList);
      + cotList_End(cotList_t *pList);
      + cotList_Next(const cotListItem_t *pListItem);
   + 反向迭代器
      + cotList_rBegin(cotList_t *pList);
      + cotList_rEnd(cotList_t *pList);
      + cotList_rNext(const cotListItem_t *pListItem);
+ 元素容量
      + cotList_Empty(cotList_t *pList)
      + cotList_Size(cotList_t *pList)
+ 元素访问
      + cotList_Front(cotList_t *pList)
      + cotList_Back(cotList_t *pList)
+ 元素插入
   + 动态节点添加(需要在初始化时提供内存)
      + cotList_Insert(cotList_t *pList, const void *pdata)
      + cotList_PushFront(cotList_t *pList, const void *pdata)
      + cotList_PushBack(cotList_t *pList, const cotListItem_t *pListItem, cotListItem_t *pNewItem)
   + 静态节点添加(需要自己定义节点信息后插入)
      + cotList_InsertItem(cotList_t *pList, const cotListItem_t *pListItem, cotListItem_t *pNewItem)
+ 元素移除
      + cotList_Erase(cotList_t *pList, const cotListItem_t *pListItem)
      + cotList_Remove(cotList_t *pList, const void *pdata)
      + cotList_RemoveIf(cotList_t *pList, bool (*pfnCondition)(const void *pData))
   + 弹出节点
      + cotList_PopFront(cotList_t *pList)
      + cotList_PopBack(cotList_t *pList)
+ 内存交换(链表内存交换,减少内存拷贝)
      + cotList_Swap
*/

实现:

考虑到MCU小内存的使用场景,在实现中并没有采用动态内存分配的方式进行扩展,而是提前分配内存,同时采用动态节点添加静态节点添加的方式实现链表的“元素插入”功能。

动态节点添加:在初始化时提供一片内存给到链表添加节点使用(这里只为节点cotListItem_t分配内存,节点中的数据指针pData指向插入元素原本的内存),在添加元素数据的时候使用内存为新的节点分配。

静态节点添加:自己定义节点,通过通过对应的函数接口插入链表中,这个操作不会使用初始化提前分配内存。
好处在于:既可以节约内存开销(甚至初始化时不分配内存,放弃动态节点添加功能),又可以临时插入几个元素数据(不需要定义节点)

注:C++的链表中插入元素时链表会使用新的内存保存数据,不会使用插入元素原本的内存

迭代器:

迭代器的好处:统一的访问方式(不论是数组、链表还是其他容器,都可以通过迭代器进行遍历和操作,这简化了代码的编写和维护,使得代码更加可读和可复用),隐藏容器的内部结构(迭代器屏蔽了容器的内部结构,将访问元素的细节隐藏起来,提供了一种抽象的视图),安全性和稳定性(迭代器提供了安全的方式来遍历容器,保证了正确的访问顺序和边界条件的检查。使用迭代器可以避免出现越界访问或其他潜在的错误),支持多种遍历方式(正向和反向遍历)。

{
    cotList_t list;
    cotListItem_t nodeBuf[3];
    cotList_Init(&list, nodeBuf, 3);

    int data1 = 10;
    int data2 = 20;
    int data3 = 30;

    // 推送数据(在链表末尾插入数据)
    cotList_PushBack(&list, &data1);
    cotList_PushBack(&list, &data2);
    cotList_PushBack(&list, &data3);

    for_list_each(item, list)  // 正向遍历
    {
        printf("%d\n", *item_ptr(int, item));
    }
}

元素操作:

容量

提供相关接口可以知道链表中的元素数目。

访问

如果不采用迭代器的话,可以访问链表的首尾两个元素节点数据。

插入

动态节点添加(需要在初始化时提供内存)

  • cotList_Insert

  • cotList_PushFront

  • cotList_PushBack

静态节点添加(需要自己定义节点信息后插入,不会使用初始化时提供的内存)

  • cotList_InsertItem

移除

提供了多种元素移除方式,可以通过节点信息删除(建议通过迭代器进行操作)、数据指针地址(匹配则删除,链表中多个节点的数据指针都指向同一个数据时也会被删除)、条件删除(传入条件的回调函数,凡是满足条件的节点都会在链表中删除)、从链表首尾两端删除

交换

两个链表所有的信息都会进行交换,通过交换关键内存信息即可完成链表的交换,减少内存拷贝的性能开销或者互斥锁等频繁操作的开销。

在多线程场景下,事先定义两个同样内存大的链表,在不同的场景下使用,比如线程1仅对链表1插入新元素、线程2仅对链表2访问后删除,在链表2元素为空时和链表1进行交换,这样可以保证链表2的操作不用考虑多线程问题,只需要对链表1考虑多线程问题,从而提高效率。
当然,两个内存不一致大的链表也能完成链表的内存交换使用

其他

还有一些功能待实现,比如查找(可以参考“移除”的多种方式实现)、反转链表等

六、下载链接

C语言扩展库(cot)的容器功能函数中有链表的完整实现,有兴趣的朋友可以参考:

下载链接(或点击“阅读原文”):https://gitee.com/const-zpc/cot


END

来源:大橙子疯嵌入式

版权归原作者所有,如有侵权,请联系删除。

推荐阅读
CAN总线比UART串口难吗?
分享一个开源串口神器,太强了!
短短三个月,稚晖君创业项目已获三轮融资

→点关注,不迷路←

嵌入式ARM 关注这个时代最火的嵌入式ARM,你想知道的都在这里。
评论
  • 自动化已成为现代制造业的基石,而驱动隔离器作为关键组件,在提升效率、精度和可靠性方面起到了不可或缺的作用。随着工业技术不断革新,驱动隔离器正助力自动化生产设备适应新兴趋势,并推动行业未来的发展。本文将探讨自动化的核心趋势及驱动隔离器在其中的重要角色。自动化领域的新兴趋势智能工厂的崛起智能工厂已成为自动化生产的新标杆。通过结合物联网(IoT)、人工智能(AI)和机器学习(ML),智能工厂实现了实时监控和动态决策。驱动隔离器在其中至关重要,它确保了传感器、执行器和控制单元之间的信号完整性,同时提供高
    腾恩科技-彭工 2025-01-03 16:28 166浏览
  • PLC组态方式主要有三种,每种都有其独特的特点和适用场景。下面来简单说说: 1. 硬件组态   定义:硬件组态指的是选择适合的PLC型号、I/O模块、通信模块等硬件组件,并按照实际需求进行连接和配置。    灵活性:这种方式允许用户根据项目需求自由搭配硬件组件,具有较高的灵活性。    成本:可能需要额外的硬件购买成本,适用于对系统性能和扩展性有较高要求的场合。 2. 软件组态   定义:软件组态主要是通过PLC
    丙丁先生 2025-01-06 09:23 71浏览
  •     为控制片内设备并且查询其工作状态,MCU内部总是有一组特殊功能寄存器(SFR,Special Function Register)。    使用Eclipse环境调试MCU程序时,可以利用 Peripheral Registers Viewer来查看SFR。这个小工具是怎样知道某个型号的MCU有怎样的寄存器定义呢?它使用一种描述性的文本文件——SVD文件。这个文件存储在下面红色字体的路径下。    例:南京沁恒  &n
    电子知识打边炉 2025-01-04 20:04 79浏览
  • 物联网(IoT)的快速发展彻底改变了从智能家居到工业自动化等各个行业。由于物联网系统需要高效、可靠且紧凑的组件来处理众多传感器、执行器和通信设备,国产固态继电器(SSR)已成为满足中国这些需求的关键解决方案。本文探讨了国产SSR如何满足物联网应用的需求,重点介绍了它们的优势、技术能力以及在现实场景中的应用。了解物联网中的固态继电器固态继电器是一种电子开关设备,它使用半导体而不是机械触点来控制负载。与传统的机械继电器不同,固态继电器具有以下优势:快速切换:确保精确快速的响应,这对于实时物联网系统至
    克里雅半导体科技 2025-01-03 16:11 176浏览
  • 根据Global Info Research项目团队最新调研,预计2030年全球封闭式电机产值达到1425百万美元,2024-2030年期间年复合增长率CAGR为3.4%。 封闭式电机是一种电动机,其外壳设计为密闭结构,通常用于要求较高的防护等级的应用场合。封闭式电机可以有效防止外部灰尘、水分和其他污染物进入内部,从而保护电机的内部组件,延长其使用寿命。 环洋市场咨询机构出版的调研分析报告【全球封闭式电机行业总体规模、主要厂商及IPO上市调研报告,2025-2031】研究全球封闭式电机总体规
    GIRtina 2025-01-06 11:10 87浏览
  • 光耦合器,也称为光隔离器,是一种利用光在两个隔离电路之间传输电信号的组件。在医疗领域,确保患者安全和设备可靠性至关重要。在众多有助于医疗设备安全性和效率的组件中,光耦合器起着至关重要的作用。这些紧凑型设备经常被忽视,但对于隔离高压和防止敏感医疗设备中的电气危害却是必不可少的。本文深入探讨了光耦合器的功能、其在医疗应用中的重要性以及其实际使用示例。什么是光耦合器?它通常由以下部分组成:LED(发光二极管):将电信号转换为光。光电探测器(例如光电晶体管):检测光并将其转换回电信号。这种布置确保输入和
    腾恩科技-彭工 2025-01-03 16:27 171浏览
  • 每日可见的315MHz和433MHz遥控模块,你能分清楚吗?众所周知,一套遥控设备主要由发射部分和接收部分组成,发射器可以将控制者的控制按键经过编码,调制到射频信号上面,然后经天线发射出无线信号。而接收器是将天线接收到的无线信号进行解码,从而得到与控制按键相对应的信号,然后再去控制相应的设备工作。当前,常见的遥控设备主要分为红外遥控与无线电遥控两大类,其主要区别为所采用的载波频率及其应用场景不一致。红外遥控设备所采用的射频信号频率一般为38kHz,通常应用在电视、投影仪等设备中;而无线电遥控设备
    华普微HOPERF 2025-01-06 15:29 92浏览
  • 随着市场需求不断的变化,各行各业对CPU的要求越来越高,特别是近几年流行的 AIOT,为了有更好的用户体验,CPU的算力就要求更高了。今天为大家推荐由米尔基于瑞芯微RK3576处理器推出的MYC-LR3576核心板及开发板。关于RK3576处理器国产CPU,是这些年的骄傲,华为手机全国产化,国人一片呼声,再也不用卡脖子了。RK3576处理器,就是一款由国产是厂商瑞芯微,今年第二季推出的全新通用型的高性能SOC芯片,这款CPU到底有多么的高性能,下面看看它的几个特性:8核心6 TOPS超强算力双千
    米尔电子嵌入式 2025-01-03 17:04 48浏览
  • 在智能家居领域中,Wi-Fi、蓝牙、Zigbee、Thread与Z-Wave等无线通信协议是构建短距物联局域网的关键手段,它们常在实际应用中交叉运用,以满足智能家居生态系统多样化的功能需求。然而,这些协议之间并未遵循统一的互通标准,缺乏直接的互操作性,在进行组网时需要引入额外的网关作为“翻译桥梁”,极大地增加了系统的复杂性。 同时,Apple HomeKit、SamSung SmartThings、Amazon Alexa、Google Home等主流智能家居平台为了提升市占率与消费者
    华普微HOPERF 2025-01-06 17:23 97浏览
  • 车身域是指负责管理和控制汽车车身相关功能的一个功能域,在汽车域控系统中起着至关重要的作用。它涵盖了车门、车窗、车灯、雨刮器等各种与车身相关的功能模块。与汽车电子电气架构升级相一致,车身域发展亦可以划分为三个阶段,功能集成愈加丰富:第一阶段为分布式架构:对应BCM车身控制模块,包含灯光、雨刮、门窗等传统车身控制功能。第二阶段为域集中架构:对应BDC/CEM域控制器,在BCM基础上集成网关、PEPS等。第三阶段为SOA理念下的中央集中架构:VIU/ZCU区域控制器,在BDC/CEM基础上集成VCU、
    北汇信息 2025-01-03 16:01 193浏览
  • 本文介绍Linux系统更换开机logo方法教程,通用RK3566、RK3568、RK3588、RK3576等开发板,触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。制作图片开机logo图片制作注意事项(1)图片必须为bmp格式;(2)图片大小不能大于4MB;(3)BMP位深最大是32,建议设置为8;(4)图片名称为logo.bmp和logo_kernel.bmp;开机
    Industio_触觉智能 2025-01-06 10:43 72浏览
  • 彼得·德鲁克被誉为“现代管理学之父”,他的管理思想影响了无数企业和管理者。然而,关于他的书籍分类,一种流行的说法令人感到困惑:德鲁克一生写了39本书,其中15本是关于管理的,而其中“专门写工商企业或为企业管理者写的”只有两本——《为成果而管理》和《创新与企业家精神》。这样的表述广为流传,但深入探讨后却发现并不完全准确。让我们一起重新审视这一说法,解析其中的矛盾与根源,进而重新认识德鲁克的管理思想及其著作的真正价值。从《创新与企业家精神》看德鲁克的视角《创新与企业家精神》通常被认为是一本专为企业管
    优思学院 2025-01-06 12:03 76浏览
  • 这篇内容主要讨论三个基本问题,硅电容是什么,为什么要使用硅电容,如何正确使用硅电容?1.  硅电容是什么首先我们需要了解电容是什么?物理学上电容的概念指的是给定电位差下自由电荷的储藏量,记为C,单位是F,指的是容纳电荷的能力,C=εS/d=ε0εrS/4πkd(真空)=Q/U。百度百科上电容器的概念指的是两个相互靠近的导体,中间夹一层不导电的绝缘介质。通过观察电容本身的定义公式中可以看到,在各个变量中比较能够改变的就是εr,S和d,也就是介质的介电常数,金属板有效相对面积以及距离。当前
    知白 2025-01-06 12:04 110浏览
  • 在快速发展的能源领域,发电厂是发电的支柱,效率和安全性至关重要。在这种背景下,国产数字隔离器已成为现代化和优化发电厂运营的重要组成部分。本文探讨了这些设备在提高性能方面的重要性,同时展示了中国在生产可靠且具有成本效益的数字隔离器方面的进步。什么是数字隔离器?数字隔离器充当屏障,在电气上将系统的不同部分隔离开来,同时允许无缝数据传输。在发电厂中,它们保护敏感的控制电路免受高压尖峰的影响,确保准确的信号处理,并在恶劣条件下保持系统完整性。中国国产数字隔离器经历了重大创新,在许多方面达到甚至超过了全球
    克里雅半导体科技 2025-01-03 16:10 122浏览
  • 在测试XTS时会遇到修改产品属性、SElinux权限、等一些内容,修改源码再编译很费时。今天为大家介绍一个便捷的方法,让OpenHarmony通过挂载镜像来修改镜像内容!触觉智能Purple Pi OH鸿蒙开发板演示。搭载了瑞芯微RK3566四核处理器,树莓派卡片电脑设计,支持开源鸿蒙OpenHarmony3.2-5.0系统,适合鸿蒙开发入门学习。挂载镜像首先,将要修改内容的镜像传入虚拟机当中,并创建一个要挂载镜像的文件夹,如下图:之后通过挂载命令将system.img镜像挂载到sys
    Industio_触觉智能 2025-01-03 11:39 115浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦