4165 – FinserareKX

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 *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 C++ cu următorul prototip:

   void FInserareKX(Nod * &head, int k, int x);

care, în lista pentru care primul element are adresa memorată în pointerul head, inserează pe poziția k un nou nod cu informația x. Dacă lista are mai puțin de k noduri, inserarea se face la sfârșitul listei, iar dacă k ≤ 1, atunci inserarea se va face la începutul listei. Lista poate fi inițial și vidă, caz în care head = NULL. De exemplu, dacă lista conține inițial informațiile 1, 2, 3, 4, 5, k = 3 și x = 100, atunci lista devine: 1, 2, 100, 3, 4, 5.

Important

Rezolvarea se va face în python. 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. 4165 FInserareKX

class Node:

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

def FInserareKX(head, k, x):

 new_node = Node(x)
 
 # Cazul în care lista este inițial vidă sau inserăm la începutul listei
 if head is None or k <= 1:
   new_node.next = head
   head = new_node
   return head
 
 # Cazul în care lista are cel puțin un nod și inserăm pe poziția k sau la sfârșitul listei
 current = head
 prev = None
 count = 1
 
 while current and count < k:
   prev = current
   current = current.next
   count += 1
 
 if current is None:  # Inserare la sfârșitul listei
   prev.next = new_node
 else:  # Inserare pe poziția k
   new_node.next = current
   prev.next = new_node
 
 return head

1. Funcție pentru afișarea listei

def afisare_lista(head):

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

1. Exemplu de utilizare

if __name__ == "__main__":

 # Inițializare lista cu câteva noduri
 head = Node(1)
 head.next = Node(2)
 head.next.next = Node(3)
 head.next.next.next = Node(4)
 head.next.next.next.next = Node(5)
 
 # Inserare pe poziția k = 3 a valorii x = 100
 head = FInserareKX(head, 3, 100)
 
 # Afișare lista rezultată
 afisare_lista(head)

</syntaxhighlight>