C Implementação de Índices remissivos usando Arvores Binarias

[filipeoioi]

Estou fazendo ED1, e estou estudando arvores binarias, então foi passado uma prática que consiste em ler um arquivo .txt e identificar em qual pagina os termos passados aparecem, e imprimi-los em um arquivo de saída seguindo um padrão, criando assim um índice remissivo, tudo isso utilizando uma arvore binaria, consegui implementar o que foi pedido utilizando arvores binarias, porém não consegui imprimi-los na forma correta, acho que eu deveria utilizar algum outro tipo de ED para imprimir o índice de forma correta. Queria que alguém me dasse um help de como fazer isso kkkkkk. Desde já agradeço, segue o código e os arquivos texto da entrada, de como deve sair e de como saiu. Obs.: Deixei a parte do protótipo de ED que eu fiz como comentário, antes de pensar como implementar ela kkkkk. Obs2.: Passei os arquivos por parâmetro, qualquer coisa é só mudar. 

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//----------------------------------------------------------------
//                     Fila estatica
//----------------------------------------------------------------
/*
#define QNT 10

typedef struct
{
    int inicio;
    int fim;
    char palavra[QNT];
    int contador;
} FilaEstatica;

int incrementaIndice(int pos) { return (pos + 1) % QNT; }

//iniciar a fila
void iniciaFilaEstatica(FilaEstatica *fila)
{
    fila->inicio = 0;
    fila->fim = -1;
    fila->contador = 0;
}

//verifica se a fila esta vazia ou se a fila esta cheia
bool estaVaziaFilaEstatica(FilaEstatica *fila) { return (fila->contador == 0); }
bool estaCheiaFilaEstatica(FilaEstatica *fila) { return (fila->contador == QNT); }

//insere itens na fila
void enfileiraFilaEstatica(FilaEstatica *fila, char *x)
{
    if (!estaCheiaFilaEstatica(fila))
    {
        fila->fim = incrementaIndice(fila->fim);
        for (int i = 0; i < 10; i++)
        {
            fila->palavra[fila->fim] = x[i];
        }

        fila->contador++;
    }
    else
    {
        printf("Warning: fila cheia, não foi inserido\n");
    }
}

//retira itens da fila
int desenfileiraFilaEstatica(FilaEstatica *fila)
{
    int temp = -99;
    if (!estaVaziaFilaEstatica(fila))
    {
        temp = fila->palavra[fila->inicio];
        fila->inicio = incrementaIndice(fila->inicio);
        fila->contador--;
    }
    else
    {
        printf("Wrning: não pode ser removido\n");
    }
    return (temp);
}
*/
//----------------------------------------------------------------
//                     ARVORE BINARIA
//----------------------------------------------------------------

typedef struct NoArvore *PtrNoArvore;

typedef struct NoArvore
{
    char key[10];
    PtrNoArvore direita;
    PtrNoArvore esquerda;
} NoArvore;

//inicia a arvore
void iniciaArvore(PtrNoArvore *arvore) { *arvore = NULL; }

//verifica se ela ta vazia
bool arvoreVazia(PtrNoArvore *arvore) { return (*arvore == NULL); }

//insere elementos na arvore
bool inserearvore(PtrNoArvore *arvore, char *x)
{
    char aux;
    aux = x[0];

    if (*arvore == NULL)
    {
        (*arvore) = malloc(sizeof(NoArvore));
        (*arvore)->direita = NULL;
        (*arvore)->esquerda = NULL;
        for (int i = 0; i < 10; i++)
        {
            (*arvore)->key[i] = x[i];
        }
        return true;
    }
    if (strcmp((*arvore)->key, x) == 0)
    {
        return false;
    }
    if ((*arvore)->key[0] > aux)
    {
        return (inserearvore(&(*arvore)->esquerda, x));
    }
    else
    {
        return (inserearvore(&(*arvore)->direita, x));
    }
}


// Imprime Pre-ordem
void impressaoPreordem(PtrNoArvore *arvore)
{
    if ((*arvore) == NULL)
        return;

    printf("%s ", (*arvore)->key);
    impressaoPreordem(&(*arvore)->esquerda);
    impressaoPreordem(&(*arvore)->direita);
}

// Consulta/Pesquisa
bool procuraArvore(PtrNoArvore *arvore, char *x)
{
    if (*arvore == NULL)
        return false;

    if (strcmp((*arvore)->key, x) == 0)
        return true;

    if ((*arvore)->key[0] > x[0])
    {
        return (procuraArvore(&(*arvore)->esquerda, x));
    }
    else
    {
        return (procuraArvore(&(*arvore)->direita, x));
    }
}

