Tabela HASH C++ [Resolvido]

[Pedro3]

Boa noite galera. Tenho que fazer um programa que leia uma palavra e retorne se esta palavra é uma palavra reservada da linguagem C ou não. Para fazer isso tenho que utilzar uma tabela hash.

 

Bem até o momento eu não sei começar esse programa em C++. A minha dúvida é a seguinte. Eu tenho uma lista de palavras reservadas que somam ao todo 62 palavras e 369 caracteres. Qual a melhor função matemática/função hash que eu posso usar para simplificar a busca com essa quantidade de palavras? Quero evitar o máximo de dispersão. Gostaria de saber também como iniciar essa tabela em C++. Toda ajuda é bem vinda. Obrigado gente.

[atlos]

oi,se nao tem a minima ideia de como começar a fazer isso em C++,voce deve estudar containers associativos ou containers hash associativos

aqui tem um tutorial,porém os containers hash ai mostrados nao são standard

http://easycplusplus.com/stl/stltutorial3a.html

[Pedro3]

Galera consegui fazer. Vou postar aqui para os demais que talvez tem dúvida sobre esse assunto. Fiz esse programa porque precisava de fazer um exercício aonde o usuário vai digitar alguma palavra reservada qualquer e tem que retornar para ele se ela está ou não na lista. Foi solicitado também o uso de uma tabela hash.

 

hash.cpp

#include <iostream>#include <iostream>#include "hash.h"#include <string>#include <cstdlib>using namespace std;hash::hash(){for(int i = 0; i < TamanhoTabela; i++){TabelaHash[i] = new item;TabelaHash[i]->reservada = "vazio";TabelaHash[i]->prox = NULL;}}void hash::Inserir(string reservada){int indice = Hash(reservada);if(TabelaHash[indice]->reservada == "vazio"){TabelaHash[indice]->reservada = reservada;}else{item* ptr = TabelaHash[indice];item* n = new item;n->reservada = reservada;n->prox = NULL;while(ptr->prox != NULL){//faz o ponteiro percorrer até o final da tableptr = ptr->prox;}ptr->prox = n;}}int hash::NumeroDeItensNaLista(int indice){int contagem = 0;if(TabelaHash[indice]->reservada=="vazio"){return contagem;}else{contagem++;item* ptr = TabelaHash[indice];while(ptr->prox != NULL){contagem++;ptr = ptr->prox;}}return contagem;}void hash::ImprimirTabela(){int numero;for(int i = 0;i < TamanhoTabela; i++){numero = NumeroDeItensNaLista(i);cout<<"-------------------\n";cout<<"indice = "<<i<<endl;cout<<TabelaHash[i]->reservada <<endl;cout<<"# de itens na neste indice: "<<numero<<endl;cout<<"-------------------\n";}}void hash::ImprimirItensNoIndice(int indice){item* ptr = TabelaHash[indice];if(ptr->reservada == "vazio"){cout<<"indice = "<<indice<<" esta vazio"<<endl;}else{cout<<"indice = "<<indice<<" tem os seguintes itens: "<<endl;while(ptr!=NULL){cout<<"-------------------\n";cout<<ptr->reservada <<endl;cout<<"-------------------\n";ptr = ptr->prox;}}}int hash::Hash(string chave){int hash = 0;int indice;for(int i = 0; i<chave.length();i++){hash = hash + (int)chave[i];}indice = hash % TamanhoTabela;return indice;}void hash::BuscaPalavra(string reservada){int indice = Hash(reservada);bool EncontrarPalavra = false;string palavra;item* ptr = TabelaHash[indice];while(ptr != NULL){ //percorrer a tabelaif(ptr->reservada == reservada){EncontrarPalavra = true;palavra = ptr->reservada;}ptr=ptr->prox;}if(EncontrarPalavra == true){cout<<"A palavra esta na tabela"<<endl;}else{cout<<reservada<< " nao esta na tabela"<<endl;}}hash::~hash(){item* ptr;for(int i=0;i<TamanhoTabela;i++){while(TabelaHash[i] != NULL){ptr = TabelaHash[i];TabelaHash[i] = TabelaHash[i]->prox;delete ptr;}}}

hash.h

#ifndef HASH_H#define HASH_H#include <iostream>#include <string>#include <cstdlib>using namespace std;class hash{private:static const int TamanhoTabela = 10; //define o tamanho da tabela dentro da classestruct item{string reservada;item *prox;};item* TabelaHash[TamanhoTabela]; //ponteiro com o tamanho da tabelapublic:int Hash(string chave);void Inserir(string reservada);int NumeroDeItensNaLista(int indice);void ImprimirTabela();void ImprimirItensNoIndice(int indice);void BuscaPalavra(string reservada);hash();~hash();};#endif // HASH_H

main.cpp

