Ir ao conteúdo
  • Cadastre-se
Daniel Teles Barbosa

Encontrar combinações em uma arvore trie

Recommended Posts

Boa tarde pessoal, estou com o seguinte trabalho de estutura de dados  2 para fazer:

 

 

 Implemente em c um sistema que leia um texto escrito com caracteres ASCII e insira todas as combinações de caracteres do texto com no máximo 30 caracteres em uma árvore TRIE. Em seguida o sistema deve permitir que o usuário digite sequências de caracteres de no máximo 30 caracteres e o sistema retorne todas as ocorrências (posições) da sequência dentro do texto.

            Por exemplo, considere o seguinte texto:

1 Uma função de transformação perfeita é específica para um conjunto de chaves conhecido, ao contrário

2 da função de transformação universal apresentada no programa anterior. Em outras palavras, ela não

3 pode ser uma  função genérica e tem de ser pré-calculada.

 

Para o texto acima, caso o usuário informe a sequência “perfeita”, o sistema deverá imprimir:

Perfeita : Linha 1, coluna 29

            Para a implementação, necessariamente deve ser utilizada a estrutura de dados Árvore PATRICIA para o armazenamento das combinações do texto.

            Para o armazenamento das posições utilize um vetor.

 

 

 

 

Pois bem, eu já tenho uma função para gerar as combinações para qualquer arquivo de texto e estou salvando em um arquivo apenas para a visualização das combinações : 

 

#include <stdio.h>

#include <stdlib.h>
#include <string.h>
 
 
typedef struct no {
    char ch;
    int linha;
    int coluna;
}Info;
 
typedef struct ocorrencias {
int quant;
struct no ocorr[100];
}ListaOcorrencias;
 
 
 
 
 
 
void leiaVet(Info * v, int * tam) {
    int i=0;
    while(i<(*tam))
    {
 
 
        printf("\n %c - Linha %d - Coluna %d",v.ch,v.linha,v.coluna);
 
        i++;
    }
 
}
 
void combinacoes(Info *v , int *tam, FILE *arq) // estrutura que utiliza o força bruta para fazer as combinações
{
    int i,j,k,l;
    int qtd=0;
    i=0;
    while (i < 30){
        j = 0;
        k = i;
        while(k<=(*tam-1)){
            fprintf((arq),"\n%c", '\n');
            for(l = j; l <= k; l++) {
            qtd++;
            if(l==k){
 
                    fprintf((arq),"%c ----- LINHA %d | COLUNA %d",v[l].ch,v[l-i].linha,v[l-i].coluna);
                }
                else{
                    fprintf((arq),"%c", v[l].ch);
 
                }
            }
 
            j++;
            k++;
        }
        i++;
    }
    fprintf((arq),"\n\n%c", ' ');
    fprintf((arq),"",(*tam),qtd);
}
 
 
 
 
 
 
int main(){
char txtI[]="TEXTO.txt";
char txtII[]="COMBINADO.txt";
char ch;
int qChar=0, qLinha=1, qColuna=0;
    int i=0;
    Info vet[500];
    FILE *arq;
FILE *combinado;
arq = fopen(txtI, "r");
    combinado = fopen(txtII, "r+");
if(combinado == NULL){ // verificando o estado do arquivo
        printf("ERRO!!!!\n");
    }
if(arq == NULL) {
        printf("ERRO!!!!\n");
        qLinha=0;
        qColuna=0;
    }
else{
        fprintf((combinado),"", ' ');
   while( (ch=fgetc(arq))!= EOF){
 
            putchar(ch);
            qChar++;
            qColuna++;
            vet.ch = ch;
            vet.coluna = qColuna;
            vet.linha = qLinha;
            fprintf((combinado),"%c",vet.ch);
            i=i+1;
            if(ch =='\n'){ // verificando se quebrou linha ou não..
                qLinha ++;
                vet.linha=qLinha;
                qColuna=0;
            }
        }
        fprintf((combinado),"\n\n%c\n", ' ');
    }
    printf("\n A quantidade de characteres no texto é de : %d\n",qChar); // imprimindo na tela apenas para controle do arquivo
    printf("A quantidade de linhas é : %d",qLinha); // verificando se está certo ou não ( imprimindo na tela)
    printf("\n A quantidade de colunas é: %d ", qColuna);
    fprintf((combinado),"\n\n%c", ' ');
    combinacoes(vet,&qChar,combinado); // chamando a função de combinar hehe
fclose(arq);
    fclose(combinado);
 
    return 0;
}
 
 
 
E tenho também um codigo da arvore TRIE... o meu problema é o seguinte... não estou conseguindo alterar a arvore TRIE para poder realizar o que o trabalho pede... alguém aí já fez algo parecido ou tem alguma ideia? 
 
 
o codigo da trie : #include <stdio.h>
#include <stdlib.h>
 
typedef struct no{
    char info;
    struct no* esq; // bit 0
    struct no* dir; // bit 1
}ArvoreTRIE;
 
int pega_bit(char info,int pos){
    return (info >> (7-pos)) & 1;
}
 
ArvoreTRIE* insere(ArvoreTRIE* arv, char info,int pos){
    ArvoreTRIE* novo;
    if(arv == NULL){
        novo = malloc(sizeof(ArvoreTRIE));
        novo->esq = novo->dir = NULL;
        if(pos == 8)
            novo->info = info;
        else{
            if(pega_bit(info,pos) == 0) {
                novo->esq = insere(novo->esq,info,pos+1);
            }else{
                novo->dir = insere(novo->dir,info,pos+1);
            }
        }
        return novo;
   }else{
       if(pega_bit(info,pos) == 0){
           arv->esq = insere(arv->esq,info,pos+1);
           return arv;
       }else{
           arv->dir = insere(arv->dir,info,pos+1);
           return arv;
       }
   }
}
 
