练习 2.62

有序集合的 union-set 定义如下,它的复杂度为 \(\Theta(n)\)

;;; 62-union-set.scm

(define (union-set set another)
    (cond ((and (null? set) (null? another))
            '())
          ((null? set)
            another)
          ((null? another)
            set)
          (else
            (let ((x (car set)) (y (car another)))
                (cond ((= x y)
                        (cons x (union-set (cdr set) (cdr another))))
                      ((< x y)
                        (cons x (union-set (cdr set) another)))
                      ((> x y)
                        (cons y (union-set set (cdr another)))))))))

这个 union-set 要处理多个情况:

首先,如果两个输入表都是空表,那么返回空表。

其次,如果两个输入表其中一个为空表,那么返回另外一个表。

如果两个输入表都不为空,那么取出这两个表的第一个元素,通过对比元素来决定将它们放到结果表的那个位置上。

另一个值得一说的情况是,当一个表比另一个表长的时候,多出来的表的剩余元素会被 cons 直接连上,也即是, union-set 的执行步数由较短的输入列表的长度决定。以下展开式说明了这样一个例子:

(union-set (list 1 2) (list 1 3 5 7 9))

(cons 1 (union (list 2) (list 3 5 7 9)))

(cons 1
      (cons 2 (union '() (list 3 5 7 9))))

(cons 1
      (cons 2
            (list 3 5 7 9)))

'(1 2 3 5 7 9)

测试

1 ]=> (load "62-union-set.scm")

;Loading "62-union-set.scm"... done
;Value: union-set

1 ]=> (union-set '() (list 1 2 3))

;Value 13: (1 2 3)

1 ]=> (union-set (list 1 2 3) (list 1 3 5))

;Value 11: (1 2 3 5)

1 ]=> (union-set (list 1 2 3) (list 1 3 5 7 9))

;Value 12: (1 2 3 5 7 9)

讨论

blog comments powered by Disqus