纯C中的"多用途"链表实现

这不完全是一个技术问题,因为我知道C有足够的东西来做我需要的东西(我的意思是,不是'让语言妨碍你'),所以这个问题基本上是'什么方向'采取'问题.

情况是:我目前正在学习高级算法课程,并且为了"成长为程序员",我需要使用纯C来实现实际任务(它运作良好:几乎任何小错误你实际上都是你完全理解你正在做什么来解决它).在实现过程中,我显然遇到了必须从头开始实现"基本"数据结构的问题:实际上不仅是链表,还有堆栈,树等等.

我专注于本主题中的列表,因为它通常是一个结构,我最终在程序中使用了很多,作为"主"结构或作为其他更大的结构的"帮助"结构(例如,一个哈希树,可以解决使用链表冲突).

这要求列表存储许多不同类型的元素.我假设这里作为一个前提,我不想为每种类型重新编码列表.所以,我可以提出这些替代方案:

制作一个void指针列表(有点不优雅;更难调试)

只有一个列表,但是有一个联合作为'元素类型',包含我将在程序中使用的所有元素类型(更容易调试;如果元素的大小不同,则浪费空间)

使用预处理器宏为SGLIB样式重新生成每种类型的代码,"模仿"C++的STL(创造性解决方案;不浪费空间;元素具有返回时实际的显式类型; 列表中的任何更改代码可以真的很戏剧化)

你的想法/解决方案

要明确问题:上述哪一个最好？

PS:由于我基本上处于学术背景中,因此我对在行业中使用纯C的人的观点也非常感兴趣.我知道大多数纯C程序员都在嵌入式设备领域,我不认为我面临的这种问题很常见.但是,如果那里的任何人知道它是如何"在现实世界中"完成的,我会对你的意见非常感兴趣.

A void *在链表中有点痛苦,因为你必须将它的分配单独管理到列表本身.我过去使用的一种方法是使用"可变大小"结构,例如:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

现在我意识到看起来不是变量大小但是让我们分配一个结构:

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

现在你有一个节点,出于所有意图和目的,它看起来像这样:

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

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

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

也就是说,假设您知道如何正确地处理有效负载.这可以按如下方式完成:

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

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

使用此方法,您可以在节点中携带所需的任何有效负载类型,甚至可以在每个节点中携带不同的有效负载类型,而不会浪费联合空间.可以通过以下方式看到这种浪费:

union {
    int x;
    char y[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;

我的$ .002:

制作一个无效指针列表(有点不好;难以调试)

如果您必须使用C语言编写,这不是一个糟糕的选择,恕我直言.您可以添加API方法以允许应用程序提供print()方法以便于调试.当(例如)项目被添加到列表或从列表中删除时,可以调用类似的方法.(对于链表,这通常不是必需的,但对于更复杂的数据结构 - 例如哈希表) - 它有时可以成为救星.)

只有一个列表,但是有一个联合作为'元素类型',包含我将在程序中使用的所有元素类型(更容易调试;如果元素的大小不同,则浪费空间)

我会像瘟疫一样避免这种情况.(好吧,你确实问过.)从数据结构到其包含的类型具有手动配置的编译时依赖性是所有世界中最糟糕的.再次,恕我直言.

使用预处理器宏为SGLIB(sglib.sourceforge.net)的样式重新生成每种类型的代码,'模仿'C++的STL(创造性的解决方案;不浪费空间;元素具有他们实际上的显式类型)返回;列表代码中的任何更改都可能非常引人注目)

有趣的想法,但由于我不知道SGLIB,我不能说更多.

你的想法/解决方案

我会选择第一个选择.

我在过去,在我们的代码中已经完成了这个(之后已经转换为C++),并且当时决定使用void*方法.我只是为了灵活性而这样做 - 我们几乎总是在列表中存储一个指针,并且解决方案的简单性和它的可用性(对我而言)超过了其他方法的缺点.

话虽这么说,有一次它引起了一些难以调试的讨厌的bug,所以它绝对不是一个完美的解决方案.不过,如果我现在再次这样做,我认为它仍然是我要采取的.

使用预处理器宏是最佳选择.在Linux内核链表是一个优秀的一个eficient实施下一个循环链接的列表是非常便携且易于使用.这里是一个独立版本的linux内核2.6.29 list.h头文件.

FreeBSD/OpenBSD sys/queue是基于通用宏的链表的另一个好选择