3527 – FȘterge Duplicate

Enunţ

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

   struct Nod{
     int val;
     Nod *next;
   };

în care câmpul val memorează un număr întreg, iar câmpul next memorează adresa următorului element al listei.

Valorile din listă sunt ordonate crescător.

Cerința

Să se scrie o funcție C++ cu următorul prototip:

void FStergeDuplicate(Nod *&L); Funcția primește ca parametru un pointer L la o listă simplu înlănțuită care are valorile din noduri în ordine crescătoare. Funcția trebuie să elimine nodurile care conțin valori duplicate. De exemplu, dacă lista conține valorile 3,3,3,5,6,7,7,7,7,20, atunci după eliminarea duplicatelor, lista va conține 3,5,6,7,20.

Restricții și precizări

• numele funcției va fi FStergeDuplicate.

Important

Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei. Rezolvarea se va face în python.

Enunţ

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

   struct Nod{
     int val;
     Nod *next;
   };

în care câmpul val memorează un număr întreg, iar câmpul next memorează adresa următorului element al listei.

Valorile din listă sunt ordonate crescător.

Cerința

Să se scrie o funcție C++ cu următorul prototip:

void FStergeDuplicate(Nod *&L); Funcția primește ca parametru un pointer L la o listă simplu înlănțuită care are valorile din noduri în ordine crescătoare. Funcția trebuie să elimine nodurile care conțin valori duplicate. De exemplu, dacă lista conține valorile 3,3,3,5,6,7,7,7,7,20, atunci după eliminarea duplicatelor, lista va conține 3,5,6,7,20.

Restricții și precizări

• numele funcției va fi FStergeDuplicate.

Important

Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei. Rezolvarea se va face în python.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3527 FStergeDuplicate
2. Definim clasa pentru nodul unei liste liniare simplu înlănțuite

class Nod:

 def __init__(self, val=0, next=None):
   self.val = val
   self.next = next

1. Funcția care elimină duplicatele din lista

def FStergeDuplicate(L):

 if L is None:
   return

 current = L
 while current.next is not None:
   if current.val == current.next.val:
     next_next = current.next.next
     current.next = None
     current.next = next_next
   else:
     current = current.next

1. Funcția care creează o listă liniară simplu înlănțuită pe baza unei liste de valori

def createLinkedList(values):

 if not values:
   return None

 # Creăm primul nod al listei
 head = Nod(values[0])
 current = head

 # Iterăm prin valorile date și le adăugăm ca noduri în listă
 for val in values[1:]:
   current.next = Nod(val)
   current = current.next

 return head

1. Exemplu de utilizare

if __name__ == "__main__":

 # Lista de valori din exemplu
 values = [3, 3, 3, 5, 6, 7, 7, 7, 7, 20]

 # Creăm lista liniară simplu înlănțuită
 L = createLinkedList(values)

 # Eliminăm duplicatele din lista
 FStergeDuplicate(L)

 # Afisam lista rezultata
 current = L
 while current is not None:
   print(current.val, end=" ")
   current = current.next

</syntaxhighlight>