Árvore de prefixos para corretor ortográfico

Olá, pessoal.

Abaixo está o código de árvore de prefixos que vocês fizeram em sala de aula. Corrigi os problemas com UNICODE e a função de impressão. Na próxima aula vou dar uma explicação sobre UNICODE pra que entendam de vez todas as funções utilizadas.

Agora, basta modificar o código para abrir um outro arquivo e imprimir as palavras incorretas com o número da linha de cada uma.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>
#include <wchar.h>

#define ORDEM 77

using namespace std;

/* Estrutura de um nó */
struct no
{
    wchar_t letra;
    struct no *p;
    struct no *f[ORDEM];
    bool fim;
};

/* Cria um novo nó */
struct no *criar(wchar_t letra = 0)
{
    struct no *novo = (struct no *)malloc(sizeof(struct no));
    novo->letra = letra;
    novo->p = NULL;
    novo->fim = false;
    
    for (int i = 0; i < ORDEM; i++)
        novo->f[i] = NULL;
    
    return novo;
}

/* Remove \n no final da string */
wchar_t *remove_enter(wchar_t *str)
{
    int p = wcslen(str);
    str[p] = 0;
    str[p - 1] = 0;
    return str;
}

/* Calcula a posição no vetor de filhos */
int posicao(wchar_t letra)
{
    if  ((letra >= L'a') && (letra <= L'z'))
        return (int) letra - L'a';

    if  ((letra >= L'A') && (letra <= L'Z'))
        return (int) letra - L'A';

    switch (letra)
    {
        case L'Ç':
            return 52;
            break;
        case L'á':
            return 53;
            break;
        case L'à':
            return 54;
            break;
        case L'â':
            return 55;
            break;            
        case L'ã':
            return 56;
            break;
        case L'é':
            return 57;
            break;            
        case L'ê':
            return 58;
            break;
        case L'í':
            return 59;
            break;   
        case L'ó':
            return 60;
            break;
        case L'ô':
            return 61;
            break;   
        case L'õ':
            return 62;
            break;   
        case L'ú':
            return 63;
            break;   
        case L'ç':
            return 64;
            break;
        case L'Á':
            return 65;
            break;                      
        case L'À':
            return 66;
            break;     
        case L'Â':
            return 67;
            break;   
        case L'Ã':
            return 68;
            break;
        case L'É':
            return 69;
            break;   
        case L'Í':
            return 70;
            break;
        case L'Ó':
            return 71;
            break;  
        case L'Ô':
            return 72;
            break;
        case L'Õ':
            return 73;
            break;
        case L'Ú':
            return 74;
            break;
        case L'Ü':
            return 75;
            break;
        case L'ü':
            return 76;
            break;
        default:
            wprintf(L"Caractere não reconhecido: %lc (%d)\n", letra, letra);
            return -1;
    }
}

/* Adiciona elemento na árvore */
void adicionar(struct no *raiz, wchar_t nome[256])
{
    if (nome[0] == 0)
    {
        raiz->fim = true;
        return;
    }
    
    int p = posicao(nome[0]);
    if (p == -1)
        return;
    
    if (raiz->f[p] == NULL)
    {
        raiz->f[p] = criar(nome[0]);
        raiz->f[p]->p = raiz;
    }
    
    adicionar(raiz->f[p], &nome[1]);
}

/* Adiciona palavras do dicionário */
void adicionar_lista(struct no *raiz, char caminho[256])
{
    wchar_t verbete[256];
    FILE* arquivo;

    arquivo = fopen(caminho, "r");

    if(arquivo == NULL)
        return;

    while(!feof(arquivo))
    {
        wmemset(verbete, 0, 256);
        fgetws(verbete, 255, arquivo);
        remove_enter(verbete);
        adicionar(raiz, verbete);
    }
    
    fclose(arquivo);
}

/* Imprime o conteúdo da árvore */
void imprimir(struct no *raiz)
{
    if(raiz == NULL)
        return;
        
    for(int i = 0; i < ORDEM; i++)
    {
        if(raiz->f[i] != NULL)
        {
            if(raiz->f[i]->fim == true)
            {
                struct no *atual = raiz->f[i];
                wchar_t palavra[256] = {0};
                wcsncpy(palavra, &atual->letra, 1);
                
                while (atual->p != NULL)
                {
                    atual = atual->p;
                    wchar_t c[256] = {0};
                    wcsncpy(c, &atual->letra, 1);
                    wcscpy(palavra, wcscat(c, palavra));
                }
                
                wprintf(L"%ls\n", palavra);
            }
            
            imprimir(raiz->f[i]);
        }  
    }  
}

/* Função principal */
int main(void)
{
    setlocale(LC_ALL, "");

    struct no *arvore = (struct no *)malloc(sizeof(struct no));
    arvore->letra = ' ';

    int opt;
    wchar_t palavra[256];
    char caminho[256];

    do
    {
        wprintf(L"Escolha uma opção:\n\n");
        wprintf(L"1 - Adicionar\n");
        wprintf(L"2 - Listar\n");
        wprintf(L"3 - Remover\n");
        wprintf(L"4 - Abrir dicionário\n");
        wprintf(L"0 - Sair\n\n");
        wprintf(L"Opção: ");
        scanf("%d", &opt);

        switch(opt)
        {
        case 1:
            wprintf(L"\n\nDigite uma palavra: ");
            scanf("%ls", palavra);
            adicionar(arvore, palavra);
            break;

        case 2:
            wprintf(L"\n\nConteúdo da árvore:\n");
            imprimir(arvore);
            break;

        case 3:
            wprintf(L"\n\nNão implementado!\n");
            break;

        case 4:
            wprintf(L"\n\nDigite o nome do arquivo: ");
            scanf("%s", caminho);
            adicionar_lista(arvore, caminho);
            break;

        case 0:
            return 0;

        default:
            wprintf(L"Opção inválida!\n\n");
        }
        
        wprintf(L"\n\n");
    }
    while(1);

    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

*