int main(int argc, char *argv[])
{

    //system("cls");

    //Abertura dos arquivos e declaracao do nos da arvore
    PtrNoArvore Termos;
    FILE *arqEntrada = fopen(argv[1], "r");
    FILE *arqSaida = fopen(argv[2], "w");

    //Declaracao das variaveis
    char palavras[100];
    char *aux;
    char x[100];
    int page = 0;

    //Inicia Arvore
    iniciaArvore(&Termos);

    //Verifica se a erros
    if (arqEntrada == NULL || arqSaida == NULL)//-------------------não TA FUNCIONANDO
    {
        printf("\n\n#### Ocorreu um erro ao abrir o arquivo ####\n#### O programa esta sendo encerrado ####\n\n");
        exit(1);
    }
    if (argc != 3)//--------------------------TA FUNCIONANDO
    {
        printf("\n\nERROR!!: A quantidade de argumentos inseridos sao invalidos\n\n");
        exit(1);
    }

    // Leitura dos termos da arvore--------------------FUNCIONANDO
    fscanf(arqEntrada, "<termos:%s", x);
    aux = strtok(x, ",>");
    while (aux != NULL)
    {   //insere os termos na arvore
        inserearvore(&Termos, aux);
        aux = strtok(NULL, ",>");
    }

    //identifica os temos ----------------------- FUNCIONANDO
    printf("*****************************************************\n");
    printf("Termos na arvore : ");
    impressaoPreordem(&Termos);
    printf("\n*****************************************************\n");



    //Verifica se as palavras estão na arvore e conta as paginas ---------------------FUNCIONANDO PARCIALMENTE
    while (EOF != fscanf(arqEntrada, "%s", x))
    {

        aux = strtok(x, "<,.:()>");
        while (aux != NULL)
        {
            if (strcmp(aux, "page") == 0)
            {
                page++;
            }
            if (procuraArvore(&Termos, aux))
            {
                printf("%s , Na pagina %d\n", aux, page);
                fprintf(arqSaida, "%s, %d \n", aux, page);//Organizar a saida no arquivo

                //O programa imprime o termo, e o numero da pagina

                //Encontrar uma forma de imprimir:
                // TERMO, pag 1, ..., pag n
            }
            aux = strtok(NULL, "<,.:()>");
        }
    }
    printf("\n*****************************************************\n");
    printf("O numero de paginas eh %d", page);
    printf("\n*****************************************************\n");

    free(arqEntrada);
    free(arqSaida);

    return 0;
}

 

saida_certa.txt saida_errada.txt entrada.txt

[arfneto]

 Ajude os outros a ajudarem você...

 

3 downloads separados de arquivos minúsculos é bem evitável. Ou não?

 

Veja:

 

Exemplo da Entrada

 

<termos:celula,arvores,chave,busca>
<page:1>
Arvores binarias de busca
Arvores binarias generalizam a ideia de listas encadeadas. Da mesma forma,
arvores binarias de busca generalizam a ideia de listas encadeadas crescentes. Em inglês, essas arvores sao
<page:2>
conhecidas como search trees. Dizemos que uma arvore binaria e de busca (ou de pesquisa) se cada uma de suas
celulas tem a seguinte propriedade: a chave da celula e
<page:3>
maior ou igual que a chave de qualquer celula na subarvore esquerda e menor ou igual que a chave de qualquer celula
na subarvore direita.
<page:4>
Em outras palavras, se r e o endereco de uma celula qualquer, se q e o endereco de alguma celula na subarvore esquerda
de r e se s e o endereco de alguma celula na subarvore direita de r entao
<page:5>
q.chave menor ou igual a r.chave menor ou igual a s.chave.

 

Saída esperada
 

arvores,1
busca,1
celula,2,3,4
chave,2,3,5

 

Saída do programa (errada)

 

busca, 1 
arvores, 1 
busca, 1 
arvores, 1 
busca, 2 
chave, 2 
celula, 2 
chave, 3 
celula, 3 
chave, 3 
celula, 3 
celula, 4 
celula, 4 
celula, 4 
chave, 5 
chave, 5 
chave, 5 

 

 

Sobre o programa

 

// verifica se ela ta vazia
bool arvoreVazia(PtrNoArvore* arvore) { return (*arvore == NULL); }

// insere elementos na arvore
bool inserearvore(PtrNoArvore* arvore, char* x)
{
    char aux;
    aux = x[0];

    if (*arvore == NULL)
    {
        (*arvore)           = malloc(sizeof(NoArvore));
        (*arvore)->direita  = NULL;
        (*arvore)->esquerda = NULL;
        for (int i = 0; i < 10; i++) { (*arvore)->key[i] = x[i]; }
        return true;
    }

 

Evite trechos assim. O usual é ter apenas ponteiros e retorna os valores, como por exemplo

 

Arvore* arv_cria();
Arvore* arv_apaga(Arvore*);
int     arv_insere(Registro*, Arvore*);

 

E sua árvore tem nodes e os nodes tem --- apontam para --- registros. É muito mais simples.

 

E as funções que tratam seus dados não deveriam ter qualquer referência à arvore. É melhor para você.

 

A estrutura de dados deve ficar DENTRO da implementação. porque é mais simples.

 

Sobre a lógica

 

Acho que você já sabe...

 

2 horas atrás, filipeoioi disse:

acho que eu deveria utilizar algum outro tipo de ED para imprimir o índice de forma correta

 

Sim, O seu node está errado, ou inconveniente ao menos...

 

Compare com esse exemplo (não testado)

 

typedef struct
{
    char*    palavra;
    unsigned n;    // quantas tem
    int*     pag;  // as paginas
} Registro;

typedef struct st_node
{
    Registro*       info;
    struct st_node* L;
    struct st_node* R;
} Node;

typedef struct 
{
    unsigned N; // nodes
    Node*           raiz;
} Arvore;


Arvore* arv_cria();
Arvore* arv_apaga();
int     arv_insere(Registro*, Arvore*);

 

Assim o índice está sempre pronto