Dúvida em problema

[R. Bighi]

Ae galera, estou fazendo um trabalho de faculdade e ando meio enferrujado na linguagem. O problema se resume a ler um vetor com alguns valores e armazená-los numa tabela usando Hash, com tratamento de colisão por Quociente linear, mas creio q minha dúvida seja mais sobre C em si. Aí vai o que fiz até agora, mas não consigo compilar por conta de um problema no 1o if, onde verifico se a posição na tabela está vazia (ou pelo menos tento).

#include <stdio.h>
#include <stdlib.h>

#define N 11

int hash(int valor)
{
    return valor % N;
}

int doubleHash(int incremento)
{
    return incremento / N;
}

int main (void)
{
    int tabela[N], incremento[N], valor[N], posicao=0;
    int contador = 0; int i= 0;
    
    valor[0] = 27;
    valor[1] = 18;
    valor[2] = 29;
    valor[3] = 28;
    valor[4] = 39;
    valor[5] = 13;
    valor[6] = 16;
    
    while (contador<N)
    {
        posicao = hash(valor[i]);
        if (tabela[posicao] == NULL)
        {
            tabela[posicao] = valor[contador];
            contador++;
        }
        else
        {
            incremento[posicao] = doubleHash(posicao);
            while (tabela[posicao] =! NULL)
            {
                posicao = ((posicao + incremento[posicao]) % N);
            }
            tabela[posicao] = valor[contador];
            contador++;
        }    
        i++;
    }
}

O programa ainda tá em fase inicial e ainda to tentando fzer o básico funcionar pra continuar progredindo, mas realmente não entendi o porque do erro. Se alguém puder dar uma luz, agradeço muito! Vlw gente!

[Léo Ferreir?]

Aqui rodou normal. :blink:

Mas arrisco que o problema possa estar no NULL:

if (tabela[posicao] == NULL)

Isto apenas verifica se algo está ou não iniciado. Se devolver NULL, você tem uma variável que aponta para um endereço de memória que ainda não é válido.

Uma forma de reconhecer se uma matriz unidimensional está vazia, é adotando um valor para isso. Por exemplo, ''0'' para ela vazia, se for vetor de inteiros. Ou qualquer outro valor estipulado pelo programador.

No caso, eu recomendaria o próprio zero. Sem contar que, o NULL é um macro expandido para zero. Geralmente utilizado em ponteiros...

O erro é estranho, já que o NULL deveria estar contido por padrão nas bibliotecas padrões do C (Deveria não, está!!).

Mas tente trocar o NULL por 0 e poste o resultado...

Abraços!

[R. Bighi]

Cara, muito obrigado pelas informações! Eu modifiquei algumas coisas no programa, entre essas modificações, criei uma função pra inicializar a tabela, retornando todas as posições dela como vazias (NULL). Agora tá compilando direitinho, mas ainda tá dando algum erro que não consigo descobrir qual... Tentei debugar, mas ainda não resolvi o problema. Alguém dá uma luz?

#include <stdio.h>
#include <stdlib.h>

#define N 11

int *criar()
{
    return NULL;
}

int hash(int valor)
{
    return valor % N;
}

int doubleHash(int valor)
{
    return  valor / N;
}

int main (void)
{
    int *tabela[N], incremento[N], valor[N], posicao=0;
    int contador = 0; int i;
    
    for (i = 0; i < N; i++)
        tabela[i] = criar();    // Inicializa a Tabela
    
    valor[0] = 27;
    valor[1] = 18;
    valor[2] = 29;
    valor[3] = 28;
    valor[4] = 39;
    valor[5] = 13;
    valor[6] = 16;
    
    while (contador<N)
    {
        posicao = hash(valor[contador]);
        if (tabela[posicao] == NULL)
        {
            *tabela[posicao] = valor[contador];
            contador++;
        }
        else
        {
            incremento[contador] = doubleHash(valor[contador]);
            while (*tabela[posicao] =! NULL)
            {
                posicao = ((posicao + incremento[posicao]) % N);
            }
            *tabela[posicao] = valor[contador];
            contador++;
        }     
        contador++;
    }
}

[Myho]

Olá, não testei seu código, mas por cima posso dizer aonde encontrei alguns erros.

if (tabela[posicao] == NULL)
        {
            *tabela[posicao] = valor[contador];
            contador++;
        }

Não precisa colocar aquele asterisco antes de tabela posição, e da maneira como foram declaradas as variaveis tem que por um & na frente de valor[contador]. Tabela[posições] espera receber um endereço de memória e não um valor. Se sua ideia é essa mesmo faça as alterações, senão já são outras mudanças necessárias.

else
        {
            incremento[contador] = doubleHash(valor[contador]);
            while (*tabela[posicao] =! NULL)
            {
                posicao = ((posicao + incremento[posicao]) % N);
            }
            *tabela[posicao] = valor[contador];
            contador++;
        }

No teste do while, tire o asterisco em frente a tabela[posicao] e mude =! para != pois do jeito que está é uma atribuição negada e não uma comparação.

e após as chaves do while novamente retire o asterisco da frente de tabela[posicao] e coloque um & em frente a valor[contador]

[R. Bighi]

Cara, muito obrigado pela ajuda! Consertei os erros e fui utilizando de vários printf pelo programa pra ver até onde está rodando perfeitamente. Meu grande (e creio que ultimo) problema está sendo no último while que, por algum motivo, ele entra e não sai nunca (a variavel posicao não está sendo incrementada como deveria...). Alguém sabe resolver?

while (tabela[posicao] != NULL)
            {
                posicao += incremento[posicao];
                if (posicao > N) posicao = posicao % N;
                printf("posicao2: %d\n", posicao);
            }

O que ele faz aí (ou a idéia, no caso) é que, enquanto a posicao atual da tabela não estiver vazia, ele soma um incremento à essa posição e vai tentando até achar uma vazia.

[Durub]

E se não achar? Ele volta. E tenta. E tenta. E tenta de novo. Infinitas vezes! Somente neste trecho, é impossível que alguma posição da tabela fique vazia. Talvez você queira sair do loop caso não encontre uma vazia?

Abraços!