A. Considerații teoretice

Limbajele de programare de nivel înalt (PASCAL, C, JAVA etc.) oferă posibilitatea alocării dinamice a memoriei. Aceasta se realizează prin două zone distincte ale memoriei, puse la dispoziția programului. Prima zonă, numită stiva programului, se utilizează pentru memorarea informațiilor asociate apelurilor de subprograme. A doua zonă, numită heap, de unde pot fi "luate" sau unde pot fi "aruncate" blocuri de diferite dimensiuni, permite programului să ocupe, la un moment dat, numai spațiul de memorie strict necesar. Zonele din heap nu au nume simbolic (identificator) asociat în program, ele fiind accesate prin adresa de memorie a începutului (prima locație).

Pe un calculator compatibil IBM PC o adresă de memorie este reprezentată pe patru octeți (două cuvinte), doi pentru adresa segmentului (din considerente de arhitectură hardware, memoria este împărțită în "felii" numite segmente) și doi octeți pentru deplasamentul (distanța sau offset-ul) de la începutul segmentului.

În limbajul PASCAL o astfel de adresă se declară ca în exemplul următor:

type adresa = ^<tip_variabila_alocata_dinamic>;

unde tipul variabilei alocate dinamic se poate declara și ulterior, și poate fi orice tip simplu sau structurat. O variabilă de tipul adresă poate memora adresa primei locații a unei zone contigue de memorie care conține informațiile asociate variabilei alocate dinamic. Pentru a rezerva o astfel de zona din heap este necesară o variabilă de tip adresă (numită și pointer) și apelul unei proceduri standard PASCAL - new:

var p: adresa;
...
begin
  ...
  new(p);
  ...

Lungimea zonei indicată de variabila p va fi lungimea necesară memorării unei variabile de tipul tip_variabila_alocata_dinamic. Numele acestei zone va fi p^. Dacă:

  ...
  r := p;   { r de tipul adresa }
  new(p);   { o noua alocare din heap }
  ...

atunci p^ va desemna o altă variabilă dinamică, pointerul r indicând spre prima variabilă dinamică creată.

Pentru a "reintroduce" în heap zona ocupată de o variabilă dinamică, de care nu mai este nevoie, trebuie cunoscută adresa ei de început și lungimea. Acestea se află memorate în pointerul care indică zona respectivă, precum și în tipul variabilei. Pentru eliberarea zonei de memorie se folosește procedura standard dispose.

Este recomandabil ca toți pointerii din program care nu indică spre o zona alocată din heap să fie setați pe valoarea nil (cuvânt rezervat PASCAL, care înseamnă pointer spre nicăieri).


B. Exemple

O listă simplu înlănțuită este o structură de date omogenă, secvențială, formată din elemente numite noduri. Fiecare nod conține o informație utilă (valoare) și o informație de legătură. O ilustrare a acestui concept se poate urmări în următorul applet :

Programul de navigare nu suportă appleturi Java.

În continuare este prezentat un program care, utilizând structura de tip listă simplu înlănțuită execută o serie de operații cu pointeri (indicate de către utilizator) și afișează permanent starea și valoarea acestora.

program liste1;
uses crt;
type
  ptr = ^nod;
  nod = record
    nr: integer;
    urm: ptr;
  end;
  ConvPtr = record
    ofs: word;
    seg: word;
  end;

var
  n: integer;
  r: ptr;
  op: char;

procedure Initializari;
begin
  n := 0;
  r := nil
end;

function Hexa (x: word): string;
const CifreH: array[0..15] of char =
  ('0', '1', '2', '3', '4', '5', '6', '7',
   '8', '9', 'A', 'B', 'C', 'D', 'E', 'F');
var s: string;
begin
  s := '';
  repeat
    s := CifreH[x mod 16] + s;
    x := x div 16;
  until x = 0;
  Hexa := '$' + s
end;

procedure ScrieOAdresa(p: ptr);
begin
  if p = nil then
    write(' nil')
  else
    write(' ', Hexa(ConvPtr(p).Seg), ':', Hexa(ConvPtr(p).Ofs))
end;

procedure ScrieNod(p: ptr);
begin
  write('Adresa '); ScrieOAdresa(p);
  write(' : nr= ', p^.nr:1, ' , urm=');
  ScrieOAdresa(p^.urm);
  writeln;
  delay(1000);
end;

procedure ScrieLista;
var q: ptr;
begin
  write('Radacina= ');
  ScrieOAdresa(r);
  writeln;
  q := r;
  while q <> nil do
  begin
    ScrieNod(q);
    q := q^.urm;
  end;
  writeln;
end;

function NodNou: ptr;
var p: ptr;
begin
  new(p);
  n := n + 1;
  with p^ do
  begin
    nr := n;
    urm := nil
  end;
  write('S-a alocat nodul: '); 
  delay(1000);
  ScrieNod(p);
  delay(1000);
  NodNou := p;
end;

procedure InserIncep;
var nnod: ptr;
begin
  writeln('Inserare la inceput...');
  nnod := NodNou;
  nnod^.urm := r;
  write('nnod^.urm:=r; Noul nod: ');
  ScrieNod(nnod);
  delay(1000);
  r := nnod
end;

procedure InserSf;
var nnod, q: ptr;
begin
  writeln('Inserare la sfarsit...');
  nnod := NodNou;
  if r = nil then r := nnod
    else
    begin
      q := r;
      while q^.urm <> nil do q := q^.urm;
      q^.urm := nnod
    end;
end;

function CautaNod(NumarNod: integer): ptr;
var q: ptr;
begin
  q := r;
  while (q <> nil) and (q^.nr <> NumarNod) do
    q := q^.urm;
  if q = nil then
  begin
    writeln('Nodul cautat nu exista.');
    delay(1000)
  end;
  CautaNod := q;
end;

procedure Ins(numar: integer);
var nnod, q, q1: ptr;
begin
  q := CautaNod(Numar);
  if q = nil then InserSf
  else
  begin
    write('Nodul q^: ');
    ScrieNod(q);
    nnod := NodNou;
    new(q1);
    write('new(q1) - ');
    ScrieNod(q1);
    q1^ := q^;
    write('q1^=q^ - ');
    ScrieNod(q1);
    nnod^.urm := q1;
    write('nnod^.urm:=q1 ');
    ScrieNod(nnod);
    q^ := nnod^;
  end;
end;

procedure Inserare;
var op: integer;
begin
  writeln;
  writeln(' 0 = inserare la INCEPUTUL listei');
  writeln('-1 = inserare la SFARSITUL listei');
  writeln(' n = inserarea INAINTEA nodului "n"');
  write('Optiunea: ');
  readln(op);
  case op of
    0: InserIncep;
    -1: InserSf;
    else Ins(op)
  end;
end;

procedure SterIncep;
var ps: ptr;
begin
  writeln('Stergere la inceputul listei...');
  ps := r;
  r := ps^.urm;
  dispose(ps);
  writeln('dispose(ps);');
  delay(1000)
end;

procedure SterSf;
var q1, ps: ptr;
begin
  writeln('Stergere la sfarsitul listei...');
  q1 := r;
  while q1^.urm^.urm <> nil do q1 := q1^.urm;
  ps := q1^.urm;
  q1^.urm := nil;
  dispose(ps);
  writeln('dispose(ps);');
  delay(1000)
end;

procedure Ster(q: ptr);
var ps: ptr;
begin
  writeln('Stergere in interiorul listei...');
  ps := q^.urm;
  q^ := ps^;
  dispose(ps);
  writeln('dispose(ps);');
  delay(1000)
end;

procedure Stergere;
var
  nn: integer;
  q: ptr;
begin
  write('Stergeti nodul nr. ');
  readln(nn);
  q := CautaNod(nn);
  if q <> nil then
  begin
    write('Nodul q^: ');
    ScrieNod(q);
    delay(1000);
    if q = r then SterIncep
    else
      if q^.urm = nil then SterSf
      else Ster(q)
    
  end;
end;

begin { Programul Principal }
  Initializari;
  writeln('Lista initiala este: ');
  ScrieLista;
  delay(2000);
  repeat
    writeln;
    writeln('I = Inserare');
    writeln('S = Stergere');
    writeln('T = Stop');
    write('Optiunea: ');
    op := readkey;
    writeln(op);
    case op of
      'I','i': Inserare;
      'S','s': Stergere;
    end;
    if op in ['I', 'i', 'S', 's'] then
    begin
      writeln('Lista a devenit:');
      ScrieLista;
      delay(2000);
    end;
  until op in ['T','t'];
end.

Click aici pentru sursa completă (ex09_1.pas)

La început, lista prelucrată în program este vidă (r - radacina = nil). Operatorul are posibilitatea să introducă sau să extragă noduri din această listă, după fiecare operație afișându-se conținutul listei, sub forma:

Radacina = <adresa primului nod>
Adresa <adr. prim. nod>: nr= <nr de ord.>, urm= <adr. urm. nod>
...
Adresa <adr. ultim. nod>: nr= <nr de ord.>, urm= nil

Pentru claritate, funcția NodNou, de fiecare dată când alocă un nod din heap, memorează în acesta un număr de ordine.

În practică se obișnuiește ca adresele de memorie să se afișeze în hexazecimal; în acest scop se folosește funcția Hexa, care returnează șirul de cifre hexazecimale, precedat de '$', corespunzător unui număr.

Se atrage atenția asupra modului în care poate fi afișat "conținutul" unui pointer - adresa spre care indică acesta: se utilizează facilitatea de conversie de tip oferita de TurboPASCAL, prin care o variabila de tip pointer este transformată într-o variabilă formată din două cuvinte (word). O instrucțiune de genul:

write(<variabila pointer>);

nu ar avea sens. De aceea, se recomandă citirea cu atenție a procedurii ScrieOAdresa și a subprogramelor apelate de catre aceasta, în primul rând a modului de realizare a conversiei de tip (cu ajutorul lui ConvPtr).

Programul oferă următoarele opțiuni:

Dacă se încearcă inserarea înaintea unui nod inexistent, se va efectua o adăugare a noului nod la sfârșitul listei.


C. Teme

  1. Să se ruleze programul prezentat, executând diverse operații asupra listei, urmărind valorile pointerilor și înlănțuirile care apar. Să se întocmească o diagramă pentru fiecare stare a listei, cu adresele și valorile cheilor din listă.

  2. Să se scrie un program asemănator, dar care prelucrează o listă ordonată permanent în ordinea crescătoare a cheilor, care vor fi furnizate de catre utilizator (nu se mai generează în mod automat).

  3. * Să se utilizeze o lista dublu înlănțuită.