LISP - 集合

Common Lisp 不提供集合数据类型。 但是，它提供了许多允许在列表上执行集合操作的函数。

您可以根据各种条件添加、删除和搜索列表中的项目。 您还可以执行各种集合运算，例如:并集、交集和集差。

在 LISP 中实现集合

集合和列表一样，通常是用 cons 单元来实现的。 然而，正是由于这个原因，集合变得越大，集合操作的效率就越低。

adjoin 函数允许您建立一个集合。 它接受一个项目和一个表示集合的列表，并返回一个表示包含该项目和原始集合中所有项目的集合的列表。

adjoin函数首先在给定列表中查找项目，如果找到，则返回原始列表； 否则，它会创建一个新的 cons 单元，其中 car 作为项目，cdr 指向原始列表并返回此新列表。

adjoin 函数还采用 :key 和 :test 关键字参数。 这些参数用于检查该项目是否存在于原始列表中。

由于 adjoin 函数不会修改原始列表，因此要对列表本身进行更改，您必须将 adjoin 返回的值分配给原始列表，或者您可以使用宏 pushnew 将项目添加到集合中。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

执行代码时，会返回以下结果 −

NIL
(2 1)
(2 1)
(3 2 1)

检查成员

成员函数组允许您检查元素是否是集合的成员。

以下是这些函数的语法 −

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

这些函数在给定列表中搜索满足测试的给定项目。 如果没有找到这样的项目，则函数返回nil。否则，返回以该元素作为第一个元素的列表的尾部。

仅在顶层进行搜索。

这些函数可以用作谓词。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

执行代码时，会返回以下结果 −

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

设置并集

函数的 union 组允许您在测试的基础上对作为这些函数的参数提供的两个列表执行集合并集。

以下是这些函数的语法 −

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

union 函数接受两个列表并返回一个新列表，其中包含两个列表中存在的所有元素。 如果存在重复项，则返回的列表中仅保留该成员的一份副本。

nunion 函数执行相同的操作，但可能会破坏参数列表。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

执行代码时，会返回以下结果 −

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

请注意

对于三个向量的列表，如果没有 :test-not #'mismatch 参数，并集函数将无法按预期工作。 这是因为，列表是由 cons 单元组成的，虽然这些值在我们看来看起来是相同的，但单元的 cdr 部分并不匹配，因此它们与 LISP 解释器/编译器不完全相同。 这就是原因； 不建议使用列表来实现大集合。 不过，它对于小型设备来说效果很好。

设置交叉点

函数的交集组允许您在测试的基础上对作为这些函数的参数提供的两个列表执行交集。

以下是这些函数的语法 −

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

这些函数采用两个列表并返回一个新列表，其中包含两个参数列表中存在的所有元素。 如果任一列表有重复条目，则冗余条目可能会也可能不会出现在结果中。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

执行代码时，会返回以下结果 −

(C)
(#(A B) #(5 6 7))
NIL

交集函数是交集的破坏性版本，即它可能会破坏原始列表。

设置差异

set-difference 函数组允许您在测试的基础上对作为这些函数的参数提供的两个列表执行集合差异。

以下是这些函数的语法 −

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

set-difference 函数返回第一个列表中未出现在第二个列表中的元素列表。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

执行代码时，会返回以下结果 −

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))