具有抽象数据类型的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 {
    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[]，而无需强制转换为其他类型。

Answer 2

在C中处理任意数据通常是通过使用指针来完成的-在大多数情况下特别是void *。

Answer 3

显然，linux内核在内核本身和许多设备驱动程序模块中的许多地方都使用了链表。几乎所有这些都是使用linux/list.h中定义的相同宏集实现的。

请参阅http://isis.poly.edu/kulesh/stuff/src/klist/或http://kernelnewbies.org/FAQ/LinkedLists以获得更好的解释。

宏一开始看起来有点奇怪，但很容易使用，很快就变成了第二天性。它们可以简单地调整为在用户空间中使用(请参阅list.h)。