Prolog - 链接列表

以下章节描述了如何使用递归结构生成/创建链表。

链表有两个部分，整数部分和链接部分。链接部分将保存另一个节点。列表末尾的链接部分将包含 nil。

链表

在 prolog 中，我们可以使用node(2, node(5, node(6, nil))) 来表达这一点。

注意- 最小的可能列表是 nil，并且每个其他列表将包含 nil 作为结束节点的“下一个”。在列表术语中，第一个元素通常称为列表的头部，列表的其余部分称为尾部。因此上面的列表的头部是2，它的尾部是列表node(5,node(6,nil))。

我们还可以将元素插入正面和背面 -

程序

add_front(L,E,NList) :- NList = node(E,L).

add_back(nil, E, NList) :-
   NList = node(E,nil).
   
add_back(node(Head,Tail), E, NList) :-
   add_back(Tail, E, NewTail),
   NList = node(Head,NewTail).

输出

| ?- [linked_list].
compiling D:/TP Prolog/Sample_Codes/linked_list.pl for byte code...
D:/TP Prolog/Sample_Codes/linked_list.pl compiled, 7 lines read - 966 bytes written, 14 ms

(15 ms) yes
| ?- add_front(nil, 6, L1), add_front(L1, 5, L2), add_front(L2, 2, L3).

L1 = node(6,nil)
L2 = node(5,node(6,nil))
L3 = node(2,node(5,node(6,nil)))

yes
| ?- add_back(nil, 6, L1), add_back(L1, 5, L2), add_back(L2, 2, L3).

L1 = node(6,nil)
L2 = node(6,node(5,nil))
L3 = node(6,node(5,node(2,nil)))

yes
| ?- add_front(nil, 6, L1), add_front(L1, 5, L2), add_back(L2, 2, L3).

L1 = node(6,nil)
L2 = node(5,node(6,nil))
L3 = node(5,node(6,node(2,nil)))

yes
| ?-