Função HASH em C++

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

[ Hits: 10.736 ]

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

Algoritmo de ordenação Quick Sort

Locadora Simples c/arquivos

CD Player 0.1

2° mod do CGI

Exemplo de sistema especialista usando Inteligência Artificial


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

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

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts