1

我正在尝试编写一个 Huffman-leaves 程序；该过程从创建的霍夫曼树中返回一个对列表。运行方式示例

  (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. 为 Huffman 树编写数据定义

  2. 制作示例输入霍夫曼树，根据步骤 1 中的数据定义和预期输出（在本例中为叶子列表）进行编码。

  3. 按照设计配方为该huffman-leaves功能构建一个基本模板。

  4. ...根据您在步骤 2 中构建的示例填写模板。

  5. 将步骤 2 中的示例转换为测试，并测试步骤 4 中的代码。

抱歉，如果上述内容似乎含糊不清，但这是我迄今为止在此问题中提供的详细程度（或缺乏详细程度）所能提供的最佳建议。如果您可以为上述步骤提供答案，并明确说明您被阻止的步骤，那么我们可以帮助您以更系统的方式克服您的作家阻止。

如果您更喜欢真正的代码，您可以按照以下方向为您的问题制定一个非常通用的解决方案：

;; 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 回答