模块化编程中的数据结构封装

数据结构封装，说白了就是把那些常用的数据容器——动态数组、链表、哈希表、树——做成一个个独立的模块。我做了十几年嵌入式开发，发现很多新手喜欢在业务代码里直接写链表操作，结果代码越写越乱，最后自己都看不懂。嗯，今天我们就聊聊怎么把这些数据结构封装好。

一、动态数组模块

动态数组，其实就是能自动扩容的数组。我在项目中遇到过一个问题：一个传感器数据采集系统，采集频率不固定，用固定数组要么浪费内存，要么不够用。后来我封装了一个动态数组模块，问题就解决了。

接口设计

// dynarray.h
#ifndef DYNARRAY_H
#define DYNARRAY_H

#include <stddef.h>

typedef struct DynArray DynArray;

// 创建动态数组，初始容量为 capacity
DynArray* dynarray_create(size_t capacity);

// 销毁动态数组
void dynarray_destroy(DynArray* da);

// 追加元素
int dynarray_append(DynArray* da, void* element);

// 获取元素
void* dynarray_get(DynArray* da, size_t index);

// 获取当前元素个数
size_t dynarray_size(DynArray* da);

#endif

你看，接口很简洁。为什么用 void*？因为这样能存任意类型的数据。我建议你把这个模块做成通用型，别跟具体数据类型绑定。

内部实现要点

操作	时间复杂度	注意事项
追加元素	均摊 O(1)	扩容时需重新分配内存
随机访问	O(1)	直接通过索引访问
插入/删除	O(n)	需要移动后续元素

二、链表模块

链表和动态数组正好互补。动态数组适合随机访问，链表适合频繁插入删除。我个人习惯把链表做成双向的，虽然多了一个指针，但操作起来方便很多。

接口设计

// linkedlist.h
typedef struct LinkedList LinkedList;
typedef struct ListNode ListNode;

LinkedList* list_create();
void list_destroy(LinkedList* list);

// 在头部插入
int list_push_front(LinkedList* list, void* data);
// 在尾部插入
int list_push_back(LinkedList* list, void* data);
// 删除指定节点
void list_remove(LinkedList* list, ListNode* node);

// 遍历回调
typedef void (*list_visit_fn)(void* data);
void list_foreach(LinkedList* list, list_visit_fn visit);

这里有个设计细节：我把 ListNode 结构体暴露出来了。为什么？因为有时候用户需要自己管理节点的位置，比如在哈希表的链地址法中。当然，如果你不想暴露，也可以完全隐藏，只提供迭代器接口。

三、哈希表模块

哈希表，说白了就是通过键直接找到值。我做过一个配置管理系统，用哈希表存储键值对，查找速度比链表快了几百倍。

核心设计

// hashtable.h
typedef struct HashTable HashTable;

// 创建哈希表，size为桶的数量
HashTable* ht_create(size_t size);

// 插入键值对
int ht_insert(HashTable* ht, const char* key, void* value);

// 查找
void* ht_find(HashTable* ht, const char* key);

// 删除
void ht_remove(HashTable* ht, const char* key);

// 哈希函数（可自定义）
typedef size_t (*hash_fn)(const char* key);
void ht_set_hash_fn(HashTable* ht, hash_fn fn);

你想想看，哈希函数有多重要？如果哈希函数写得不好，所有键都映射到同一个桶里，那哈希表就退化成链表了。我一般用 djb2 或者 sdbm 算法，效果还不错。

四、树模块

树结构在嵌入式里用得相对少一些，但一旦用上，就是关键场景。比如文件系统的目录树、表达式解析、路由表查找。我重点讲二叉搜索树和平衡树。

二叉搜索树

// bstree.h
typedef struct BSTree BSTree;

BSTree* bst_create(int (*cmp)(const void* a, const void* b));
void bst_destroy(BSTree* tree);

int bst_insert(BSTree* tree, void* data);
void* bst_search(BSTree* tree, void* key);
void bst_delete(BSTree* tree, void* key);

// 遍历
void bst_inorder(BSTree* tree, void (*visit)(void* data));

比较函数 cmp 是核心。你传什么类型的数据，就用什么比较逻辑。我建议把比较函数做成回调，这样树模块就完全跟数据类型解耦了。

五、模块化封装的核心技巧

说了这么多，其实封装数据结构的核心就几点：

1. 隐藏实现：结构体定义放在.c文件里，.h文件只放前向声明。用户看不到内部细节，也就不会依赖它们。
2. 统一错误处理：所有函数返回int，0表示成功，负数表示错误码。别用全局变量errno，多线程下会出问题。
3. 内存管理：谁创建谁销毁。模块只负责管理自己的内存，不碰用户传进来的数据。
4. 线程安全：如果要在多线程环境下使用，加一把锁。我习惯在模块内部加锁，对外透明。

六、知识体系结构图

下面这张图展示了四种数据结构的封装层次和关系：

你看这张图，四种数据结构各有特点。动态数组和链表是基础，哈希表和树是进阶。实际项目中，我经常组合使用：比如哈希表的每个桶挂一个链表，或者用树来管理动态数组的索引。