A. Consideratii teoretice

In cazul in care viteza de executie a programelor nu reprezinta o cerinta importanta, multe din structurile de date uzuale este indicat sa fie implementate cu ajutorul pointerilor.

Este si cazul structurii de tip coada, a carei implementare cu ajutorul tipului tablou a fost prezentat intr-o lucrare anterioara . O coada poate sa aiba dimensiunea 0 sau o dimensiune foarte mare (la fel ca o stiva). Pentru a nu depasi dimensiunea tabloului care memoreaza elemntele cozii trebuie apreciata lungimea ei maxima. Tabloul se declara cu aceasta lungime fixa, el ocupand tot timpul un spatiu de memorie foarte mare. Utilizarea alocarii dinamice a memoriei cu tipul pointer evita acest neajuns.


B. Exemple

Reluand lucrarea anterioara despre cozi (lucrarea numarul 4), reamintim cele 5 operatii asociate acestei structuri de date: initializarea, coada_vida, scoate, adauga(x), primul_element.

Pentru o implemntare mai eficienta, se va pastra un pointer la ultimul element. De asemena, ca la toate tipurile de liste, se va pastra si pointerul la primul elemnt al listei. Este util ca la implemtare sa se foloseasca si un nod fictiv ca si prim nod al cozii, caz in care pointerul de inceput va indica acest nod. Aceasta conventie permite o manipulare mai convenabila a cozilor vide.

Tipul de date utilizate este urmatorul:

type
  ptr=^element;
  element=record
    el: TipElement;
    next:ptr
  end;

si tipul coada:

type 
  coada=record
    primul, ultimul: ptr
  end;
var c: coada;

procedure initializare;
begin
  new(c.primul);        {creeaza nodul fictiv}
  c.primul^.next:=nil;
  c.ultimul:=c.primul;  {nodul fictiv este primul si ultimul nod}
end;

function coada_vida: boolean;
begin
  coada_vida:=c.primul=c.ultimul;
end;

function primul_element: TipElement;
begin
  if coada_vida then 
     writeln('Eroare--Coada este vida')
  else 
     primul_element:=c.primul^.urm^.el;
end;

procedure adauga(x: TipElement);
begin
  new(c.ultimul^.next);   {Se adauga la capatul cozii}
  c.ultimul:=c.ultimul^.next;
  c.ultimul^.el:=x;
  c.ultimul^.next:=nil;
end;

function scoate: TipElement;
begin
  if coada_vida then
    writeln('Eroare--Coada este vida')
  else
  begin
    scoate:=c.primul^.next^.el;
    c.primul:=c.primul^.next;
  end;
end;

C. Teme

  1. Agenda pe calculator. Se va construi un program care gestioneaza o coada in care vor fi introduse mesaje care contin un text si o ora (h,min,sec). Programul va rula continuu in felul urmator: va balea coada in cautarea unui element care are o ora mai mica decat ora curenta. Acesta va fi afisat si se va modifica ora lui cu ora 25:00:00 (va fi practic dezactivat). Daca utilizatorul apasa o tasta va putea fi introdus un nou mesaj in coada. Daca textul mesajului este 'STOP', se va opri programul.

  2. Acelasi program, dar mentinand coada ordonata crescator dupa orele mesajelor. Se va verifica numai primul element valid si cand acesta va fi afisat, va fi scos din coada. Introducerea mesajelor se va face ca in problema anterioara.

  3. Incercati implementarea abandonand cozile si utilizand o lista circulara simplu inlantuita. Care dintre cele trei implementari este constructiv mai simpla?