ArvoreTRIE* inserir_trie(ArvoreTRIE* arv,char info){
    arv = insere(arv,info,0);
    return arv;
}
 
void caminhaEmOrdem(ArvoreTRIE *arv){
    if( arv != NULL){
        caminhaEmOrdem(arv->esq);
        if((arv->esq == NULL) && (arv->dir == NULL))
            printf("%c\n",arv->info);
        caminhaEmOrdem(arv->dir);
    }
}
 
ArvoreTRIE* remover(ArvoreTRIE* arv, char info, int pos){
    if(arv != NULL){
        if((pos == 8) && (arv->info == info)){
            free(arv);
                return NULL;
        }else{
            if(pega_bit(info,pos)== 0)
                arv->esq =  remover(arv->esq,info,pos+1);
            else
                arv->dir =  remover(arv->dir,info,pos+1);
 
            if((arv->esq == NULL) && (arv->dir == NULL)){
                free(arv);
                    return arv;
            }else
                return arv;
        }
    }else
        return arv;
}
 
ArvoreTRIE* RemoveTrie(ArvoreTRIE* arv, char info){
    return remover(arv,info,0);
}
 
 
int main (){
    ArvoreTRIE* A = NULL;
 
    A = inserir_trie(A,'B');
    A = inserir_trie(A,'C');
    A = inserir_trie(A,'J');
    A = inserir_trie(A,'M');
 
    printf("Arvore Trie Original\n");
    caminhaEmOrdem(A);
    A = RemoveTrie(A,'B');
 
    printf("Arvore Trie apos a exclusao do B\n");
    caminhaEmOrdem(A);
 
return 0;
}
 
Sei que o topico ficou confuso, porém já estou desesperado pra acabar isso, rs desde já obrigado.
 

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Acho que não precisa daquela função de força bruta lá.

Basicamente você só precisa mesmo percorrer o texto normalmente, fazendo as inserções.

Exemplo: "uma função de transformação perfeita"

Adiciona (u)

Adiciona (um) (a função de inserir da árvore trie vai achar o nó "u" e inserir "um" como uma folha de "u")

Adiciona (uma) (mesma coisa... a árvore procura "um" e adiciona "uma" como folha dele)

(espaço) --> não faz nada

Adiciona (f)

Adiciona (fu) em f

Adiciona (fun) em fu

Adiciona (funç) em fun

etc.

Ou seja, é só separar o texto em palavras, e adicionar todas as substrings daquela palavra na árvore.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Entendi, o problema cara é que na verdade não deve ser feito as inserçoes na arvore, digo... cada nó da arvore trie tem um vetor para 256 posições ( numero de codigos da tabela ascII).. a partir desses vetores de 256 posições que eu devo percorrer na arvore... eu estava tentando fazer desse jeito inserindo as combinações na arvore mas não deu. Por orientação do professor ele disse que não quer q insira as combinações, apenas que percorra pela arvore e encontre a posição linha e coluna daquela palavra! 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Eu não entendi.

Pra percorrer a árvore e encontrar as combinações, aquelas combinações precisam ser adicionadas antes, né?

Como a árvore vai saber que o elemento "u" da raiz tem uma folha "-ma" e outra folha "-niversal" se você não inserir elas?

Compartilhar este post


Link para o post
Compartilhar em outros sites

esse é o grande ponto da questão! As combinaçoes não são inseridas na arvore! Cada nó da trie tem um vetor para retornar linha e coluna daquela combinação e outro vetor de 256 posições com todos os elemtnos possiveis no texto! Daí teremos ...

 

Para achar a combinação "Uma" no primeiro nó desce pelo ponteiro para o U

Em seguida desce pelo ponteiro para o M 

E por ultimo pelo ponteiro para o A...

 

Tá conseguindo entender? 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Cara, eu sei como funciona uma árvore trie... o que eu tô tentando dizer, é que por padrão a árvore começa vazia. O programador precisa adicionar esses valores.

Por exemplo, você tem uma estrutura assim:

struct No {    struct No* elementos[255]; // vetor que vai guardar os ponteiros pras próximas folhas    ...}
Você cria a raiz da tua arvore:

struct No* raiz;

Começa a ler o texto:

"teste testando"

Adiciona (t). O algoritmo de inserção procura a posição de 't' da raiz. Se for NULL, adiciona a posição.

raiz->elementos[(posição de t)] = malloc(blablabla);

Depois você lê o "te", daí procura na raiz a posição do "t" e adiciona o "e":

raiz->elementos['posição de t']->elementos['posiçao de e em t'] = malloc(blablabla);

Depois adiciona o "tes". Procura a posição de 't', depois a posição de 'e' em t, e adiciona o 's' em 'e'.

raiz->elementos['posição de t']->elementos['posição de e em t']->elementos['posição de s em e'] = malloc(...);

E vai repetindo isso até ler o texto inteiro, de modo que no final você tenha uma árvore assim:

[null, null, null, null, ... 't', null, null, ...]                              |            [null, null, ... 'e', null, null, ...]                              |                        [... 's', ...]                              |                        [... 't', ...]                              |                             / \                            /   \                     [... 'e'] ['a', ...]                                 |                           [... 'n', ...]...etc
Ou seja, é você quem insere os valores na árvore. Eles não estão lá por padrão. Apenas as posições estão lá, mas elas começam vazias.

Compartilhar este post


Link para o post
Compartilhar em outros sites

No google tem um monte de códigos prontos de árvore trie em C e C++.

Daí você se preocupa apenas com a lógica da tua struct e de percorrer o texto.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×