A. Considerații teoretice

În unele aplicații este util să memorăm datele sub formă de liste ordonate sau liste dublu înlănțuite.

Î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 :

Programul de navigare nu suportă appleturi Java.

În cazul în care aplicația necesită traversarea listei în ambele sensuri (înainte și înapoi), maniera cea mai simplă de a realiza acest lucru este de a memora în fiecare nod al listei referințele înainte și înapoi, lucru care conduce la structura de listă dublu înlanțuită.

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}

În continuare se va pezenta macheta unei posibile aplicatii, utilizând acestă structură de date.


B. Exemple

Se consideră un dicționar enciclopedic care conține cuvinte din limba româna și explicații semantice ale acestor cuvinte. Programul care va gestiona aceste informații va funcționa în stil meniu de comenzi, după algoritmul următor (în pseudocod) :

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;

Folosind o listă dublu înlănțuită, este judicios să o păstrăm ordonată. Fiecare adaugare a unei noi informații în dicționar se va face în așa fel încât lista să rămână permanent ordonată.

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

  1. Să se realizeze programul care implementează algoritmul prezentat pentru dicționarul enciclopedic. Se va acorda o atenție deosebită metodei de căutare a cuvintelor, fiind incurajate ideile originale.

  2. Același program, folodind o listă circulară dublu înlănțuită cu un singur pointer (călător).