Недавно мне выполнили требование, согласно которому мне нужно было получить список записей базы данных из таблицы с самосоединением, в которой каждая запись также предоставляла бы полную иерархию этого соединения в обратном порядке.
Для дальнейшего объяснения представьте семейное древо, описанное в одной таблице. Конечно, у каждой записи есть свой первичный ключ, но также будет поле «ParentID» для описания иерархии. Самый верхний родительский элемент может содержать «null», и каждый дочерний элемент будет хранить первичный ключ другой родительской записи в таблице в поле «ParentID». А теперь представьте, что перебираете эти записи в цикле и создаете для каждой новую строку, которая будет содержать иерархию, снизу вверх.
Рекурсия может быть первым, что приходит вам в голову, и вы были бы правы! Обычно вы используете рекурсию в обратном направлении (сверху вниз) для обычных задач, что может сначала сбить с толку эту конкретную проблему. Хороший алгоритм для снизу вверх, который я собираюсь вам показать, называется сначала в глубину.
Вот краткое руководство по использованию подхода, ориентированного на глубину, для получения иерархических данных в обратном порядке на C #.
Мы собираемся подделать данные генеалогического древа, описанные ранее, в простой коллекции List в простом консольном приложении C #.
Во-первых, давайте смоделируем наши фиктивные данные в едином классе под названием Item.
public class Item {
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public string Path { get; set; }
public Item(int id, int parentId, string name) {
Id = id;
ParentId = parentId;
Name = name;
}
}
У нас есть «самосоединяющиеся» первичный и внешний ключи с Id и ParentId. Имя описывает создаваемый элемент, а Путь будет использоваться для хранения обратной последовательности полной иерархии каждого элемента в глубину, поскольку каждый элемент анализируется для его определения.
Скоро все это станет более понятным.
Продолжая, давайте создадим наши данные из этого класса сущности в методе Main программы.
static void Main(string[] args) {
var items = new List<Item>() {
new Item(1, 0, “Ralph”),
new Item(2, 1, “Ron”),
new Item(3, 2, “Vin”),
new Item(4, 3, “Armando”),
new Item(5, 3, “Alex”),
new Item(6, 3, “Ana”)
};
}
Это мое генеалогическое древо, начиная с моего деда Ральфа и заканчивая моим младшим ребенком Аной. Я использовал ноль в свойстве / параметре ParentId, чтобы определить самую верхнюю запись в иерархии, у которой нет родителя.
Теперь, как нам это осуществить? Какую садистскую логику сумасшедшего ученого нужно придумать, чтобы выполнить это безумное требование? Это на удивление легко благодаря Делегатам C # и синтаксису Lambda. Этого можно достичь с помощью краткого 15-строчного выразительного кода.
static string GetParentsString(List<Item> all, Item current) {
string path = “”;
Action<List<Item>, Item> GetPath = null;
GetPath = (List<Item> ps, Item p) => {
var parents = all.Where(x => x.Id == p.ParentId);
foreach (var parent in parents) {
path += $”/{parent.Name}”;
GetPath(ps, parent);
}
};
GetPath(all, current);
string[] split = path.Split(new char[] { ‘/’ });
Array.Reverse(split);
return string.Join(“/”, split);
}
Сначала это может показаться немного странным, но позвольте мне разбить его построчно. Во-первых, я объявил полное строковое значение иерархии в глубину, которое собираюсь построить. Затем я объявляю делегат действия, который я определяю в следующей строке. По сути, это функция, которая принимает в качестве параметров полный список объектов Item и один элемент. Таким образом, я могу описать метод срабатывания позже, который будет создавать значение переменной path. Фактически, это происходит сразу после этого на линии.
Почему?
Это называется «закрытием» или функцией внутри функции, которая имеет доступ к окружающей области. В этом случае я могу вызвать GetPath внутри этого метода GetParentsString, получить значение моего пути и вернуть его в потокобезопасном режиме. Я не пишу в глобальную переменную, что может быть небезопасно в контексте, в котором я использую этот код. По сути, это самодостаточный механизм, в котором вы можете передать все свои элементы и ваш «текущий элемент» в цикле и получить строку пути полной иерархии, которую я обсуждал. .
Сам делегат GetPath является немного более запутанным. Он проверяет весь список объектов Item на предмет любых, которые соответствуют родительскому элементу текущего элемента. Проще говоря: «Дайте мне всех родителей этого предмета». Затем он просматривает результаты в списке родителей и записывает значение пути. Возможно, вы заметили, что он вызывает себя позже внутри цикла. Здесь мы используем рекурсию для перемещения вверх по иерархии, пока не исчерпаем родительский узел Item s. Передав тот же список всех объектов Item, а также текущий родительский элемент в цикле, он проверяет себя и записывает в строку путь. значение, пока в списке не останется ни одного родителя.
Последние несколько строк GetParentsString имеют дело с изменением порядка наших результатов на обратный и их форматированием для представления.
Быстрый и функциональный способ просмотреть эти записи, чтобы увидеть результаты, - это одна строка кода. Поместите это под списком сущностей предметов, которые мы определили в самом начале.
items.ForEach(item => Console.WriteLine($”({item.Id}): {item.Name} {GetParentsString(items, item)}”));
Уф! Это сложно переварить в небольшом фрагменте кода. Чтобы лучше это понять, предлагаю попробовать самому. Вот весь класс и весь проект в одном файле.
using System;
using System.Collections.Generic;
using System.Linq;
namespace DepthFirstTreeTraversal {
public class Item {
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public string Path { get; set; }
public Item(int id, int parentId, string name) {
Id = id;
ParentId = parentId;
Name = name;
}
}
class Program {
static void Main(string[] args) {
var items = new List<Item>() {
new Item(1, 0, “Ralph”),
new Item(2, 1, “Ron”),
new Item(3, 2, “Vin”),
new Item(4, 3, “Armando”),
new Item(5, 3, “Alex”),
new Item(6, 3, “Ana”)
};
items.ForEach(item => Console.WriteLine($”({item.Id}): {item.Name} {GetParentsString(items, item)}”));
Console.ReadLine();
}
static string GetParentsString(List<Item> all, Item current) {
string path = “”;
Action<List<Item>, Item> GetPath = null;
GetPath = (List<Item> ps, Item p) => {
var parents = all.Where(x => x.Id == p.ParentId);
foreach (var parent in parents) {
path += $”/{parent.Name}”;
GetPath(ps, parent);
}
};
GetPath(all, current);
string[] split = path.Split(new char[] { ‘/’ });
Array.Reverse(split);
return string.Join(“/”, split);
}
}
}
Прошу прощения за форматирование, я знаю, что это отвратительное. Надеюсь, вы вставили это в Visual Studio, и это выглядит потрясающе. Когда-нибудь я найду минуту, чтобы понять, как использовать Gist, и начну публиковать читаемые образцы.
Наслаждаться!
