Tabela hash com classes e tratamento de colisões por encadeamento
Publicado por Bruno (última atualização em 16/01/2017)
[ Hits: 3.482 ]
Homepage: ...
Tabela hash bem simples, apenas para fixar melhor o seu funcionamento na prática.
/* 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; } } }
Calculadora de equações de 2º grau versão 2 (com funções)
2 Programinhas em C para conversão de bases
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (20)
Alguém pode me ajudar porfavor como executar comandos ao iniciar no i3... (1)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba