2563 – FAdCresc

Enunţ

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 * urm;
   };

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

Informațiile din listă sunt ordonate crescător.

Cerința

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

   void ins_cresc(nod *&p, int x);

care inserează în listă un nou nod care memorează valoarea x astfel încât informațiile din lista să fie în continuare ordonate crescător; pointerul p are ca valoarea adresa primului element din listă.

Restricții și precizări

• numele funcției va fi ins_cresc.
• lista conține inițial cel puțin un nod.
• rezolvarea problemei se va face în ptyhon

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="python" line>

1. 2563 FAdCresc

class Node:

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

def ins_cresc(p, x):

 new_node = Node(x)
 
 # Dacă lista este goală sau noul nod trebuie inserat înaintea primului nod
 if p is None or x < p.info:
   new_node.next = p
   p = new_node
   return p
 
 # Parcurgem lista până găsim locul corect pentru inserare
 current = p
 while current.next is not None and current.next.info < x:
   current = current.next
 
 # Inserăm noul nod între current și current.next
 new_node.next = current.next
 current.next = new_node
 
 return p

1. Funcție pentru afișarea listei

def print_list(p):

 current = p
 while current is not None:
   print(current.info, end=" ")
   current = current.next
 print()

1. Funcție pentru crearea listei inițiale

def create_list(values):

 if not values:
   return None
 
 p = Node(values[0])
 current = p
 for val in values[1:]:
   current.next = Node(val)
   current = current.next
 
 return p
   

1. Funcție pentru afișarea listei în ordine crescătoare

def print_list_sorted(p):

 # Creează o listă pentru a stoca valorile din listă
 values = []
 current = p
 while current is not None:
   values.append(current.info)
   current = current.next
 
 # Sortează valorile
 values.sort()
 
 # Afișează valorile sortate
 for val in values:
   print(val, end=" ")
 print()

if __name__ == "__main__":

 # Cream lista de test
 values = [2, 4, 8, 6, 1, 0]
 p = create_list(values)

 #  Afisam lista in ordine crescatoare
 print("Lista creata:")
 print_list_sorted(p)

</syntaxhighlight>