Lista Encadeada para colisões Tabela Hash

[Minduca]

Olá a todos,

Estou com uma dificuldade em entender(implementar em C)

um código que trata de colisão numa tabela hash utilizando

lista encadeada, não estou conseguindo montar o código,

sei que o princípio e fazer com que as chaves que tiveram

o enderço hash colididos vão para uma lista encadeada

através de um ponteiro?!!...mas como seria isso em C ??

estou estudando C para conhecer por conta própria mas

esta parte de tabelas hash não estou conseguindo visualizar

estou TENTANDO fazer um código para consulta, inserção e

remoção, mas não estou conseguindo!!!

att

Minduca

[p4t0X]

Posta alguma coisa ae, e fala a dúvida

[Minduca]

Posta alguma coisa ae, e fala a dúvida

Olá p4t0X,

o que fiz aqui foi a inclusão inserção deleção lista encadeada, porem

sem o tal do tratamento de colisão para uma tabela hash, ok?

veja abaixo:

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


struct lista_no {                 /* representação do nó */
 int info;
 struct lista_no *ant;
 struct lista_no *prox;
};

typedef struct lista_no LISTA;

LISTA* criar(void);
LISTA* insert(LISTA* l, int v);
LISTA* buscar(LISTA* l, int v);
LISTA* remover(LISTA* l, int v);


main(void) 
{ 
    inv v;
    printf("\nEntre com a chave: ");
    scanf("%d",&v); 
    LISTA *p;
    p=criar();
    p=inserir(p,v);
    printf("Fim P -->%p\n",p);   /* dou um print no endereço da inserção */
    system("PAUSE");
    
getch();
return (0);
}

LISTA* criar(void)              /* aqui é a inicialização da Lista */
{
    return NULL;
}

LISTA* inserir(LISTA* l, int,v)  /* Inserindo o registro no início da lista */
{
    LISTA* novo = (LISTA*) malloc(sizeof(LISTA));
    novo->info = v;
    novo->prox = l;
    novo->ant  = NULL;
    
    if(l != NULL)                /* verifico a lista não vazia */
       l->ant = novo;
    return novo;
}

LISTA* buscar(LISTA* l, int v)   /* busca a chave digitada v */
{ 
    LISTA* p;
    for(p=l;p!=NULL;p=p->prox)
       { 
          if(p->info == v)
             return p;           /* endereço encontrado */
       }
    return NULL;                 /* endereço não encontrado */
}

LISTA* remover(LISTA* l, int v)  /* remover chave digitada */
{
    LISTA* p = buscar(l,v);      /* uso primeiro a função buscar */

    if(p == NULL)
       return l;                 /* não encontrou */

    if(l == p)                   /* verifica se é 1º elemento */
       l = p->prox;
    else
       p->ant->prox = p->prox;

    if(p->prox != NULL)          /* verifica se é o último elemento */
       p->prox->ant = p->ant;
    free(p);

    return l;
}

Minhas dúvidas estão sendo as seguintes:

1 - quero fazer o tratamento hash utilizando o método

da divisão, ok?

2 - neste caso como seria esta código dentro do que já fiz?

faço a função para obter o endereço hash onde?

3- faço somente na função de inclusão, pois é aí que precisarei

verificar se há colisão dos endereços das chaves?

4 - Se for isso, como faço este código para implementar neste que já construí?

Em suma, não sei como será o código para implemento da colisão e nem

onde exatamente aplicá-lo?? Na teoria?, após encontrado a chave cujo endereço

hash tiver colidido com um já existente, tenho que apontar para lista encadeada este

endereço colidido, estou perdidão!!!! o que uso para apontar é o VALOR da chave

digitada ou o endereço da função hash encontrado??

Agradeço desde já

Minduca.

[p4t0X]

Você deve ter procurado na net por algum material, mais oh, vê se dá uma clareada:

http://pt.wikipedia.org/wiki/Tabela_de_hashing

Pra quando você tem que entregar isso?!

[Minduca]

Você deve ter procurado na net por algum material, mais oh, vê se dá uma clareada:

http://pt.wikipedia.org/wiki/Tabela_de_hashing

Pra quando você tem que entregar isso?!

Olá p4t0X,

Seguinte, não tem data de entrega nehuma, cliquei no link

que sugeriu, e verifiquei que é um link que já havia consultado

o que estou fazendo é isso, busco na net o que estou interessado

em aprender passo pro meu devc++ para poder analisar e entender

o código depois tento fazer um baseado no que tenho entendido do

exemplo que consegui sobre aquele assunto. Eu até tenho alguns códigos

de exemplo de colisões com listas encadeadas, só que não estou conseguindo

entendê-los, e de mais a mais, se fosse algo para entrega, seria porque

estou estudando em algum curso, aí bastaria eu pedir a meu instrutor

que explicasse o funcionamento do código que já tenho e o problema

