3

Estou fazendo um programa que aloca um dicionário na memória para verificar palavras com erros ortográficos em arquivos de texto. A função abaixo converte as palavras do dicionário em inteiros e os armazena em estruturas árvore.

  • Minha dúvida é como escrever corretamente e iterativamente a parte do código que vai armazenando os números na árvore(a partir da linha 24).

Vi muitos exemplos, mas todos recursivos e não entendi muito bem, fique à vontade em dar qualquer tipo de exemplo para outros usuários que possam ter a mesma dúvida.

typedef struct arvore
{
    unsigned int n;
    struct arvore *esq, *dir;
}arvore;

arvore *raiz;

unsigned int
BPHash(const char* str, unsigned int len)
{
    unsigned int hash;
    for (unsigned int i = 0; i < len; str++, i++)
        hash = hash << 7 ^ (*str);
    return hash;
}

bool
load(const char *dict)
{
    FILE *fp = fopen(dict, "r"); // dict = arquivo que serve como dicionário
    if (fp == NULL)
        return false;

    char str[LENGTH+1]; // LENGTH = tamanho máximo da string (45)
    unsigned int strtam, hash; // Tamanho da string e string convertida em inteiro com função hash
    struct arvore dicio = {0, NULL, NULL};
    raiz = &dicio; // Ponteiro global

    while (fgets(str, LENGTH, fp) != NULL)
    {
        strtam = strlen(str);
        hash = BPHash(str, strtam); // BPHash = função hash

        if (raiz->n == 0) // Minha dúvida se refere as linhas abaixo
            raiz->n = hash;

        else if (raiz->n < hash)
        {
            raiz->esq = (arvore*)malloc(sizeof(arvore));
            raiz->dir = NULL;
            raiz->n = hash;
        }

        else
        {
            raiz->dir = (arvore*)malloc(sizeof(arvore));
            raiz->esq = NULL;
            raiz->n = hash;
        }
    }

    return true;
}
1

1 Resposta 1

2

Seu primeiro problema é que a raiz da árvore (dicio) está declarada dentro da própria função load, alocada estaticamente na pilha de execução (variáveis locais são alocadas na pilha de execução). Isso significa, que quando a função terminar, a parte correspondente da pilha de execução vai ser limpa e com ela a raiz da árvore. A raiz ainda poderia ser recuperada pela variável global raiz, mas isso vai ser um ponteiro que vai apontar para uma parte da pilha que não existe mais e que em breve será sobreescrita, tornando-se então em lixo.

A melhor solução para isso seria retornar a raiz da árvore ou NULL se ela não puder ser criada. Evite usar variáveis globais, pois fazer isso é uma péssima prática de programação. Mas, como você está sendo obrigado a trabalhar dessa forma, então infelizmente não há outra saída.

Outro problema é que a sua árvore tem no máximo três nós: raiz, raiz->dir e raiz->esq. Aliás, só terá dois, pois quando você cria o nó esquerdo, você apaga o direito e vice-versa. Além disso, você apaga esses nós sem desalocá-los, ocasionando vazamento de memória. Você nunca está criando ou acessando nós em níveis mais profundos.

Seu código revisado é esse:

// LENGTH = tamanho máximo da string
#define LENGTH 45

// função hash
unsigned int BPHash(const char *str, int len) {
    unsigned int hash = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = hash << 7 ^ (*str);
    }
    return hash;
}

typedef struct arvore {
    unsigned int n;
    struct arvore *esq, *dir;
} arvore;

arvore *raiz = NULL;

