乐正

Actions speak louder than words.

Sicp-ex3-25

问题

请推广一维表格和二维表格的概念,说明如何实现一种表格,其中的值可以保存在任一个关键码之下,不同的值可能对于不同数目的关键码。对应的lookupinsert!过程以一个关键码的表作为参数去访问这一表格。

解答

练习3.25 (ex3-25.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
(define (make-table)
  (let ((local-table (list '*table*)))
    (define (assoc key records)
      (cond ((null? records) #f)
            ((equal? key (caar records)) (car records))
            (else (assoc key (cdr records)))))
    (define (lookup keys)
      (define (iter table keys)
        (if (null? keys) table
            (let ((subtable (assoc (car keys) table)))
              (if subtable
                  (iter (cdr subtable) (cdr keys))
                  #f))))
      (iter (cdr local-table) keys))
    (define (insert! keys value)
      (define (iter table keys)
        (if (null? keys)
            'ok
            (let ((subtable (assoc (car keys) (cdr table))))
              (if (not subtable)
                  (begin
                    (set! subtable (cons (car keys) '()))
                    (set-cdr! table (cons subtable
                                          (cdr table)))))
              (if (null? (cdr keys))
                  (set-cdr! subtable value))
              (iter subtable (cdr keys)))))
      (iter local-table keys))
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown 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
(put (list 'a 'b) 'c)
;Value: ok

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

(put (list 'a 'd 'c) 1)
;Value: ok

(get (list 'a 'd 'c))
;Value: 1

(put (list 1 'c 'd 'f) 4)
;Value: ok

(get (list 1 'c 'd 'f))
;Value: 4

draft

« sicp-ex3-24 sicp-ex3-26 »

Comments