具有抽象数据类型的 C 双链表

Question

我需要在 C 中的双链表中，但它必须用于不同的类型。在 C++ 中，我们为它使用模板。我在哪里可以找到 C 中带有抽象类型项的双链表的示例。

谢谢

Answer 1

您可以采用几种方法，其中一种涉及在您的 ADT 中存储一个 void*。

我一直发现这在链表中有点麻烦，因为您必须单独管理它对链表本身的分配。换句话说，要分配一个节点，您需要分别分配该节点及其有效负载(并记住在删除时也要清除它们)。

我过去使用的一种方法是使用“可变大小”结构，例如:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char payload[1];
} tNode;

现在看起来大小可变，但让我们这样分配一个结构:

typedef struct {
    char Name[30];
    char Addr[50];
    char Phone[20];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

现在您有一个节点，就所有意图和目的而言，它看起来像这样:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char Name[30];
    char Addr[50];
    char Phone[20];
} tNode;

或者，以图形形式(其中 [n] 表示 n 字节):

+------------+
| prev[4]    |
+------------+
| next[4]    |
+------------+ +-----------+
| payload[1] | | Name[30]  | <- overlap
+------------+ +-----------+
               | Addr[50]  |
               +-----------+
               | Phone[20] |
               +-----------+

也就是说，假设您知道如何正确处理负载。这可以按如下方式完成:

node->prev = NULL;
node->next = NULL;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Richard Cranium");
strcpy (person->Addr, "10 Smith St");
strcpy (person->Phone, "555-5555");

该转换行只是将 payload 字符(在 tNode 类型中)的地址转换为实际 tPerson 有效负载的地址类型。

使用这种方法，您可以在一个节点中携带您想要的任何有效负载类型，甚至每个节点中的不同有效负载类型，如果您使结构更像:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;       // Allows different payload type at each node.
    char payload[1];
} tNode;

并使用 payloadType 来存储关于有效载荷实际是什么的指示符。

与 union 相比，它的优势在于它不会浪费空间，如下所示:

union {
    int fourBytes;
    char oneHundredBytes[100];
} u;

每次在列表中存储整数类型时都会浪费 96 个字节(对于 4 字节整数)。

tNode 中的负载类型使您可以轻松检测此节点承载的负载类型，因此您的代码可以决定如何处理它。您可以使用以下内容:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

或(可能更好):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

您唯一需要注意的是确保负载对齐正确。由于我的负载占位符和负载都是 char 类型，所以这不是问题。但是，如果您的负载包含具有更严格对齐要求的类型(例如比指针更严格的类型，您可能需要针对它进行调整)。

虽然我从未见过对齐比指针更严格的环境，但根据 ISO C 标准，它是可能的。

您通常可以简单地通过使用具有最严格对齐要求的有效负载占位符数据类型来获得所需的对齐方式，例如:

long payload;

---

回想起来，我突然想到您可能需要一个数组作为负载占位符。只要有一些你可以获取地址的东西就足够简单了。我怀疑我的特定习语可以追溯到我刚刚存储字符数组(而不是结构)并直接引用它们的日子。在这种情况下，您可以单独使用 payload[] 而无需转换为另一种类型。