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