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

#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

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

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