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

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


# 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)