c＃遞歸泛型數據結構搜索

Question

已經掙扎了幾天，現在仍然難倒。 我有一個數據結構，從可以容納其他容器的容器開始，最後是葉節點。我正在尋找一種直接迭代類型元素的方式，而不需要將它們拉入另一個集合中，這樣我就可以對它們進行操作，然後將結果保存到外面。

下面的代碼是一個noddy版本，如果你在每個findElements函數上設置一個斷點，你會發現它沒有遞歸就退出。這是單聲道和MS運行時間，所以我敢肯定，這是我沒有得到的東西，而不是一個錯誤;）

也，功能最好應

IEnumerable<object> findElements<T>(); 

，但我不能讓投要在這一行工作，那麼：

if (this is T) yield return this; 

理論上應

if (this is T) yield return (T)this; 

感謝您的任何建議/ CLA rity/light

using System; 
using System.Collections.Generic; 
using System.Text; 

namespace covariantTest { 
class MainClass { 
    public static void Main(string[] args) { 
     Console.WriteLine("Starting"); 
     Document root = new Document("rooty"); 
     root.Children.Add(new File("file 1")); 
     root.Children.Add(new File("file 2")); 
     Document doc2 = new Document("doc2"); 
     File file3 = new File("file 3"); 
     file3.Lines.Add(new Line("line 1 file 3")); 
     file3.Lines.Add(new Line("line 2 file 3")); 
     doc2.Children.Add(file3); 
     File file4 = new File("file 4"); 
     file4.Lines.Add(new Line("stuff about stuff")); 
     file4.Lines.Add(new Line("Babylon n ting")); 
     file4.Lines.Add(new Line("last line")); 
     doc2.Children.Add(file4); 
     root.Children.Add(doc2); 

     // find the lines 
     foreach (object obj in root.findElements<Line>()) { 
      Line line = obj as Line; 
      Console.WriteLine(line.Contents); 
     } 
     // done 
     Console.WriteLine("Press enter to finish"); 
     Console.ReadLine(); 
    } 
}// Main 

#region classes 
public class Line : ISearchable { 
    private string _contents = string.Empty; 

    public Line() {} 
    public Line(string contents) { 
     _contents = contents; 
    } 
    #region properties 
    public string Contents { 
     get { return _contents; } 
     set { _contents = value; } 
    } 
    #endregion properties 
    public IEnumerable<object> findElements<T>() { 
     if (this is T) yield return this; 
    } 
}// Line 

public class File : Container { 
    private List<Line> _lines = new List<Line>(); 

    public File() : base() {} 
    public File(string name) : base(name) {} 

    #region properties 
    public List<Line> Lines { 
     get { return _lines; } 
     set { _lines = value; } 
    } 
    #endregion properties 
    public override IEnumerable<object> findElements<T>() { 
     if (this is T) yield return this; 
     else base.findElements<T>(); 
    } 
}// File 

public class Document : Container { 

    public Document() : base() {} 
    public Document(string name) : base(name) {} 

    public override IEnumerable<object> findElements<T>() { 
     if (this is T) yield return this; 
     else base.findElements<T>(); 
    } 

}// Document 

public abstract class Container : ISearchable { 
    private string _name = string.Empty; 
    private List<Container> _children = new List<Container>(); 

    public Container() {} 
    public Container(string name) { 
     _name = name; 
    } 
    #region properties 
    public string Name { 
     get { return _name; } 
     set { _name = value; } 
    } 
    public List<Container> Children { 
     get { return _children; } 
     set { _children = value; } 
    } 
    #endregion properties 
    #region interfaces 
    public virtual IEnumerable<object> findElements<T>() { 
     if (this is T) yield return this; 
     foreach (Container item in _children) { 
      item.findElements<T>(); 
     } 
    } 
    #endregion interfaces 
}// Container 
#endregion classes 

#region interfaces 
public interface ISearchable { 
    IEnumerable<object> findElements<T>(); 
} 
#endregion interfaces 
}// namespace 

Answer 1

我覺得你的代碼有點複雜，但是我可能對你的目標不瞭解。
無論如何，這裏是一個樣本，以「平坦時尚」的方式掃描你的樹。我也用一個非常小的代碼來演示，但顯然你必須努力。

namespace ConsoleApplication3 
{ 
    //this is a node of your tree, but you may add whatever you want inside 
    class Item 
    { 
     public List<Item> Items { get; set; } 
    } 


    class Program 
    { 
     static void Main(string[] args) 
     { 
      //define the tree structure 
      var tree = new Item(); 

      // (complete your tree-structrure) 

      //define the action delegate 
      Action<Item> action = (item) => Console.WriteLine(item); 

      //scan the hierarchy 
      Scan(
       tree, 
       typeof(Item), 
       action); 
     } 


     //here is the flat-scan function, the "typeToFind" here is just 
     //for example and have very little sense to be in 
     static void Scan(
      Item startItem, 
      Type typeToFind, 
      Action<Item> action) 
     { 
      var temp = new List<Item>(); 
      temp.Add(startItem); 

      while (temp.Count > 0) 
      { 
       var item = temp[0]; 
       temp.RemoveAt(0); 

       if (typeToFind.IsInstanceOfType(item)) 
       { 
        action(item); 
       } 

       temp.AddRange(item.Items); 
      } 
     } 
    } 
} 

希望這會有所幫助。乾杯。

Answer 2

您如何期待它的工作？如果我理解正確，那麼從另一個函數調用yield時不起作用（所以如果你調用base.findElements，那麼你不會從它得到任何結果）。我建議重寫它而不收益。爲了避免造成許多名單，我會通過列表作爲參數，以這樣的方式：

public interface ISearchable { 
    void doFindElements<T>(List<T> putThemHere); 
} 

// this is extender for syntactical sugar 
public static class SearchableExtender 
{ 
    public static IEnumerable<T> findElements<T>(this ISearchable obj) 
    { 
     List<T> result = new List<T>(); 
     obj.doFindElements(result); 
     return result; 
    } 
} 

public abstract class Container : ISearchable { 
... 
    public virtual void doFindElements<T>(List<T> putThemHere) 
    { 
     if (this is T) putThemHere.Add(this); 
     foreach (Container item in _children) { item.doFindElements(putThemHere); } 
    } 
... 
} 

順便說一句，你不需要重寫doFindElements在文件中，繼承容器版本會做OK，如「這」意味着一個文件在這裏。 File的實現是完全錯誤的。 Base Container類不會看到Lines屬性，而是使用空的Children屬性。有兩種方法可以解決此問題：

1. 你需要殺死_lines，而是與_children從基類的工作（例如，你可以讓Collection<Line>後代，這將是圍繞_children類的包裝通過重寫InsertItem ，SetItem，RemoveItem和ClearItems並調用適當的方法_children）。

2. 從容器中取出_children，反而讓虛擬抽象函數IEnumerable GetChildElements()每個後代將實現並返回它的子元素的自己List<>。在doFindElements中，您將調用該函數而不是_children。您甚至可以創建第二個基類，如UntypedContainer：將聲明List<Container> _children的容器，覆蓋GetChildElements()以返回_children並從中繼承Document。文件仍然會從簡單的容器繼承，因爲它有自己的子列表。

第二種方法更簡單，更好。