Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.98/56: Рейтинг темы: голосов - 56, средняя оценка - 4.98
45 / 45 / 5
Регистрация: 04.01.2010
Сообщений: 337

Как реализовать префиксное дерево на C#?

04.12.2014, 20:08. Показов 12702. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Необходимо реализовать префиксное дерево на C# (добавление, удаление, поиск)
Правильным ли будет для этих целей создать класс, в котором:
1) переменную char - в качестве символа кода
2) переменную string - предложение, которое будет выдаваться по ключу
3) List<из нашего класса> - список потомков

Правильно ли я понимаю, что значение хранится в конкретном листе, и допустим если ищем значение по ключу "привет", то мы из корня (пустого) попадаем на п, потом на р, и так далее, и когда доходим до т то именно оттуда и берём значение?
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
04.12.2014, 20:08
Ответы с готовыми решениями:

Как реализовать бинарное дерево?
Здравствуйте! Нужно реализовать структуру данных &quot;список&quot;. Я чуть-чуть знаком с С++, но в С# совсем новичок. Застрял я на работе с...

Как реализовать двоичное дерево не используя готовых методов
Как реализовать двоичное дерево не используя готовых методов. Если есть готовый код можете скинуть, или ссылку подкинуть. Спасибо

Префиксное дерево, проверка на корректность
Доброго времени суток, Пишу собственный набор функций для работы с префиксным деревом, но наткнулся на небольшие проблемы. #include...

11
871 / 721 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
04.12.2014, 21:08
yura097,
Элементы дерева вынесите в отдельный класс вместе со списком для потомков.
В классе дерева уже оперируйте элментами самого дерева
2
45 / 45 / 5
Регистрация: 04.01.2010
Сообщений: 337
04.12.2014, 22:04  [ТС]
XRoy,
хм. то есть класс дерева и класс элементов, или что вы имеете ввиду ?
0
871 / 721 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
05.12.2014, 13:20
yura097,
Да, у вас это отдельный классы должны быть, дерево оперирует классом элемента.
И не совсем понятно зачем вам char и string поля, можно же обойтись только string
Почитайте к примеру http://habrahabr.ru/post/151421/
1
45 / 45 / 5
Регистрация: 04.01.2010
Сообщений: 337
05.12.2014, 14:01  [ТС]
XRoy, просто идеей было создать класс дерево, в котором есть код текущей вершины, список листов и значение.
Там же поиск, добавление и удаление.
Тоесть например при добавлении ключа "ад" и значения к нему "жизнь прекрасна" ищем листы у начального, не находим, добавляем в список листов новый лист с кодом "а", опять же ищем в нем листы, не находим добавляем "д", раз конец ключа, то в значение листа "д" записываем "жизнь прекрасна"
Или я что то нет так понимаю? )
0
871 / 721 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
06.12.2014, 16:40
yura097,
Почему в значение?
Записываем как потомка

У нас значения могут быть только листами (leaf)

Добавлено через 1 час 0 минут
Вот вам простенький пример, только для латиницы
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
    internal class TreeNode
    {
        public TreeNode[] Childs { get; set; }
        public String Value { get; set; }
 
        public Boolean HasValue
        {
            get { return Value != null; }
        }
 
        public TreeNode()
        {
            // Для английского алфавита (26 букв)
            Childs = new TreeNode[26];
        }
    }
 
    class PrefixTree
    {
        TreeNode Root = new TreeNode();
 
        public void Add(string key, string value)
        {
            TreeNode current = Root;
 
            foreach (char c in key)
            {
                // Создаем узел если не существует
                current.Childs[c - 'a'] = current.Childs[c - 'a'] ?? new TreeNode();
                current = current.Childs[c - 'a'];
            }
 
            current.Value = value;
        }
 
        public string Get(string key)
        {
            TreeNode current = Root;
 
            foreach (var c in key)
            {
                if (current.Childs[c - 'a'] == null)
                {
                    throw new ArgumentException();
                }
 
                current = current.Childs[c - 'a'];
            }
 
            if (current.HasValue)
            {
                return current.Value;
            }
            else
            {
                throw new ArgumentException();
            }
        }
    }
 
    class Program
    {
        public static void Main(string[] args)
        {
            PrefixTree trie = new PrefixTree();
 
            trie.Add("hell", "good");
            trie.Add("hello", "goor");
 
            Console.WriteLine(trie.Get("hell"));
            Console.WriteLine(trie.Get("hello"));
        }
    }
