2

Tenho uma lista de contatos e preciso que sejam removidos duplicatas, estava tentando resolver usando o código abaixo:

Elemento* remove_duplicados(Elemento* agenda)
{
    Elemento* a = NULL; //POnteiro do Elemento anterior
    Elemento* p;
    Elemento* q;

    for(p = agenda; p != NULL; p = p -> prox){//Analisa do primeiro elem até o ultimo
        for(q = p -> prox; q != NULL; q = q -> prox){//Analisa proximo elem de p até o fim
            if(0 != strcmp(p -> info.nome, q -> info.nome)){
                a = q; 
            }
        }

        if(a == NULL){ //Remove elemento do início e aponta para o 2º
            agenda = p -> prox;
        } 
        else
            a -> prox = p -> prox; //Ponteiro anterior levará para o prox

        free(p); //Libera o espaço
    }
    return agenda;
}

O problema é que ao executar o programa, ao chegar nessa etapa ele encerra :/

1
  • Faz um merge sort de lista, mas não põe os resultados repetidos 30/11/2017 às 18:11

1 Resposta 1

2

Problemas

Tem algumas falhas na lógica que está implementada:

  • Não está a remover os vários repetidos sucessivamente, pois apenas utiliza o a no fim do segundo for
  • Não pode fazer free(p) e depois utilizar no for para avançar para o próximo com p = p -> prox
  • O avanço agenda = p -> prox não é necessário se remover os duplicados do primeiro ao invés do primeiro em si. Isto faz com que a sua instrução devesse ser agenda->prox = p->prox ou p->prox =q->prox uma vez que para a ser NULL p tem de estar exatamente no elemento seguinte

Corrigindo os problemas

Utilizando a lógica e variáveis que tem sugiro que faça assim:

Elemento* remove_duplicados(Elemento* agenda){
    Elemento* a;
    Elemento* p;
    Elemento* q;

    for(p = agenda; p != NULL; p = p -> prox ){
        a = NULL; //a cada varrimento a começa a NULL

        for(q = p -> prox; q != NULL; ){ //sem incremento
            if(0 == strcmp(p -> info.nome, q -> info.nome)){ //teste de igual
                if(a == NULL){ //remove do inicio
                    p -> prox = q -> prox;
                }
                else{ //ou do meio/fim
                    a -> prox = q -> prox;
                }

                Elemento* remover = q;
                q = q -> prox;
                free(remover);
            }
            else { //so atualiza o anterior quando não é igual
                a = q;
                q = q->prox;
            }
        }
    }

    return agenda;
}

Retirei os comentários que tinha para poder evidenciar os que eu pus, e com as explicações associadas às trocas que fiz.

Veja este código a funcionar no Ideone

Refatorando para melhor legibilidade

Os nomes de variáveis que tem são muito pouco sugestivos e dificultam a leitura. Deve sempre tentar dar nomes representativos do conteúdo que as variáveis tem. Para além disso o primeiro elemento nunca é alterado uma vez que são removidos os duplicados para a frente, e por isso o tipo de retorno também não é necessário, devendo ser void.

Tomando isto em consideração podemos tornar a função bastante mais clara:

void remove_duplicados(Elemento* agenda){
    Elemento *anterior, *corrente, *seguinte;

    for(corrente = agenda; corrente != NULL; corrente = corrente -> prox ){
        anterior = NULL;

        for(seguinte = corrente -> prox; seguinte != NULL; ){
            if(0 == strcmp(corrente -> info.nome, seguinte -> info.nome)){
                if(anterior == NULL)
                    corrente -> prox = seguinte -> prox;
                else
                    anterior -> prox = seguinte -> prox;

                Elemento* remover = seguinte;
                seguinte = seguinte -> prox;
                free(remover);
            }
            else {
                anterior = seguinte;
                seguinte = seguinte->prox;
            }
        }
    }
}

Eficiência com tabela de Hash

Se houver preocupação em relação à eficiência, a solução apresentada por si, que foi a que eu peguei, pode trazer problemas se a quantidade de dados for larga, uma vez que é uma solução quadrática, com complexidade de tempo na ordem de O(n²).

Existem várias formas de melhorar a solução mas com uma tabela de hash e garantindo poucas colisões conseguimos uma solução na ordem de O(n).

Começamos pela estrutura de cada entrada da tabela de hash e o respetivo array que a representa:

typedef struct entrada {
    struct info *dados;
    struct entrada *prox;
} entrada;

#define TAMANHO_HASH 100
entrada *hash_nomes[TAMANHO_HASH];

Para achar a entrada referente a um determinado valor é preciso a função de hash, que neste caso podemos usar como strings:

unsigned long hash(char *str){
    unsigned long hash = 5381;
    int c;
    while (c = *str++)
        hash = ((hash << 5) + hash) + c;

    return hash;
}

Criar uma boa função de hash é só por si uma ciência, e irá refletir-se no desempenho do algoritmo pois irá criar muitas ou poucas colisões dependendo de como for construida. Por simplicidade usei uma já conhecida.

A função que remove_duplicados fica agora mais simplificada pois baseia-se inteiramente na tabela de hash para saber se o valor corrente já existe:

void remove_duplicados(Elemento* agenda){
    Elemento *corrente = agenda, *anterior = NULL;

    while (corrente != NULL){
        if (adiciona_se_inexistente(&corrente->info) == 0){ //0 não adicionou por já existir
            anterior->prox = corrente->prox;
            Elemento* remover = corrente;
            corrente = corrente -> prox;
            free(remover);
        }
        else {
            anterior = corrente;
            corrente = corrente -> prox;
        }
    }
}

Aqui foi utilizada a função adiciona_se_inexistente para adicionar na tabela de hash se não existir:

int adiciona_se_inexistente(struct info* dados){
    unsigned long key = hash(dados->nome) % TAMANHO_HASH; //achar a entrada

    entrada *corrente = hash_nomes[key];
    while (corrente != NULL){ //verificar se já existe
        if (strcmp(corrente->dados->nome, dados->nome) == 0){
            return 0;
        }
        corrente = corrente->prox;
    }

    //não existe adiciona a nova entrada
    entrada *nova = malloc(sizeof(entrada));
    nova->prox = hash_nomes[key];
    nova->dados = dados;
    hash_nomes[key] = nova;
    return 1;
}

A tabela de hash tem de ser inicializada com as entradas todas a NULL, o que eu fiz utilizando a função memset.

Observações:

  • Implementei a tabela de hash com lista de colisões internas ao invés de endereçamento aberto, o que acaba por utilizar mais espaço, mas é potencialmente mais simples de implementar.
  • Esta solução é muito mais eficiente a nível de desempenho se garantirmos que temos poucas colisões, algo que depende da função de hash e do tamanho da tabela. No entanto irá utilizar mais memória que a sua solução original. Note que o tamanho de 100 que eu escolhi para a tabela é bom para a quantidade de nomes que usei (5), mas se tiver mais nomes já pode gerar muitas colisões, logo é algo que tem que adaptar às suas necessidades.
  • Vale também relembrar que se apenas precisar desta função num ponto do programa e tiver a certeza que mais à frente não será necessária, tem de liberar o espaço de todas as entradas preenchidas da tabela de hash, com free.

Exemplo desta implementação no Ideone

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .