浅谈：《嵌入式软件中的那些数据结构》

目录

引 言

概 念

数据结构基本类型

数据结构的意义 

结 尾

One| 引 言

如果问软件三要素是什么？你知道吗？

在软件工程导论中，给出了基本概念：

   软件 = 程序 + 数据 + 文档

如果再问，作为软件基石之一的数据，核心要素是什么？答案是：

   数据结构

只要涉及软件设计，就必提的数据结构，到底有多重要？

可以这么讲，如果说软件设计有三板斧，那数据结构至少占一板斧还多。

Two| 概 念

在计算机科学中，数据结构是由组织方式、存储格式、管理方式三者共同组成。

说人话就是，计算机中的数据是怎么被存储和被访问的。

如果要说的再具体一些，数据结构是指数据元素之间的关系，以及操作这些数据元素的方法。

以最常见的数组为例，它就是基本的数据结构之一；

组织方式：大小固定，元素间连续排列；

存储格式：按照元素索引依次存储在一段连续的内存中；

管理方式：支持快速访问，按照索引直接查找；

#include <stdio.h>

#define ARRAY_SIZE 5
int main() {
    int arr[ARRAY_SIZE] = {1, 2, 3, 4, 5};  // 静态初始化
    //访问元素
    printf("第三个元素: %d\n", arr[2]);  // 输出: 3
    return 0;
}

Three| 数据结构基本类型

常见的基本的数据结构类型有：

· 数组(Array)

· 栈(Stack)

· 队列(Queue)

· 链表(Linked List)

· 树(Tree)

· 图(Graph)

· 堆(Heap)

· 散列表(Hash)

   栈(Stack)

· 结构类型：属于线性数据结构；

· 核心特征：LIFO(后进先出，Last In First Out)，类似叠盘子，最后插入的元素反而最先被移除；

· 操作原则：仅允许在栈顶 PUSH(插入) 或 POP(删除)，不支持类似数组那种随机访问；

· 核心价值：能够高效管理具有临时性、且对顺序依赖的数据；

   队列(Queue)

· 结构类型：属于线性数据结构；

· 核心特性：FIFO(先进先出，First In First Out)，类似排队规则，先进入队列的元素会被先处理；

· 操作原则：数据只能从Rear(队尾)插入，或者只能从Front(队首)删除，也就是常说的入队(enqueue)、出队(dequeue);

· 核心价值：在需要严格保证顺序处理的场景下，按照顺序公平处理数据；

   链表(Linked List)

· 结构类型：属于线性数据结构；

· 核心特征：存储在堆内存中，内存动态分配，存储空间不连续，支持灵活的增删操作；参考FreeRTOS中的任务链表；

· 操作原则：通过指针或者引用连接各个节点，支持随机插入和随机访问；特别是每个节点需要额外存储指针；

· 核心价值：具有动态、增删高效的特性，非常适合用于嵌入式系统中，数据量变化频繁的应用场景；

注意：操作过程要进行动态分配内存，要小心内存管理漏洞，出现内存泄漏等问题，解决方法可以参考FreeRTOS中内存池的方式；

   树(Tree)

· 结构类型：属于非线性数据结构；

· 核心特征：由Node(节点)和Edge(边)组成，具有层次化、分支化特点；每个树都仅有一个Root(根节点)，其它节点为Subtree(子树)，互不相交，以此形成分层关系；

· 操作原则：同链表，支持插入(需要维护有序性)、删除(需要进行子节点重组)、查找、遍历；

· 核心价值：具有层次性、高效的特点，非常适合嵌入式系统中，需要动态管理有序数据，或者需要表达复杂关系的应用场景；(像文件系统、任务调度等)

· 注意：小心深度递归(确保实时性保障)；同链表一样，需要注意内存管理；

   图(Graph)

· 结构类型：属于非线性数据结构；

· 核心特征：由 Vertex(顶点) 和 Edge(边) 共同表示成复杂的关系网络；顶点表示实体(例如设备、任务、状态等)，边表示与顶点的关系，可以带方向，也可以带权重(例如通信延迟、路径成本等)；

· 操作原则：图的操作经常需要借助一些算法来完成，例如遍历时，需要配合DFS（深度优先搜索）、BFS(广度优先搜索)；

· 核心价值：具有灵活性、关系建模能力，特别适合嵌入式系统中的网络通信、任务调度等复杂的应用场景；但使用时，需要较高的内存和计算开销，需要权衡内存优化、算法优化、硬件性能等因素；

   堆(Heaph)

· 结构类型：属于特殊的完全二叉树数据结构；

· 核心特征：最后一层除外，其它各层节点都是满状态，且最后一层的节点按照从左到右进行填充；可以使用数组方式来实现，利用索引计算父节点、子节点的位置；

· 操作原则：支持Insert(插入)、删除根节点、随机访问节点值、支持构建堆；在插入和删除操作后，通过上浮或下浮，快速恢复堆序性；

· 核心价值：堆具备的高效最值操作和动态调整能力，特别适合在嵌入式系统中管理优先级任务和实施资源；通过静态数组实现和迭代优化，能够在资源受限的苛刻条件下兼顾性能和稳定性。

· 注意：数据结构采用堆时，一定要注意内存分配、时间复杂度确定、边界安全，以此保证操作过程中满足嵌入式系统实时性的需求。

   散列表(Hash)

· 结构类型：也就是常说的哈希表，属于通过哈希函数将键值映射到存储位置的数据结构；

· 核心特性：高效访问，各种操作耗时基本一致；Hash Function(哈希函数)，将键值转换到数组索引，继而决定核心性能；具备冲突解决机制，机制三大法则：链地址法、开放寻址法、再哈希法；负载因子，因子值越高，冲突概率越大，性能越低；

· 操作原则：支持查找、插入、删除、随机访问；

· 核心价值：这种高效查找特性，非常适合嵌入式系统中管理键值映射；但是散列表的性能非常依赖哈希函数的设计、冲突处理机制和内存管理；

Four| 数据结构的意义 

介绍完基本的数据结构类型，回过头来看数据结构在整个软件设计过程中的意义就非常清晰；

数据结构更像是软件的骨架；

在软件设计过程中，选择哪种数据结构，决定了数据的组织方式和执行效率。

不同的数据结构适用于不同的场景，合理的选择数据结构可以提升软件的性能、可维护性、拓展性。

基于上述的描述，可见在资源有限、性能有限的嵌入式领域，数据结构的意义不言而喻。

即使是当下多么复杂的算法，基石其实还是数据结构。

Five| 结 尾

数据结构作为计算机科学中，独立的一门专业课；

不可能一篇文章就能详述，还有很多的细节需要去注意、研究。

本篇文章旨在作为一个引子，希望能够引起各位小伙伴的重视；

特别是我们电子系出身，比较偏硬件的专业，更需要系统且认真的学习一遍数据结构。

日拱一卒，愿我们的技术更上一层楼。