C双向链表与抽象数据类型

Question

我需要一个C语言中的双向链表，但它必须适用于不同的类型。在C++中，我们使用模板来实现这个功能。

请问在哪里可以找到一个关于使用抽象数据类型项的C语言双向链表的示例？

- 0xAX

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

也就是说，假设你知道如何正确地处理负载(payload)，可以按照以下方式进行操作：

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");

那个 cast 行将 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;

每当您将整数类型存储在列表中时（对于4字节的整数），就会浪费96字节。

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[]而无需将其转换为其他类型。

- paxdiablo

---

我个人使用 char payload[0]，所以 sizeof 只代表头部，没有其他内容。 - strager

128位向量类型在x86架构上（由SSE指令集使用）需要16字节对齐，例如。 - zvrba

@strager，我很确定在C99中数组大小为0是非法的（至少对于常量大小的数组是这样）。将有效载荷地址赋值给tPerson类型（person）是我所说的强制转换。从那里开始，您可以使用person访问成员。 - paxdiablo

0大小的数组是gcc扩展。实现此功能的C99兼容方式是使用C99灵活数组。作为结构体的最后一个成员，您可以使用char x []省略大小。然后，在分配时不需要使用-1进行大小计算。 - Michał Trybus

我在使用gcc时真的需要强制使用“-std=c99”。xD - strager

Answer 2

在C语言中，处理任意数据通常需要使用指针，特别是在大多数情况下需要用到“void *”。

- Carl Norum

---

@sterh，没错。然后将列表结构的void *成员指向您想要使用列表跟踪的数据。 - Carl Norum

分配结构本身并不改变。实际上，所有指针（int *、void *等）的大小都相同。只有它们指向的实际数据是不同的。 - casablanca

还要注意，您可以在void和“小”类型之间进行转换，因此可以通过将值直接存储到void使用的位置来避免动态内存分配。 - zvrba

@zvrba：这是一个不好的想法，因为对于一些64位平台来说，指针大小和小数据大小是不同的。 - Joel

@Joel：问题到底出在哪里？将32位整数塞入void*中不会丢失任何数据，通过舍弃高位比特将这样的“指针”转换回整数也不会丢失任何信息（因为它们是零）。当sizeof(small data) > sizeof(void*)时就会出现问题。通过“强制转换”，我实际上是指像*(unsigned*)&void_pointer = 17; 这样的操作。这会严重违反别名规则，因此人们可能希望使用memcpy(&void_pointer, &integer, sizeof(integer))来代替。应该仍然比内存分配快。 - zvrba

Answer 3

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

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

这些宏一开始看起来有些奇怪，但很容易使用，并很快变得自然。它们可以轻松地适应用户空间的使用（请参见list.h）。

- Dipstick

---

这些方法微妙而相当聪明。它们是通常方法的倒置：不是在列表节点类型中存储（指向）您的数据类型，而是在您的数据类型中存储列表节点类型的实例。 - caf

Answer 4

在C语言中，最接近“对象”基类或模板类型的东西是一个void指针。 void *表示指向某个东西的指针，但它并没有指定指向的数据类型。如果您想访问数据，则需要使用转换。

双向链表节点可能看起来像这样：

struct DoubleLinkedListNode {
    struct DoubleLinkedListNode *previous, *next;
    void *data;
};

要为一个节点分配一个字符串，例如，你可以这样做：

char myString[80] = "hello, world";
struct DoubleLinkedListNode myNode;
myNode.data = myString;

要从节点中获取字符串，您需要使用转换操作符：

char *string = (char *)myNode.data;
puts(string);

如果要存储非指针变量，则需要从数据生成一个指针。对于结构体，如果其生命周期足够长（类似于上面的例子），您可能只需取消引用该实例即可。如果不是这样，或者您正在处理原始类型（例如int或float），则需要malloc一些空间。请确保在完成后释放内存。

- strager

Answer 5

您可以像这里演示的那样使用宏（此特定示例实现了通用哈希表）。

- zvrba