乐正

Actions speak louder than words.

Sicp-ex2-60

问题

我们前面说明了如何将程序表示为没有重复元素的表。现在假定允许重复,例如,集合[1, 2, 3] 可能会被表示为表(2 3 2 1 3 2 2)。请为在这种表示上的操作设计过程element-of-set?adjoin-setunion-setintersection-set。与前面不重复表示里的相应操作相比, 现在各个操作的效率怎么样?在什么样的程序里面你更倾向于使用这种表示,而不是前面那 种无重复的表示?

解答

练习2.60 (ex2-60.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? (car set) x) #t)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (if (null? set1) set2
    (union-set (cdr set1) (cons (car set1) set2))))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1) (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

在这种情况下,可以看出element-of-set?所需要的步数依然使$\Theta (n)$,union-set 所需要的步数也是$\Theta (n)$,intersection-set所需要的部署还是$\Theta (n^2)$, 但是adjoin-set变成了$\Theta (1)$。

所以,在以插入操作为主要使用场景的时候,可以使用这种表示方式。

draft

« sicp-ex2-59 sicp-ex2-61 »

Comments