Ajuda para implementar Tabela Hash em C/C++ (vetor de listas encadeadas)

Programação C e C++
#1

Bom, eu preciso fazer uma tabela hash de 100 elementos como mostrado no esquema:

Sem%20t%C3%ADtulo1
Sem título1.png795×641 12.1 KB

essa tabela (vetor) de 100 elementos … cada um deles possuem números chamados de “chaves” e um ponteiro apontando para o a próxima chave (lista encadeada).
A regra que deve ser seguida para as inserções no vetor, é que o ultimo digito da chave é seu “endereço”, e esse endereço indica qual posição do vetor eu devo inserir.

Ex: Inserir a chave 487
(chave) 487 % (tamanho do vetor) 100 = 7
Então devo inserir a chave 487 na posição 87 do vetor: v[87] = 487

Porém eu estou tendo problemas com os ponteiros para chamar as funções e utiliza-los… Eu sei fazer uma lista encadeada, porém não sei como fazer um vetor disso…
Esse é um pouco do que eu fiz quando era só uma lista encadeada…

struct dados
{
    int chave;
    struct dados *prox;
};

typedef struct dados Lista;

void Cria(Lista **L)
{
    *L = NULL;
}

void Inserir(Lista **L, int v)
{
    Lista *p, *q;
    p = (Lista*)calloc(1, sizeof(Lista));
    
    p->chave = v;
    p->prox = NULL;
    if(*L == NULL)
    {
        *L = p;
    }
    else
    {
        q = *L;
        while(q->prox != NULL)
        {
            q = q->prox;
        };
        q->prox = p;
    }
}

Eu conversei com um amigo e ele me indicou fazer a declaração da struct dessa forma:

struct dados
{
int chave;
struct dados * prox;
} tabela[100];

typedef struct dados Elemento;

Entretanto eu não tenho ideia de como eu vou chamar isso na função… Porque o vetor vai estar na main()… e eu só vou chamar a função “Inserir” com o vetor e o valor para inserir

Como eu chamaria essa função ? Inserir(???,int chave)

Se alguém puder me dar uma luz, eu agradeço demais … Preciso fazer varias coisas alem da inserção, mas não consigo porque eu não sei de que forma eu vou chamar o vetor

#2

Use a opção texto pré-formatado </> da caixa de texto para inserir o seu código fica mais legível.

#3

Obrigado, realmente não estava conseguindo deixar o código de forma que legível… Eu aproveitei e dei uma reformulada no texto.

#4

Melhor portal (que eu conheço) da linguagem C: Prof. Dr. André Backes - ED. A partir da aula 89, começa a tratar sobre tabelas hash.

#5

Obrigado, dei uma olhada e realmente ajudou bastante… Acabei fazendo 2 structs, uma sendo elemento e a outra sendo a tabela com vários elementos… nem tinha pensado nisso kkkkk

Ta ai oque eu fiz, caso possa ajudar alguém…

#define tam 10

struct elemento
{
	int chave;
	struct elemento *prox;
};

struct tabela
{
	struct elemento **dados;
};

tabela* Cria_Tabela()		//	cria uma tabela vazia
{
	tabela *t = (tabela*) malloc(sizeof(tabela));
	t->dados = (struct elemento**) malloc(tam * sizeof(struct elemento*));
	for(int i=0; i<tam;i++)
		t->dados[i] = NULL;
	return t;
}

void Inserir(tabela *T, int chave)
{
	int end = chave%tam;
	elemento *novo = (elemento*) malloc(sizeof(elemento));
	
	novo->chave = chave;
	novo->prox = NULL;
	
	if(T->dados[end] != NULL)
	{
		elemento *p;
		p = T->dados[end];
		while(p->prox != NULL)
		{
			p = p->prox;
		}
		p->prox = novo;
	}
	else
		T->dados[end] = novo;
}
1 curtida