A. Considerații teoretice
Într-o listă ordonată, elementele sunt dispuse în ordinea crescătoare (sau
descrescătoare) a valorilor unei chei. În general, listele ordonate se
pot utiliza în majoritatea situațiilor în care se utilizează tablouri
ordonate. Avantajele listelor ordonate, față de tablouri, constau în
viteza inserării (datorită faptului că nu trebuie să deplasăm nici un element)
și în faptul că o listă se poate extinde până când umple toată memoria
disponibilă (în timp ce tabloul este limitat la o dimensiune fixă). Prețul
acestor avantaje este însă un algoritm a cărui implementare este ceva mai
dificilă decât în cazul unui tablou ordonat. De exemplu, pentru a insera un
element într-o listă ordonată, algoritmul trebuie mai întâi să caute în listă
poziția corespunzătoare pentru noul element; aceasta este exact înainte de
primul element mei mare decât cel care se inserează. După ce algoritmul
găsește poziția respectivă, elementul este inserat în mod obișnuit,
modificându-i câmpul de legătură astfel încât să indice următorul nod (primul
mai mare) din listă și modificând câmpul de legătură al nodului anterior
astfel încât să se refere la noul nod (cel care se inserează). Există și
câteva cazuri speciale care trebuie condiderate, anume atunci când noul
element trebuie inserat la începutul listei, respectiv la sfârșitul ei. O
ilustrare a acestui concept se poate urmări în următorul applet :
Se poate construi lista memorând în permanență primul nod, ultimul nod, și folosind un pointer ''călător'' care circulă de-a lungul listei în ambele direcții. Fiind date cele trei puncte de plecare posibile, crește viteza medie de acces la un nod oarecare.
Se poate implementa și structura de tip listă dublu înlănțuită circulară, care utilizează numai pointerul ''călător''. Această structură de date dinamică este preferată deseori de catre programatori, permițând implementări simple și sigure. Declararea acestui tip de date se face în felul următor:
type ptr = ^element; element = record el: TipElement; anterior, urmator: ptr end; var prim, ultim, curent: ptr; {cei trei pointeri}
B. Exemple
repeat clrscr; { sterge ecranul } *afiseaza meniul; *citeste optiunea; case *optiune of *adaugare: *adauga la lista un nou cuvant si explicatia aferenta lui; *interogare: *citeste un cuvant si afiseaza explicatia aferenta lui; *modificare: *citeste un cuvant si modifica explicatia aferenta lui; *stergere: *elimina un cuvant din dictionar ; *oprire: stop := true end; until stop;
La ștergere, interogare, sau modificare, trebuie găsit în dicționar un cuvânt citit de la tastatură. Pentru ca acestă căutare să dureze cât mai puțin, contează punctul de plecare și direcția de parcurgere alese. De exemplu, dacă cuvântul începe cu o literă de la începutul alfabetului se pornește de la primul nod spre înainte. Dacă cuvântul începe cu o literă de la sfârșitul alfabetului, se începe de la ultimul nod înapoi. Sau, se mai poate folosi pointerul călător, după ce s-a stabilit în ce direcție se va porni.
C. Teme