lista encadeada simples com tabela hash

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

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

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!

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

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..

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

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!

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

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..

#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");

}

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

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!

*/
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.

*/
}

while (escolha > 0); /* Loop Principal. */

return 0;
}

Mas isso é C...

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

seria sim..

Em Java seria muito simples, pois já se tem as implementações que você precisa!

This message was edited 1 time. Last update was at 20/01/2009 07:30:51

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:

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é!

Entusiasta Java Membro desde: 03/01/2009 13:41:28 Mensagens: 21 Offline

valeu pessoal pelas dicas, vou tentar fazer depois mando p/ vcs avaliarem ok?
valeuuuu

Notícias, artigos e o maior fórum brasileiro sobre Java