宏实现数据结构：链表、栈、队列与哈希表

说实话，C语言里用宏来实现数据结构，这事儿我早年刚入行时也觉得有点「邪门」。毕竟教科书上教我们的是结构体+函数，谁没事用宏去折腾链表？但后来在嵌入式项目里，我遇到了一个内存极度受限的场景——每多一个函数调用，栈空间就多一分风险。那时候我才真正体会到，宏在某些场合下，比函数更「香」。

今天我们就来聊聊，怎么用宏去实现链表节点、栈、队列，甚至哈希表。嗯，这里要注意：宏不是万能的，但用对了地方，它能让你的代码既高效又优雅。

一、宏实现链表节点

链表的核心是节点。每个节点包含数据和指向下一个节点的指针。用宏来定义节点，好处是你可以轻松地「泛型化」——说白了，就是让同一个宏能生成不同类型的链表节点。

核心思路：利用宏参数替换数据类型，生成结构体定义。

// 定义链表节点宏
#define LIST_NODE(type) \
    struct list_node_##type { \
        type data; \
        struct list_node_##type *next; \
    }

// 使用示例
LIST_NODE(int);      // 生成 struct list_node_int
LIST_NODE(float);    // 生成 struct list_node_float
LIST_NODE(char*);    // 生成 struct list_node_char_ptr

我在项目中遇到过一个问题：如果直接用 typedef 加宏，容易搞混类型名。所以我个人习惯在宏里用 ## 拼接，这样每个类型生成的节点结构体名字都是唯一的，不会冲突。

小技巧：你还可以把节点的创建、插入、删除也写成宏。但要注意，宏展开后是原地替换，调试时不好单步跟踪。所以我的建议是：节点定义用宏，操作函数用内联函数或普通函数。

二、宏实现栈

栈是一种后进先出的结构。用宏实现栈，我通常会定义一个「栈容器」——说白了就是一个结构体，里面包含一个数组和一个栈顶指针。

// 栈的宏定义
#define STACK(type, size) \
    struct stack_##type { \
        type data[size]; \
        int top; \
    }

// 栈操作宏
#define STACK_PUSH(stack, value) \
    do { \
        if ((stack).top < (sizeof((stack).data) / sizeof((stack).data[0]))) { \
            (stack).data[(stack).top++] = (value); \
        } \
    } while(0)

#define STACK_POP(stack) \
    ((stack).top > 0 ? (stack).data[--(stack).top] : (typeof((stack).data[0]))0)

#define STACK_EMPTY(stack) ((stack).top == 0)

嗯，这里要注意：do { ... } while(0) 这个写法很关键。如果不加这个，宏在 if-else 语句里展开时可能会出问题。我曾经因为漏了这个，排查了整整一个下午的 bug……

避坑指南：宏里的 typeof 是 GNU C 的扩展，不是标准 C。如果你用 MSVC 或者一些老编译器，可能不支持。这时候可以改成传一个默认值参数进去。

三、宏实现队列

队列是先进先出的结构。用宏实现队列，我一般用环形缓冲区的方式——这样空间利用率高，而且不需要频繁移动数据。

// 队列宏定义（环形缓冲区）
#define QUEUE(type, size) \
    struct queue_##type { \
        type data[size]; \
        int head; \
        int tail; \
        int count; \
    }

#define QUEUE_ENQUEUE(queue, value) \
    do { \
        if ((queue).count < (sizeof((queue).data) / sizeof((queue).data[0]))) { \
            (queue).data[(queue).tail] = (value); \
            (queue).tail = ((queue).tail + 1) % \
                (sizeof((queue).data) / sizeof((queue).data[0])); \
            (queue).count++; \
        } \
    } while(0)

#define QUEUE_DEQUEUE(queue) \
    ({ \
        typeof((queue).data[0]) __val = (typeof((queue).data[0]))0; \
        if ((queue).count > 0) { \
            __val = (queue).data[(queue).head]; \
            (queue).head = ((queue).head + 1) % \
                (sizeof((queue).data) / sizeof((queue).data[0])); \
            (queue).count--; \
        } \
        __val; \
    })

你想想看，环形队列的好处是什么？头尾指针都在循环移动，不会出现「前面空着，后面满了」的情况。我在一个串口数据缓冲的项目里用过这个宏，效果很好——代码量少，运行效率高。

注意：队列的 count 字段用来区分「空」和「满」。如果不加这个字段，头尾相等时你无法判断是空还是满。这是环形队列的经典问题，别踩坑。

四、宏实现哈希表

哈希表稍微复杂一点。用宏实现哈希表，我通常的做法是：定义一个固定大小的桶数组，每个桶里挂一个链表（用我们前面定义的链表节点宏）。

// 哈希表宏定义
#define HASH_TABLE(type, key_type, buckets) \
    struct hash_table_##type { \
        struct list_node_##type *slots[buckets]; \
        int (*hash_fn)(key_type key); \
    }

// 插入宏
#define HASH_INSERT(table, key, node) \
    do { \
        int __idx = (table).hash_fn(key) % \
            (sizeof((table).slots) / sizeof((table).slots[0])); \
        (node)->next = (table).slots[__idx]; \
        (table).slots[__idx] = (node); \
    } while(0)

// 查找宏（返回节点指针，没找到返回NULL）
#define HASH_FIND(table, key, type, member) \
    ({ \
        int __idx = (table).hash_fn(key) % \
            (sizeof((table).slots) / sizeof((table).slots[0])); \
        struct list_node_##type *__cur = (table).slots[__idx]; \
        typeof((type*)0) __result = NULL; \
        while (__cur) { \
            if (__cur->data.key == key) { \
                __result = &__cur->data; \
                break; \
            } \
            __cur = __cur->next; \
        } \
        __result; \
    })

说实话，哈希表的宏实现里，最麻烦的是查找宏。因为你要从链表节点里取出数据，还要比较 key。我一般会在数据里内嵌一个 key 字段，然后用 member 参数来访问——但这样写起来确实有点绕。

我的建议：哈希表这种复杂结构，如果项目对性能要求不是极端苛刻，还是用函数实现更稳妥。宏适合做「小而美」的封装，太大太复杂的宏，调试起来真的很痛苦。

五、知识体系总览

下面这张图，是我对本章知识结构的梳理。你可以看到，从最基础的链表节点出发，逐步构建出栈、队列和哈希表。宏就像一把「瑞士军刀」，小巧但锋利。

宏实现数据结构知识体系 宏定义（#define） 链表节点 栈（后进先出） 队列（先进先出） 哈希表 核心思想：利用宏参数替换和 ## 拼接，实现「泛型」数据结构 适用场景：嵌入式系统、内存受限环境、对性能有极致要求的代码

六、总结与避坑

用宏实现数据结构，说白了就是「用空间换时间，用预处理器换运行时」。宏在编译阶段就展开了，没有函数调用的开销，也没有栈帧的压栈出栈。但代价是：代码体积变大，调试困难，可读性下降。

我个人总结了几条经验，分享给你：

  • 节点定义用宏，操作函数用内联。这样既保证了泛型能力，又保留了可调试性。
  • 宏里多用 do { ... } while(0)。这是 C 语言宏的「安全套」，能避免很多展开后的语法错误。
  • 复杂结构（如哈希表）慎用宏。如果一定要用，建议把哈希函数和比较函数作为参数传进去，而不是硬编码在宏里。
  • 注意编译器兼容性。typeof、## 拼接这些特性，不是所有编译器都支持。跨平台项目要提前测试。

我曾经踩过的坑：有一次我在一个宏里用了 ++ 操作符，结果宏参数被展开了两次，导致变量自增了两次。从那以后，我养成了一个习惯——宏参数如果可能被多次引用，先赋值给一个局部变量再使用。

好了，关于宏实现数据结构的内容就聊到这里。记住，宏是一把双刃剑，用好了是利器，用不好是凶器。希望你能在实际项目中，找到最适合自己的平衡点。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →