0

我有一个小问题，我想听听你的意见。

我正在处理文件而不是参考其他文件。从任何文档开始，我都需要获取该文档引用的所有文档的 ID。问题是允许循环引用，所以如果 A ref B ref C，C 可以再次引用 A，我进入循环。如何在 C# 中解决这个问题？

一个小例子：

假设这是一个代表文档的类：

public class Document
{
    public Document(int id)
    {
        this.ID = id;
    }

    private int m_ID;

    public int ID
    {
        get { return m_ID; }
        set { m_ID = value; }
    }

    private List<Document> m_Children = new List<Document>();

    public List<Document> Children
    {
        get { return m_Children; }
        set { m_Children = value; }
    }

    private List<Document> m_Parent = new List<Document>();

    public List<Document> Parent
    {
        get { return m_Parent; }
        set { m_Parent = value; }
    }

    public Document AddChild(Document child)
    {
        child.Parent.Add(this);
        this.Children.Add(child);

        return child;
    }

    public Document AddChild(int child)
    {
        Document d = new Document(child);

        return AddChild(d);
    }
}

现在让我们创建一个包含一些引用的 Document 类：

public static Document CreateReferences()
{
    Document d = new Document(1);

    Document temp = d.AddChild(2);

    for (int i = 3; i < 6; i++)
    {
        temp = temp.AddChild(i);
    }

    temp.AddChild(d);

    return d;
}

现在我需要在 Document 类中实现一个方法，比如

public List<int> GetReferencedDocuments()
{    }

最好的方法是什么？可以实现任何特定的算法吗？

任何建议都会被接受！

谢谢

4

4 回答 4

4

任何树遍历算法都可以。

除了您要建立的文档列表之外，维护一个您尚未检查的文档队列，将第一个文档添加到该列表中。

然后，当队列不为空时，获取下一个文档，如果它不在您的列表中，然后添加它，并将所有引用的文档添加到您的队列中。

List<Document> FoundDocs = new List<Documents();
Queue<Document> DocsToSearch = new Queue<Document>();

DocsToSearch.Enqueue(StartDoc);

while(DocsToSearch.Count != 0)
{
    Document Doc = DocsToSearch.Dequeue();
    if(!FoundDocs.Contains(Doc))
    {
        FoundDocs.Add(Doc);
        foreach(var ChildDoc in Doc.Children)
        {
            DocsToSearch.Enqueue(ChildDoc);
        }
    }
}
于 2011-07-01T08:16:26.177 回答
0

最好的方法是进行深度优先搜索或广度优先搜索

于 2011-07-01T08:15:18.213 回答
0

解决这种对递归数据的递归搜索的主要方法有两种：标记或记录。

标记：每次列出文档时，将其标记为已查看。不要处理标记的文档。

所以你的 GetReferenceDocuments 看起来有点像这样：

GetReferencedDocuments（起点）

如果（起点。标记）返回空

起点标志

新列表结果=起点

foreach（子文档在

文件.儿童）

result.append(getreferenceddocuments(subdocuments))// 如果不为空

记录：类似的方法，但标志指示符被已引用文档的列表替换（可能是单独的 id 列表），并且标志检查是在此列表中搜索此文档。

根据您的对象、大小和比例，任何一种方式都可以。如果您无法更改文档对象，则必须列出它们。如果您的扫描中可能有 1M 文档，则您不想列出它们。

于 2011-07-01T08:30:28.510 回答
0

示例实现：

public List<int> GetReferencedDocuments()
{    
    var referencedIds = new List<int>();
    var queue = new Queue<Document>(this);
    while (queue.Count > 0)
    {
         var newDocuments = queue.Dequeue().Children
                                           .Where(d => !referencedIds.Contains(d.ID))
         foreach (Document newDocument in newDocuments) 
         {
             queue.Enqueue(newDocument);
             referencedIds.Add(newDocument.ID);
         }
    }
    return referencedIds;
}
于 2011-07-01T08:34:35.123 回答