C# 具有多个分支的链表

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 7 年前。

Improve this question

我一直在尝试完成我的作业，但我不知道如何创建具有多个分支的链表。我提取了数据，缩小了范围，然后将其存储在列表中。

List<Route> routes = new List<Route>();

路线包含两个字符串变量:city1Name 和 city2Name。

Route route = new Route("FirstCity", "SecondCity");

这意味着 FirstCity 和 SecondCity 之间有一条路线。每个城市可以有多条通往其他城市的路线。

有人可以告诉我如何将此数据存储在链接列表中吗？我了解链表是什么，我想我可以随后使用 foreach 获取多个可能的路线数据，但我无法为此编写算法。 :(

Answer 1

您可以使用 List<T>.Add 附加 T 类型的任何项目而 T 可以是任何符合 .NET 的数据类型。在你的情况下T是 Route 。因此，您可以附加任何可以隐式转换为 Route 的值。

routes.Add(route);

此外，在 .NET 中 List<T>不是链接列表。 List<T> is implemented using Array internally 。 .NET 中的链接列表实现是 LinkList<T>

编辑

这是一个非常简单的实现，用于查找从一个城市到另一个城市的路径。

static bool TryFindPath(List<Route> routes, string from, string to, int maxDepth) {

    if (maxDepth <= 0) // To prevent StackOverFlowException
        return false;

    // Find all the routes with starting point == `from`
    var startingPoints = Routes.Where(r => r.From == from).ToArray();
    if (startingPoints.Length == 0) // No such route exists
        return false;

    // See if any of route directly leads to `to`
    var matchingRoute = startingPoints.Where(r => r.To == to).FirstOrDefault();
    if (matchingRoute != null) {
        routes.Add(matchingRoute); // If so, we found that
        return true;
    }


    // We are stepping into next level, decrease maxDepth by one
    maxDepth -= 1;

    // Otherwise iterate through all starting points and find path from
    // that specific city refered by to our destination 
    foreach (var route in startingPoints) {

        // Clone `routes`
        var thisRoutes = new List<Route>(routes);
        thisRoutes.Add(route);

        if (TryFindPath(thisRoutes, route.To, to, maxDepth)) {

            // Copy all newly added routes in `thisRoutes` to original `routes` 
            for (var i = routes.Count; i < thisRoutes.Count; i++) {
                routes.Add(thisRoutes[i]);
            }

            return true;
        }
    }

    return false;
}

我假设遵循 Route 类的定义

class Route {

    public string From { get; set; }
    public string To { get; set; }

    public Route(string from, string to) {
        From = from;
        To = to;
    }
}

您可以找到工作演示 here