Проблемы с функцией тройного поиска trie insert

Question

Итак, я пытаюсь выполнить троичный поиск.Прямо сейчас я работаю только над функцией insert.Я понял основную идею троичного поиска в Интернете.Я знаю, что один корневой узел имеет 3 листа, и если символ стоит перед корнем, он идет влево, после - вправо, и если он соответствует корню, он идет к среднему листу.Итак, моя главная цель - создать программу, которая может подсказывать слова для неправильно написанных введенных пользователем слов.Но на данный момент я просто работаю над тем, чтобы сделать тройной поиск простым.Я использую trie для создания словаря, с помощью которого я проверяю введенные пользователем слова, чтобы предложить следующую наилучшую альтернативу.Но прямо сейчас я просто работаю над вводом некоторых символов в троичное дерево, и когда я его отображаю, оно должно отображаться по порядку.Я не уверен на 100% в своей логике относительно средних листьев.Теперь моя программа при запуске выдает мне несколько мусорных неограниченных значений, каким-то образом связанных с последним введенным символом.Я не знаю, где я ошибся.Не мог бы кто-нибудь, пожалуйста, указать, где я допустил свою ошибку?Кроме того, не могли бы вы, пожалуйста, сказать мне, является ли какая-либо логика, которую я написал, неверной?Я имею в виду, вам не обязательно давать мне код или что-то еще, поскольку я чувствую, что способен сделать это сам, как только пойму, где я ошибся, но если бы кто-нибудь мог просто помочь мне найти мои ошибки, это бы мне очень помогло!

ВЕСЬ код ЦЕЛИКОМ :

#include <stdio.h>
#include <stdlib.h>  //Because usage of malloc gives warnings without this header
typedef struct tstree
{
    struct tstree *lokid;
    struct tstree *hikid;
    struct tstree *eqkid;
    char letter;
}node;
node *head = NULL;
int count = 0;
int insert(char x, node **head)
{
    if (*head==NULL)            //If it's the first element
    {
        *head = malloc(sizeof(node));   
        (*head)->letter = x;
        count++;            
        (*head)->lokid = (*head)->hikid = (*head)->eqkid = NULL;            //Assign all 3 to null initially
    }
    else if ((*head)->letter == x)          //If equal, insert below
    insert(x , &((*head)->eqkid) );
    else if ((*head)->letter > x)   //If inserted char comes before current val, insert to left
    insert(x,&(*head)->lokid);
    else
    insert(x,&(*head)->hikid);              //Else to the right
    return 0;
}
void display(node *head)
{
    if(head)
    {
        display(head->lokid);               //print in infix order
        printf("%c ",head->letter);
        display(head->hikid);
    }
    //return 0;
}
int main()
{   
    int op;
    char num;
    printf("\nWelcome Fabiz. Hope it meets your expectations!\n");
    while(1)
    {
        printf("\n1. To insert an element\n2. Display the tree\n3. Exit\nOption :");
        scanf("%d",&op);
        switch(op)
        {
            case 1:
            {
                system("clear");
                printf("\nEnter the element : ");
                scanf(" %c",&num);
                insert(num,&head);
                break;
            }
            case 2:
            {
                system("clear");
                if(count == 0)
                printf("\nEmpty tree\n");
                else
                {
                    printf("Display in order..\n");
                    display(head);
                }
                break;
            }
            default: exit(0);
        }
    }
    return 0;
}

Я использую текстовый редактор Geany и использую Linux Mint.У меня возникла проблема, когда компилятор просто печатает последний символ, который я ввел бесконечно, когда я нажимаю на функцию отображения.Любая помощь будет очень полезна!Спасибо!

Answer 1

Ваша функция отображения неверна.Условие цикла никогда не принимает значение false:

while(&(*head)->lokid!=NULL && &(*head)->hikid!=NULL)

Это не то, чего ты хочешь.Ни один из &(*head)->lokid или &(*head)->hikid когда-нибудь оценит, чтобы NULL.Если head это не так NULL, тогда &(*head)->lokid это точно такой же адрес, как *head плюс смещение lokid в struct tstree.Обратите внимание, что в вашем цикле даже нет инструкции update, которая могла бы сделать условие ложным, и в нем нет никаких break - это обречено.

На самом деле, вам вообще не нужен цикл.Чтобы распечатать его по порядку, это все, что вам нужно:

void display(node *head) {
    if (head) {
        display(head->lokid);
        printf("%c ", head->letter);
        display(head->hikid);
    }
}

Обратите внимание, что нет никакой цели в передаче node ** (Я изменил это на node *), и возвращаемое значение должно быть void.

Обновить

Ваш insert() функция верна, но вы используете неправильную переменную в main.Это присвоение в базе рекурсии из insert() вызывает непреднамеренное поведение:

temp = *head = malloc(sizeof(node));

Обратите внимание, что каждый раз, когда вы переходите к базовому варианту, вы назначаете новый узел *head и temp, таким образом теряя ссылку на то , что было сохранено в temp раньше.Тогда ты позвонишь display(temp).Да, вы создаете trie, но вы печатаете его, начиная с последнего вставленного узла - не то, что вы хотите.

Вместо этого вам следует позвонить display с глобальной переменной head, который является правильным корнем вашего дерева:

display(head);

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

insert(num, &head);

И раз уж мы об этом заговорили, обратите внимание, что temp в этом нет никакой необходимости.Тебе это не нужно. insert манипулирует глобальным заголовком по ссылке, temp здесь это бесполезно (и на самом деле это привело к ошибке).

Достаточно изменить эти 2 строки в main, протестировал это здесь, и это работает как по маслу.