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

• Download hash
• Enviar nova versão

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

Média do aluno

Cones

Usando uma header...

Lista Simples em C

Peso ideal

Nenhum comentário foi encontrado.