1

ハフマンが残した手続きを書こうとしています。このプロシージャは、作成されたハフマン ツリーからペアのリストを返します。実行方法の例

  (huffman-leaves sample-tree) 
   ->((A . 8) (C . 5) (B . 1) (D . 1))

私が思いついたが、作家がブロックしたこと...

(define (huffman-leaves tree)
  (define (huffman-get-pairs current-branch pairs)
     (if (or (null? tree) (null? current-branch))
         pairs
         (let ((next-branch
                (get-branch (car current-branch) current-branch)))
           (not (member? next-branch pairs)
                (if (leaf? next-branch)
                    (cons (append  pairs next-branch)
                          (display pairs)
                          (huffman-get-pairs (cadr current-branch) pairs))
                    (huffman-get-pairs next-branch pairs))))))
  (huffman-get-pairs tree '()))

  (member? item 'list) #if item in list return #t else #false

私は何か間違ったことをしていることを知っていますが、それを見ることはできません。スキームでハフマンツリーの検索を停止するにはどうすればよいですか? 私が違うことをしなければならないヒントはありますか？

4

1 に答える 1

3

私はお勧め：

  1. ハフマン木のデータ定義を書く

  2. ステップ 1 のデータ定義に従ってエンコードされた入力ハフマン ツリーの例と、期待される出力 (この場合は葉のリスト) を作成します。

  3. デザイン レシピに従って、関数の基本的なテンプレートを作成しhuffman-leavesます。

  4. ...ステップ 2 で作成した例に従って、テンプレートに入力します。

  5. ステップ 2 の例をテストに変換し、ステップ 4 のコードをテストします。

上記が漠然としているように思われる場合は申し訳ありませんが、これまでにこの質問で提供された詳細のレベル (または詳細の欠如) を考慮して、私が提供できる最善のアドバイスです。上記の手順に対する回答を提供し、どの手順でブロックされているかを明示していただければ、より体系的な方法でライターのブロックを乗り越えることができます。

実際のコードを好む場合は、問題の非常に一般的な解決策を作成するために使用できる 1 つの方向を次に示します。

;; make-visitor : (X -> Y) (X -> [Listof X]) (Y [Listof Z] -> Z) -> Z
;; Very generic descend+map+recombine routine
;; (note X, Y, Z are implicitly universally quantified above).
(define (make-visitor transform children combine)
  (lambda (x)
    (let rec ((x x)) ;; rec : X -> Z
      (combine (transform x)
               (map rec (children x))))))

;; ... the hard bit is coming up with the appropriate lambda
;; expressions for `transform`, `children`, and `combine` above.

(define leaves
  (make-visitor (lambda (x) ...)
                (lambda (x) ...)
                (lambda (y zs) ...)))

この形式のソリューションに直接ジャンプしようとすることは実際にはお勧めしません。設計のレシピに従って、問題を直接解決しようとすると、より良い結果が得られます。しかし、一度それを行ったら、上記の一般的なルーチンに独自のソリューションを後付けできるかどうかを確認するための教育的な演習になる可能性があります。

于 2013-03-12T01:28:42.197 に答える