Implementarea tipului de date abstract sir

Implementarea tipului de date abstract sir

Sunt cunoscute doua tehnici majore de implementare a sirurilor:

Implementarea bazata pe tablouri

Implementarea bazata pe pointeri.

1. Implementarea sirurilor cu ajutorul tablourilor

Cea mai simpla implementare a TDA-sir se bazeaza pe doua elemente:

o      (1) Un intreg reprezentand lungimea sirului

o      (2) Un tablou de caractere care contine sirul propriu-zis.

In tablou caracterele pot fi pastrate ca atare sau intr-o forma impachetata.

Un exemplu de astfel de implementare Pascal este urmatorul [1.a].

CONST LungimeMax = ;

TYPE TipLungime = 0..LungimeMax;

TipIndice = 1..LungimeMax; [1.a]

TipSir = RECORD

lungime: TipLungime;

sir: ARRAY[TipIndice] OF char

END;

VAR s: TipSir;

Acest mod de implementare al sirurilor nu este unic.

Se utilizeaza tablouri intrucat tablourile ca si sirurile sunt structuri liniare.

Campul lungime este utilizat deoarece sirurile au lungimi diferite in schimb ce tablourile au lungimea fixa.

Implementarea se poate dispersa de campul lungime , caz in care se poate utiliza un caracter convenit pe post de santinela de sfarsit (marker).

In aceasta situatie operatorul LungimeSir va trebui sa contorizeze intr-o maniera liniara caracterele pana la detectarea markerului.

Din acest motiv este preferabil ca lungimea sa fie considerata un element separat al implementarii.

In contextul implementarii sirurilor cu ajutorul tablourilor se defineste notiunea de sir complet ca fiind sirul care are lungimea egala cu LungimeMaxima, adica dimensiunea tabloului definit spre a-l implementa.

Sirurile implementate in acest mod nu pot depasi aceasta lungime, motiv pentru care in acest context opereaza operatorul boolean SirComplet.

In acceptiunea modelului anterior prezentat, in continuare se prezinta o implementare a operatorilor primitivi [1.b,c,d,e].

PROCEDURE CreazaSirVid(VAR s: TipSir);

BEGIN

s.lungime:= 0 [1.b]

END;

FUNCTION LungSir(VAR s: TipSir): TipLungime;

BEGIN

LungSir:= s.lungime [1.c]

END;

FUNCTION FurnizeazaCar(s: TipSir,poz: TipIndice): char;

BEGIN

IF (poz<1) OR (poz>s.lungime) THEN

BEGIN [1.d]

*eroare(pozitie incorecta);

FurnizeazaCar:= chr(0)

END

ELSE

FurnizeazaCar:= s.sir[poz]

END;

PROCEDURE AdaugaCarSir(VAR s: TipSir; c: char);

BEGIN

IF s.lungime=LungimeMax THEN

*eroare(se depaseste lungimea maxima a sirului)

ELSE

BEGIN

s.lungime:= s.lungime+1; [1.e]

s.sir[s.lungime]:= c

END

END;

Se observa ca toate aceste operatii ruleaza in O(1) unitati de timp indiferent de lungimea sirului.

Procedurile CopiazaSubSir, ConcatSir, StergeSir si InsereazaSir se executa intr-un interval de timp liniar O(n), unde n este dupa caz lungimea subsirului sau a sirului de caractere.

Spre exemplu procedura CopiazaSubsir (u,s,poz,lung) returneaza in u subsirul avand lung caractere incepand cu pozitia poz .

Accesul la elementele subsirului se realizeaza direct (s.sir[poz], s.sir[poz+1],,s.sir[poz+lung-1]), astfel incat consumul de timp al executiei este dominat de mutarea caracterelor [1.f].

-------- ----- ------ ----- ----- -----------------
PROCEDURE CopiazaSubsir(VAR u,s: TipSir, poz, lung:

TipLungime);

VAR indexSursa,indexCopiere: TipLungime;

BEGIN

IF (poz<1) OR (poz>s.lungime) THEN

u.lungime:= 0

ELSE

BEGIN [1.f]

indexSursa:= poz-1;

indexCopiere:= 0;

WHILE (indexSursa<s.lungime) AND

(indexCopiere<u.lungime) DO BEGIN

indexSursa:= indexSursa+1;

indexCopiere:= indexCopiere+1;

u.sir[indexCopiere]:= s.sir[indexSursa]

END;

u.lungime:= indexCopiere

END

END;

