Tabela hash com classes e tratamento de colisões por encadeamento

Publicado por Bruno (última atualização em 16/01/2017)

[ Hits: 3.462 ]

Homepage: ...

Download hash




Tabela hash bem simples, apenas para fixar melhor o seu funcionamento na prática.

  



Esconder código-fonte

/* by Unclear, Tabelha Hash tratando colisoes com encadeamento*/

--MAKEFILE

CPP=g++
CPPFLAGS = -W -Wall

OBJ = tabHash.o main.o

all: main

tabHash.o: tabHash.cpp tabHash.h
   $(CPP) $(CPPFLAGS) -c tabHash.cpp

main.o: main.cpp
   $(CPP) $(CPPFLAGS) -c main.cpp

main: $(OBJ)
   $(CPP) $(CPPFLAGS) -o main $(OBJ)

clean:
   rm -f *.o
   
   
--MAIN.CPP 

#include <iostream>
#include <string>

#include "tabHash.h" 

using namespace std;

int main(){
   
   int op = 0, tam = 0;
   string c = "", v = "";
   tabHash *th;

   menu();
   do{
      cout << "\nDigite uma opcao" << endl;
      cin >> op;
      switch(op){
         case 1:
            cout << "Digite um numero: " << endl;
            cin >> tam;
            th = new tabHash[tam];
            break;
         case 2:
            cout << "Digite uma chave: " << endl;
            cin >> c;
            cout << "Digite um conteudo: " << endl;
            cin >> v;
            th->insere(c, v);
            break;
         case 3:
            cout << "Digite uma chave: " << endl;
            cin >> c;
            cout << th->recupera(c) << endl;
            break;
         case 4:
            cout << "Digite uma chave: " << endl;
            cin >> c;
            cout << "Digite um conteudo: "<< endl;
            cin >> v;
            th->altera(c, v);
            break;
         case 5:
            cout << "Digite uma chave: " << endl;
            cin >> c;
            th->remove(c);
            break;
         case 6:
            cout << endl;
            th->percorre();
            cout << endl;
            break;
         default:
            cout << "Digite uma opcao contida no menu" << endl;
      }
   }while(op != 0);
       
   return 0; 
}

--TABHASH.H 

#ifndef TABHASH_H
#define TABHASH_H 1

#include <string>

using namespace std;

int funcaoHash(string c, int tam);
void menu();

class noh{
friend class tabHash;
private:
   string chave;
   string valor;
   noh *prox = NULL;

public:
   noh();
};

class tabHash{
private:
   noh **elementos;
   int capacidade;

public:
   tabHash(int cap = 100);
   ~tabHash();
   void insere(string c, string v);
   string recupera(string c);
   void remove(string c);
   void percorre();
   void altera(string c, string v);
};

#endif

--TABHASH.CPP

#include <iostream>
#include <string>

#include "tabHash.h"

using namespace std;

void menu(){
   cout << "1- Definir tamanho da tabela. (Tamanho 100 por default)" << endl
       << "2- Inserir na tabela." << endl
       << "3- Buscar elemento." << endl
       << "4- Alterar elemento." << endl
       << "5- Remover elemento." << endl
       << "6- Imprimir tabela." << endl
       << "0- Sair." << endl;
}

int funcaoHash(string c, int tam){
   long index = 0;
   for(unsigned i = 0; i < c.length(); i++){
      index = (index * 7 + c[i]) % tam;
   }
   return index;
}

noh::noh(){
   chave = "";
   valor = "";
}

tabHash::tabHash(int cap){
   elementos = new noh*[cap];
   capacidade = cap;

   for(int i = 0; i < capacidade; i++){
      elementos[i] = NULL;
   }

}

// remove toda a tabela 
tabHash::~tabHash(){
   for(int i = 0; i < capacidade; i++){
      noh *aux;
      noh *atual = elementos[i];
      while(atual != NULL){
         aux = atual;
         atual = atual->prox;
         delete aux;
      }
   }
   delete [] elementos;
}

void tabHash::insere(string c, string v){
   int index = funcaoHash(c, capacidade);

   if(recupera(c) == "NAO ENCONTRADO"){//checa se o elemento existe
      if(elementos[index] == NULL){
         elementos[index] = new noh;// adiciona elemento
         elementos[index]->chave = c;
         elementos[index]->valor = v;
      }else{// cria o encadeamento devido a colisao
         cout << "A Chave '" << c <<"' colidiu."<< endl; 
         noh *atual = elementos[index];
         while(atual->prox != NULL){
            atual = atual->prox;      
         }
         noh *novo = new noh;
         novo->chave = c;
         novo->valor = v;
         atual->prox = novo;

      }
   }else{
      cout << "A chave '" << c << "' ja esta na tabela." << endl;
   }
}

string tabHash::recupera(string c){
   int index = funcaoHash(c, capacidade);
   // recupera apenas elementos do inicio
   if(elementos[index] != NULL && elementos[index]->chave == c){
      return elementos[index]->valor;
   }else{//recupera elementos do resto do encadeamento
      noh *atual = elementos[index];
      while((atual != NULL) && (atual->chave != c)){
         atual = atual->prox;
      }

      if(atual != NULL && atual->chave == c){
         return atual->valor;
      }else{
         return "NAO ENCONTRADO";
      }
   }
}

void tabHash::remove(string c){
   int index = funcaoHash(c, capacidade);
   //remove apenas elementos do inicio
   if(elementos[index] != NULL && elementos[index]->chave == c){
      noh *aux = elementos[index];
      elementos[index] = elementos[index]->prox;
      delete aux;
   }else{// checa o resto do encadeamento
      noh *atual = elementos[index];
      noh *ant;
      while(atual != NULL && atual->chave != c){
         ant = atual;
         atual = atual->prox;
      }

      if(atual != NULL && atual->chave == c){
         ant->prox = atual->prox;
         delete atual;
      }else{
         cerr << "\nOcorreu um erro na remocao." << endl;
      }   
   }
}

// apenas para conferir a tabela
void tabHash::percorre(){
   for(int i = 0; i < capacidade; i++){
      cout << i << ": ";
      noh *atual = elementos[i];
      while(atual != NULL){
         cout <<"["<<atual->chave << "|" << atual->valor <<"]->";
         atual  = atual->prox;
      }
      cout << "NULL" << endl;
   }
}

//altera apenas o valor
void tabHash::altera(string c, string v){
   int index = funcaoHash(c, capacidade);

   if(elementos[index] != NULL && elementos[index]->chave == c){
      elementos[index]->valor = v;
   }else{
      noh *atual = elementos[index];
      while(atual != NULL && atual->chave != c){
         atual = atual->prox;
      }
   
      if(atual != NULL && atual->chave == c){
         atual->valor = v;         
      }else{
         cout << "A chave '" << c << "' nao esta na tabela." << endl;
      }
   }
}

Scripts recomendados

Sopa de Letras

Média do aluno

Uma pincelada no printf

fibonacci

gerenciador de historico de comandos


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts