嵌入式软件需要掌握的几种数据结构

嵌入式软件开发与通用软件开发在数据结构的选择和使用上有显著差异，主要受限于嵌入式系统的资源约束（如内存、处理器能力）和实时性要求。

本文将详细介绍嵌入式开发中最关键的数据结构及其高效使用方法。

在嵌入式系统开发中选择数据结构时，需要考虑以下关键因素：

内存效率：优先选择内存占用小的结构
时间确定性：确保操作时间可预测，满足实时性要求
静态分配：尽可能避免动态内存分配
缓存友好性：考虑CPU缓存的影响
功耗影响：数据结构的选择会影响功耗

常用数据结构

1. 数组（Array）

特点：

内存连续分配，访问效率高
大小固定，无内存分配开销
缓存友好

示例代码：

// 静态数组声明
#define SENSOR_READINGS_SIZE 10
static int32_t sensor_readings[SENSOR_READINGS_SIZE];

// 循环缓冲区实现
typedef struct 
{
    uint8_t buffer[64];
    uint8_t head;
    uint8_t tail;
} CircularBuffer;

void circular_buffer_push(CircularBuffer* cb, uint8_t data) 
{
    cb->buffer[cb->head] = data;
    cb->head = (cb->head + 1) % sizeof(cb->buffer);
}

使用技巧：

使用const数组存储不变数据（如查找表）
针对特定架构对齐数据（如ARM的ALIGN(4)）
使用位数组(bit array)压缩布尔值存储

2. 链表（Linked List）

嵌入式变体：

单向链表
静态分配的链表（预分配节点池）
侵入式链表（节点包含在数据结构中）

实现示例：

// 静态分配的链表节点池
#define MAX_NODES 32
typedef struct Node 
{
    int value;
    struct Node* next;
} Node;

Node node_pool[MAX_NODES];
Node* free_list = NULL;

void init_pool() 
{
    for(int i=0; i<MAX_NODES-1; i++) 
    {
        node_pool[i].next = &node_pool[i+1];
    }
    node_pool[MAX_NODES-1].next = NULL;
    free_list = &node_pool[0];
}

Node* alloc_node() 
{
    if(!free_list) return NULL;
    Node* node = free_list;
    free_list = free_list->next;
    return node;
}

适用场景：

动态变化但数量可预测的数据集合
需要频繁插入删除的场景
内存碎片敏感的系统

3. 队列（Queue）

嵌入式使用：

环形缓冲区（最常用）
链表实现（动态大小）

环形队列实现：

typedef struct 
{
    uint8_t* buffer;
    size_t head;
    size_t tail;
    size_t size;
    size_t capacity;
} RingBuffer;

bool ring_buffer_init(RingBuffer* rb, uint8_t* buf, size_t capacity) 
{
    rb->buffer = buf;
    rb->capacity = capacity;
    rb->size = 0;
    rb->head = 0;
    rb->tail = 0;
    returntrue;
}

bool ring_buffer_push(RingBuffer* rb, uint8_t data)
{
    if(rb->size >= rb->capacity) returnfalse;
    rb->buffer[rb->head] = data;
    rb->head = (rb->head + 1) % rb->capacity;
    rb->size++;
    returntrue;
}

应用场景：

串口通信缓冲区
生产者-消费者模式
中断与主循环间的数据传递

4. 栈（Stack）

实现要点：

静态分配内存
深度限制检查
ISR安全版本

实现示例：

#define STACK_SIZE 64
typedef struct 
{
    uint32_t data[STACK_SIZE];
    int32_t top;
} Stack;

void stack_init(Stack* s) 
{
    s->top = -1;
}

bool stack_push(Stack* s, uint32_t value)
{
    if(s->top >= STACK_SIZE-1) returnfalse;
    s->data[++s->top] = value;
    returntrue;
}

bool stack_pop(Stack* s, uint32_t* value) 
{
    if(s->top < 0) returnfalse;
    *value = s->data[s->top--];
    returntrue;
}

应用场景：

函数调用跟踪
表达式求值
状态机实现
低内存环境下的深度优先搜索

5. 哈希表（Hash Table）

嵌入式应用：