Se observa faptul ca in interiorul buclei WHILE exista 3 atribuiri, care pentru o lungime lung a sub sirului determina 3 lung + 3 atribuiri.

Se observa de asemenea ca procedura CopiazaSubsir este liniara in raport cu lungimea lung a subsirului.

Un alt exemplu il reprezinta implementarea functiei PozitieSubsir [1.g].

FUNCTION PozitieSubsir(VAR sub,s: tipSir): TipLungime;

VAR mark,

indexSub,

indexSir: TipIndex;

poz: TipLungime;

stop: boolean;

BEGIN

indexSir:= 1;

poz:= 0;

REPEAT

indexSub:= 1;

mark:= indexSir;

stop:= false;

WHILE (NOT stop) AND (indexSir<=s.lungime) AND

(indexSub<=sub.lungime) DO

IF s.sir[indexSir]=sub.sir[indexSub] THEN

BEGIN

indexSir:= indexSir+1;

indexSub:= indexSub+1 [1.g]

END

ELSE

stop:= true;

IF indexSub>sub.lungime THEN

poz:= mark

ELSE

indexSir:= mark+1

UNTIL (poz>0) OR

(indexSir+sub.lungime-1>s.lungime);

PozitieSubsir:= poz

END;

Complexitatea functiei PozitieSubsir(sub,s)este O(lungime  s.lungime) unde lungime este lungimea modelului iar s.lungime este lungimea sirului in care se face cautarea.

Exista insa si alte metode mult mai performante de cautare care fac obiectul unui paragraf ulterior.

Unul din marele avantaje ale utilizarii datelor abstracte este urmatorul:

In situatia in care se gaseste un algoritm mai performant pentru o anumita operatie, se poate foarte simplu inlocui o implementare cu alta fara a afecta restul programului in conditiile pastrarii nealterate a prototipului operatorului.

2. Tabele de siruri

Utilizarea tabloului in implementarea sirurilor are avantajul ca operatorii sunt usor de redactat, simplu de inteles si suficient de rapizi.

Cu toate ca acest mod de implementare este economic din punct de vedere al timpului de executie, el este ineficient din punctul de vedere al spatiului utilizat.

Lungimea maxima a tabloului trebuie aleasa la dimensiunea celui mai lung sir preconizat a fi utilizat desi in cea mai mare parte a cazurilor se utilizeaza siruri mult mai scurte.

O modalitate de a economisi spatiul in dauna vitezei de lucru specifica implementarii cu ajutorul tablourilor, este aceea de a utiliza:

(1) Un tablou suficient de lung numit 'heap' (gramada) pentru a memora toate sirurile

(2) O tabela auxiliara de siruri care pastreaza evidenta sirurilor in heap.

Aceasta tehnica este utilizata in unele interpretere BASIC.

In acest mod de implementare a sirurilor, un sir este reprezentat printr-o intrare in tabela de siruri care contine doua valori (fig.2.a):

Lungimea sirului

Un indicator in heap care precizeaza inceputul sirului

Fig. 2.a. Modelul tabelei de siruri

Un exemplu de implementare in limbajul PASCAL apare in secventa [2.a].

Se observa ca aceasta implementare presupune:

Variabilele globale TabelaDeSiruri, Heap, Disponibil si NumarDeSiruri

Structurarea in forma unui articol cu campurile lungime si indicator a elementelor tabelei de siruri.

CONST LungimeHeap = ;

LungimeTabela = ;

TYPE ElementTabela = RECORD

lungime,

indicator: 1..LungimeHeap [2.a]

END;

TipSir = 1..LungimeTabela;

VAR TabelaDeSiruri: ARRAY[1..LungimeTabela] OF

ElementTabela;

Heap: ARRAY[1..LungimeHeap] OF char;

Disponibil: 0..LungimeHeap;

NumarDeSiruri: 0..LungimeTabela;

In continuare se prezinta pentru exemplificare implementarea functiei AdaugaCarSir.

Deoarece adaugarea unui caracter produce depasirea sirului in cauza in dauna sirului urmator din spatiul de lucru, functia AdaugaCarSir trebuie:

(1) Sa creeze o noua copie a sirului in zona disponibila a heap-ului

(2) Sa reactualizeze tabela de siruri si variabila Disponibil [2.b].

PROCEDURE AdaugaCarSir(VAR s: TipSir; c: char);

VAR i,lungimeVeche,indicatorVechi: integer;

BEGIN

IF (s<1) OR (s>NumarDeSiruri) THEN

