这不完全是一个技术问题,因为我知道C足以完成我需要做的事情(我的意思是,就不会“让语言妨碍您进行操作”而言),因此,这个问题基本上是一个“方向”提出'问题。
情况是:我目前正在上一门高级算法类(class),并且为了“成长为程序员”,我被要求使用纯C来实现实际分配(效果很好:实际上,您犯的任何小错误几乎都是强制性的您需要完全了解自己在做什么才能对其进行修复)。在实现过程中,我显然遇到了必须从头开始实现“基本”数据结构的问题:实际上不仅是链表,而且还有栈,树等。
我主要关注本主题中的列表,因为它通常是我在程序中经常使用的结构,或者作为其他较大结构的“主”结构或“辅助”结构(例如,解析使用链表冲突)。
这需要列表存储许多不同类型的元素。 我在这里假设我不想为每种类型重新编码列表。因此,我可以提出以下替代方案:
要明确这个问题:以上哪一项最好?
PS:由于我基本上是在学术背景下工作,所以我对业界使用纯C的人们的看法也很感兴趣。我了解到,大多数纯C程序员都在嵌入式设备 Realm ,我认为我所遇到的这种问题并不常见。但是,如果外面有人知道它是如何在“现实世界中”完成的,那么我会对您的观点非常感兴趣。
最佳答案
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;
每次将整数类型存储在列表中(对于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;
关于c - 纯C中的“多用途”链表实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/736307/