霍夫曼解码（斯卡拉）

我想写一个算法来执行霍夫曼解码。我在Scala中完成它 - 这是Coursera课程的一个任务，我不想违反荣誉代码，所以下面是伪代码而不是Scala。霍夫曼解码（斯卡拉）

我写的算法需要树tree和位列表bits，并且应该返回消息。但是，当我在提供的树上尝试它时，我得到一个NoSuchElementException（空列表的头）。我看不出为什么。

我知道我的代码可以整理一下 - 我对函数式编程还是很新的，所以我用一种对我来说很有意义的方式编写代码，而不是以最紧凑的方式编写代码。

def decode(tree, bits) [returns a list of chars]: { 

    def dc(aTree, someBits, charList) [returns a list of chars]: { 

     if aTree is a leaf: 

      if someBits is empty: return char(leaf) + charList 
      else: dc(aTree, someBits, char(leaf) + charList) 

     else aTree is a fork: 

      if someBits.head is 0: dc(leftFork, someBits.tail, charList) 
      else someBits is 1: dc(rightFork, someBits.tail, charList) 
     } 

    dc(tree, bits, [empty list]) 

    }

在此先感谢您的帮助。这是我第一次在StackOverflow上，所以我可能有一些学习如何最好地使用该网站。

来源

2017-02-22 gadje

如果我理解正确，你想通过分叉（从位的方向），直到你会找到一片叶子。然后，您将为您的char列表添加叶值，并从这一点开始您要重复步骤。如果我是对的，那么你应该把原始树传递给你的帮助方法，而不是现在是叶的leftFork或rightFork。所以它会是这样的：

if aTree is a leaf: 
    if someBits is empty: return char(leaf) + charList 
    else: dc(tree, someBits, char(leaf) + charList)

来源

2017-02-22 13:42:19 Rumid

太棒了！谢谢。这正是问题所在。在我的脑海中，屏幕上出现错误。 – gadje

我很高兴能帮上忙。你可以批准一个答案吗？：P – Rumid

哈，是的，对不起，新的。 – gadje

霍夫曼解码（斯卡拉）

回答

相关问题