Skip to content

Instantly share code, notes, and snippets.

@divanibarbosa
Last active April 26, 2021 18:04
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save divanibarbosa/2af8ddff8b430349366b8175bdaaead3 to your computer and use it in GitHub Desktop.
Save divanibarbosa/2af8ddff8b430349366b8175bdaaead3 to your computer and use it in GitHub Desktop.
Tabela Hash com tratamento de colisões Linear em C++
// Tabela HASH com tratamento de colisões linear
// Criado por: profa. Divani Barbosa Gavinier
// Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
// divanibarbosa@gmail.com
#include <iostream>
#include <math.h>
using namespace std;
struct HASH {
double item;
bool ocupado;
};
class HashLinear {
private: HASH *tab;
private: int tam_max, n;
public: HashLinear(int tam) {
tab = new HASH[tam];
tam_max = tam;
n=0;
for(int i=0; i<tam; i++) // inicializando
tab[i].ocupado = false;
}
private: int funcaohash(double chave) {
int v = (int) chave;
return ( abs(v) % tam_max );
}
public: bool cheia() {
return n == tam_max;
}
public: void insere(double chave) {
if (cheia()) {
cout << "\n->ATENCAO Tabela cheia\n";
return;
}
int pos = funcaohash(chave);
// INICIO ROTINA TRATAMENTO DE COLISAO
if (tab[pos].ocupado) {
cout << "-> Ocorreu uma colisao na posicao " << pos << endl;
while (true) {
if (chave == tab[pos].item) {
cout << "\n->ATENCAO Item já cadastrado";
return;
}
if (pos == tam_max-1 ) pos = -1;
pos++;
if ( !tab[pos].ocupado ) break;
}
}
// FIM ROTINA TRATAMENTO DE COLISAO
tab[pos].item = chave;
tab[pos].ocupado = true;
n++; // incrementa um item na tabela
cout << "-> Inserido HASH[" << pos << "]";
}
public: int busca(double chave) { // Recuperando um elemento
int pos = funcaohash(chave);
if (tab[pos].ocupado) { // se posição ocupada
if (tab[pos].item == chave) return pos;
int iniciobusca = pos;
while (true) {
if (pos == tam_max-1) pos = -1;
pos++;
if (tab[pos].ocupado && tab[pos].item == chave) return pos;
if (pos == iniciobusca) return -1;
}
} // fim if tab[pos].ocupado (se posição ocupada)
return -1;
}
public: void apaga(double chave) {
int pos = busca(chave);
if (pos != -1) {
tab[pos].ocupado = false;
n--;
cout << "-> Dados da posicao " << pos << " apagados\n";
}
else cout << "Item nao encontrado\n";
}
public: void imprime() {
for (int i=0; i<tam_max; i++)
if ( tab[i].ocupado )
cout << "\nHash[" << i << "] = " << tab[i].item;
}
};
main() {
HashLinear tab(7);
double item;
cout << "\n************************************************************\n";
cout << "Tabela HASH com tratamento de colisoes Lista (7 itens reais - double)\n";
cout << "************************************************************\n";
for (int i=0; i<7; i++){
cout << "\n\nInserindo elemento " << (i+1) << endl;
cout << " - Forneca valor real: ";
cin >> item;
tab.insere(item);
}
cout << "\n\nBuscando campo\n>> Forneca o item: ";
cin >> item;
if ( tab.busca(item) != -1 )
cout << "Item encontrado na posicao " << tab.busca(item);
else
cout << "Item nao encontrado";
cout << "\n\nApagando campo\n>>> Forneca o item: ";
cin >> item;
tab.apaga(item);
cout << "\n\nImprimindo conteudo";
tab.imprime();
cout << endl;
}
@gus-melo
Copy link

Boa tarde, estou estudando tabela Hash, além de estar fazendo um trabalho, será que poderia tirar umas dúvidas com você ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment