Exclua os nós duplicados de uma lista vinculada não classificada
Neste artigo, veremos as diferentes abordagens para excluir os nós duplicados da lista vinculada usando a programação C ++. Vamos começar com uma explicação do que os "nós duplicados" em uma lista vinculada significam.
Recebemos uma lista vinculada não classificada neste desafio e solicitamos a exclusão de todos os membros duplicados da lista. Vamos usar alguns exemplos para tentar entender o problema.
A lista vinculada de entrada não classificada é a seguinte:
Os elementos 8, 10 e 9 aparecem mais de uma vez na lista vinculada, como visto na lista anterior. Isso indica que existem duplicatas de 8, 10 e 9 na lista vinculada que devemos eliminar. A lista vinculada de saída é a seguinte assim que as entradas duplicadas forem removidas da lista:
Uma maneira rápida e fácil de descobrir é comparar todos os pares possíveis de nós da lista para ver se eles têm as mesmas informações. Quando a informação deles coincide, nos livramos do segundo nó, excluindo -as. Mas essa abordagem é mais demorada.
Melhor eficiência é possível usando Hashing. O objetivo é trabalhar na lista fornecida e adicionar cada nó a um conjunto à medida que você avança. Se o nó atualmente visto aparecer no conjunto anterior, poderá ser desconsiderado com segurança. Quando o processo estiver concluído, a lista não contém mais nós duplicados.
Vamos entender cada abordagem em detalhes.
Abordagem 1: Usando dois loops
Etapas do algoritmo
- Crie uma função de lista vinculada, “CreateLinkedList“, Que pode criar uma lista vinculada.
- Crie uma função chamada “DeLetedUplicatesNodes”Isso pode excluir o nó duplicado da lista vinculada.
- Crie dois ponteiros locais, ptr1 e ptr2, dentro do “DeLetedUplicatesNodes”Função.
- Atribua o PTR1 = HeadNode e ptr2 = nulo Valores, onde o ptr1 é usado para rastrear o nó cujas duplicatas precisam ser verificadas e o ptr2 é usado para atravessar cada nó da lista vinculada para verificar se algum dado do nó é o mesmo que os dados do nó ptr1.
- O ponteiro de loop aninhado PTR2 continua atravessando todo o nó da lista vinculada até encontrar NULL.
- Se os dados do nó ptr1 forem semelhantes aos dados do nó ptr2 de loop aninhados, exclua esse nó da lista vinculada.
- Se não, incrementar o ptr1-> próximo e verifique os dados do próximo nó para duplicar.
- As etapas 4 a 7 são repetidas até que o ptr1 não seja igual a nulo, o que indica que atingiu o final da lista vinculada.
- Finalmente, imprimimos a lista vinculada.
- Fim do algoritmo.
Implementação de código C ++ (usando dois loops)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #incluir |
Saída:
| 1 2 3 4 5 6 7 8 9 10 11 12 | Digite o tamanho (n) da matriz: |
Explicação:
Linhas 21 a 52: Criamos uma função com o nome "CreateLinkedList". Passamos dois parâmetros (um ponteiro de cabeça para o ponteiro e um valor) nessa função. Conforme mostrado no programa anterior, sempre que essa função é chamada, primeiro cria um novo nó com um valor (que passamos) e um endereço de nó com um valor nulo.
/* Crie um novo nó*/
Nó* newNode = new Node ();
Nó * lastNode = * headNode;
newNode-> data = value; / * Adicionando os dados */
/* Endereço deste novo nó mantido intimamente nulo*/
newNode-> próximo = null;
Então, ele verifica se a referência da cabeça é nula. Se for, o nó recém -criado se torna a cabeça.
/* Verificando a referência do código da cabeça é nula ou não.
Se sim, então o newNode se tornará o nó de cabeça*/
if (*headNode == null)
*headNode = newNode;
retornar;
Se a referência do NODE não for nula, ele anexará o último dia da lista vinculada. O endereço deste newNode recém -criado é atribuído ao LastNode para que ele possa começar a apontar para o recém -criado newNode.
/* Se não, então isso enquanto o loop vai
execute e encontre o último nó do vinculado
Lista, para que o recém -criado NewNode anexe no último*/
while (lastNode-> próximo != Null)
lastNode = lastNode-> Next;
Agora, o recém -criado NewNode se torna o LastNode. Este processo continua até aquele momento em que chamamos essa função.
As etapas anteriores criam a lista vinculada conforme nossos requisitos. Agora, excluímos os nós duplicados da lista vinculada.
Linhas 57 a 75: Criamos uma função chamada "DeleteDuplicatesNodes", que aceita um parâmetro que é o ponteiro do código da cabeça da lista vinculada. Criamos duas variáveis de nível local, PTR1 e PTR2, para rastrear a lista vinculada quando o loop para descobrir as duplicatas na lista vinculada. Inicializamos o ptr1 com o nó de cabeça, pois este será o loop superior e o ptr2 com o valor nulo.
pTr1 = HeadNode;
ptr1: Esta variável está no loop externo e rastreia os elementos cujas duplicatas vamos verificar.
ptr2: Essa variável está dentro do loop e continua a verificar os dados de cada nó para descobrir se corresponder aos dados do PTR1 Hold. Se corresponder, suas duplicatas serão removidas da lista vinculada. Isso é verificado e continua até que não atinja o último nó cujo valor é nulo.
Quando ptr2-> próximo == nulo, o aninhado enquanto o loop termina e o externo enquanto o loop incrementa o ptr1 = ptr1-> próximo com os próximos dados do nó.
Observação: O ptr2 termina quando o ptr1 Loop acabou porque ptr2 está dentro do loop ptr1.
enquanto (ptr1 != Null && ptr1-> próximo != Null)
ptr2 = ptr1;
while (ptr2-> próximo != Null)
/* Se encontrado, o código abaixo excluirá
duplica o nó*/
if (ptr1-> dados == ptr2-> next-> dados)
duplicate = ptr2-> próximo;
ptr2-> próximo = ptr2-> próximo-> próximo;
excluir (duplicar);
else /* se não for encontrado, o ptr2 será atualizado para
para o próximo nó*/
ptr2 = ptr2-> próximo;
ptr1 = ptr1-> próximo;
Linhas 78 a 84: Isso exibe a lista final vinculada sem qualquer duplicação. Nesse caso, passamos no código de cabeça como um parâmetro que é o endereço da lista vinculada.
/* Esta função imprimirá a lista vinculada*/
Void Display (nó* nó)
while (nó-> a seguir)
printf ("%d ->", node-> dados);
nó = nó-> a seguir;
printf ("%d", node-> dados);
Abordagem 2: Método de Hashing
Etapas do algoritmo
- Crie uma função de lista vinculada, "CreateLinkedList", que pode criar uma lista vinculada.
- Crie uma função chamada “DeleteDuplicatesNodes” que pode excluir o nó duplicado da lista vinculada.
- Crie dois ponteiros locais, CurrentNode e AnteriorNode, dentro da função "DeletEdUplicatesNodes".
- Crie um hash não classificado definido dentro dos “DeLetedUplicatesNodes”.
- Atribua os valores CurrentNode = HeadNode e AnteriorNode = NULL, onde o CurrentNode é usado para rastrear o nó cujas duplicatas devem ser verificadas e o Node anterior é usado para rastrear o nó anterior do CurrentNode.
- O loop while atravessa todo o nó da lista vinculada até currentNode == null.
- Se os dados do CurrentNode já estiverem no conjunto de hash, o nó será excluído.
- Caso contrário, acrescenta os dados desse nó ao conjunto de hash.
- As etapas 5 a 8 são repetidas até que o Node Current não seja igual a NULL, o que indica que atingiu o final da lista vinculada.
- Finalmente, imprimimos a lista vinculada.
- Fim do algoritmo.
Implementação de código C ++ (usando o método hash)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #incluir |
Saída:
| 1 2 3 4 5 6 7 8 9 10 11 12 | Digite o tamanho (n) da matriz: |
Linhas 26 a 52: Criamos uma função com o nome "CreateLinkedList". Nessa função, passamos dois parâmetros (um ponteiro de cabeça para o ponteiro e um valor). Como mostrado no programa anterior, sempre que essa função é chamada, primeiro cria um novo nó com um valor (que passamos) e um endereço com um valor nulo.
/* Crie um novo nó*/
Nó* newNode = new Node ();
Nó * lastNode = * headNode;
newNode-> data = value; / * Adicionando os dados */
/* Endereço deste novo nó mantido intimamente nulo*/
newNode-> próximo = null;
Então, ele verifica se a referência da cabeça é nula. Se for, o nó recém -criado se torna a cabeça.
/* Verificando a referência do código da cabeça é nula ou não.
Se sim, então o newNode se tornará o nó de cabeça*/
if (*headNode == null)
*headNode = newNode;
retornar;
Se a referência do NODE não for nula, ele anexará o último dia da lista vinculada. O endereço deste newNode recém -criado é atribuído ao LastNode para que ele possa começar a apontar para o recém -criado newNode.
/* Se não, então isso enquanto o loop vai
execute e encontre o último nó do vinculado
Lista, para que o recém -criado NewNode anexe no último*/
while (lastNode-> próximo != Null)
lastNode = lastNode-> Next;
Agora, o recém -criado NewNode se torna o LastNode. Este processo continua até aquele momento em que chamamos essa função.
As etapas anteriores criam a lista vinculada conforme nossos requisitos. Agora, excluímos os nós duplicados da lista vinculada.
Linhas 57 a 75: Criamos uma função chamada "DeleteDuplicatesNodes", que aceita um parâmetro que é o ponteiro do código da cabeça da lista vinculada. Criamos um hash hashset não classificado. Também criamos duas variáveis de nível local, CurrentNode e anteriorNode, Para rastrear a lista vinculada quando o loop para descobrir as duplicatas na lista vinculada. Inicializamos o CurrentNode com o NODE DE CABE.
Nó da estrutura* currentNode = headNode;
Nó da estrutura* anteriorNode = null;
CurrentNode: Esta variável está no loop externo e rastreia os elementos cujas duplicatas vamos verificar.
anteriorNode: Isso lida com o nó anterior do CurrentNode. Criamos um laço de tempo que é executado até que o CurrentNode não encontre o valor nulo, o que significa no final da lista vinculada. Se os dados do CurrentNode já estiverem no mapa de hash, atribua o valor do CurrentNode's Próximo ponteiro para o anteriorNode's Próximo ponteiro.
anteriorNode-> Next = CurrentNode-> Next;
Caso contrário, adicione os dados do CurrentNode ao mapa de hash e faça o anteriorNode igual ao CurrentNode.
outro
cerquilha.inserir (currentNode-> dados);
anteriornode = currentNode;
No final, atribua o valor do próximo ponteiro do NODE anterior ao CurrentNode.
while (CurrentNode != Null)
/* Se os dados do Node Current já visitaram, então este
Código excluirá esse nó
*/
if (hash.LINDO (CurrentNode-> Data) != hash.fim())
anteriorNode-> Next = CurrentNode-> Next;
excluir (currentNode);
/*
Se não for visitado os dados do CurrentNode, então
inserir no hash
*/
outro
cerquilha.inserir (currentNode-> dados);
anteriornode = currentNode;
currentNode = anteriorNode-> Next;
Linhas 84 a 90: Isso exibe a lista final vinculada sem qualquer duplicação. Nesse caso, passamos no código de cabeça como um parâmetro que é o endereço da lista vinculada.
/* Esta função imprimirá a lista vinculada*/
Void Display (nó* nó)
while (nó-> a seguir)
printf ("%d ->", node-> dados);
nó = nó-> a seguir;
printf ("%d", node-> dados);
Conclusão
No primeiro método, para se livrar das duplicatas, utilizamos dois loops: um loop externo que itera a lista vinculada e seleciona um elemento e um segundo loop que itera sobre esse elemento para procurar qualquer possível duplicado. Assim que uma duplicata é detectada, ela é excluída da lista. Este método usa um loop aninhado para examinar e eliminar duplicatas de uma lista vinculada não classificada que aumenta a complexidade do tempo do processo. A complexidade do tempo é O (n2).
No segundo método, o hash pode ser usado para minimizar a complexidade temporal de remover as duplicatas de uma lista vinculada não classificada. Nesse caso, se o nó aparecer no hashmap duas vezes, é uma duplicação e a primeira ocorrência deve ser excluída. Se um nó está faltando no mapa, é porque há um novo que deve ser adicionado. Leva em média o tempo O (n) para passar por uma lista vinculada de comprimento "n" e verifica se seus nós estão no mapa. A complexidade temporal para procurar um valor em uma tabela de hash é o (1). Considerando os pré -requisitos acima mencionados juntos, a complexidade total do tempo é O (n).