Tipul de date abstract sir

Tipul de date abstract sir

Un sir este o colectie de caractere, spre exemplu "Structuri de date'.

In toate limbajele de programare in care sunt definite siruri, acestea au la baza tipul primitiv char, care in afara literelor si cifrelor cuprinde si o serie de alte caractere.

Se subliniaza faptul ca intr-un sir, ordinea caracterelor conteaza. Astfel sirurile 'CAL' si 'LAC' desi contin aceleasi caractere sunt diferite.

De asemenea, printr-un usor abuz de notatie se considera ca un caracter este interschimbabil cu un sir constand dintr-un singur caracter, desi strict vorbind ele sunt de tipuri diferite.

Asemeni oricarui tip de date abstracte, definirea precisa a TDA sir necesita:

Descrierea modelului sau matematic,

Precizarea operatorilor care actioneaza asupra elementelor tipului.

Din punct de vedere matematic, elementele tipului de date abstract sir pot fi definite ca secvente finite de caractere (c₁,c₂,,c_n) unde c_i este de tip caracter, iar n precizeaza lungimea secventei.

Cazul in care n este egal cu zero, desemneaza sirul vid.

In continuare se prezinta un posibil set de operatori care actioneaza asupra TDA sir.

Ca si in cazul altor structuri de date, exista practic o libertate deplina in selectarea acestor operatori motiv pentru care setul prezentat are un caracter orientativ.

TDA Sir

Modelul matematic:secventa finita de caractere.

Notatii: s,sub,u ‑ siruri;

c ‑ valoare de tip caracter;

b ‑ valoare booleana;

poz,lung ‑ intregi pozitivi. [4.1.a]

Operatori

CreazaSirVid(s) ‑ procedura ce creeaza sirul vid s;

b:=SirVid(s) ‑ functie ce returneaza true daca

sirul este vid;

b:=SirComplet(s) ‑ functie booleana ce returneaza

valoarea true daca sirul este complet;

lung:=LungSir(s) ‑ functie care returneaza numarul

de caractere ale lui s;

poz:=PozitieSubsir(sub,s) ‑ functie care returneaza

pozitia la care subsirul sub apare prima data
in s. Daca sub nu e gasit in s, se returneaza
valoarea 0. Pozitiile caracterelor sunt numerotate

de la stanga la dreapta incepand cu 1;

ConcatSir(u,s) ‑ procedura care concateneaza la
sfarsitul lui u atatea caractere din s, pana
cand SirComplet(u) devine true;

CopiazaSubsir(u,s,poz,lung) ‑ procedura care‑l face

pe u copia subsirului din s incepand cu pozitia
poz, pe lungime lung sau pana la sfarsitul lui s;
daca poz>LungSir(s) sau poz<1, u devine sirul

vid;

StergeSir(s,poz,lung) ‑ procedura care sterge din s,
incepand cu pozitia poz, subsirul de lung

caractere. Daca poz este invalid (nu apartine
sirului), s ramane nemodificat;

InsereazaSir(sub,s,poz) ‑ procedura care insereaza in s,
incepand de la pozitia poz, sirul sub;

c:=FurnizeazaCarSir(s,poz) ‑ functie care returneaza
caracterul din pozitia poz a lui s. Pentru poz
invalid, se returneaza caracterul nul;

AdaugaCarSir(s,c) ‑ procedura care adauga caracterul
c la sfarsitul sirului s;

StergeSubsir(sub,s,poz) ‑ procedura care sterge prima
aparitie a subsirului sub in sirul s si returneaza
pozitia poz de stergere. Daca sub nu este gasit, s
ramane nemodificat iar poz este pozitionat pe 0;

StergeToateSubsir(s,sub) ‑ sterge toate aparitiile

lui sub in s.

Operatorii definiti pentru un TDA-sir pot fi impartiti in doua categorii:

Operatori primitivi care reprezinta un set minimal de operatii strict necesare in termenii carora pot fi dezvoltati operatorii nonprimitivi.

Operatori nonprimitivi care pot fi dezvoltati din cei anteriori.

Aceasta divizare este oarecum formala deoarece, de obicei e mai usor sa definesti un operator neprimitiv direct decat sa-l definesti in termenii primitivelor.

Spre exemplu operatorul InsereazaSir poate fi definit in termenii operatorilor CreazaSirVid si AdaugaCar.

Algoritmul este simplu: se construieste un sir de iesire temporar (rezultat) caruia i se adauga pe rand:

(1) caracterele sirului sursa pana la punctul de insertie,

(2) toate caracterele sirului de inserat (subsir), urmate de

(3) toate caracterele sirului sursa de dupa punctul de insertie.

Sirul astfel construit inlocuieste sirul initial (sursa) (secventa [4.1.b]).

PROCEDURE InsereazaSir(subsir: TipSir; VAR sursa: TipSir;
p: TipIndice);

VAR rezultat: TipSir; i: TipIndice;

BEGIN

IF (p<1) OR (p>LungSir(sursa)) THEN

*eroare (pozitie ilegala in insertie)

ELSE

BEGIN [4.1.b]

CreazaSirVid(rezultat);

FOR i:= 1 TO p-1 DO

AdaugaCarSir(rezultat, FurnizeazaCarSir(sursa,i));

FOR i:=1 TO LungSir(subsir) DO

AdaugaCarSir(rezultat, FurnizeazaCarSir(subsir,i));

FOR i:=p TO LungSir(sursa) DO

AdaugaCarSir(rezultat, FurnizeazaCarSir(sursa,i));

CreazaSirVid(sursa);

FOR i:=1 TO LungSir(rezultat) DO

AdaugaCarSir(sursa, FurnizeazaCarSir(rezultat,i));

END

END;