代码之家 › 专栏 › 技术社区 › cllpse

LINQ与递归

recursion linq c#

cllpse · 技术社区 · 14 年前

请考虑以下几点:

public class Box
{
    public BoxSize Size { get; set; }

    public IEnumerable<Box> Contents { get; set; }
}

Box FindBoxBySize(Box box, BoxSize size)
{
    Box _foundBox = null;

    Action<IEnumerable<Box>> _recurse = null;

    _recurse = new Action<IEnumerable<Box>>(boxes =>
    {
        foreach (var _box in boxes)
        {
            if (_box.Size == size)
            {
                _foundBox = _box;

                return;
            }

            if (_box.Contents != null) _recurse(_box.Contents);
        }
    });

    _recurse(box.Contents);

    return _foundBox;
}

有办法吗 FindBoxBySize() 可以用LINQ压实吗?另外:欢迎对我的代码发表评论。我不做太多递归,所以我可能在实现中遗漏了一些东西。

4 回复 | 直到 14 年前

Enigmativity 14 年前

我也会使用扩展方法,但使用迭代器方法:

public static class BoxEx
{
    public static IEnumerable<Box> Flatten(this Box box)
    {
        yield return box;
        if (box.Contents != null)
        {
            foreach (var b in box.Contents.SelectMany(b2 => Flatten(b2)))
            {
                yield return b;
            }
        }
    }
}

你的 FindBoxBySize 方法现在变成:

Box FindBoxBySize(Box box, BoxSize size)
{
    return (from b in box.Flatten()
            where b.Size == size
            select b).FirstOrDefault();
}

您的原始呼叫代码无需修改即可工作:

var small = FindBoxBySize(box, BoxSize.Small);

abatishchev Marc Gravell 14 年前

扩展方法:

class Box
{
    public IEnumerable<Box> GetBoxes()
    {
        // avoid NullReferenceException
        var contents = this.Contents ?? Enumerable.Empty<Box>();

        // do the recursion
        return contents.SelectMany(b => b.GetBoxes()).Concat(contents);
    }

    public Box GetBox(int size)
    {
        return this.GetBoxes().FirstOrDefault(b => b.Size == size);
    }
}

用法:

var box_with_box = new Box { Contents = new[] { new Box() { Size = 10 } } };
var box = new Box { Contents = new[] { box_with_box, box_with_box } };

Box box10 = box.GetBox(10);

Ani 14 年前

public static IEnumerable<Box> GetBoxesRecursive(this Box box)
{
  if(box == null)
      throw new ArgumentNullException("box");

  var children = box.Contents ?? Enumerable.Empty<Box>();

                           // use lambda in C# 3.0      
  var recursiveChildren = children.SelectMany(GetBoxesRecursive);  

  return new[] { box }.Concat(recursiveChildren);                                    
}

...    

Box desiredBox = myBox.GetBoxesRecursive()
                      .FirstOrDefault(b => b.Size == desiredSize);

Jens 14 年前

你可以(在我眼里)通过写作使你的递归更清晰一些

Box FindBoxBySize(Box box, BoxSize size)
{
    if (box.Size == size)
        return box;

    foreach (var child in box.Contents)
    {
        var foundBox = FindBoxBySize(child, size);
        if(foundBox != null)
            return foundBox;
    }

    return null;
}

至于LINQ:LINQ没有一个处理递归数据结构的好方法。有几种不同的扩展方法可以通过向google请求“LINQ递归”来弥补,但我不确定它们是否在本例中增加了清晰性。