Prolog中的双链表 [英] Doubly Linked List in Prolog

问题描述

我一直在业余时间学习Prolog大约8个月到一年，现在我正着手解决一些经典数据结构和算法的实现。

<我对在Prolog中实现双链表很感兴趣，但是对如何进行却很困惑。我之所以被Prolog吸引，是因为我对逻辑纯度感兴趣。

似乎我是如此适应于面向对象的范例，以至于除了简单之外，我都无法做到

供双重链接列表参考，我的意思是类似于此链接中所述的内容：

双链表

解决方案

之所以使其成为双链表，是因为它有两个链接而不是一个链接，引用了列表中的上一项和下一项。因此我们可以制作一个 node（Value，Previous，Next）结构并手动创建列表，如下所示： A = node（1，nil，B ），B =节点（2，A，nil）。。我们可以通过类似的方式使更长的列表，只是创建更多的中间变量。

将其转换回正常列表将类似于：

  dl2list（node（X，_，nil），[X]）。 
 dl2list（node（A，_，node（X，Y，Z）），[A | Rest]）：-dl2list（node（X，Y，Z），Rest）。 
  

这并没有特别使用上一个指针，但是您可以看到它的工作原理：

 ？-A =节点（1，nil，B），
 B =节点（2，A，C）， 
 C =节点（3，B，D），
 D =节点（4，C，nil），
 dl2list（A，L）。 
 A =节点（1，nil，_S1），％其中
 _S1 =节点（2，node（1，nil，_S1），_S2），
 _S2 =节点（3，_S1 ，node（4，_S2，nil）），
 B =节点（2，node（1，nil，_S1），_S2），
 C =节点（3，_S1，node（4，_S2） ，nil）），
 D = node（4，_S2，nil），
 L = [1,2,3,4]。 
  

我们也可以从头开始向后构建：

  dl2listrev（node（X，nil，_），[X]）。 
 dl2listrev（node（A，node（X，Y，Z），_），[A | Rest]）：-dl2listrev（node（X，Y，Z），Rest）。 
 
？-A =节点（1，nil，B），
 B =节点（2，A，C），
 C =节点（3，B，D） ，
 D =节点（4，C，nil），
 dl2listrev（D，L）。 
 A =节点（1，nil，_S1），％其中
 _S1 =节点（2，node（1，nil，_S1），_S2），
 _S2 =节点（3，_S1 ，node（4，_S2，nil）），
 B =节点（2，node（1，nil，_S1），_S2），
 C =节点（3，_S1，node（4，_S2） ，nil）），
 D =节点（4，_S2，nil），
 L = [4，3，2，1] 
  

要从列表中构建双向链接列表，您需要比以下任何一个都强一点的东西：

  l2dl（L，DL）：-l2dl（L，DL，nil）。 
 
 l2dl（[X]，node（X，Prev，nil），Prev）。 
 l2dl（[X，Y | Xs]，node（X，Prev，Next），Prev）：-
 l2dl（[Y | Xs]，Next，node（X，Prev，Next）） 。 
  

您可以在这里看到双向工作：

 ？-l2dl（[1,2,3,4]，X），dl2list（X，L）。 
 X = node（1，nil，node（2，_S1，node（3，_S2，_S3）））），％其中
 _S1 = node（1，nil，node（2，_S1，node （3，_S2，_S3））），
 _S2 =节点（2，_S1，节点（3，_S2，_S3）），
 _S3 =节点（4，节点（3，_S2，_S3）） ，nil），
 L = [1,2,3,4] 
  

：

 ？-A =节点（1，nil，B），
 B =节点（2，A， C），
 C =节点（3，B，D），
 D =节点（4，C，nil），
 l2dl（L，A）。 
 A =节点（1，nil，_S1），％其中
 _S1 =节点（2，node（1，nil，_S1），_S2），
 _S2 =节点（3，_S1 ，node（4，_S2，nil）），
 B =节点（2，node（1，nil，_S1），_S2），
 C =节点（3，_S1，node（4，_S2） ，nil）），
 D =节点（4，_S2，nil），
 L = [1、2、3、4] 
  

I have been learning Prolog in my spare time for about 8 months to a year and now I am moving on to tackle implementing some of the classic data structures and algorithms .

I am interested in achieving a doubly linked list in Prolog, but quite baffled as to how to proceed . I was attracted to Prolog because I am interested in "logical purity" .

It seems that I am so accommodated to the object-oriented paradigm that beyond the simple I just cannot proceed without it !

For reference by doubly linked list I mean something similar to what is described in this link :

Double Linked List

解决方案

What makes it a doubly-linked list is that it has two links rather than one, a reference to the previous and the next item in the list. So we could make a node(Value, Previous, Next) struct and make the list manually like so: A = node(1, nil, B), B = node(2, A, nil).. We could make longer lists the analogous way, just creating more intermediate variables.

Translating that back into a "normal" list would look something like this:

dl2list(node(X, _, nil), [X]).
dl2list(node(A, _, node(X,Y,Z)), [A|Rest]) :- dl2list(node(X,Y,Z), Rest).

This makes no particular use of the "previous" pointer, but you can see it works:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2list(A, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] .

We could also build backwards, starting from the end:

dl2listrev(node(X, nil, _), [X]).
dl2listrev(node(A, node(X,Y,Z), _), [A|Rest]) :- dl2listrev(node(X,Y,Z), Rest).

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2listrev(D, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [4, 3, 2, 1] 

To construct a doubly-linked list from a list, you need something a little stronger than either of these:

l2dl(L, DL) :- l2dl(L, DL, nil).

l2dl([X], node(X, Prev, nil), Prev).
l2dl([X,Y|Xs], node(X, Prev, Next), Prev) :- 
    l2dl([Y|Xs], Next, node(X, Prev, Next)).

This you can see working in both directions here:

?- l2dl([1,2,3,4], X), dl2list(X, L).
X = node(1, nil, node(2, _S1, node(3, _S2, _S3))), % where
    _S1 = node(1, nil, node(2, _S1, node(3, _S2, _S3))),
    _S2 = node(2, _S1, node(3, _S2, _S3)),
    _S3 = node(4, node(3, _S2, _S3), nil),
L = [1, 2, 3, 4] 

and here:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   l2dl(L, A).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] 

这篇关于Prolog中的双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！