Ну, я думаю, что вы используете слишком большой укус с помощью функции add_word. Попробуйте сначала разбить его на более мелкие проблемы. Как только вы решите меньшие проблемы, большая проблема, вероятно, станет легче.
Во-первых, нам нужно создать узлы Trie (попытка сделать это в add_word была бы уродливой). Итак, давайте теперь сделаем функцию, которая делает это:
/* Allocates, initializes, and returns a new Trie node. The node will contain
* a copy of word and trans, rather than use them directly. The children array
* will be initialized to all NULL's.
*/
struct s_trie_node * trie_node_create(const char * prefix, const char * trans)
{
struct s_trie_node * n = malloc(sizeof(struct s_trie_node));
int i;
n->word = prefix ? strdup(prefix) : strdup("");
n->translation = trans ? strdup(trans) : NULL;
for (i = 0; i < UCHAR_MAX + 1; i++)
n->children[i] = NULL;
return n;
}
Обратите внимание, что мы создаем копии строк, а не используем их напрямую. Это облегчает жизнь пользователям этой библиотеки Trie, а также позволяет нам освобождать их, когда они больше не нужны, без беспокойства, если пользователь использует их где-то еще. Однако это важное решение, так как оно означает, что мы несем ответственность за обеспечение освобождения этих строк в дальнейшем. Кроме того, мы используем strdup, что означает, что мы предполагаем, что переданные нам строки являются «чистыми» (т. Е. Заканчиваются символом NULL).
В любом случае, теперь мы можем создавать узлы. Давайте перейдем к другим проблемам, связанным с Три. Понятно, что вам нужно будет иметь возможность узнать длину общего префикса из 2 строк. Если вы не можете сделать это, вы не можете сделать что-нибудь еще. Итак, мы можем использовать следующую функцию:
/* Returns length of common prefix of v & w. */
int match(char * v, char * w)
{
char * start = v;
for (; *v && *v == *w; v++, w++);
return v - start;
}
Это довольно просто, но это необходимо. Когда мы сравниваем слово с узлом префикса, знание длины общего префикса скажет нам, является ли оно точным или частичным совпадением. Точные совпадения означают, что нам просто нужно обновить узел. Частичное совпадение может привести к тому, что дочерний узел будет «разбит» на 2, и, скорее всего, это будет означать, что мы должны пойти дальше по Trie. Эта идея расщепления узлов имеет решающее значение. Если в списке только одно слово, например. «Привет», тогда будет только 2 узла: корневой узел (пустая строка) и единственный дочерний узел корневого узла «Привет». Если мы теперь хотим добавить другое слово, которое имеет общий префикс с «привет», например. «эй», нам нужно разделить «привет» на 2 узла: «он», дочерний элемент корневого узла, и «llo», дочерний элемент «он». Итак, давайте создадим функцию, которая будет обрабатывать расщепление узлов для нас:
/* Creates a new node that is a child of n. The word stored at n will be
* truncated after location (index into n->word), with the remaining suffix
* of the word belonging to the new child of n.
*/
struct s_trie_node * trie_node_split(struct s_trie_node * n, int location)
{
struct s_trie_node * child;
char * prefix;
char * suffix;
int len = strlen(n->word);
if (location <= 0)
return NULL;
if (location >= len)
return n;
prefix = strndup(n->word, location);
suffix = strndup(n->word + location, len - location);
child = trie_node_create(suffix, n->translation);
memcpy(child->children, n->children,
sizeof(struct s_trie_node *) * UCHAR_MAX);
free(n->word);
n->word = prefix;
n->translation = NULL;
n->children[0] = child;
n->children[1] = NULL;
return n;
}
Благодаря возможности находить длину общего префикса между двумя строками, создавать узлы и разбивать узлы, у нас есть все основные операции, необходимые для манипулирования и обхода нашего Trie.
Теперь рекурсия часто очень хорошо сочетается со структурами Три. Итак, представьте, что вам дано три (корневой узел) и слово для сопоставления в Три. Это слово будет иметь общий префикс с одним из наших детей или не будет. Если это не так, то мы можем просто создать новый узел, значением которого является это слово, и добавить его в наш список детей. Однако, если это так, то мы сталкиваемся с несколькими различными случаями, в зависимости от того, как долго длился общий префикс.
Случай 1: слово точно соответствует нашему ребенку (то есть слова совпадают). В этом случае наш дочерний элемент точно соответствует этому слову, и мы можем просто обновить перевод и остановить (не нужно создавать какие-либо новые узлы).
Случай 2: Слово в целом является префиксом нашего ребенка. В этом случае нам нужно разделить ребенка на 2 части; первое - наше слово, второе - остальная часть слова, которое ранее хранилось у нашего ребенка. Первая часть становится новым дочерним элементом, и мы сохраняем перевод в нем, вторая часть становится дочерним элементом нашего ребенка.
Случай 3: наш ребенок в целом является префиксом слова. В этом случае мы удаляем общий префикс из слова (сокращаем слово только до суффикса). Затем мы добавляем суффикс слова к поддереву, укорененному в нашем дочернем элементе (т. Е. Recurse).
Случай 4: общий префикс короче обоих слов. В этом случае нам нужно сначала разделить ребенка. Префикс становится новым дочерним, а суффикс - дочерним. Затем мы удаляем префикс из слова, а затем добавляем оставшуюся часть слова в поддерево с корнем нашего ребенка (т. Е. Recurse).
И это все 4 случая. Вооружившись этим, теперь мы можем легко написать функцию для обработки каждого из этих случаев, используя рекурсию для обхода дерева.
/* Add a translation to the Trie rooted at root. */
int trie_add_word(struct s_trie_node * root, char * word, char * trans)
{
struct s_trie_node ** n;
int loc;
for (n = root->children; *n; n++) {
/* Find length of longest common prefix. */
loc = match(word, (*n)->word);
if (!loc) {
continue;
} else {
if (loc != strlen((*n)->word))
trie_node_split(*n, loc);
word += loc;
if (!*word) {
if ((*n)->translation)
free((*n)->translation);
(*n)->translation = strdup(trans);
return 0;
}
return trie_add_word(*n, word, trans);
}
}
/* Failed to find any children that matched. */
if (n - root->children >= UCHAR_MAX) {
fprintf(stderr, "Ran out of room to store children in.");
return -1;
}
*n = trie_node_create(word, trans);
return 0;
}
И это все! Полагаю, длинный ответ, но это было весело.