Lisp图数据结构 [英] Lisp graph data structures

问题描述

我正在阅读 Jorge Gajon的树作为Common Lisp中的链接列表 ，其中包含对用Lisp完成的树的描述。作者给出了这个基本示例：

I'm reading Jorge Gajon's Trees as Linked Lists in Common Lisp, which includes a description of a tree done in Lisp. The author gives this basic example:

然后给出一个Lisp列表表示形式：

Then gives a Lisp list representaton:

(1 (2 6 7 8) 3 (4 (9 12)) (5 10 11))

其中位置表示层次结构级别：1是列表中的第一个，即它在顶部，2是下一个级别，但它是其级别的顶部，依此类推。但是随后他给出了警告：

where position implies hierarchy level: 1 is first in the list, i.e., it's at the top, 2 is at the next level, but it's the top of its level, etc. But then he gives this caveat:

请注意，如果您需要在生产程序中表示树，则除非有充分的理由，否则不应使用此处所述的列表。

PLEASE NOTE, that if you need to represent trees in a production program you shouldn’t use lists as described here unless you have a good reason. This is only an exercise in understanding how cons cells work.

好吧，一个人应该如何在生产中表示树数据结构？码？顺便说一句，我也想看看一个非循环有向图的例子，即类似树的东西，它也具有多父功能。例如，在上图中，8是2的孩子，也是3的孩子。我猜是这样的：

All right, how should one represent the tree data structure in "production" code? BTW, I'd also like to see an example of an acyclic directed graph, i.e., something tree-like that also has "multiple parent" capabilities. For example in the diagram above, 8 is a child of 2, but also 3. I'm guessing something like this:

(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))

，但似乎我已经创建了一个8的影子孪生子，但与3的子代8到底是哪个8也有2作为父代并没有真正的联系。如果我想拥有3个12岁的父母，这个问题会变得更糟。

but it seems like I've created a "shadow" twin of 8 and not really relating how the 8 that is the child of 3 is the same 8 that also has 2 as a parent. This problem gets worse if I wanted to have 3 as 12's parent.

(1 (2 6 7 8) (3 8 12) (4 (9 12)) (5 10 11))

可以这么说。较低的层次结构会在混洗中丢失。

The fact that 12 is in a lower hierarchy gets lost in the shuffle, so to speak.

在Lisp / Scheme / Clojure中是否有对数据结构的良好且适当的处理（书籍等）世界？我只发现了一次性的东西。

Is there a good and proper treatment (book, etc.) of data structures in the Lisp/Scheme/Clojure world? I've only found one-off stuff like this.

推荐答案

生产代码将使用CLOS（Common Lisp对象系统）来定义 NODE 类和对图/树的操作。

The 'production' code would use CLOS (the Common Lisp Object System) to define a NODE class and operations over the graph/tree.

这篇关于Lisp图数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！