乐正

Actions speak louder than words.

Sicp-ex3-26

问题

为了在上面这样实现的表格中检索,我们需要扫描这个记录表。从本质上说,这就是2.3.3节中的无序表表示方式。对于很大的表,以其他方式构造表格可能更加高效。请描述一种表格实现,其中的(key, value)记录用二叉树的形式组织起来。这要假定关键码能以某种方式排序(例如,数值序或者字典序)。(请与第2章练习2.66比较)。

解答

将采用(list (cons key children) left-branch right-branch)这样的结构来表示结构。其中,children可以是它的子树,也可以是当前key对应的值。这里采用字典序排序方法。程序表示如下:

练习3.36 (ex3-26.scm) download
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
(define (make-table)
  (define (key tree)
    (caar tree))
  (define (entry tree)
    (cdar tree))
  (define (children-tree tree)
    (cdar tree))
  (define (left-branch tree)
    (cadr tree))
  (define (right-branch tree)
    (caddr tree))
  (define (key=? key-1 key-2)
    (string=? (string key-1) (string key-2)))
  (define (key>? key-1 key-2)
    (string>? (string key-1) (string key-2)))
  (define (key<? key-1 key-2)
    (string<? (string key-1) (string key-2)))
  (define (make-tree given-key)
    (list (cons given-key '()) '() '()))
  (define (insert-tree! tree children)
    (cond ((not (pair? tree)) children)
          ((key=? (key tree) (key children)) children)
          ((key>? (key tree) (key children))
           (list (car tree)
                 (insert-tree! (left-branch tree) children)
                 (right-branch tree)))
          (else (list (car tree)
                      (left-branch tree)
                      (insert-tree! (right-branch tree) children)))))
  (define (set-value! tree value)
    (set-cdr! (car tree) value))
  (let ((local-table (make-tree '*table*)))
    (define (assoc given-key table)
      (cond ((not (pair? table)) #f)
            ((key=? given-key (key table)) table)
            ((key>? given-key (key table))
             (assoc given-key (right-branch table)))
            (else (assoc given-key (left-branch table)))))
    (define (lookup keys)
      (define (iter keys table)
        (if (null? keys)
            table
            (let ((subtable (assoc (car keys) table)))
              (if (not subtable)
                  #f
                  (iter (cdr keys) (children-tree subtable))))))
      (iter keys (children-tree local-table)))
    (define (insert! keys value)
      (define (iter table keys)
        (if (null? keys)
            (if (not (null? table))
              (begin
                (set-value! table value)
                'ok))
            (let ((subtable (assoc (car keys) (children-tree table))))
              (if (not subtable)
                  (begin
                    (set! subtable (make-tree (car keys)))
                    (set-cdr! (car table)
                              (insert-tree! (children-tree table) subtable))))
              (iter subtable (cdr keys)))))
      (iter local-table keys))
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unkown operation -- TABLE" m))))
    dispatch))

(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))

测试

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
(put (list 'a 'b) 3)
;Value: ok

(put (list 'a 'd) 4)
;Value: ok

(put (list 'a 'e) 10)
;Value: ok

(get (list 'a 'b))
;Value: 3

(get (list 'a 'd))
;Value: 4

(get (list 'a 'e))
;Value: 10

(put (list 'a 'b 'c) 20)
;Value: ok

(get (list 'a 'b 'c))
;Value: 20

(get (list 'a 'b))
;Value 49: ((c . 20) () ())

draft

« sicp-ex3-25 sicp-ex3-27 »

Comments