c - 什么是 C 中链表的忠实替代品？

Question

这个问题可能过于宽泛，或者观点有偏见，但我知道这个网站上有很多经验丰富的程序员，我认为它可能会鼓励进行很好的讨论。

我正在用 C 语言实现一个嵌入式应用程序，我在其中使用了一个链表，其中包含以下结构:

struct my
{
    uint16_t x;
    uint16_t y;

    char *text;

    struct my *next;
    struct my *prev;

};

它总体上运行良好，但在项目中，我现在正在转向 MISRA-C 编程指南。 MISRA 禁止使用任何动态数据结构，因为它可能会在内存有限的嵌入式系统中导致未指定的行为。

我首先想到的当然是经典的静态数组结构，具有固定大小。这个结构的实例永远不会超过 30 个，而且我们仍然只使用了不到 5% 的可用内存，所以即使没有使用所有这些内存，也不会影响我们的程序性能。像这样:

extern struct my arr[30];

然而，这种方法有一定的困难，例如，有时我需要从列表中删除一个元素，然后它会留下一个空元素，迫使我通过一个索引重写所有其他元素。

是否有任何干净、优雅的方式来实现类似于链表的功能，而不使用它们？

Answer 1

您可以在静态数组上使用链表。唯一的区别是，您使用的不是指向动态分配的内存块的指针，而是指向数组内元素的指针。如果您愿意，可以只使用数组索引而不是指针。当然，实现会有一些不同: - 添加或删除元素时不必(取消)分配内存 - 相反，您必须自己管理空闲槽，使用另一种结构，如队列或什至是另一个空元素列表