Ternária de pesquisa trie inserir função de problemas

Question

Então, eu estou tentando fazer um Ternária de pesquisa trie.Agora, eu estou apenas trabalhando em inserir função.Eu entendi a idéia básica de uma ternária de pesquisa trie on-line.Eu sei que um nó raiz tem 3 folhas, e se o personagem vem antes de raiz, ele vai para a esquerda, depois direita e, se ele corresponder a raiz, ele vai para o meio da folha.Então, meu principal objetivo é fazer um programa que pode sugerir palavras para perder-escrito de usuário entrou palavras.Mas no momento eu estou apenas trabalhando para tornar o ternária de pesquisa trie.Eu uso o trie para fazer um dicionário usando o que eu de verificação do usuário inserido palavras para sugerir a próxima melhor alternativa.Mas, agora, é só trabalhar em introduzir alguns caracteres em ternário trie e quando eu exibição deve exibi-lo em ordem.Não estou 100% de certeza da minha lógica sobre o meio de folhas.Agora o meu programa, quando executado, dê-me algum lixo valores ilimitados de alguma forma relacionados para o último carácter introduzido.Eu não sei onde eu tenho errado.Alguém por favor poderia apontar onde eu fiz o meu erro?Além disso, você poderia por favor me dizer se a qualquer lógica, que eu escrevi está errado?Quero dizer, você não tem de me dar o código, ou de qualquer coisa, como eu sinto que eu sou capaz de fazer-me uma vez que eu entendo de onde eu tenho errado, mas se alguém poderia ajudar-me a encontrar meus erros, ele iria me ajudar muito!

O código completo :

#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;
}

Eu estou usando o Geany editor de texto e estou no Linux Mint.Eu tenho um problema, onde, no compilador imprime apenas o último caractere entrei infinitamente quando eu acertar a função de exibição.Qualquer ajuda será muito útil!Obrigado!

Answer 1

A sua função de visor está errado.A condição de loop nunca avalia para false:

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

Este não é o que você quer.Nenhum &(*head)->lokid ou &(*head)->hikid nunca vai avaliar a NULL.Se head não é NULL, e , em seguida, &(*head)->lokid é apenas o mesmo endereço *head mais o deslocamento de lokid em um struct tstree.Note que o seu ciclo ainda não tem uma instrução update que poderia fazer a condição falsa, e não tem qualquer break - é condenado.

Na verdade, você não precisa mesmo de um loop em todos os.Para imprimi-lo em ordem, isso é tudo o que você precisa:

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

Observe que não há nenhum propósito em passar um node ** (Eu mudei isso para uma node *), e o valor de retorno deve ser void.

ATUALIZAÇÃO

O seu insert() a função está correta, mas se você usar o errado variável em main.Esta atribuição na base da recursão insert() está causando o comportamento não intencional:

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

Observe que cada vez que você acertar o caso base, você pode atribuir um novo nó *head e temp, assim, perder de referência para o que foi armazenado em temp antes.Em seguida, você chama display(temp).Sim, você constrói o trie, mas você imprimi-lo a partir do último nó inserido - não é o que você deseja.

Em vez disso, você deve chamar display com a variável global head, qual é o correto raiz do seu trie:

display(head);

O mesmo acontece quando você chamar inserir.Você não deseja inserir uma nova letra de partida no último nó adicionado, você deseja adicioná-lo a iniciar na raiz. main() deve ter isto em vez disso:

insert(num, &head);

E enquanto estamos no assunto, observe que temp é completamente desnecessário.Você não precisa dele. insert manipula o chefe global por referência, temp não é de nenhum uso aqui (e na verdade ele introduziu um bug).

Alterar essas 2 linhas principais é o suficiente, testei aqui e está funcionando como um encanto.