4170 – FlșiDesc

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 natural nenul, iar câmpul leg memorează adresa următorului element al listei.

Cerinţa

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

void FLsiDesc(Nod *head);

Lista are cel puțin un nod și are adresa primului element memorată în pointerul head. Informațiile memorate în noduri sunt ordonate strict descrescător. Funcția inserează noduri astfel încât în final lista va memora în ordine descrescătoare toate numerele de la n la 1, unde n este valoarea memorată inițial în primul nod al listei. De exemplu, dacă lista conține inițial informațiile 7,4,3, atunci la final lista va fi: 7,6,5,4,3,2,1. Dacă lista conține inițial doar informația 3, atunci la final lista va fi 3,2,1. Dacă lista conține inițial 2,1, atunci la final lista va fi 2,1. Atenție, doar inserați nodurile care lipsesc, nu efectuați alte operații.

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

     if node is None or node.info > value:
            new_node = Nod(value)
            new_node.leg = node
            return new_node
        else:
            node.leg = insert_desc(node.leg, value)

        return node


    for i in range(head.info, 0, -1):
        head = insert_desc(head, i)

    return head


head = Nod(7)
head.leg = Nod(4)
head.leg.leg = Nod(3)
head = FLsiDesc(head)
while head:
    print(head.info)
    head = head.leg