Alguem tem Patricia trie ? [RESOLVIDO]

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 17:58h

Estou precisando de uma patricia trie pra armazenar bits de rede de 32bits.
Apenas com função de inserir e busca ja está louco de vão.

Se alguém tiver por favor manda pra mim: bruno_peinado2004@yahoo.com.br

stilldre
(usa Funtoo)

Enviado em 13/06/2010 - 18:18h

já pensou em adquirir suporte especializado??

#ifndef PATRICIA_TRIE_H
#define PATRICIA_TRIE_H

#define NUMBER_OF_LETTERS_IN_ALPHABET 26
#define MAX_KEY_BITS 32
#define EMPTY_NODE 0
#define CONV_FACTOR_ASCII_TO_INT 65
#define LOWER_TO_UPPER_FACTOR 32
#define START_BIT_COUNT 0
#define ASSOCIATED_CLASS PayloadC //classe associada ao texto guardado pela classe pat
#define END_OF_STRING '\O'


mostre o que já fez e talvez possamos ajudá-lo...

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 18:33h

Compila compila mas, causa falha de fragmentacao.
Acho que eu estou alocando errado.

Na arvore AVL era so fazer.

trie cria_arvore() {//funcao que aloca nemoria
trie aux = (trie) malloc(sizeof(struct trie));
aux->raiz=NULL;
return aux;
}

Dai sempre que eu fosse usar a arvore avl, eu chamava por
trie T = cria_arvore();


Essa eh a minha libPatricia.c
############################################
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "libPatricia.h"
#include "libTrie.h"


Dib Bit(IndexAmp i, ChaveTipo k)
{
int c, j;
if(i == 0) return 0;
else{
c=k;
for (j =1; j<= D;j++) c/=2;
return(c & 1);
}
}

short EExterno(Arvore p)
{//verifica se p eh nodo externo
return (p->nt == Externo);
}

Arvore CriaNoInt(int i, Arvore *Esq, Arvore *Dir)
{
Arvore p;
p=(Arvore)malloc(sizeof(PatNo));
p->nt = Interno;
p->NO.NInterno.Esq=*Esq;
p->NO.NInterno.Dir=*Dir;
p->NO.NInterno.Index=i;
return p;
}

Arvore CriaNoExt(ChaveTipo k)
{
Arvore p;
p=(Arvore)malloc(sizeof(PatNo));
p->nt = Externo;
p->NO.Chave =k;
return p;
}

void Pesquisa(ChaveTipo k, Arvore t)
{
if(EExterno(t)){
if(k == t->NO.Chave)printf("Elemento Encontrado\n");
else printf("Elemento nao encontrado");
return;
}

if(Bit(t->NO.NInterno.Index, k) == 0)
Pesquisa(k,t->NO.NInterno.Esq);
else Pesquisa(k,t->NO.NInterno.Dir);
}

Arvore InsereEntre(ChaveTipo k, Arvore *t, int i)
{
Arvore p;
if((EExterno(*t)) || (i<(*t)->NO.NInterno.Index))
{ //cria novo no extrerno
p= CriaNoExt(k);
if(Bit(i,k) ==1) return (CriaNoInt(i,t,&p));
else return(CriaNoInt(i, &p, t));
}
else{
if(Bit((*t)->NO.NInterno.Index,k) ==1)
(*t)->NO.NInterno.Dir = InsereEntre(k,&(*t)->NO.NInterno.Dir,i);
else (*t)->NO.NInterno.Esq = InsereEntre(k,&(*t)->NO.NInterno.Esq,i);
return(*t);
}
}
Arvore Insere(ChaveTipo k, Arvore *t)
{
Arvore p;
int i;
if(*t == NULL)
return (CriaNoExt(k));
else{
p=*t;
while (!EExterno(p)){
if(Bit(p->NO.NInterno.Index,k)==1)
p=p->NO.NInterno.Dir;
else p=p->NO.NInterno.Esq;
}
//acha o primeiro bit diferente
i = 1;
while ((i<=D) &(Bit((int)i,k)==Bit((int)i,p->NO.Chave))) i++;
if (i>D){
printf("Erro>chave ja existe\n");
return(*t);
}
else return (InsereEntre(k,t,i));
}
}


