olá pessol será que alguém poderá me ajudar é que tenho que fazer um trabalho que consiste de uma tabela Hash, onde cada entrada da tabela será uma lista encadeada simples. Cada nó da lista encadeada terá o nome e telefone de uma pessoa. ´
obrigada
Lista encadeada simples com tabela hash
12 Respostas
Ok, mas qual eh o problema? Nao sabe o que eh uma lista encadeada ou uma tabela de espalhamento, nao sabe implementar ou o que?
Ate!
pelo menos como começar, pois eu tinha feito e o prof disse que não era do jeito que fiz, eu queria pelo menos o começo para eu conseguir depois desenvolver, pois estou perdida…
ele quer que inseri cada nome de uma pessoa e o tel, depois remover e procurar o tel.
Entao coloque aqui o que voce fez que vamos ajudando a ajustar.
Ate!
ele disse que com esse código não da para colocar os dois ou seja o nome e o tel. tem que ser feito na linguagem c++. obrigada
lá vai o código… não se assuste… :idea:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAMTAB 37
typedef char string[30];
typedef struct{
string tab[TAMTAB];
int ocup;
}tabela;
void pausa(){
fflush(stdin);
getchar();
}
int hash(char *nom){
int soma, i;
soma = 0;
for(i = 0; i < strlen(nom); i++)
soma += (i+1)*nom[i];
soma = soma%TAMTAB;
if(soma == 0)
return 1;
return soma;
}
int hash_insere(tabela *t, char *nome, int h){
if(strcmp(t->tab[h],"\0") == 0 || strcmp(t->tab[h], "*") == 0){
strcpy(t->tab[h], nome);
t->ocup++;
printf("\n\tO nome foi inserido na posicao %d\n", h);
return 0;
}
return 1;
}
int hash_procura(tabela *t, char *nome, int h){
int i = 0;
while(strcmp(t->tab[(h*++i*i)%TAMTAB],"\0") != 0 && strcmp(t->tab[(h*i*i)%TAMTAB], nome) != 0); //Faz ateh achar um espaco vazio ou achar o nome.
if(strcmp(t->tab[(h*i*i)%TAMTAB],"\0") == 0){
return -1;//Se nao achou, devolve -1
}
else{
printf("\n\tO nome foi encontrado na posição %d\n", h*i*i%TAMTAB);
return (h*i*i)%TAMTAB; //se achou, em que posicao achou?
}
}
void hash_remover(tabela *t, char *nome){
int a;
a = hash_procura(t, nome, hash(nome));
if(a < 0)
printf("\n\tO nome %s procurado nao consta na tabela.\n", nome);
else{
strcpy(t->tab[a], "*");
t->ocup--;
printf("\n\tO nome foi removido: %s\n", nome);
}
}
void menu(){
printf("\t0. Sair do programa\n");
printf("\t1. Inserir Nomes;\n");
printf("\t2. Procurar Nomes;\n");
printf("\t3. Remover Nomes;\n");
printf("\n\nSua escolha: ");
}
void escolha(tabela *t){
string nome;
int i, h, opc;
scanf("%d", &opc);
switch(opc){
case 0:
break;
case 1:
printf("\nDigite os nomes a serem colocados na tabela.\n");
printf("Termine a sequencia com \"*\":\n");
do{
scanf("%s", nome);
if(strcmp(nome, "*") != 0){
i = 0;
h = hash(nome);
while(hash_insere(t, nome, ((++i*h*i)%TAMTAB)));
//printf("i = %d\n", i); //imprimir o numero de tentativas
}
}while(strcmp(nome, "*")); //leitura
break;
case 2:
printf("\nDigite os nomes a serem consultados.\n");
printf("Termine a sequencia com \"*\"\n");
do{
scanf("%s", nome);
if(strcmp(nome, "*") != 0){
h = hash(nome);
i = hash_procura(t, nome,h);
if(i < 0){
printf("\n\tO nome %s nao foi encontrado\n");
}
else{
printf("\n\t%s esta na tabela!\n");
}
}
}while(strcmp(nome, "*"));//procura
break;
case 3:
printf("\nDigite os nomes a serem removidos.\n");
printf("Termine a sequencia com \"*\":\n");
do{
scanf("%s", nome);
if(strcmp(nome, "*") != 0){
hash_remover(t, nome);
}
}while(strcmp(nome, "*"));//remocao
break;
default:
printf("Opcao invalida. Por favor, digite uma opcao valida.\n");
break;
}
if(opc != 0){
menu();
escolha(t);
}
}
int main(){
tabela t;
int i;
for(i = 0; i < TAMTAB; i++){
strcpy(t.tab[i],"\0");
}
t.ocup = 0;//Ateh aqui, iniciar tabela.
menu();
escolha(&t);
printf("Saindo do programa....\n");
}
também tenho outro exercicio pronto , mas vou ter que fazer modificações, ve pra mim se esse tem alguma coisa haver com tabela hash?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define BUFFER 64
/* Estrutura da lista declarada para armazenar nossos dados. */
typedef struct lista {
char *nome;
int idade;
struct lista *proximo;
} Dados;
/* Prototipo das funcoes de manuseio dos dados. */
Dados *inicia_dados(char *nome, int idade);
Dados *insere_dados(Dados *dados, char *nome, int idade);
void exibe_dados(Dados *dados);
void busca_dados(Dados *dados, char *chave);
Dados *deleta_dados(Dados *dados);
int checa_vazio(Dados *dados);
/* Prototipo das funcoes do menu.*/
void insere(void);
void exibe(void);
void busca(void);
void deleta(void);
/* Inicializa a estrutura de dados principal. */
Dados *principal = NULL;
/* Cria a nova lista apontando o proximo no para NULL. */
Dados *inicia_dados(char *nome, int idade) {
Dados *novo;
novo = (Dados *)malloc(sizeof(Dados));
novo->nome = (char *)malloc(strlen(nome)+1);
strncpy(novo->nome, nome, strlen(nome)+1);
novo->idade = idade;
novo->proximo = NULL;
return novo;
}
/* Como a lista nao esta mais vazia, apontamos o proximo no para lista anterior. */
Dados *insere_dados(Dados *dados, char *nome, int idade) {
Dados *novo;
novo = (Dados *)malloc(sizeof(Dados));
novo->nome = (char *)malloc(strlen(nome)+1);
strncpy(novo->nome, nome, strlen(nome)+1);
novo->idade = idade;
novo->proximo = dados;
return novo;
}
/* Percorre todos os campos da lista e imprime ate o ponteiro proximo chegar em NULL. */
void exibe_dados(Dados *dados) {
fprintf(stdout, "Cadastro:\n\n");
fprintf(stdout, "------------\n");
for (; dados != NULL; dados = dados->proximo) {
fprintf(stdout, "Nome: %s\n", dados->nome);
fprintf(stdout, "Idade: %d\n", dados->idade);
fprintf(stdout, "------------\n");
}
getchar();
}
/* Percorre cada ponta comparando o nome com a chave. */
void busca_dados(Dados *dados, char *chave) {
int achou = 0;
fprintf(stdout, "Cadastro:\n\n");
for (; dados != NULL; dados = dados->proximo) {
if (strcmp(chave, dados->nome) == 0) {
fprintf(stdout, "------------\n");
fprintf(stdout, "Nome: %s\n", dados->nome);
fprintf(stdout, "Idade: %d\n", dados->idade);
fprintf(stdout, "------------\n");
achou++;
}
}
if (achou == 0)
fprintf(stdout, "Nenhum resultado encontrado.\n");
else
fprintf(stdout, "Foram encontrados %d registros.\n", achou);
sleep(1);
}
/* Deleta o ultimo registro inserido. */
Dados *deleta_dados(Dados *dados) {
Dados *novo;
novo = dados->proximo;
free(dados->nome);
free(dados);
fprintf(stdout, "O ultimo registro inserido foi deletado com sucesso.\n");
sleep(1);
return novo;
}
/* Apena checa se a lista e NULL ou nao. */
int checa_vazio(Dados *dados) {
if (dados == NULL) {
fprintf(stdout, "Lista vazia!\n");
sleep(1);
return 1;
} else
return 0;
}
/* Obtem os dados necessarios para chamar as funcoes de manuseio de dados. */
void insere(void) {
char *nome;
int idade;
nome = (char *)malloc(BUFFER);
fprintf(stdout, "\n\nDigite o Nome: \n--> ");
scanf("%s", nome);
fprintf(stdout, "\n");
fprintf(stdout, "Digite a Idade: \n--> ");
scanf("%d", &idade);
fprintf(stdout, "\n");
if (principal == NULL)
principal = inicia_dados(nome, idade);
else
principal = insere_dados(principal, nome, idade);
}
void exibe(void) {
if (!checa_vazio(principal))
exibe_dados(principal);
}
void busca(void) {
char *chave;
if (!checa_vazio(principal)) {
chave = (char *)malloc(BUFFER);
fprintf(stdout, "Digite o nome para buscar: \n--> ");
scanf("%s", chave);
busca_dados(principal, chave);
}
}
void deleta(void) {
if (!checa_vazio(principal))
principal = deleta_dados(principal);
}
int main(void) {
char escolha;
do {
system("/usr/bin/clear"); /* Nao lembro de nada melhor! :P */
fprintf(stdout, "\n\t\tCadastro de Pessoas\n\n");
fprintf(stdout, "Escolha uma opcao: \n");
fprintf(stdout, "1 - Insere Dados\n");
fprintf(stdout, "2 - Exibe Dados\n");
fprintf(stdout, "3 - Busca Dados\n");
fprintf(stdout, "4 - Deleta Dados\n");
fprintf(stdout, "5 - Sair\n\n");
scanf("%c", &escolha);
switch(escolha) {
case '1':
insere();
break;
case '2':
exibe();
break;
case '3':
busca();
break;
case '4':
deleta();
break;
case '5':
exit(0);
break;
default:
fprintf(stderr,"Digite uma opcao valida!\n");
sleep(1);
break;
}
getchar(); /* E para impedir sujeira na entrada da escolha. Nao lembro de nada melhor tambem. :P */
}
while (escolha > 0); /* Loop Principal. */
return 0;
}
Mas isso é C… 
seria sim…
Em Java seria muito simples, pois já se tem as implementações que você precisa!
Use as tags code que fica muito mais fácil entender seu código:
[code]int main(int argc, char** argv) { printf("Hello World"); }[/code]
fica:int main(int argc, char** argv) { printf("Hello World"); }
Dê um edit lá em cima para colocar isso.
Vamos lá,
o segundo código é um exemplo de lista ligada. O primeiro código é tem uma tabela de hash e uma função ruim de hash. O segundo código dá para aproveitar, o primeiro difícil.
Dê uma olhada nesses sites os seguintes links: listas encadeadas, tabelas de dispersao, registros e structs
http://www.ime.usp.br/~pf/algoritmos/
http://www.ime.usp.br/~pf/mac0122-2002/
Até!
valeu pessoal pelas dicas, vou tentar fazer depois mando p/ vcs avaliarem ok?
valeuuuu
Criado 19 de janeiro de 2009
Ultima resposta 21 de jan. de 2009
Respostas 12
Participantes 4