纯C中的“多用途”链表实现

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

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

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

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

  • 制作一个void指针列表(有点不优雅;更难调试)
  • 只创建一个列表,但是将一个联合作为“元素类型”,包含我将在程序中使用的所有元素类型(更容易调试;如果元素的大小不同,则浪费空间)
  • 使用预处理器宏来重新生成每种类型的代码,以SGLIB的方式 ,“模仿”C ++的STL(创造性的解决方案;不浪费空间;元素具有返回时实际的显式类型; 列表中的任何更改代码可以真的很戏剧性
  • 你的想法/解决方案

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

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

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; 

或者,以图形forms(其中[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内核链表是C中循环链接列表的一个非常好的实现。非常便携且易于使用。 这里是一个独立版本的linux内核2.6.29 list.h头文件。

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

我没有多年编写C语言,但GLib声称提供了“字符串和公共数据结构的大量实用函数”,其中包括链表。

尽管考虑使用另一种语言的技术来解决这类问题很有诱惑力,比如,仿制药,但在实践中它很少是一种胜利。 可能有一些固定解决方案可以在大多数情况下正确使用它(并在他们的文档中告诉你错误的时候),使用它可能会错过任务的重点,所以我会三思而后行。 对于极少数情况,推出自己的可能是可行的,但对于任何合理大小的项目,它不太可能值得调试。

相反,当用x语言编程时,你应该使用语言x的习语。 在使用python时不要编写java。 在使用方案时不要写C。 在使用C99时不要编写C ++。

我自己,我可能最终会使用类似Pax的建议,但实际上使用char [1]和void *和int的联合,以使常见的情况更方便(和一个enumed类型标志)

(我也可能最终会实现一个斐波纳契树,只是因为它听起来很整洁,你只能在失去它的味道之前多次实施RB树,即使这对于它常用的情况更好。 。)

编辑:根据您的评论,看起来您使用固定解决方案的情况非常好。 如果您的教练允许它,并且它提供的语法感觉舒适,请给它一个旋转。

这是一个很好的问题。 我喜欢两种解决方案:

  • Dave Hanson的C接口和实现使用了一个void *指针列表,这对我来说已经足够了。

  • 对于我的学生 ,我写了一个awk脚本来生成特定于类型的列表函数 。 与预处理器宏相比,它需要额外的构建步骤,但是对于没有大量经验的程序员来说,系统的操作更加透明。 它确实有助于为参数多态提供理由,他们将在后来的课程中看到这种情况。

    这是一组函数的样子:

     int lengthEL (Explist *l); Exp* nthEL (Explist *l, unsigned n); Explist *mkEL (Exp *hd, Explist *tl); 

    awk脚本是一个150行的恐怖片; 它在C代码中搜索typedef并为每个代码生成一组列表函数。 它太老了; 我现在可能做得更好了:-)

我不会在一天中的时间(或我硬盘上的空间)列出工会列表。 它不安全,并且它不可扩展,所以你也可以使用void *并完成它。

将其作为void *列表的一个改进是使它成为包含void *的结构列表和一些关于void *指向的元数据,包括其类型,大小等。

其他想法:嵌入Perl或Lisp解释器。

或者中途:与Perl库链接并将其列为Perl SV或其他内容。

我可能会自己使用void *方法,但我想到你可以将数据存储为XML。 然后列表可以只有一个char *用于数据(您可以根据需要解析所需的任何子元素)….