0
45 / 45 / 5
Регистрация: 04.01.2010
Сообщений: 337
06.12.2014, 20:11  [ТС]
XRoy,
Не смотрел cyberforum
Реализовал класс Trie со свойствами (неявными полями):
1) char key;
2) string Value;
3) List<Trie> children

Изначально в программе создаём пустой экземпляр:
1) new Trie();
Затем можем:
1) Добавлять
При добавлении key = "abc", value = "hello world"
а) добавляет в children new Trie(key[0]) (если находит просто переходит туда)
б) затем в его children new Trie(key[1])
в) затем в его children new Trie(key[2])
г) затем раз ключ кончился добавляю в текущее значение Value = value
2) Удалять детей - спускаемся по дереву, если находим то ставим в value = null;
3) Искать в них по ключу (причём сделал возможность выводить всех под детей (То есть если есть ключи abca, abcb, abcd, abce, то по запросу abc выдаст все эти ключи + значения)

В итоге изначально имеем полностью пустое дерево.
Можем добавить в него любые коды и любые значения (из любых символов) в неограниченном количестве.
Считаю, что делать ограничения по алфавиту имеет смысл вне класса.
Так же с помощью сериализации организовал сохранение деревца

Добавлено через 5 минут
Единственная вещь, это то, что он добавляет "детей" просто подряд, соответственно если этих детей будет 100,
то придётся пробежать все, чтобы узнать что именно это у нас имеет код "a", не знаю насколько это верно.
0
871 / 721 / 304
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
06.12.2014, 21:08
Лучший ответ Сообщение было отмечено yura097 как решение

Решение

yura097,
Используйте Dictionary вместо List, у него время доступа по ключу O(1)
1
45 / 45 / 5
Регистрация: 04.01.2010
Сообщений: 337
07.12.2014, 12:12  [ТС]
XRoy, никогда не изучал его, можете поможете парочкой примеров?)

И не займёт ли это намного больше памяти ?)

Добавлено через 13 часов 38 минут
Уже разобрался со словарями. Огромное спасибо
0
2 / 2 / 2
Регистрация: 01.02.2022
Сообщений: 21
25.07.2022, 18:51
Здравствуйте. МОжете объяснить что это за запись " [c - 'a'] " в выражении current.Childs[c - 'a'] = current.Childs[c - 'a'] ?? new TreeNode();
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
25.07.2022, 19:01
kravenhunter, это такой хитрый способ преобразовать символ в его порядковый номер в алфавите (латинском).
Из порядкового номера символа вычисляется порядковый номер символа "а", на выходе получается сдвиг относительно "а" в таблице юникода.
'a' - 'a' = 0,
'b' - 'a' = 1,
'c' - 'a' = 2

И т.д.
0
2 / 2 / 2
Регистрация: 01.02.2022
Сообщений: 21
25.07.2022, 19:25
Магия раскрыта, спасибо за объяснение =)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.07.2022, 19:25
Помогаю со студенческими работами здесь

Создание структуры "префиксное дерево". Ошибка "Access violation writing location".
Есть структура данных - бор или префиксное дерево. class trie { char value; // символ узла trie** pointers; // ссылки на...

Как реализовать двоичное дерево?
public class BSTree&lt;T1 extends Comparable&lt;T1&gt;, T2&gt; { static class Node&lt;T1, T2&gt; { T1 key; T2 value; ...

Как реализовать дерево в таблице
Добрый вечер я стажер PHP еще учусь в университете, на работе мне надо сделать раскрывающийся список типа дерева , с + и минусами,который...

Как реализовать бинарное дерево?
Всем привет. Ребят подскажите как реализовать бинарное дерево (не дерево бинарного поиска, а именно БИНАРНОЕ ДЕРЕВО). Знаю как...

Как реализовать дерево файлов определенной папки удаленной машины?
Есть код, который отображает дерево каталогов, он может отобразить дерево удаленного сайта либо локальной папки где исполняется код....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru