Dado um conjunto de chaves inteiras e um número primo P, utilize a função hash de divisão para mapear as chaves em uma tabela hash de tamanho P. Empregue sondagem linear para resolver colisões.

Formato de Entrada:

A primeira linha contém dois inteiros positivos N (≤ 1000) e P (o menor primo ≥ 5), onde N é o número de chaves a serem inseridas e P é o comprimento da tabela hash. A segunda linha contém N chaves inteiras, separadas por espaços.

Formato de Saída:

Exiba em uma única linha a posição de cada chave na tabela hash, com números separados por espaços, sem espaço extra no final da linha.

Exemplo de Entrada:

4 5
24 15 61 88

Exemplo de Saída:

4 0 1 3

Análise: Trata-se de um problema fundamental de tabela hassh com resolução de colisões por sondagem linear.

Abaixo, segue uma implementação em C que resolve o problema, com nomes de variáveis e estrutura alterados para manter a correção lógica.

#define TAM_MAXIMO 100000
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef enum { VALIDO, VAZIO, DELETADO } Status;

typedef struct {
    Status estado;
    int valor;
} CelulaHash;

typedef struct {
    int tamanho;
    CelulaHash *celulas;
} TabelaHash;

int calcularHash(int chave, int tamTabela) {
    return chave % tamTabela;
}

int proximoPrimo(int n) {
    int candidato = (n % 2 == 1) ? n : n + 1;
    for (; candidato < TAM_MAXIMO; candidato += 2) {
        int raiz = (int)sqrt(candidato);
        int divisivel = 0;
        for (int i = 3; i <= raiz; i += 2) {
            if (candidato % i == 0) {
                divisivel = 1;
                break;
            }
        }
        if (!divisivel) break;
    }
    return candidato;
}

TabelaHash criarTabela(int capacidade) {
    int tamTabela = proximoPrimo(capacidade);
    TabelaHash tabela;
    tabela.tamanho = tamTabela;
    tabela.celulas = (CelulaHash *)malloc(tamTabela * sizeof(CelulaHash));
    for (int i = 0; i < tamTabela; i++) {
        tabela.celulas[i].estado = VAZIO;
    }
    return tabela;
}

int buscarChave(int chave, TabelaHash tabela) {
    int pos = calcularHash(chave, tabela.tamanho);
    while (tabela.celulas[pos].estado != VAZIO &&
           tabela.celulas[pos].valor != chave) {
        pos = (pos + 1) % tabela.tamanho;
    }
    return pos;
}

void inserirChave(int chave, TabelaHash *tabela) {
    int pos = buscarChave(chave, *tabela);
    if (tabela->celulas[pos].estado != VALIDO) {
        tabela->celulas[pos].valor = chave;
        tabela->celulas[pos].estado = VALIDO;
    }
}

int main() {
    int numChaves, tamanhoTabela;
    scanf("%d %d", &numChaves, &tamanhoTabela);

    TabelaHash tabela = criarTabela(tamanhoTabela);
    int chave;

    for (int i = 0; i < numChaves - 1; i++) {
        scanf("%d", &chave);
        inserirChave(chave, &tabela);
        printf("%d ", buscarChave(chave, tabela));
    }

    scanf("%d", &chave);
    inserirChave(chave, &tabela);
    printf("%d\n", buscarChave(chave, tabela));

    free(tabela.celulas);
    return 0;
}