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

防止父/子层次结构中无限递归的防御代码

stack-overflow parent-child c#

OJay · 技术社区 · 6 年前

像这样的

public class Thing
{  
    public Thing() { this.children = new List<Thing>();}

    public int Id {get; set;}       
    public string Name {get; set;}      
    public List<Thing> children{ get; set;}

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

如果被使用(滥用!)以这样的方式

public static void Main()
{
    var root = new Thing{Id = 1,Name = "Thing1"};       
    var thing2 = new Thing{Id = 2,Name = "Thing2"};             
    var thing3 = new Thing{Id = 3,Name = "Thing3"};     
    root.children.Add(thing2);
    thing2.children.Add(thing3);                         
    thing3.children.Add(root);  //problem is here       
    Console.WriteLine(root.ToString());     
}

防守的 关于这种情况。

现在的代码生成一个 堆栈溢出、无限递归或内存超出错误 .

在(IIS)网站中,这导致w3工作进程崩溃,最终导致应用程序池关闭(快速故障保护)

数据库表结构类似于

CREATE TABLE Thing(
    Id INT NOT NULL PRIMARY KEY,
    Name NVARCHAR(255) NOT NULL,
    ParentThingId INT NULL //References self
)

所以可以说,结构可以是循环的,但是如果你想在网页上呈现这种结构,可以说是循环的 <ul><li><a>

.NET小提琴 here

3 回复 | 直到 6 年前

Magnus 6 年前

一种方法是在递归调用中包含访问节点的集合。如果你在一个周期之前被拜访。

public string ToString(int level = 0, HashSet<int> visited)
{
        foreach(var child in children)
        {
                if(visited.Add(child.Id))
                   sb.Append(child.ToString(level + 1, visited));
                else
                   //Handle the case when a cycle is detected.
        }       
        return sb.ToString();
}

stephanV 6 年前

您可以展开树结构,方法是将每个元素放在堆栈或队列上,并在集合有项时弹出其中的项。在while循环中,您将每个项的子项放在队列中。

如果您关心树中项目的级别,您可以使用存储该级别的helper对象。

展开树时,您可以将每个项放在新列表中,并将其用作循环问题的参考。

Damien_The_Unbeliever 6 年前

如果你能a)消除想要循环引用的可能性,b)保证所有的子级在父级被创建时都已经知道,那么这是一个让子级成为 不变的 仅通过构造函数设置的集合。

这就给了你一个类,通过结构递归,你知道它不能包含任何循环,不管整个结构有多大。比如:

public sealed class Thing
{  
    public Thing(IEnumerable<Thing> children) {
      this._children = children.ToList().AsReadOnly();
    }

    private readonly ReadOnlyCollection<Thing> _children;

    public int Id {get; set;}       
    public string Name {get; set;}      
    public IEnumerable<Thing> children {
       get {
         return _children;
       }
    }

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}