*eroare(referinta invalida de sir)

ELSE [2.b]

BEGIN

lungimeVeche:= TabelaDeSiruri[s].lungime;

indictorVechi:= TabelaDeSiruri[s].indicator;

FOR i:=0 TO lungimeVeche-1 DO

Heap[Disponibil+i]:=Heap[indicatorVechi+i];

Heap[Disponibil+lungimeVeche]:= c;

TabelaDeSiruri[s].indicator:= Disponibil;

TabelaDeSiruri[s].lungime:= lungimeVeche+1;

Disponibil:= Disponibil+lungimeVeche+1

END

END;

Se observa ca in aceasta implementare AdaugaCarSir necesita O(n) unitati de timp pentru un sir de n caractere fata de implementarea bazata pe tablouri care necesita un timp constant (O(1)).

Aceasta este tributul platit facilitatii de a putea lucra cu siruri de lungime variabila.

De asemenea in urma crearii noii copii a sirului supus operatiei de adaugare, vechea instanta a sirului ramane in heap ocupand memorie in mod inutil.

O alta problema potentiala a acestei implementari este urmatoarea.

Se considera spre exemplu o procedura care realizeaza copierea unui sir sursa intr-un sir destinatie

In implementarea bazata pe tabela de siruri acest lucru se poate realiza simplu facand ca sirului destinatie sa-i corespunda acelasi indicator in heap ca si sirului sursa.

Acest fenomen este cunoscut in programare sub denumirea de supraincarcare ('aliasing'), adica doua variabile diferite se refera la aceeasi locatie de memorie.

Daca se cere insa stergerea sirului sursa sau destinatie se pot pierde ambele siruri.

Aceasta problema poate fi ocolita printr-o implementare adecvata.

Spre exemplu se procedeaza ca si in cazul procedurii AdaugaCarSir, adica:

(1) Pentru sirul destinatie se creeaza o copie incepand cu prima locatie disponibila in heap;

(2) Se copiaza sursa in noua locatie;

(3) Se introduce referinta care indica aceasta locatie, in tabela de siruri in intrarea corespunzatoare sirului nou creat.

De fapt, in anumite variante ale limbajului BASIC, aceasta maniera de rezolvare a copierii sta la baza implementarii instructiunii LET.

3. Implementarea sirurilor cu ajutorul pointerilor

Esenta implementarii sirurilor cu ajutorul pointerilor rezida in reprezentarea acestora printr-o colectie de celule inlantuite.

Fiecare celula contine [3.a]

Un caracter (sau un grup de caractere intr-o implementare mai elaborata)

Un pointer la celula urmatoare.

TYPE PointerCelula = ^Celula;

Celula = RECORD

ch: char;

urm: PointerCelula [3.a]

END;

TipSir = RECORD

lungime: integer;

cap,coada: PointerCelula

END;

Spre exemplu in fig. 3.a apare reprezentarea sirului 'DATE' in aceasta implementare,

Fig. 3.a. Implementarea sirurilor cu ajutorul pointerilor

In secventele [3.b, c, d, e] apare implementarea unor operatori primitivi specifici.

PROCEDURE CreazaSirVid(VAR s: TipSir);

BEGIN

s.lungime:= 0;

s.cap:= nil; [3.b]

s:coada:= nil

END;

FUNCTION LungSir(s: TipSir): integer;

BEGIN [3.c]

LungSir:= s.lungime

END;

FUNCTION FurnizeazaCarSir(s:TipSir; poz:integer): char;

VAR contor: integer;

p: PointerCelula; [3.d]

BEGIN

IF (poz<1) AND (poz>s.lungime) THEN

BEGIN

*eroare(index eronat)

FurnizeazaCarSir:= chr(0)

END

ELSE

BEGIN

p:= s.cap;

FOR contor:= 1 TO poz‑1 DO p:= p^.urm;

FurnizeazaCarSir:= p^.ch

END

END;

PROCEDURE AdaugaCarSir(var s:TipSir; c:char);

BEGIN

IF s.lungime=0 THEN

BEGIN

new(s.cap);

s.cap^.ch:= c;

s.cap^.urm:= nil;

s.coada:= s.cap [3.e]

END

ELSE

BEGIN

new(s.coada^.urm);

s.coada^.urm^.ch:= c;

s.coada^.urm^.urm:= nil;

s.coada:= s.coada^.urm

END;

s.lungime:= s.lungime+1

END;

