Serendip

Web Studio

問題2.66

レコードの集合がキーの数値で順序づけられている二進木で構造化されている場合の lookup 手続き。

(define (key record)
  (car record))

(define (value record)
  (cadr record))

(define (make-record key value)
  (list key value))

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      #f
      (let ((entry-of-record (entry set-of-records)))
           (let ((key-of-record (key entry-of-record)))
                (cond ((= given-key key-of-record) (value entry-of-record))
                      ((< given-key key-of-record) (lookup given-key (left-branch set-of-records)))
                      ((> given-key key-of-record) (lookup given-key (right-branch set-of-records))))))))

(define record
  (list->tree (list
                (make-record 1 'john)
                (make-record 2 'paul)
                (make-record 3 'george)
                (make-record 4 'ringo))))
; ((2 paul) ((1 john) () ()) ((3 george) () ((4 ringo) () ())))

(lookup 1 record)
gosh> john
(lookup 2 record)
gosh> paul
(lookup 3 record)
gosh> george
(lookup 4 record)
gosh> ringo

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る