estaria resolvido e não precisaria passar por nehum constrangimento.

O que ocorre é que lista eu até entendi, o que fiquei perdido é

com relação a tabela hash com colisões, eu teria que fazer uma lista encadeada

dentro da própria tabela hash?? ou seja, seria uma tabela dentro de outra tabela??

Estou confundindo-me na pratica com relação ao conceito e se estivesse estudando

isso, não era pra ter dificuldade, pelo menos com a relação ao conceito, entende?

De qualquer forma, sigo meu auto estudo, acho legal isso, porque com certeza

quando conseguir, será uma coisa que não esquecerei jamais por causa das

confusões e dificuldades que estou tendo.

Valeu mesmo, ao menos você retornou meu chamado.

Minduca

[p4t0X]

Ahhh, perfeito então!

Assim fica mais fácil!

O conceito da tabela de hash você entendeu, certo?!

[== Douplus ==]

Boa noite, Minduca!

Também nunca implementei uma tabela hash embora já tenha lido a respeito várias vezes. Então pau na máquina!

Minhas dúvidas estão sendo as seguintes:

1 - quero fazer o tratamento hash utilizando o método

da divisão, ok?

Ok.

2 - neste caso como seria esta código dentro do que já fiz?

faço a função para obter o endereço hash onde?

Faça uma função de hash que receba como parâmetro o tipo de dados que você quer associar a chave (a chave no caso é int, né?)

3- faço somente na função de inclusão, pois é aí que precisarei

verificar se há colisão dos endereços das chaves?

Você pode fazer a função de inclusão chamar a função hash, ou pode chamar a função hash e passar a chave para a função de inclusão.

4 - Se for isso, como faço este código para implementar neste que já construí?

Pensei assim:

struct entrada_hash {                 /* representação da entrada */
  int chave;
  void *info; 
  struct EntradaHash **ant;
  struct EntradaHash **prox;
  struct EntradaHash *duplicatas;     /* lista de duplicatas */
};
typedef struct entrada_hash EntradaHash;

typedef struct tab_hash {
  EntradaHash *rootPtr, *primeiraEntrada, *ultimaEntrada;
  const unsigned int tamanho;
} TabelaHash;

TabelaHash criar(const int tamanho);   /* cria a tabela, tamanho indica quantas entradas pode receber inicialmente */
EntradaHash *inserir(const int c, void *i);
EntradaHash *TabelaHash buscar(TabelaHash *th, EntradaHash i);
EntradaHash *remover(TabelaHash*th, const int c);

int hash(void *i, const int numDeBytes); /* função hash */
void *redimensionar(TabelaHash *th, const int tamanho); /* redimensiona a tabela, pode ser chamada também por inserir() */

Observações:

1-) optei por usar ponteiro para void porque não seiqual tipo de dados quer associar com as chaves, desse modo um ponteiro genérico (void *) para a variável é armazenado;

2-) essas estruturas que definí para a tabela hash são variações das suas usadas para a lista.

Em suma, não sei como será o código para implemento da colisão e nem

onde exatamente aplicá-lo?? Na teoria?, após encontrado a chave cujo endereço

hash tiver colidido com um já existente, tenho que apontar para lista encadeada este

endereço colidido, estou perdidão!!!! o que uso para apontar é o VALOR da chave

digitada ou o endereço da função hash encontrado??

Na estrutura EntradaHash acrescentei uma lista de duplicatas, se não tiver nenhuma o ponteiro deve apontar para NULL.

È de quebrar um pouco a cabeça, para fazer tudo isso pensei que a tabela hash é um multimap (em C++ daria pra usar STL) e desenvolví um pouco.

Boa sorte, e quaisquer progressos ou problemas, posta aí por favor!

Até mais!

[Minduca]

Boa noite, Minduca!

quote]

Na estrutura EntradaHash acrescentei uma lista de duplicatas, se não tiver nenhuma o ponteiro deve apontar para NULL.

È de quebrar um pouco a cabeça, para fazer tudo isso pensei que a tabela hash é um multimap (em C++ daria pra usar STL) e desenvolví um pouco.

Boa sorte, e quaisquer progressos ou problemas, posta aí por favor!

Até mais!

Opa Douplus,

Agora sim deu uma bela clareada, pois nestes processos de passar parâmetros e de onde usar a função hash

estava perdidão mesmo!!! Já deu uma bela clareada!!!

Até entendo que o p4t0X possa ter me interpretado como uma pessoa que estivesse querendo que ele fizesse

algo pra mim, mas repito, cara se tivesse grana estaria ou fazendo um curso ou uma faculdade... então às vezes

vejo algo que não consigo compreender de início, até comecei uma facul, mas meu pai perdeu o trampo e tive de fechar a

matrícula e foi nesta faculdade mesmo que me interessei pela linguagem C que havia começado a estudar. Espero

que esta crise acabe logo e que eu e meu pai consigamos um trampo.