#include <iostream>#include "hash.h"#include <string>#include <cstdlib>using namespace std;int main(int argc, char *argv[]){hash ObjetoHash;ObjetoHash.Inserir("auto");ObjetoHash.Inserir("asm");ObjetoHash.Inserir("bool");ObjetoHash.Inserir("break");ObjetoHash.Inserir("case");ObjetoHash.Inserir("catch");ObjetoHash.Inserir("char");ObjetoHash.Inserir("class");ObjetoHash.Inserir("const");ObjetoHash.Inserir("const_cast");ObjetoHash.Inserir("continue");ObjetoHash.Inserir("default");ObjetoHash.Inserir("delete");ObjetoHash.Inserir("do");ObjetoHash.Inserir("double");ObjetoHash.Inserir("dynamic_cast");ObjetoHash.Inserir("else");ObjetoHash.Inserir("enum");ObjetoHash.Inserir("explicit");ObjetoHash.Inserir("extern");ObjetoHash.Inserir("false");ObjetoHash.Inserir("float");ObjetoHash.Inserir("for");ObjetoHash.Inserir("friend");ObjetoHash.Inserir("goto");ObjetoHash.Inserir("if");ObjetoHash.Inserir("inline");ObjetoHash.Inserir("int");ObjetoHash.Inserir("long");ObjetoHash.Inserir("mutable");ObjetoHash.Inserir("namespace");ObjetoHash.Inserir("new");ObjetoHash.Inserir("operator");ObjetoHash.Inserir("private");ObjetoHash.Inserir("protected");ObjetoHash.Inserir("public");ObjetoHash.Inserir("register");ObjetoHash.Inserir("reinterpret_cast");ObjetoHash.Inserir("return");ObjetoHash.Inserir("short");ObjetoHash.Inserir("signed");ObjetoHash.Inserir("sizeof");ObjetoHash.Inserir("static");ObjetoHash.Inserir("static_cast");ObjetoHash.Inserir("struct");ObjetoHash.Inserir("switch");ObjetoHash.Inserir("template");ObjetoHash.Inserir("this");ObjetoHash.Inserir("throw");ObjetoHash.Inserir("true");ObjetoHash.Inserir("try");ObjetoHash.Inserir("typedef");ObjetoHash.Inserir("typeid");ObjetoHash.Inserir("typename");ObjetoHash.Inserir("union");ObjetoHash.Inserir("unsigned");ObjetoHash.Inserir("using");ObjetoHash.Inserir("virtual");ObjetoHash.Inserir("void");ObjetoHash.Inserir("volatile");ObjetoHash.Inserir("wchar_t");ObjetoHash.Inserir("while");int opcao=0;int aux;string palavra = "";while (opcao!=4){cout<<" **** MENU ****"<<endl<<endl;cout<<"Total de palavras reservadas = 62\nEspalhadas em uma tabela hash de tamanho 10\n\n";cout<<"1 - Buscar uma palavra reservada"<<endl;cout<<"2 - Imprimir tabela por indice"<<endl;cout<<"3 - Imprimir toda a tabela"<<endl;cout<<"4 - Para finalizar"<<endl;cout<<endl<<endl<<"Digite sua opcao: "<<endl;cin>>opcao;switch(opcao){case 1:while(palavra!="sair"){cout<<"Para terminar a busca, digite sair\nBuscar por: "<<endl;cin>>palavra;if(palavra != "sair"){ObjetoHash.BuscaPalavra(palavra);}}break;case 2:cout<<endl<<"Digite o indice que deseja imprimir\nOBS: de 0 a 9"<<endl;cin>>aux;if(aux == 0 ){ObjetoHash.ImprimirItensNoIndice(0);cout<<endl;}if(aux == 1 ){ObjetoHash.ImprimirItensNoIndice(1);cout<<endl;}if(aux == 2 ){ObjetoHash.ImprimirItensNoIndice(2);cout<<endl;}if(aux == 3 ){ObjetoHash.ImprimirItensNoIndice(3);cout<<endl;}if(aux == 4 ){ObjetoHash.ImprimirItensNoIndice(4);cout<<endl;}if(aux == 5 ){ObjetoHash.ImprimirItensNoIndice(5);cout<<endl;}if(aux == 6 ){ObjetoHash.ImprimirItensNoIndice(6);cout<<endl;}if(aux == 7 ){ObjetoHash.ImprimirItensNoIndice(7);cout<<endl;}if(aux == 8 ){ObjetoHash.ImprimirItensNoIndice(8);cout<<endl;}if(aux == 9 ){ObjetoHash.ImprimirItensNoIndice(9);cout<<endl;}break;case 3:cout<<endl;ObjetoHash.ImprimirTabela();break;default:cout<<"Escolha invalida!"<<endl<<endl;break;}return 0;}}

[atlos]

mas C++ ja tem classes pra esse tipo de coisa..mesmo assim obrigado por compartilhar