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

这个树遍历代码中的bug在哪里?

html-agility-pack c#

mpen · 技术社区 · 14 年前

Traverse() 这导致它多次迭代节点。

有漏洞的代码

public IEnumerable<HtmlNode> Traverse()
{
    foreach (var node in _context)
    {
        yield return node;
        foreach (var child in Children().Traverse())
            yield return child;
    }
}

public SharpQuery Children()
{
    return new SharpQuery(_context.SelectMany(n => n.ChildNodes).Where(n => n.NodeType == HtmlNodeType.Element), this);
}

public SharpQuery(IEnumerable<HtmlNode> nodes, SharpQuery previous = null)
{
    if (nodes == null) throw new ArgumentNullException("nodes");
    _previous = previous;
    _context = new List<HtmlNode>(nodes);
}

    static void Main(string[] args)
    {
        var sq = new SharpQuery(@"
<a>
    <b>
        <c/>
        <d/>
        <e/>
        <f>
            <g/>
            <h/>
            <i/>
        </f>
    </b>
</a>");
        var nodes = sq.Traverse();
        Console.WriteLine("{0} nodes: {1}", nodes.Count(), string.Join(",", nodes.Select(n => n.Name)));
        Console.ReadLine();

输出

19个节点:#document,a,b,c,g,h,i,d,g,h,i,e,g,h,i,f,g,h,i

预期产量

好像不知道哪里出了问题。。。 node.ChildNodes 做直接带孩子回去,对吧?(来自HtmlAgilityPack)

全班(浓缩)如果你想自己尝试运行它。

public class SQLite
{
    private readonly List<HtmlNode> _context = new List<HtmlNode>();
    private readonly SQLite _previous = null;

    public SQLite(string html)
    {
        var doc = new HtmlDocument();
        doc.LoadHtml(html);
        _context.Add(doc.DocumentNode);
    }

    public SQLite(IEnumerable<HtmlNode> nodes, SQLite previous = null)
    {
        if (nodes == null) throw new ArgumentNullException("nodes");
        _previous = previous;
        _context = new List<HtmlNode>(nodes);
    }

    public IEnumerable<HtmlNode> Traverse()
    {
        foreach (var node in _context)
        {
            yield return node;
            foreach (var child in Children().Traverse())
                yield return child;
        }
    }

    public SQLite Children()
    {
        return new SQLite(_context.SelectMany(n => n.ChildNodes).Where(n => n.NodeType == HtmlNodeType.Element), this);
    }
}

6 回复 | 直到 14 年前

Frédéric Hamidi 11 年前

首先,请注意,只要我们在没有任何兄弟元素的元素上迭代,一切都会按照计划进行。一碰到元素 <c> ,事情开始变得一团糟。有趣的是 < , <d> 和 <e> 所有人都认为它们包含 <f>

让我们仔细看看你打给 SelectMany() :

_context.SelectMany(n => n.ChildNodes)

在 _context 累积每个项的子节点。让我们看看 _上下文 List 长度 1 . 还是这样?

我怀疑你 SharpQuery(string) 可能没有长度 1个 选择多个() 累积列表中每个项的子节点。

_上下文 是一个包含 <c> , <d> , <e> <f> <f> 有孩子,而且 选择多个() <f> 四次。

我想那是你的虫子。

编辑: 既然你把全班都发了,我就不用再猜了。当你迭代的时候看看操作的顺序 <b> (为了更好地理解,用列表替换了迭代器):

呼叫 Children() 在 <b> ,它返回 <c> , <d> , <e> <f>
呼叫 Traverse() 在结果列表中:
1. 呼叫在 <c> , 但是 _上下文 实际包含 <c> <d> <e> 和 < ,不仅如此 < ,以便返回 <g> , <h> <i> ,
2. 呼叫 子项() 在 < ,同样的事情 _上下文 相同的 二者都 <c> <d> <e> <f> ),

Robert Jeppesen 14 年前

Children()已断开,它还选择兄弟姐妹的子级。我会重写如下:

public IEnumerable<HtmlNode> Traverse(IEnumerable<HtmlNode> nodes)
{
    foreach (var node in nodes)
    {
        yield return node;
        foreach (var child in Traverse(ChildNodes(node)))
            yield return child;
    }
}

private IEnumerable<HtmlNode> ChildNodes(HtmlNode node)
{
    return node.ChildNodes.Where(n => n.NodeType == HtmlNodeType.Element);
}


public SharpQuery(IEnumerable<HtmlNode> nodes, SharpQuery previous = null)
{
    if (nodes == null) throw new ArgumentNullException("nodes");
    _previous = previous; // Is this necessary?
    _context = new List<HtmlNode>(nodes);
}

500 - Internal Server Error 14 年前

这还不够吗?

public IEnumerable<HtmlNode> Traverse()
{
    foreach (var node in _context)
    {
        Console.WriteLine(node.Name);
        yield return node;
        foreach (var child in Children().Traverse())
            {} //yield return child;
    }
}

Wildhorn 14 年前

我说不清楚,但你可以看到这样的模式,一旦你的东西遇到“c”的“/”,它就开始认为“g,h,I”是随后每个字母的一部分,直到它遇到“f”的“/”。

很可能你有一个额外的循环,你应该得到骑。

dexter 14 年前

我想做这样的事情,看看是否能解决问题:

public IEnumerable<HtmlNode> Traverse()
{
foreach (var node in _context)
{
    Console.WriteLine(node.Name);
    if(!node.HasChildren) {
     yield return node;
    }
    else {
    foreach (var child in Children().Traverse())
        yield return child;
    }
    }
}
}

Community Ian Goodfellow 7 年前

public IEnumerable<HtmlNode> All()
{
    var queue = new Queue<HtmlNode>(_context);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        yield return node;
        foreach (var next in node.ChildNodes.Where(n => n.NodeType == HtmlNodeType.Element))
            queue.Enqueue(next);
    }
}

courtesy link