带有抽象数据类型的C双链表
我需要C中的双链表，但它必须适用于不同的类型。 在C ++中，我们使用模板。 我在哪里可以找到C中的示例，用于带有抽象类型项的双链表。
谢谢
您可以采取一些方法，其中一种方法是在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;
或者，以图形forms（其中[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[]使用payload[]而无需转换为其他类型。
在C中处理任意数据通常是通过使用指针来完成的 – 特别是在大多数情况下为void * 。
显然，linux内核在内核本身和许多设备驱动程序模块中的许多地方使用链表。 几乎所有这些都是使用linux / list.h中定义的一组宏来实现的
有关详细说明，请参见http://isis.poly.edu/kulesh/stuff/src/klist/或http://kernelnewbies.org/FAQ/LinkedLists 。
这些宏一开始看起来有点奇怪，但很容易使用，很快成为第二天性。 它们可以简单地适用于用户空间（参见list.h ）。
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一些空间。 完成后一定要释放内存。
您可以使用此处演示的宏（此特定示例实现通用散列表）。