Valeu mesmo, a ajuda cara!

Minduca

obs. assim que conseguir posto o código aqui pra todos poderem consultar, mesmo que demore, como

não é para entregar a ninguém e sim para meu conhecimento, tempo é o que não me falta!!... abraço

[Minduca]

Boa noite, Minduca!

quote]

Na estrutura EntradaHash acrescentei uma lista de duplicatas, se não tiver nenhuma o ponteiro deve apontar para NULL.

È de quebrar um pouco a cabeça, para fazer tudo isso pensei que a tabela hash é um multimap (em C++ daria pra usar STL) e desenvolví um pouco.

Boa sorte, e quaisquer progressos ou problemas, posta aí por favor!

Até mais!

Opa Douplus,

Agora sim deu uma bela clareada, pois nestes processos de passar parâmetros e de onde usar a função hash

estava perdidão mesmo!!! Já deu uma bela clareada...

Valeu mesmo, a ajuda cara!

Minduca

obs. assim que conseguir posto o código aqui pra todos poderem consultar, mesmo que demore, como

não é para entregar a ninguém e sim para meu conhecimento, tempo é o que não me falta!!... abraço

Olá a Todos, conforme dito segue o código de INSERÇÃO de registros em tabela Hash:

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

/*============================================================================*/
/*                 PROGRAMA PARA INSERIR DADOS NUMA TABELA HASH               */
/*============================================================================*/ 

struct lista_no {
   int    chave; 
   struct lista_no *prox; 
};
typedef struct lista_no LISTA; 

/* ----------------------------- Protótipos ----------------------------------*/

LISTA *criar(void); 
LISTA *insere(LISTA *a, int v, char op);
int hash(int v,int n);
void imprimir(LISTA *a);

/* --------------------------------- MAIN ------------------------------------*/

main(void)
{
  int v, n, x, cont, i =0;
  char op;
  LISTA *p;  
  
/* --------------------------- CRIANDO A TABELA ------------------------------*/

   
       printf("\nEntre com a quantidade de linhas da tabela = ");   
       scanf("%d",&n);  
       LISTA *tab[n];                                  
       for (i = 0; i < n; i++) 
            tab[i] = criar();   
/* ---------------------------------------------------------------------------*/
                       /* ENTRO COM O VALOR DA CHAVE */
  printf("\nDeseja inserir as chaves no inicio ou no final da lista ?(i/f): ");
  scanf("%s",&op); 
                 
  for(cont=0;cont<n;cont++)               
      { printf("\nEntre com o valor da chave = "); 
        scanf("%d",&v);      
        tab[hash(v,n)] = insere(tab[hash(v,n)],v,op);        
      }
/* ---------------------------------------------------------------------------*/
                          /* DESCARREGO A TABELA */
                             
  for(x=0;x<n;x++){
      printf("\n Tab[%d]:%p\n",x,tab[x]);                    
      imprimir(tab[x]); }     
        
getch();
return (0); 
}

/* ---------------------------------------------------------------------------*/
                              /* FUNÇÕES */
                         
LISTA* insere(LISTA * a, int v, char op)
{ 
  LISTA *ant = NULL;   /*  aponta para lista anterior  */
  LISTA *p = a;
              
  while (p != NULL)   /*   faz uma busca na tabela     */
   {
       if (p->chave == v)
          {
            printf("\n registro %d já existe",v);
            break;
          }
       ant = p;
       p = p->prox;       
   }
   
  if (p == NULL)   /* chave não encontrada ---> CRIANDO o NÓ -----------------*/
     {               
        
        p = (LISTA *)malloc(sizeof(LISTA));             
        p->chave = v;
        p->prox = NULL;
                    
        if (ant == NULL)      /* inserção quando a lista esta vazia */
            {a = p;
            return a;}  
        else                 /* quando a lista tem registros, verifica opção de inserção */
            if(op == 'i')    /* se a op = i, insere no início, senão, insere no final    */   
              {a = p;        
               a->prox = ant;            
               return a; } 
            else
              {ant->prox = p;
               return ant;}                  
     }     
}    
/* -------------------------------função hash---------------------------------*/

int hash(int v, int n)
{
  return (v%n);
}
/* --------------------------função imprimir recursiva -----------------------*/

void imprimir(LISTA *a)
{      LISTA *p = a;
       if (p != NULL){  
           printf("\t chave = %d",p->chave);               
           imprimir(p=p->prox); }    
}
/* -------------------------------função criar--------------------------------*/
LISTA *criar()
  { return NULL; 
  }

Agradecimentos ao Sr. Douplus que muito me ajudou nesta experiência, Valeu Douplus!!!

abraços a todos

Minduca

[vhmvictor]

Opa, bom dia. Também estou implementando tabela Hash. Como ficou o código final ? Estou tento dificuldades em algumas partes...

Editado Outubro 13, 2017 por vhmvictor