Parcurgerea listei înlănțuite nu se mai oprește (lipsește curent = curent.urm)
În bucla while curent: ai uitat să avansezi cu curent = curent.urm (sau avansezi doar pe o ramură a unui if), așa că nodul curent nu se schimbă și bucla rulează la nesfârșit; editorul o oprește după limita de timp. Avansează pe fiecare drum prin buclă.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Parcurgerea unei liste înlănțuite are mereu forma while curent: ... curent = curent.urm. Bucla se termină pentru că, la un moment dat, curent devine None. Dacă linia de avans lipsește, sau există doar pe o ramură a unui if, curent rămâne pe același nod și condiția e adevărată pentru totdeauna.
Python nu dă o excepție pentru bucle infinite. În editorul nostru programul e oprit după limita de timp, cu mesajul „Programul a rulat prea mult și a fost oprit”. Dacă bucla adaugă ceva într-o listă la fiecare pas, poți vedea și o creștere a memoriei.
O a doua cauză, mai subtilă: lista chiar are un ciclu (ultimul nod trimite înapoi la un nod anterior), de exemplu după o inversare sau o reordonare greșită. Atunci și o parcurgere corectă nu se mai termină. Algoritmul Floyd (rapid-lent) detectează un astfel de ciclu.
De ce apare: cauzele frecvente
1Lipsește avansul
total = 0
curent = cap
while curent:
total += curent.valtotal = 0
curent = cap
while curent:
total += curent.val
curent = curent.urmFără curent = curent.urm, curent rămâne primul nod, iar while curent e mereu adevărat.
2Avansul doar pe o ramură
while curent:
if curent.val < 0:
continue
pozitive += 1
curent = curent.urmwhile curent:
if curent.val >= 0:
pozitive += 1
curent = curent.urmcontinue sare peste avans, deci primul nod negativ blochează bucla. Avansul trebuie să se execute la fiecare iterație.
3Ciclu creat de o operație greșită
ultimul.urm = cap
cap = cap.urmultimul.urm = cap
cap = cap.urm
ultimul.urm.urm = NoneLa rotații și reordonări, nodul care devine ultimul trebuie să primească urm = None, altfel lista se închide în buclă.
Repară eroarea, direct în pagină
Funcția suma_pozitive(cap) adună valorile pozitive dintr-o listă înlănțuită de tranzacții, dar programul nu se termină și e oprit după limita de timp. Repar-o ca să afișeze 17, 0 și 0.
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def construieste(valori):
cap = None
for v in reversed(valori):
cap = Nod(v, cap)
return cap
def suma_pozitive(cap):
total = 0
curent = cap
while curent:
if curent.val < 0:
continue
total += curent.val
curent = curent.urm
return total
print(suma_pozitive(construieste([5, -3, 12, -1])))
print(suma_pozitive(construieste([-4])))
print(suma_pozitive(construieste([])))17 0 0
Indiciu
continue sare peste linia care trece la nodul următor.
Reparația
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def construieste(valori):
cap = None
for v in reversed(valori):
cap = Nod(v, cap)
return cap
def suma_pozitive(cap):
total = 0
curent = cap
while curent:
if curent.val > 0:
total += curent.val
curent = curent.urm
return total
print(suma_pozitive(construieste([5, -3, 12, -1])))
print(suma_pozitive(construieste([-4])))
print(suma_pozitive(construieste([])))De ce merge
La primul nod negativ (-3), continue sărea direct la condiția buclei, fără să execute curent = curent.urm. curent rămânea pe același nod, care era tot negativ, deci bucla se repeta la nesfârșit. În varianta corectă, adunarea e condiționată, iar avansul e pe ultima linie a buclei, fără nicio ramură care să-l ocolească: fiecare iterație trece la nodul următor, iar bucla se termină la None.
Alte forme ale mesajului
Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.
Cum o eviți pe viitor
Scrie linia de avans (curent = curent.urm) imediat după ce scrii while curent:, apoi completează corpul buclei. Evită continue în parcurgerile de liste înlănțuite sau pune avansul înainte de el. După operațiile care rearanjează nodurile (inversare, rotire, reordonare), verifică că noul ultim nod are urm = None, afișând lista cu o funcție care se oprește după un număr maxim de pași.
Întrebări frecvente
Cum îmi dau seama dacă e o buclă fără avans sau un ciclu în listă?
Afișează curent.val în buclă pentru primii 20 de pași. Dacă vezi mereu aceeași valoare, lipsește avansul. Dacă valorile se repetă în același tipar, lista are un ciclu.
Pe calculatorul meu programul se blochează fără niciun mesaj. E aceeași problemă?
Da. Python nu oprește singur o buclă infinită. Apasă Ctrl+C: vei vedea KeyboardInterrupt și linia la care rula programul.
Erori înrudite
AttributeError: 'NoneType' object has no attribute 'urm' Ai ajuns la capătul listei înlănțuite (nodul curent e None) și ai cerut încă .urm sau .val. Verifică nodul înainte de acces: while curent and curent.urm:, iar la doi pași (rapid.urm.urm) verifică ambii pași. Căutarea binară intră în buclă infinită (stanga = mijloc) Când ai actualizat capătul cu stanga = mijloc (sau dreapta = mijloc într-o buclă cu <=), intervalul nu se mai micșorează și bucla se repetă la nesfârșit; editorul oprește programul după limita de timp. Mută capătul dincolo de mijloc: stanga = mijloc + 1 și dreapta = mijloc - 1. BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate) BFS-ul pune în coadă vecinii fără să verifice dacă au mai fost descoperiți, iar pe un graf cu ciclu (sau neorientat) aceleași noduri intră în coadă la nesfârșit; editorul oprește programul după limita de timp. Marchează nodul ca vizitat când îl pui în coadă. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
