Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » referate » informatica
Tipul de date abstract sir

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 (c1,c2,,cn) unde ci 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;







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



Sistem informatic privind acordarea de credite persoanelor fizice
Analiza activitatii firmei PC
ORGANIZAREA DATELOR PE UNITATILE DE DISC (HDD, FLOPPY,CD-ROM, ETC.)
Date si informatii
Microcontrolerul AT89C52
Notiuni de software
Sumatoare paralele pe principiul conditionarii prin transport a sumei
Elementele de baza ale unui template Joomla



Termeni si conditii
Contact
Creeaza si tu