bool load(const char *dict) {

    // Primeiro, destroi qualquer árvore que já houvesse antes, para evitar vazamento de memória.
    destruir_arvore(raiz);
    raiz = NULL;

    FILE *fp = fopen(dict, "r"); // dict = arquivo que serve como dicionário
    if (fp == NULL) return false;

    char str[LENGTH + 1];

    while (fgets(str, LENGTH, fp) != NULL) {
        arvore *novo = (arvore *) malloc(sizeof(arvore));
        novo->n = BPHash(str, strlen(str));
        novo->esq = NULL;
        novo->dir = NULL;

        arvore *no = raiz;

        while (1) {
            if (no == NULL) {
               raiz = novo;
               break;
            } else if (no->n < hash) {
                if (no->esq == NULL) {
                    no->esq = novo;
                    break;
                }
                no = no->esq;
            } else {
                if (no->dir == NULL) {
                    no->dir = novo;
                    break;
                }
                no = no->dir;
            }
        }
    }

    return true;
}

Observe que temos dois whiles aqui. O while externo percorre o arquivo lendo as strings dele, e a cada iteração, um nó novo é criado. O while interno usa um ponteiro no, que começa na raiz e vai descendo na árvore (no = no->esq; e no = no->dir;) até encontrar um lugar vazio onde o nó novo possa ser inserido. Quando o nó novo é inserido na árvore, dá-se um break; no while interno. O if (no == NULL) é para criar a raiz da árvore. Essa abordagem ainda tem a vantagem de que o zero não é especial e a função funciona mesmo se BPHash retornar zero. Não é utilizada recursão aqui.

Uma função para destruir a(s) árvore(s) criada(s) também é necessária a fim de evitar-se vazamentos de memória (dessa vez com recursão, já que a versão sem recursão é bem mais complicada):

void destruir_arvore(arvore *no) {
    if (no == NULL) return;
    destruir_arvore(no->esq);
    destruir_arvore(no->dir);
    free(no);
}

É claro que isso tudo depende de a função BPHash ter sido implementada adequadamente (faltou inicializar o hash com zero nela). Não sei se a implementação é ou não adequada. Também não sei se essa árvore será de fato útil ao que você quer, mas se for, é do jeito que coloquei acima que você irá construí-la.

8
  • Adicionei a função BPHash e mais alguns comentários. "Seu primeiro problema é que a raiz da árvore está declarada dentro da própria função load" O ponteiro raiz é uma variável global, está declarado fora de qualquer função. "A melhor solução para isso é retornar a raiz da árvore ou NULL se ela não puder ser criada" Neste exercício não posso mudar a declaração de load, tem que retornar um bool, por isso criei o ponteiro global raiz, para acessar a arvore dicio de qualquer função.
    – Matheus
    10/12/2017 às 16:49
  • "Aliás, só terá dois, pois quando você cria o nó esquerdo, você apaga o direito e vice-versa" Essa é minha maior dificuldade, criar novos nós iterativamente, e não sobrescrevê-los. "Além disso, você apaga esses nós sem desalocá-los, ocasionando vazamento de memória. Você nunca está criando ou acessando nós em níveis mais profundos." Estou ciente disso, não me preocupei em desalocar porque ainda nem consegui criar rsrs.
    – Matheus
    10/12/2017 às 16:53
  • 1
    @Matheus [continuação] É de se crer que sizeof(arvore) == sizeof(unsigned int) + sizeof(arvore *) + sizeof(arvore *), mas é permitido ao compilador acrescentar uns bytes a mais de padding para se aproveitar de alinhamentos de dados na memória. Também é de se esperar que todos os ponteiros tenham o mesmo tamanho, seja ele 4 ou 8 bytes (em arquiteturas de 16 bits isso não acontecia, havia dois tipos de ponteiros, near e far de tamanhos diferentes). [continua] 10/12/2017 às 22:58
  • 1
    @Matheus [continuação] De acordo com este teste, o unsigned int tem 4 bytes, cada ponteiro tem 8 bytes, os componentes da estrutura somam 20 bytes, mas o tamanho da estrutura é de 24 bytes, havendo portanto 4 bytes de sobra (padding). Mas novamente, isso daí é algo que o compilador tem poder de decidir e depende da plataforma, do compilador em questão, de otimizações aplicadas, do ambiente de execução, etc. 10/12/2017 às 23:00
  • 1
    @Matheus ideone.com/ft87Kj 12/12/2017 às 16:41

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .