Ir ao conteúdo
Regras do Clube do Hardware

C++ Como remover elementos repetidos de uma Lista Simplesmente Encadeada em C/C++

Welington Silva 2002

Por Welington Silva 2002
em C/C#/C++

 Compartilhar
Ir à solução Resolvido por arfneto,

Posts recomendados

arfneto
 

arfneto

Postado
Postado

devia ter dito o que você já testou e o que aconteceu ...
 

3 horas atrás, Welington Silva 2002 disse:

Minha dúvida é o melhor modo de se fazer isso com ponteiros, já pensei de tudo, testei mas nao deu

 

Se foi você que criou a lista, podia inserir na ordem... Isso ajudaria na performance.

 

Mas para um programa de estudo com menos que milhares de itens pode fazer o simples como vou te explicar:

  • você deve ter uma  função que lista todos os elementos, afinal deve ter escrito isso para poder testar. Se não tem escreva uma porque já devia ter feito isso
  • você precisa de uma função que apaga um elemento da lista, por valor, e pode usar aqui
  • listas com ponteiros só para um lado são um 1nf3rn0. Não é vantagem e sim prejuízo. Como não tem ponteiros para trás precisa reiniciar toda hora que quer voltar, se só tem ponteiros para frente
  • copie a função que lista para uma que vai remover as duplicatas porque é quase a mesma coisa.
  • na sua nova função: para cada elemento da lista você chama a função que remove, passando a lista que começa no item seguinte e o valor que está vendo agora, até a função retornar "não encontrado"

E é só isso.

 

Exemplo: uma lista de letras: a b c c b a a 

  • uma função
     
    Citação

        int remove_um(char letra, Lista* lista);

    que retorna 0 quando não consegue apagar o elemento. não estou usando o código porque de novo o botão sumiu do forum
     

  • uma função
     
    Citação

    int remove_duplicados(Lista lista);

     

Eis o que vai acontecer em remove_duplicados():

  • vai rodar até o fim da lista
  • começa com 'a'
    • chama remove_um a partir de 'a'->proximo [ b c c b a a ]
    • vai retornar 1 e remover o sexto elemento [fica b c c b a ]
    • vai retornar 1 e remover o quinto elemento [ fica b c c b ]
    • vai retornar 0 e a lista em [ a b c c b ]
  • passa para 'b'
    • chama remove_um() a partir de 'b'->proximo [ c c b ]
    • vai retornar 1 e remover o terceiro elemento [ fica c c ]
    • vai retornar 0 e a lista fica [ a b c c ]
  • passa para 'c' 
    • chama remove_um() a partir de 'c'->proximo [ c ]
    • vai retornar 1 e remover o primeiro elemento [ fica vazia ]
    • vai retornar 0 e a lista fica [ a b c ]
  • acabou!

Isso é uma descrição do processo apenas

  • Obrigado 1
Welington Silva 2002
 

Welington Silva 2002

Postado
  • Autor
Postado

@arfneto  Eu devia ter mandado o código... Aí está...

Ainda não consegui. Então seria bom eu passar o elemento de cada percorrida na Lista para a função remove, certo?

 

 

#include <iostream>

using namespace std;

struct No {
   int Info;
   No * Lig;
};

typedef struct No *NoPtr;


void InsereLista (NoPtr& L, int Novo) {
  if (L == NULL) {  // INSERÇÃO DO PRIMEIRO NÓ
      L = new No;
      L->Info = Novo;
      L->Lig = NULL;
  } else {                // AJUSTA PONTEIROS ANT E AUX
      NoPtr Ant = NULL;
      NoPtr Aux = L;
      while((Aux != NULL)&&(Aux->Info < Novo)) {//ENCONTRA POSIÇÃO
              Ant = Aux;
             Aux = Aux->Lig;
      }
      Aux = new No;
      Aux->Info = Novo;     // INSERE O NO E AJUSTA PONTEIROS
      if (Ant == NULL) {
            Aux->Lig = L;
            L = Aux;
      } else {
            Aux->Lig = Ant->Lig;
            Ant->Lig = Aux;
      }
  }
}

bool RetiraLista (NoPtr& L, int Novo) {

//serve para passagem do elemento, tipo RetiraLista (L1, 3)
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  while ((Aux != NULL) && (Aux->Info != Novo)) { // TENTA ENCONTRAR ELEMENTO
          Ant = Aux;
          Aux = Aux->Lig;
  }
  if (Aux == NULL)
         return false;  // RETORNA FALSO SE NÃO ENCONTRA ELEMENTO
  if (Aux == L)        // SE ELEMENTO É O PRIMEIRO, REDIRECIONA O PONTEIRO
         L = L->Lig;
  else
         Ant->Lig = Aux->Lig; // REDIRECIONA O PONTEIRO
  delete Aux;  // APAGA O ELEMENTO
  return true;
}