In ceea ce priveste implementarea operatiei de copiere apar aceleasi probleme legate de supraincarcare care pot fi rezolvate intr-o maniera asemanatoare prin generarea unui sir nou destinatie identic cu sursa.

Un astfel de operator Copiaza(sursa, destinatie) poate fi utilizat cu succes in implementarea operatiei ConcatSir [3.f].

PROCEDURE ConcatSir(VAR u: TipSir; s: TipSir);

VAR temp: TipSir;

BEGIN

IF u.lungime=0 THEN

Copiaza(u,s)

ELSE

IF s.lungime<>0 THEN

BEGIN [3.f]

Copiaza(temp,s);

u.coada^.urm:= temp.cap;

u.coada:= temp.coada

END

END;

Acest mod de reprezentare a sirurilor are unele avantaje.

(1) Permite o mare flexibilitate in gestionarea sirurilor

(2) Inlatura dezavantajul lungimii fixe.

Principalele dezavantaje rezida in:

(1) Parcurgerea secventiala a sirului in vederea realizarii accesului la o anumita pozitie,

(2) Risipa de spatiu de memorie datorata prezentei pointerului asociat fiecarui caracter al sirului.

4. Comparatie intre metodele de implementare a sirurilor

Dupa cum s-a vazut, se utilizeaza trei maniere de implementare a sirurilor,

Implementarea bazata pe tablouri,

Implementarea bazata pe pointeri

Implementarea bazata pe o tabela care reuneste partial caracteristicile structurilor anterioare.

Din punctul de vedere al paragrafului de fata prezinta interes primele doua metode, caracteristicile celei de-a treia putand fi usor deduse din acestea.

Diferentele marcante dintre cele doua moduri de implementare a sirurilor si anume prin tablouri si pointeri isi au de fapt originea in caracterul fundamental al structurilor de date suport. Astfel:

Sirul implementat ca tablou este o structura de date cu acces direct;

Sirul implementat prin pointeri este o structura cu acces secvential, de fapt o lista inlantuita.

Aceste caracteristici fundamental diferite influenteaza intr-o maniera decisiva atat proprietatile sirurilor in fiecare din cele doua moduri de reprezentare, cat si algoritmii care implementeaza operatorii specifici.

Implementarea sirurilor cu ajutorul tablourilor

Posibilitatea realizarii directe a accesului la caractere.

Accesul la o pozitie precizata intr-un sir este imediat, element care avantajeaza operatiile CopiazaSubsir, StergeSir, InsereazaSir, FurnizeazaCarSir.

Algoritmii specifici pentru FurnizeazaCarSir, AdaugaCarSir si LungSir sunt rapizi (O(1)),

Restul operatorilor in marea lor majoritate avand performanta O(n).

Operatorul PozitieSubsir in implementarea bazata pe cautare directa are performanta O(n  m) unde n este lungimea sirului iar m lungimea subsirului, (exista pentru aceasta reprezentare si metode mult mai performante).

Dezavantaje ale acestui mod de implementare:

Trunchierea cauzata de insertia intr-un sir complet.

Insertia si suprimarea intr-un sir presupun miscari de elemente si consum de timp proportional cu lungimea sirului.

Implementarea sirurilor cu ajutorul pointerilor

Se bucura de flexibilitatea specifica acestei implementari

Este grevata de proprietatile rezultate din caracterul secvential al reprezentarii.

Faza de insertie propriu-zisa si suprimare din cadrul operatorilor InsereazaSir si StergeSir se realizeaza in O(1) unitati de timp

Cautarea pozitiei insa necesita practic O(n) unitati.

De fapt cautarea secventiala a pozitiei numerice este marele dezavantaj al acestei reprezentari care diminueaza performanta marii majoritati a operatorilor.

Cu toate ca in fiecare moment se consuma spatiu de memorie numai pentru caracterele existente, totusi risipa de memorie datorata pointerilor este mare.

Performanta operatorilor ConcatSir si AdaugaCarSir creste in mod semnificativ daca se utilizeaza pointerul 'coada'.

Aceasta implementare este indicat a fi utilizata atunci cand:

Este foarte important ca sirurile sa nu fie trunchiate

Cand se cunoaste cu probabilitate redusa lungimea maxima a sirurilor.

Admitand trunchierea ca si un rau necesar, marea majoritate a versiunilor PASCAL care definesc si implementeaza in cadrul limbajului tipul string si operatorii aferenti utilizeaza implementarea sirurilor bazata pe tablouri.