固定大小设计
简单哈希函数（如CRC16）
开放寻址法解决冲突（节省内存）

实现示例：

#define HASH_SIZE 32
typedef struct 
{
    uint16_t key;
    void* value;
    bool used;
} HashEntry;

typedef struct 
{
    HashEntry entries[HASH_SIZE];
} HashTable;

uint16_t simple_hash(uint16_t key) 
{
    return key % HASH_SIZE;
}

bool hash_insert(HashTable* ht, uint16_t key, void* value) 
{
    uint16_t index = simple_hash(key);
    for(int i=0; i<HASH_SIZE; i++) {
        uint16_t slot = (index + i) % HASH_SIZE;
        if(!ht->entries[slot].used) {
            ht->entries[slot].key = key;
            ht->entries[slot].value = value;
            ht->entries[slot].used = true;
            returntrue;
        }
    }
    returnfalse;
}

应用场景：

快速设备ID查找
资源管理
配置参数存储

6. 树结构

嵌入式常用变体：

二叉树（特别是平衡二叉搜索树）
前缀树（Trie，用于字符串处理）
空间分区树（如KD树用于传感器数据处理）

优化技巧：

数组表示的完全二叉树（节省指针空间）
静态分配节点
针对特定应用优化的变体

数组实现二叉树示例：

#define MAX_TREE_NODES 127
typedef struct 
{
    int data[MAX_TREE_NODES];
    size_t size;
} ArrayBinaryTree;

size_t left_child(size_t index) { return 2*index + 1; }
size_t right_child(size_t index) { return 2*index + 2; }

void tree_insert(ArrayBinaryTree* tree, int value)
{
    if(tree->size >= MAX_TREE_NODES) return;
    tree->data[tree->size++] = value;
}

应用场景：

文件系统目录结构
网络协议解析
数据压缩（霍夫曼编码）

7. 位图和位字段

优势：

极低的内存占用
高效的位操作

实现示例：

// 位图实现
#define BITMAP_SIZE 128
typedef struct 
{
    uint8_t bits[BITMAP_SIZE/8];
} Bitmap;

void bitmap_set(Bitmap* bm, size_t bit) 
{
    bm->bits[bit/8] |= (1 << (bit % 8));
}

bool bitmap_test(Bitmap* bm, size_t bit) 
{
    return (bm->bits[bit/8] & (1 << (bit % 8))) != 0;
}

// 位字段实现
typedef struct 
{
    uint32_t flag1 : 1;
    uint32_t flag2 : 1;
    uint32_t mode : 3;
    uint32_t value : 10;
} PackedData;

应用场景：

资源分配表
设备状态标志
紧凑协议编码

其他数据结构

1. 内存池（Memory Pool）

#define POOL_SIZE 1024
#define BLOCK_SIZE 32
#define NUM_BLOCKS (POOL_SIZE/BLOCK_SIZE)

typedef struct 
{
    uint8_t pool[POOL_SIZE];
    uint8_t used[NUM_BLOCKS];
} MemoryPool;

void* pool_alloc(MemoryPool* mp) 
{
    for(int i=0; i<NUM_BLOCKS; i++) 
    {
        if(!mp->used[i])
        {
            mp->used[i] = 1;
            return &mp->pool[i*BLOCK_SIZE];
        }
    }
    return NULL;
}

2. 事件队列

typedef enum { SENSOR_UPDATE, BUTTON_PRESS, TIMEOUT } EventType;

typedef struct
{
    EventType type;
    uint32_t timestamp;
    union 
    {
        int32_t sensor_value;
        uint8_t button_id;
    } data;
} Event;

#define MAX_EVENTS 16
typedef struct 
{
    Event events[MAX_EVENTS];
    uint8_t front;
    uint8_t rear;
    uint8_t count;
} EventQueue;

3. 时间轮定时器

#define TIMER_SLOTS 32
typedef void (*TimerCallback)(void*);

typedef struct 
{
    uint32_t timeout;
    TimerCallback cb;
    void* arg;
    uint32_t remaining;
} Timer;

typedef struct 
{
    Timer slots[TIMER_SLOTS][8];
    uint8_t counts[TIMER_SLOTS];
    uint32_t current_slot;
} TimerWheel;