1476 – FSortare

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.

Cerința

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

 void sortareCrescator(nod *&prim)

care sortează crescător elementele listei al cărei prim element are adresa memorată în prim.

Restricții și precizări

• numele funcției va fi sortareCrescator
• lista va conține cel puțin 3 elemente
• rezolvarea se va face in python

Exemplu

Dacă lista este formată din valorile (5, 3, 9, 4, 2, 12), după apelul funcţiei ea va conţine elementele (2, 3, 4, 5, 9, 12).

Rezolvare

<syntaxhighlight lang="python" line>

1. 1476 FSortare

class Node:

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

def create_linked_list(values):

   head = None
   tail = None
   for value in values:
       new_node = Node(value)
       if head is None:
           head = new_node
           tail = new_node
       else:
           tail.next = new_node
           tail = new_node
   return head

def sortareCrescator(prim):

   # Funcție pentru inserarea unui nod într-o listă sortată
   def insert_sorted(head, new_node):
       if head is None or head.info >= new_node.info:
           new_node.next = head
           return new_node

       current = head
       while current.next is not None and current.next.info < new_node.info:
           current = current.next
       
       new_node.next = current.next
       current.next = new_node
       return head
   
   # Inițializăm lista sortată ca fiind lista vidă
   sorted_list = None
   current = prim
   
   # Parcurgem lista inițială și inserăm fiecare nod în lista sortată
   while current is not None:
       sorted_list = insert_sorted(sorted_list, Node(current.info))
       current = current.next
   
   # Copiem lista sortată înapoi în lista inițială
   current = prim
   sorted_current = sorted_list
   while sorted_current is not None:
       current.info = sorted_current.info
       current = current.next
       sorted_current = sorted_current.next

1. Testăm funcția

def print_list(head):

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

1. Cream lista de test folosind funcția create_linked_list

values = [5, 3, 9, 4, 2, 12] l = create_linked_list(values)

print("Lista initiala:") print_list(l)

1. Sortam lista

sortareCrescator(l)

print("Lista sortata:") print_list(l) </syntaxhighlight>