4167 – FlșiElimină

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

struct Nod
{
    int info;
    Nod *leg;
};

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

Cerinţa

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

def FLsiElimina(head): head = None

care, în lista pentru care primul element are adresa memorată în pointerul head, elimină toate nodurile cuprinse între cel mai din stânga nod care memorează un număr divizibil cu 3 și cel mai din dreapta nod care memorează un număr divizibil cu 3, inclusiv acestea. Se garantează că lista va conține cel puțin două noduri care au informația divizibilă cu 3. Dacă se elimină toate nodurile, atunci după apelul funcției trebuie ca head = NULL. De exemplu, dacă lista conține inițial informațiile 1,27,3,4,13,12,44,23, atunci la final lista va fi: 1,44,23.

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.

Rezolvare

<syntaxhighlight lang="python3"> class Nod:

   def __init__(self, info):
       self.info = info
       self.leg = None

def FLsiElimina(head):

   # Cautăm primul nod cu informația divizibilă cu 3
   primul_nod = None
   nod_curent = head

   while nod_curent is not None and nod_curent.info % 3 != 0:
       primul_nod = nod_curent
       nod_curent = nod_curent.leg

   # Cautăm ultimul nod cu informația divizibilă cu 3
   ultimul_nod = None
   nod_curent = head
   while nod_curent is not None:
       if nod_curent.info % 3 == 0:
           ultimul_nod = nod_curent
       nod_curent = nod_curent.leg

   # Eliminăm nodurile cuprinse între primul_nod și ultimul_nod, inclusiv acestea
   nod_curent = head
   while nod_curent is not None and nod_curent != primul_nod:
       nod_urmator = nod_curent.leg
       del nod_curent
       nod_curent = nod_urmator

   if primul_nod is not None:
       primul_nod.leg = ultimul_nod.leg
       nod_curent = ultimul_nod.leg
       while nod_curent is not None:
           nod_urmator = nod_curent.leg
           del nod_curent
           nod_curent = nod_urmator
   else:
       # Dacă primul_nod este None, eliminăm toate nodurile de la început până la ultimul_nod
       head = ultimul_nod.leg
       nod_curent = ultimul_nod.leg
       while nod_curent is not None:
           nod_urmator = nod_curent.leg
           del nod_curent
           nod_curent = nod_urmator

   return head

1. Funcție de afișare a listei

def afisare_lista(head):

   while head is not None:
       print(head.info, end=" ")
       head = head.leg
   print()

head = Nod(1) head.leg = Nod(27) head.leg.leg = Nod(3) head.leg.leg.leg = Nod(4) head.leg.leg.leg.leg = Nod(13) head.leg.leg.leg.leg.leg = Nod(12) head.leg.leg.leg.leg.leg.leg = Nod(44) head.leg.leg.leg.leg.leg.leg.leg = Nod(23)

print("Lista initiala:", end=" ") afisare_lista(head)

head = FLsiElimina(head)

print("Lista finala:", end=" ") afisare_lista(head)

</syntaxhighlight>