“多用途”纯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实现的实际分配（它工作得很好：pretty多的你居然让小失误迫使你完全理解你为了解决这个问题）做什么。在实施的过程中，我明明碰上不必实现从地面的基本数据结构行动的问题：实际上不仅链表，还叠加，树木等等。

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).

这需要许多不同类型的列表存储元素。我假设在这里作为我不想重新code列表中的每一个premise类型。所以，我可以拿出这些方​​案：

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:

• 制空指针列表（有点不雅，难以调试）


• 制作只有一个名单，但有一个联盟为元素类型，载我会在程序中使用的所有元素类型（容易调试;浪费空间，如果内容都不尽相同大小）


• 使用preprocessor宏再生code对每种类型，在 SGLIB 风格，'模仿' C ++的STL（创造性的解决方案，不浪费空间;元素都具有明确的类型，他们实际上是在返回他们;的列表中的code的任何变化可真是戏剧性的）


• 您的想法/解决方案

• 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.

推荐答案

A 无效* 是位链表痛，因为你必须要管理它的分配分别以列表本身。我已经在过去使用的一种方法是有一个像可变大小的'结构：

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 字节）：

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

这是投行只铸载荷字符的地址（在 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 让您轻松检测到这种节点执行什么类型的有效载荷，所以你的code可以决定如何处理它。您可以使用的线沿线的东西：

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屋！