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

• Download teste-1.cpp
• Enviar nova versão

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;
}

Google Code Jam 2010 - Africa Classification Round A

Minishell

[C] Fatorial ilimitado

livraria

Jogo Snake (com gráficos)

Nenhum comentário foi encontrado.