纯 C 中的“多用途"链表实现 [英] 'Multipurpose' linked list implementation in pure C

问题描述

这不完全是一个技术问题，因为我知道 C 足以做我需要做的事情(我的意思是，就不要让语言妨碍你"而言)，所以这个问题基本上是一个要采取什么方向"的问题.

This is not exactly a technical question, since I know C kind of enough to do the things I need to (I mean, in terms of not 'letting the language get in your way'), so this question is basically a 'what direction to take' question.

情况是:我目前正在学习高级算法课程，为了成长为程序员"，我被要求使用纯 C 语言来实现实际作业(效果很好:几乎任何你犯的小错误make 实际上迫使你完全理解你在做什么以修复它).在实现过程中，我显然遇到了必须从头开始实现基本"数据结构的问题:实际上不仅是链表，还有栈、树等.

Situation is: I am currently taking an advanced algorithms course, and for the sake of 'growing up as programmers', I am required to use pure C to implement the practical assignments (it works well: pretty much any small mistake you make actually forces you to understand completely what you're doing in order to fix it). In the course of implementing, I obviously run into the problem of having to implement the 'basic' data structures from the ground up: actually not only linked lists, but also stacks, trees, et cetera.

我关注本主题中的列表，因为它通常是我最终在程序中大量使用的结构，要么作为主"结构，要么作为其他更大结构的辅助"结构(例如，散列使用链表解决冲突的树).

I am focusing on lists in this topic because it's typically a structure I end up using a lot in the program, either as a 'main' structure or as a 'helper' structure for other bigger ones (for example, a hash tree that resolves conflicts by using a linked list).

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

This requires that the list stores elements of lots of different types. I am assuming here as a premise that I don't want to re-code the list for every type. So, I can come up with these alternatives:

• 制作空指针列表(有点不优雅；更难调试)
• 只制作一个列表，但有一个联合作为元素类型"，包含我将在程序中使用的所有元素类型(更容易调试；如果元素大小不同，则会浪费空间)
• 使用预处理器宏为每种类型重新生成代码，采用 SGLIB 的风格，模仿"C++STL(创造性的解决方案；不浪费空间；元素在返回时具有它们实际的显式类型；列表代码中的任何更改都可能非常戏剧化)
• 您的想法/解决方案

• Making a list of void pointers (kinda inelegant; harder to debug)
• Making only one list, but having a union as 'element type', containing all element types I will use in the program (easier to debug; wastes space if elements are not all the same size)
• Using a preprocessor macro to regenerate the code for every type, in the style of SGLIB, 'imitating' C++'s STL (creative solution; doesn't waste space; elements have the explicit type they actually are when they are returned; any change in list code can be really dramatic)
• Your idea/solution

把问题说清楚:以上哪一个最好?

PS:因为我基本上是在学术背景下工作的，我也对业内使用纯 C 的人的看法很感兴趣.我知道大多数纯 C 程序员都在嵌入式设备领域，我认为我面临的这种问题并不常见.但是，如果有人知道它是如何在现实世界"中完成的，我会对您的意见非常感兴趣.

PS: Since I am basically in an academic context, I am also very interested in the view of people working with pure C out there in the industry. I understand that most pure C programmers are in the embedded devices area, where I don't think this kind of problem I am facing is common. However, if anyone out there knows how it's done 'in the real world', I would be very interested in your opinion.

推荐答案

void * 在链表中有点麻烦，因为您必须单独管理它对链表本身的分配.我过去使用的一种方法是使用可变大小"结构，例如:

A void * is a bit of a pain in a linked list since you have to manage it's allocation separately to the list itself. One approach I've used in the past is to have a 'variable sized' structure like:

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

现在我意识到看起来不是可变大小，而是让我们这样分配一个结构:

Now I realize that doesn't look variable sized but let's allocate a structure thus:

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

现在您有一个节点，无论出于何种意图和目的，它都如下所示:

Now you have a node that, for all intents and purposes, looks like this:

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

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

or, in graphical form (where [n] means n bytes):

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

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

That is, assuming you know how to address the payload correctly. This can be done as follows:

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 有效负载的地址类型.

That cast line simply casts the address of the payload character (in the tNode type) to be an address of the actual tPerson payload type.

使用这种方法，您可以在一个节点中携带您想要的任何有效载荷类型，甚至每个节点中的不同有效载荷类型，而不会浪费联合空间.这种浪费可以通过以下方式看出:

Using this method, you can carry any payload type you want in a node, even different payload types in each node, without the wasted space of a union. This wastage can be seen with the following:

union {
    int x;
    char y[100];
} u;

每次在列表中存储整数类型时都会浪费 96 个字节(对于 4 字节整数).

where 96 bytes are wasted every time you store an integer type in the list (for a 4-byte integer).

tNode 中的有效载荷类型允许您轻松检测此节点携带的有效载荷类型，因此您的代码可以决定如何处理它.您可以使用以下内容:

The payload type in the tNode allows you to easily detect what type of payload this node is carrying, so your code can decide how to process it. You can use something along the lines of:

#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;

这篇关于纯 C 中的“多用途"链表实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！