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

Question

Поэтому я пытаюсь сделать поиск в троице. Сейчас я работаю только над функцией вставки. Я понял основную идею троичного поиска в Интернете. Я знаю, что у одного корневого узла есть 3 листа, и если символ идет перед корнем, он идет налево, после - справа, и если он соответствует корню, он переходит к среднему листу. Поэтому моя главная цель - создать программу, которая может предлагать слова для слов, введенных пользователем с ошибкой. Но в данный момент я просто работаю над поиском троичного поиска. Я использую три для создания словаря, с помощью которого я проверяю введенные пользователем слова, чтобы предложить следующую лучшую альтернативу. Но сейчас, просто работаю над вводом некоторых символов в троичное дерево, и когда я отображаю его, он должен отображаться по порядку. Я не уверен на 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

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

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

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

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

display(head);

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

insert(num, &head);

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

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