Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Implementarea tipului de date abstract sir

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.








Politica de confidentialitate

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Caracteristicile marketingului electronic
ARHITECTURA GENERALA A SISTEMULUI ELECTRONIC DE CALCUL
Problema cititorilor si scriitorilor
Soft power in lumea contemporana
CALCULUL CLIENT/SERVER
ATESTAT INFORMATICA FIRMA DE INCHIRIERI AUTO ‘TOP_CARS_RENT’
Algoritmul FFT bazat pe segmentarea in timp
SISTEM INFORMATIONAL SI SISTEM INFORMATIC


Termeni si conditii
Contact
Creeaza si tu