###########################################
Esse eh o libPatricia.h
##########################################
#ifndef _LIBPATRICIA_H_
#define _LIBPATRICIA_H_
#define D 8 //depende de chavetipo

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

typedef unsigned char ChaveTipo;
typedef unsigned char IndexAmp;
typedef unsigned char Dib;

typedef enum{
Interno, Externo
}NoTipo;

typedef struct PatNo* Arvore;
typedef struct PatNo{
NoTipo nt;
union{
struct{
IndexAmp Index;
Arvore Esq, Dir;
}NInterno;
ChaveTipo Chave;
}NO;
}PatNo;

PatNo cria();
Arvore Insere(ChaveTipo k, Arvore *t);
Arvore InsereEntre(ChaveTipo k, Arvore *t, int i);
void Pesquisa(ChaveTipo k, Arvore t);
Arvore CriaNoInt(int i, Arvore *Esq, Arvore *Dir);
Arvore CriaNoExt(ChaveTipo k);
short EExterno(Arvore p);
Dib Bit(IndexAmp i, ChaveTipo k);
#endif

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 18:36h

assim e tem a libTrie mas a Trie funciona.

###########################################
libtrie.h
###########################################
#ifndef _LIBTRIE_H_
#define _LIBTRIE_H_

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

typedef struct no {
int chave, vetor[32];
struct no *esq;
struct no *dir;
} *no;

typedef struct trie {
struct no *raiz;
} *trie;

trie cria_arvore ();
int busca(no noaux, int auxvetor[32], int posicao, int dados);
int insere (no *noatual, int valor, int n[32], int posicao);
void ZeraVetor(int vetor[], int tamanho);
void LeVetor(int vetor[], int tamanho);
void LeVetorDetalhado(int vetor[], int tamanho);
int imprime (no arvore);

#endif

###############################
libTrie.c
###############################
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "libTrie.h"

trie cria_arvore() {//funcao que aloca nemoria
trie aux = (trie) malloc(sizeof(struct trie));
aux->raiz=NULL;
return aux;
}

void ZeraVetor(int vetor[], int tamanho)

{
int i;
for (i=0; i<tamanho;i++)
vetor[i] = 0;
}
void LeVetor(int vetor[], int tamanho)
{
int i;
for (i=tamanho-1; i>=0;i--)
printf("%d", vetor[i]);
}
void LeVetorDetalhado(int vetor[], int tamanho)
{
int i;
for (i=0; i<tamanho;i++)
{
printf("Vetor[%d]: ", i);
printf("%d\n", vetor[i]);
}
}
//possicao = vetor de bits[posicao]
//dados numero procurado
//vetor = vetor que esta sendo procurado
int busca(no noaux, int vetor[32], int posicao, int dados)
{
//LeVetor(vetor,31);
//printf("\nnoaux->chave: %d", noaux->chave);
//printf("vetor[%d]: ", posicao);
//printf("%d,", noaux->vetor[posicao]);
if (noaux == NULL)
{
printf("\n\nERRO: nao existe!\n");
return 0;
}
if (posicao > 0)
{
posicao = posicao-1;
LeVetor(vetor,posicao+1);
printf(",");
if (vetor[posicao] == 1)
busca(noaux->dir,vetor,posicao,dados);
else
busca(noaux->esq,vetor,posicao,dados);
}
if (posicao == 0)
printf("(%d)", noaux->chave);
}


int insere (no *noatual, int valor, int n[32], int posicao)
{
int i;
//printf("\nValor->%d\n", valor);
//print f("posicao->%d\n", posicao);
//LeVetorDetalhado(n,31);

if((valor == 2147483647) || (valor < 0))
{
printf("\nERRO: numero recusado\n");
return 0;
}
//printf("P:%d, ", posicao);
if (posicao > -1)
{
posicao = posicao -1;
if(n[posicao] == 0)//entao vai pra esquerda
{
// printf("<");
if ((*noatual) == NULL){
(*noatual) =(no) malloc(sizeof(struct no));
(*noatual)->vetor[posicao] = 0;
//(*noatual)->esq = NULL;
//(*noatual)->dir = NULL;
insere(&(*noatual)->esq, valor, n, posicao);
}
else
insere(&(*noatual)->esq, valor, n, posicao);
}
if(n[posicao] == 1)
{
if ((*noatual) == NULL){
//printf(">");
(*noatual) =(no) malloc(sizeof(struct no));
(*noatual)->vetor[posicao] = 1;
//(*noatual)->esq = NULL;
//(*noatual)->dir = NULL;
insere(&(*noatual)->dir, valor, n, posicao);
}
else
insere(&(*noatual)->dir, valor, n, posicao);
}
}
if((*noatual) == NULL)
{
//printf("\nachou null\n");
(*noatual) =(no) malloc(sizeof(struct no));
for (i=31; i<0;i--)
(*noatual)->vetor[i] = n[i];
(*noatual)->chave = valor;
(*noatual)->esq = NULL;
(*noatual)->dir = NULL;
LeVetor(n,31);
printf("\nInserido: %d com sucesso!\n", (*noatual)->chave);
return 1;
}

}

