2563 – FAdCresc
De la Universitas MediaWiki
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 C++ 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)