本文主要介绍不同的数据抽象，对应用程序在使用公共函数时会造成何种影响。这里主要是使用集合使用三种数据来表示：集合作为未排序的表、集合作为排序的表、集合作为有序二叉树，探讨不同的数据对象形式表示集合时，对使用集合的程序性能的影响。

基本概念

  • 选择函数与构造函数
    • 构造函数：说明一个数据对象是由哪些原始组成的。
    • 选择函数：怎么将数据对象中的组成元素抽取出来。
  • 数据抽象定义
    数据定义就是一组选择函数与构造函数，以及为了使它们成为一套合法的表示。因此它们需要满足一组特定的条件。

看着上面两个定义是不是很拗口，不知道在说啥。举个例子来说，如果一个有理数p是由整数 n 和 整数 d 构造而成。也就是 p = n /d。

1
2
3
4
5
;构造函数 p = n / d
p = (make-rat n d)
;选择函数
n = (numer p)
d = (denom p)

集合操作

在高中的数学我们学习过，集合表示一组无重复的元素聚集而成。在数据结构中，集合表示一组具有相同属性的元素，并且满足数学中的集合属性：无序性。

常见集合的操作，判断某个元素是否属于某个集合、求两个集合的交集、求两个集合的并集。假设集合A={1,2,3}、B={2,3,4}，以及元素m=2,n=5，则：

  • 判断某个元素是否属于某个集合：m 属于A,也属于B，而n不属于A,也不属于B;
  • A 与 B 的交集为：{2, 3};
  • A 与 B 的并集为：{1, 2, 3, 4}
    下面我们来看看使用三种不同的数据表示，会对写集合常见操作造成什么样影响。

集合作为未排序的表

构造函数与选择函数

直接使用list 函数，但是集合中元素是排序的，比如集合A={1, 10, 2, 4, 3}。

判断某个元素是否属于某个集合

1
2
3
4
(define (element-of-set? x set)
    (cond ((null? set) #f)
          (else (or (equal? x (car set)) 
                    (element-of-set? x (cdr set))))))

求两个集合的交集

1
2
3
4
5
(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))))

求两个集合的并集

1
2
3
4
5
6
(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((element-of-set? (car set1) set2)
            (union-set (cdr set1) set2))
         (else (cons (car set1) (union-set (cdr set1) set2)))))

将某个元素加入集合中

1
2
3
4
(define (adjion-set x set)
    (if (element-of-set? x set)
        set
        (cons x set)))

集合作为排序的表

构造函数与选择函数

直接使用list 函数，但是集合中元素是排序的，比如集合A={1, 2, 3, 4, 5, 10}。

判断某个元素是否属于某个集合

1
2
3
4
5
(define (element-of-set? x set)
    (cond ((null? set) #f)
          ((equal? x (car set)) #t)
          ((< x (car set)) #f)
          (else (element-of-set? x (cdr set)))))

求两个集合的交集

1
2
3
4
5
6
7
8
(define (intersection-sort-set set1 set2)
    (if (or (null? set1) (null? set2))
        '()
        (let ((x (car set1))
              (y (car set2)))
             (cond ((= x y) (cons x (ntersection-sort-set (cdr set1) (cdr set2))))
                   ((< x y) (intersection-sort-set (cdr set1) set2))
                   (else (intersection-sort-set set1 (cdr set2)))))))

将某个元素加入到集合中

1
2
3
4
5
(define (adjoin-set x set)
    (cond ((null? set) (cons x set))
          ((equal? x (car set)) set)
          ((< x (car set)) (cons x set))
          (else (cons (car set) (adjoin-set x (cdr set))))))

求两个集合的并集

1
2
3
4
5
6
7
8
(define (union-sort-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else (let ((x (car set1))
                      (y (car set2)))
                   (cond ((< x y) (cons x (nion-sort-set (cdr set1) set2)))
                         ((> x y) (cons y (union-sort-set set1 (cdr set2))))
                         (else (cons x (union-sort-set(cdr set1) (cdr set2)))))))))

集合作为有序二叉树

构造函数与选择函数

1
2
3
4
5
6
7
8
9
10
11
;(dataItem, left-branch, right-branch)

(define (entry tree)
    (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left-branch right-branch)
    (list entry left-branch right-branch))

判断某个元素是否属于某个集合

1
2
3
4
5
6
7
(define (element-of-set? x set)
    (if (null? set)
        #f
        (let ((dataItem (entry set)))
            (cond ((= dataItem x) #t)
                  ((> dataItem x) (element-of-set x (left-branch set)))
                  (else (element-of-set x (right-branch set)))))))

求两个集合的交集

1
2
3
4
5
(define (intersection-set set1 set2)
    (let ((list1 (tree->list set1))
          (list2 (tree->list set2)))
        (let ((res (intersection-sort-set list1 list2)))
             (list-tree res))))

求两个集合的并集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
; 辅助函数：将树形结构转为列表结构
(define (tree->list tree)
    (define (copy-to-list tree result-list)
        (if (null? tree)
            result-list
            (copy-to-list (left-branch tree)
                          (cons (entry tree)
                                (copy-to-list (right-branch tree)
                                              result-list)))))
    (copy-to-list tree '()))

;辅助函数：将列表结构转位树形结构
(define (list-tree elements)
    (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
    (if (= n 0)
        (cons '() elts)
        (let ((left-size (quotient (- n 1) 2)))
             (let ((left-result (partial-tree elts left-size)))
                  (let ((left-tree (car left-result))
                        (non-left-elts (cdr left-result))
                        (right-size (- n (+ left-size 1))))
                       (let ((this-entry (car non-left-elts))
                             (right-result (partial-tree (cdr non-left-elts) right-size)))
                            (let ((right-tree (car right-result))
                                  (remaining-elts (cdr right-result)))
                                 (cons (make-tree this-entry left-tree right-tree)
                                        remaining-elts))))))))

(define (union-set set1 set2)
    (let ((list1 (tree->list set1))
          (list2 (tree->list set2)))
         (let ((res (union-sort-set list1 list2)))
              (list-tree res))))

添加元素到集合

1
2
3
4
5
6
7
8
9
(define (adjoin-set x set)
    (cond ((null? set) (make-tree x '() '()))
          ((= x (entry set)) set)
          ((< x (entry set)) (make-tree (entry set) 
                                        (adjoin-set x (left-branch set))
                                        (right-branch set)))
          (else (make-tree (entry set)
                           (left-branch set)
                           (adjoin-set x (right-branch set))))))

总结

通过三种不同的数据表示集合，分析了程序在使用集合操作，比如检查是否属于集合、集合的交集、集合并集等操作，在时间复杂度上是存在差异的。如下表格：

表示法 检查元素是否属于集合 添加元素 交集 并集
未排序的表 O(n) O(n) O(n^2) O(n^2)
排序的表 O(n) O(n) O(n) O(n)
有序二叉树 O(log n) O(log n) O(n) O(n)

也就是我们常说:

程序=数据结构+算法