c#实现哈夫曼树算法

今天看了一下数据结构，一个练习就是构建哈夫曼树，就顺手用C#写了一个。

static void Main(string[] args)
{
    var numbers = new int[] { 1, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7 };

    var treeList = new List<HuffmanTree>();
    treeList.AddRange(from n in numbers
                     group n by n into g
                     select new HuffmanTree { Value = g.Key, Degree = g.Count() });

    while (treeList.Count>1)
    {
        var sel = from i in treeList
                 orderby i.Degree ascending
                 select i;
        var min = sel.Take(2).ToArray();

        treeList.Add(new HuffmanTree { Left = min[0], Right = min[1], Degree = min[0].Degree + min[1].Degree });

        treeList.Remove(min[0]);
        treeList.Remove(min[1]);
    }
}

class HuffmanTree
{
    public HuffmanTree Left { get; set; }
    public HuffmanTree Right { get; set; }

    public int Value { get; set; }
    public int Degree { get; set; }

    public override string ToString()
    {
        return Value + " " + Degree;
    }
}

我用LINQ很直接的写出了这段代码，写完后我都觉得有点吃惊：基本上每一步都只用了一句话完成了，并且都是自注释的，写得让人感觉十分流畅。

虽然这个实现运行效率不高，还有一些可以优化的地方，但我却非常喜欢这种简洁、高效（开发效率）的代码，看着十分舒服。这也是C#的一个十分让我入迷的地方->优雅：可以将心中的想法快速用代码表现出来，高屋建瓴，一气呵成，不必于在拘泥于细节。很多时候，在细节实现苦苦琢磨的时往往会忘记最开始突发的灵感和编程的乐趣。

同时我想起了前几天发的一个算法练习的帖子，虽然用C#可以在20行之内实现，但一大片经验丰富的程序员在4个小时之内用C语言（不能使用任何库）却无法完成。我想，对那同一个题目，用20行和用200行实现的时候的人心情是截然不同的吧。

到此这篇关于c#实现哈夫曼树的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持自由互联。