void ImprimeLista (NoPtr L) {
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  cout << "L -> ";
  while ((Aux != NULL)) {
          Ant = Aux;
          Aux = Aux->Lig;
          cout << Ant->Info << " -> ";
  }
  if (Aux == NULL)
      cout << "NULL" << endl;

}
bool RemoveRepetidos (NoPtr& L) //Sem funcao ainda, nem chamei na main()
{
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  // RemoveRepetidos (Aux->Lig); //Havia tentado algo recursivo
}


int main () {

  NoPtr L1 = NULL;

  InsereLista(L1, 1);
  InsereLista(L1, 4);
  InsereLista(L1, 2);
  InsereLista(L1, 2);
//_______________________________________________________________
  cout<<"LISTA NORMAL: "<<endl;
  ImprimeLista(L1); cout<<endl;
  cout<<"LISTA SEM REPETIDOS: "<<endl;
 // RemoveRepetidos(L1);
//_______________________________________________________________


return 0;
}

 

2 minutos atrás, Welington Silva 2002 disse:

@arfneto  Eu devia ter mandado o código... Aí está...

Ainda não consegui. Então seria bom eu passar o elemento de cada percorrida na Lista para a função remove, certo?

 

 

#include <iostream>

using namespace std;

struct No {
   int Info;
   No * Lig;
};

typedef struct No *NoPtr;


void InsereLista (NoPtr& L, int Novo) {
  if (L == NULL) {  // INSERÇÃO DO PRIMEIRO NÓ
      L = new No;
      L->Info = Novo;
      L->Lig = NULL;
  } else {                // AJUSTA PONTEIROS ANT E AUX
      NoPtr Ant = NULL;
      NoPtr Aux = L;
      while((Aux != NULL)&&(Aux->Info < Novo)) {//ENCONTRA POSIÇÃO
              Ant = Aux;
             Aux = Aux->Lig;
      }
      Aux = new No;
      Aux->Info = Novo;     // INSERE O NO E AJUSTA PONTEIROS
      if (Ant == NULL) {
            Aux->Lig = L;
            L = Aux;
      } else {
            Aux->Lig = Ant->Lig;
            Ant->Lig = Aux;
      }
  }
}

bool RetiraLista (NoPtr& L, int Novo) {

//serve para passagem do elemento, tipo RetiraLista (L1, 3)
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  while ((Aux != NULL) && (Aux->Info != Novo)) { // TENTA ENCONTRAR ELEMENTO
          Ant = Aux;
          Aux = Aux->Lig;
  }
  if (Aux == NULL)
         return false;  // RETORNA FALSO SE NÃO ENCONTRA ELEMENTO
  if (Aux == L)        // SE ELEMENTO É O PRIMEIRO, REDIRECIONA O PONTEIRO
         L = L->Lig;
  else
         Ant->Lig = Aux->Lig; // REDIRECIONA O PONTEIRO
  delete Aux;  // APAGA O ELEMENTO
  return true;
}

void ImprimeLista (NoPtr L) {
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  cout << "L -> ";
  while ((Aux != NULL)) {
          Ant = Aux;
          Aux = Aux->Lig;
          cout << Ant->Info << " -> ";
  }
  if (Aux == NULL)
      cout << "NULL" << endl;

}
bool RemoveRepetidos (NoPtr& L) //Sem funcao ainda, nem chamei na main()
{
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  // RemoveRepetidos (Aux->Lig); //Havia tentado algo recursivo
}


int main () {

  NoPtr L1 = NULL;

  InsereLista(L1, 1);
  InsereLista(L1, 4);
  InsereLista(L1, 2);
  InsereLista(L1, 2);
//_______________________________________________________________
  cout<<"LISTA NORMAL: "<<endl;
  ImprimeLista(L1); cout<<endl;
  cout<<"LISTA SEM REPETIDOS: "<<endl;
 // RemoveRepetidos(L1);
//_______________________________________________________________


return 0;
}

 

 

Na verdade,a questao pede para fazer com listas... Não especificou nao... entao se for mais fácil com duplamente encadeada ou generalizada, acredito que podem ser usadas

Entendi entendi, vou tentar aqui. Obrigado! 😇@arfneto

@arfneto

 