int imprime (no arvore)
{

int a=1,b=1;
if (arvore != NULL)
{
printf("(%d,", arvore->chave);
a = imprime(arvore->esq);
b = imprime(arvore->dir);
printf(")");
//if (b == 0)
/// printf("(),");
//if (a == 0)
// printf("(),");
}
else
printf("()");
return 0;
}

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 18:37h

Eu só não procuro suporte especializado, porque isso é trabalho de faculdade. Daí utiliza a estrutura de trie e patricia, teoricamente eu sei como funciona mas quando é pra implementa daí complica nessas alocação de memoria.

stilldre
(usa Funtoo)

Enviado em 13/06/2010 - 18:45h

por que nao usa em conjunto com o metodo huffman? vc esta usando c puro? eu faço em c++

#define DEBUG 1
#define MAX_STRING_FOR_KEY MAX_KEY_BITS+1

#ifdef DEBUG
#include <iostream.h>
#endif


typedef unsigned int keyType;
typedef char bitPositionType;

///////////////////
class PayloadC
{
private:

public:

PayloadC () {}
~PayloadC () {}
};
///////////////////
class PatriciaNodeC
{
public:

PatriciaNodeC (ASSOCIATED_CLASS* _payload, keyType _key)
{ leaf.payload = _payload; leaf.key = _key; is_leaf = true; }

PatriciaNodeC (void)
{ internal.left = EMPTY_NODE; internal.right = EMPTY_NODE; is_leaf = false; }

~PatriciaNodeC ()
{ }

{
struct
{
PatriciaNodeC* left;
PatriciaNodeC* right;
}
internal;

struct
{
ASSOCIATED_CLASS* payload;
keyType key;
}
leaf;
};

bool is_leaf;
};
....

depois.... joga o metodo huffman aqui... com a construtora do patriciatriec

stilldre
(usa Funtoo)

Enviado em 13/06/2010 - 18:51h

vou te mandar um pat... ta como .zip mas é em c++... se ajudar...

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 18:53h

Foi exigência do professor, ser em C puro.
Sou muito mais java.

Olha só eu quero aloca a estrutura da Patricia.

Dai eu fiz a funcao.

PatNo cria(){
patNo aux = (PatNo) malloc(sizeof(struct PatNo));
aux->NO=NULL;
return aux;
}

só que dai aparece error conversion to non-scalar typerequested.

peinado
(usa Ubuntu)

Enviado em 13/06/2010 - 18:55h

Meu principal problema nessa patricia.
É em como devo fazer a alocação inicial.

Pra iniciar a arvore tem que aloca na memoria antes de tudo, mas eu estou apanhando pra alocar essa estrutura da libPatricia.h

stilldre
(usa Funtoo)

Enviado em 13/06/2010 - 19:06h

pois é... o problema é que malloc não aloca blocos de memória nao contíguos... e quando a alocação é não contígua como mostrado, o codigo falha... a solução seria alocar assim:

int main(void)
{
struct { size_t x; char a[]; } *p;
p = malloc(sizeof *p + 100);
if (p)
{
// agora voce acessa p->a[99] com segurança
}
}

stilldre
(usa Funtoo)

Enviado em 14/06/2010 - 11:08h

e aí??? nenhuma notícia == boas notícias??? gostaria muito de saber se funcionou... aguardo o feedback...

peinado
(usa Ubuntu)

Enviado em 16/06/2010 - 15:08h

Funcionar funcionou, faz além do que eu esperava.
Ainda estou vendo como funciona o algortmo da patricia com o huffman.