問題2.69 – SICP（計算機プログラムの構造と解釈）その81

2009年01月25日
blog
sicp

問題2.69

対のリストとその順序づけられたリストが以下の場合…

(make-leaf-set '((A 4) (B 2) (C 1) (D 1)))
gosh> ((leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

次のような形で…

SICP 問題2.69 successive-merge 手続き

以下のような Huffman木 を生成する手続きを考える。

((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8)

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge pairs)
  (if (null? (cdr pairs))
      (car pairs)
      (successive-merge
        (adjoin-set
          (make-code-tree (car pairs) (cadr pairs))
          (cddr pairs)))))

(display (generate-huffman-tree '((A 4) (B 2) (C 1) (D 1))))
gosh> (((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8))#<undef>
計算機プログラムの構造と解釈
計算機プログラムの構造と解釈

posted with amazlet at 08.11.07
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
Amazon.co.jp で詳細を見る
«
»