0

下面的过程采用两个列表并将它们的并集作为有序列表返回。

(defun stable-union (lst1 lst2)
  (cond ((null lst1) lst2)
        ((null lst2) lst1)
        ((and (null lst1) (null lst2)) nil)
        (t
         (let ((el1 (car lst1))
               (el2 (car lst2)))
           (cond ((string= el1 el2)
                  (cons el1
                     (stable-union (cdr lst1)  (cdr lst2))))
                  ((string< el1 el2)
                   (cons el1
                         (stable-union (cdr lst1)  lst2)))
                  (t
                   (cons el2
                         (stable-union lst1 (cdr lst2)))))))))

它适用于某些示例，但不适用于其他示例。例如：

STABLE-UNION: (STABLE-UNION '(A B C) '(B A D)) failed: 
Expected (A B C D) but saw (A B A C D)
STABLE-UNION: (STABLE-UNION '(A B C) '(A D B E)) failed: 
Expected (A B C D E) but saw (A B C D B E)
STABLE-UNION: (STABLE-UNION '(C B A) '(A E B D)) failed: 
Expected (C B A E D) but saw (A C B A E B D)

你能指导我在我的代码中犯错误的地方吗？太感谢了。

4

1 回答 1

5

上述函数仅适用于由已按字典顺序排列的符号组成的列表。因此，例如，它适用于'(A B C) '(A B D)，但不适用于'(A B C) '(B A D)。

有几种方法可以纠正它。最简单的一种是通过对两个参数进行排序（使用稳定排序）来调用它，例如：

(defun stable-union-general (lst1 lst2)
   (stable-union (stable-sort lst1 #'string<) (stable-sort lst2 #'string<)))

(stable-union-general '(A B C) '(B A D))
(A B C D)

另一种效率较低的方法是通过考虑无序列表来更改算法。

最后请注意，外部条件的第三个分支永远不会被统计：((and (null lst1) (null lst2)) nil)

这是因为，在这种情况下，第一个分支为真并且函数返回nil。

于 2019-10-25T18:39:02.790 回答