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

Question

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

谢谢

Answer 1

您可以采取一些方法,其中一种方法是void*在ADT中存储a .

我总是发现这在链表中有点痛苦,因为你必须将它的分配单独管理到列表本身.换句话说,要分配节点,您需要单独分配节点及其有效负载(并记住在删除时同时清除它们).

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

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 {
    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[]而不必转换为其他类型.