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];

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

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

score 6 · Accepted Answer

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

score 0 · Accepted Answer

您可以使用数组索引代替指针。然后，您可以构建链接列表并使用索引值访问下一个或上一个小部件。

score 0 · Accepted Answer

有很多方法可以实现这一点，但这里有一个：您可以创建一个数组struct widget+ 一个布尔数组来标记它们是否自由。然后你可以用找到第一个struct widget可用的函数替换你的 malloc。这类似于在各种内核中发现的平板分配器。

score 0 · Accepted Answer

您可以使用另一个bool数组来标记使用了哪些条目。

有很多现有的 API 提供了在编译时为最大数量的实体保留内存的功能，并提供分配和释放它们的函数。有关示例，请参阅Contiki membAPI 和实现。

score 0 · Accepted Answer

最好使用静态数组方法，而不是指针，您可以访问需要访问的元素的索引。

虽然您将面临一些常见问题，例如；

优点是；

5 回答 5