Eu fiz isso aqui, saberia me dizr onde to errando?

 

#include <iostream>

using namespace std;

struct No {
   int Info;
   No * Lig;
};

typedef struct No *NoPtr;


void InsereLista (NoPtr& L, int Novo) {
  if (L == NULL) {  // INSERÇÃO DO PRIMEIRO NÓ
      L = new No;
      L->Info = Novo;
      L->Lig = NULL;
  } else {                // AJUSTA PONTEIROS ANT E AUX
      NoPtr Ant = NULL;
      NoPtr Aux = L;
      while((Aux != NULL)&&(Aux->Info < Novo)) {//ENCONTRA POSIÇÃO
              Ant = Aux;
             Aux = Aux->Lig;
      }
      Aux = new No;
      Aux->Info = Novo;     // INSERE O NO E AJUSTA PONTEIROS
      if (Ant == NULL) {
            Aux->Lig = L;
            L = Aux;
      } else {
            Aux->Lig = Ant->Lig;
            Ant->Lig = Aux;
      }
  }
}

bool RetiraLista (NoPtr& L, int Novo) {
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  while ((Aux != NULL) && (Aux->Info != Novo)) { // TENTA ENCONTRAR ELEMENTO
          Ant = Aux;
          Aux = Aux->Lig;
  }
  if (Aux == NULL)
         return false;  // RETORNA FALSO SE NÃO ENCONTRA ELEMENTO
  if (Aux == L)        // SE ELEMENTO É O PRIMEIRO, REDIRECIONA O PONTEIRO
         L = L->Lig;
  else
         Ant->Lig = Aux->Lig; // REDIRECIONA O PONTEIRO
  delete Aux;  // APAGA O ELEMENTO
  return true;
}

void ImprimeLista (NoPtr L) {
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  cout << "L -> ";
  while ((Aux != NULL)) {
          Ant = Aux;
          Aux = Aux->Lig;
          cout << Ant->Info << " -> ";
  }
  if (Aux == NULL)
      cout << "NULL" << endl;
}

bool RemoveRepetidos (NoPtr& L)
{
  NoPtr Ant = NULL;
  NoPtr Aux = L;
  int valor;
  while(Aux!=NULL){
      if(Ant==NULL)
      return false;
      if(Ant==Aux){
      RetiraLista(Aux, valor);
      Ant=Aux;
      Aux = Aux->Lig;
      return true;
     }
  }
}


int main () {

  NoPtr L1 = NULL;

  InsereLista(L1, 1);
  InsereLista(L1, 4);
  InsereLista(L1, 2);
  InsereLista(L1, 2);

  cout<<"LISTA NORMAL: "<<endl;
  ImprimeLista(L1); cout<<endl;
 
  cout<<"LISTA SEM REPETIDOS: "<<endl;
  while(RemoveRepetidos(L1))
  ImprimeLista(L1);
  cout<<endl;

return 0;
}

  • Solução
arfneto
 

arfneto

Postado
  • Solução
Postado
1 hora atrás, Welington Silva 2002 disse:

Eu devia ter mandado o código... Aí está...

Ainda não consegui. Então seria bom eu passar o elemento de cada percorrida na Lista para a função remove, certo?

 

Eu te mostrei até os protótipos...

Para  a função que remove os duplicados naturalmente você passa o endereço do início da lista.

Para a função que remove um você passa o endereço do próximo na lista

Seguiu o exemplo que expliquei? com as sete letras?

 

sobre seu programa

  • uma lista não é um nó. Sempre que programar assim vai ter mais trabalho. Uma lista é uma coleção de nós e deve ser uma estrutura que mostra isso. E em cada nó tem um dado e devia ser só um ponteiro porque assim você usa sempre o mesmo código, que pode deixar em um arquivo separado e nem ficar compilando.
  • main() deve ser a primeira função. Sempre.
  • Não use typedef para criar tipos para ponteiros. Só dá confusão. Para isso tem o asterisco.
  • Não retorne void. Em geral é um desperdício. Às vezes um erro mesmo.
  • Retorne o endereço da lista nas funções que podem mudar tal valor, ao invés de usar um tipo para um ponteiro e passar o endereço. Não é necessário e fica ruim de ler
  • porque está removendo por endereço e não por valor?

 

  •  
  • Amei 1

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora
 Compartilhar
Ir à lista de tópicos

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

Mais

×
×
  • Criar novo...

LANÇAMENTO!

eletronica2025-popup.jpg


CLIQUE AQUI E BAIXE AGORA MESMO!