Função HASH em C++

Publicado por José Cleydson Ferreira da Silva (última atualização em 09/03/2010)

[ Hits: 10.580 ]

Homepage: geminivirus.org

Download teste-1.cpp




Essa é uma simples introdução a estruturação de dados que faz um simples HASH com complexidade O(n) - int h(string nome) -, seu resultado é apurar o número de colisão.

Para compilá-lo basta usar o compilador g++ da seguinte forma:

$ g++ teste-1.cpp -o teste-1.exe
$ ./teste-1.exe

  



Esconder código-fonte

#include <iostream>
#include <string>

using namespace std;

struct Pessoa
{
   string nome;
   int colisao;
};

char alfabeto[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','x','z','w','y'};

string lerNome()
{
   string nome;
   
   cout << "informe o proximo nome: " << endl;
   cin >> nome;
   
   if (nome == "")
   {
     cout << "Nome não pode ser vazio: " << endl;
     return "";
   }
   
   return nome;
}

int h(string nome)
{
   char letra;
   int soma = 0;
   int somaFim = 0;
   
   for(int n=0; n < 15 ; n++)
   {
      letra = nome[n];
      for (int i=0; i<=40; i++)
      {
         if(letra == alfabeto[i])
         {
            soma = i + 43;
            break;
         };
      };
      somaFim += soma;
         
   };
   
   somaFim = somaFim * 3;
   somaFim *= somaFim;
   
   return somaFim % 7;
}

Pessoa* inicializarColisoes()
{
    Pessoa *pessoas = new Pessoa[7];
    for (int i=0; i<7; i++)
    {   
      pessoas[i].nome = "";
      pessoas[i].colisao = 0;
    }
    
    return pessoas;
}

void mostrarColisoes(Pessoa *pessoas)
{
  for (int i = 0; i<7; i++)
  {
     // if (pessoas[i].nome == "")
   // break;
      
      cout<<"Posição " << i << endl;
      cout<<"Colisões " << pessoas[i].colisao << endl << endl;
  }
}

int main()
{
   Pessoa *p = new Pessoa[7]; 
   p = inicializarColisoes();
   int tam; //define o tamanho da palavra para n�o ser preciso ir at� o final da palavra
   int somaLetra;
   string nome;
   int valorHash;
   char sair = 'n';
   
   while (sair != 's' )
   {
      nome = lerNome();
      if (nome == "")
          continue;
      valorHash = h(nome);
      cout<<"Valor Hash: "<<valorHash<<endl;
      if (p[valorHash].nome != "")
      {
         p[valorHash].colisao++;         
      }
      p[valorHash].nome = nome;
      
      cout << "Deseja sair?" << endl;
      cin >> sair;
   }
   
   mostrarColisoes(p);

   return 0;
}


Scripts recomendados

Árvore B com Arquivos (inserção e pesquisa)

Fila em C

Função "Partição de Inteiros" Recursiva COM Tabela Estática em C

Cálculo de logaritmo de um número por Método de Newton-Raphson em C

Escaneando diretório


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts