练习 2.61

以下是有序集合的 adjoin-set 函数的定义：

;;; 61-adjoin-set.scm

(define (adjoin-set x set)
    (if (null? set)
        (list x)
        (let ((current-element (car set))
              (remain-element (cdr set)))
            (cond ((= x current-element)
                    set)
                  ((> x current-element)
                    (cons current-element
                          (adjoin-set x remain-element)))
                  ((< x current-element)
                    (cons x set))))))

adjoin-set 遍历并使用 cons 重新组合整个表，并在重新组合的过程中将 x 加入到集合中去，这个程序的复杂度为 \(\Theta(n)\) 。

利用已排序元素的表示，平均每次只需要对表内的一半元素进行查找，就能完成添加新元素的任务。

1 ]=> (load "61-adjoin-set.scm")

;Loading "61-adjoin-set.scm"... done
;Value: adjoin-set

1 ]=> (adjoin-set 1 '())                ; 空表

;Value 11: (1)

1 ]=> (adjoin-set 3 (list 1 2 3))       ; x 已经存在于 set

;Value 12: (1 2 3)

1 ]=> (adjoin-set 3 (list 1 2 4 5))     ; x 不存在于 set

;Value 13: (1 2 3 4 5)

另一种 adjoin-set 实现

实现 adjoin-set 的另一种方法是，将新元素转换成一个包含单元素的集合（只有一个元素的列表），然后将两个集合进行 union-set 操作：

;;; 61-another-adjoin-set.scm

(load "62-union-set.scm")

(define (adjoin-set x set)
    (union-set (list x) set))

其中 union-set 函数来自 练习 2.62 ，这个 adjoin-set 实现的复杂度也是 \(\Theta(n)\) 。

1 ]=> (load "61-another-adjoin-set.scm")

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

1 ]=> (adjoin-set 1 '())                ; 空集

;Value 11: (1)

1 ]=> (adjoin-set 3 (list 1 2 3))       ; 元素已存在

;Value 12: (1 2 3)

1 ]=> (adjoin-set 3 (list 1 2 4 5))     ; 元素不存在

;Value 13: (1 2 3 4 5)

讨论

blog comments powered by Disqus