C#具有多个分支的链接列表

Question

我一直在努力完成我的任务,但我不知道如何创建一个包含多个分支的链表.我已经提取了我的数据,将其缩小,然后将其存储在List中.

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

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>是在内部使用Array实现的..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;
    }
}

你可以在这里找到工作演示