Цифровой словарь

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

Оригинальная формулировка: tt25.rar

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

Для применения в чистом виде, вещь абсолютно бесполезная (почему? объяснять не буду). Но писать её немного интереснее чем, алгоритмы для make файлов (которые в тестах бывают чаще всего). Само дерево храниться ввиде списка рёбер. Каждое ребро имеет текст, потомка, список соседей по узлу и счётчик использования. Текст ребра выделяется отдельно от стуктуры ребра. Если по размеру текст ребра не больше чем размер ссылки, то текст хранится непосредвенно в байтах самой ссылки. Если счётчик использования ребра меньше чем сумма счётчиков его прямых потомков, то считается что данное ребро содержит конец слова. Для ребра без потомков, сумма счётчиков потомков равна нулю.

abc (count=2) 123 (count=1) 456 (count=1)

Содержит два слова 'abc123', 'abc456'.

123 (count=2) 456 (count=1)

Содержит два слова '123456', '123'.

Вот в целом и всё. Прилагается исходник в оригинальном исполнении с набором тестовых процедур. Немного изменена процедура SpliceNode(...). В ней, выделение памяти вместо кучи происходит в стеке, поэтому с большими словами надо быть осторожным. Прилагается более быстрый и экономный менеджер памяти, который можно в него вставить.

Файлы

Тестовые словари можно взять тут: http://www.insidepro.com/rus/download.shtml

Функции

BOOL Insert(char*); - добавить строку (возвращает TRUE если строка добавлена)
BOOL Remove(char*); - удалить строку (возвращает TRUE если строка удалена)
BOOL Find(char*); - проверить наличие строки (TRUE если строка есть в наличие)